Debian Codegraph @

crypto_kem/460896pcf/vec/pk_gen.c

raw
1 /*
2 This file is for public-key generation
3 */
4 // 20240822 djb: more cryptoint usage
5 // 20240805 djb: more use of cryptoint
6 // 20240715 djb: more use of crypto_*_mask
7 // 20240611 djb: using crypto_uint64_bottomzeros_num
8 // 20240608 djb: using crypto_*_mask
9 // 20240508 djb: switch to crypto_sort_int64
10 // 20221231 djb: remove unused min definition
11 // 20221231 djb: more 0 initialization to clarify data flow; tnx thom wiggers
12 // 20221230 djb: add linker lines
13
14 // linker define pk_gen
15 // linker use fft vec_inv vec_mul
16
17 #include "pk_gen.h"
18
19 #include "controlbits.h"
20 #include "crypto_sort_int64.h"
21 #include "transpose.h"
22 #include "params.h"
23 #include "benes.h"
24 #include "util.h"
25 #include "fft.h"
26 #include "crypto_declassify.h"
27 #include "crypto_uint16.h"
28 #include "crypto_uint64.h"
29 #include "crypto_int64.h"
30
31 static crypto_uint64 uint64_is_equal_declassify(uint64_t t,uint64_t u)
32 {
33 crypto_uint64 mask = crypto_uint64_equal_mask(t,u);
34 crypto_declassify(&mask,sizeof mask);
35 return mask;
36 }
37
38 static crypto_uint64 uint64_is_zero_declassify(uint64_t t)
39 {
40 crypto_uint64 mask = crypto_uint64_zero_mask(t);
41 crypto_declassify(&mask,sizeof mask);
42 return mask;
43 }
44
45 #include <stdint.h>
46
47 static void de_bitslicing(uint64_t * out, const vec in[][GFBITS])
48 {
49 int i, j, r;
50
51 for (i = 0; i < (1 << GFBITS); i++)
52 out[i] = 0 ;
53
54 for (i = 0; i < 128; i++)
55 for (j = GFBITS-1; j >= 0; j--)
56 for (r = 0; r < 64; r++)
57 {
58 out[i*64 + r] <<= 1;
59 out[i*64 + r] |= crypto_int64_bitmod_01(in[i][j], r);
60 }
61 }
62
63 static void to_bitslicing_2x(vec out0[][GFBITS], vec out1[][GFBITS], const uint64_t * in)
64 {
65 int i, j, r;
66
67 for (i = 0; i < 128; i++)
68 {
69 for (j = 0;j < GFBITS;++j) out0[i][j] = out1[i][j] = 0;
70
71 for (j = GFBITS-1; j >= 0; j--)
72 for (r = 63; r >= 0; r--)
73 {
74 out1[i][j] <<= 1;
75 out1[i][j] |= crypto_int64_bitmod_01(in[i*64 + r], j + GFBITS);
76 }
77
78 for (j = GFBITS-1; j >= 0; j--)
79 for (r = 63; r >= 0; r--)
80 {
81 out0[i][GFBITS-1-j] <<= 1;
82 out0[i][GFBITS-1-j] |= crypto_int64_bitmod_01(in[i*64 + r], j);
83 }
84 }
85 }
86
87 static int mov_columns(uint64_t mat[][ ((SYS_N + 63) / 64) ], int16_t * pi, uint64_t * pivots)
88 {
89 int i, j, k, s, block_idx, row;
90 uint64_t buf[64], ctz_list[32], t, d, one = 1;
91
92 row = PK_NROWS - 32;
93 block_idx = row/64;
94
95 // extract the 32x64 matrix
96
97 for (i = 0; i < 32; i++)
98 buf[i] = mat[ row + i ][ block_idx ];
99
100 // compute the column indices of pivots by Gaussian elimination.
101 // the indices are stored in ctz_list
102
103 *pivots = 0;
104
105 for (i = 0; i < 32; i++)
106 {
107 t = buf[i];
108 for (j = i+1; j < 32; j++)
109 t |= buf[j];
110
111 if (uint64_is_zero_declassify(t)) return -1; // return if buf is not full rank
112
113 ctz_list[i] = s = crypto_uint64_bottomzeros_num(t);
114 *pivots |= crypto_uint64_shlmod(one,ctz_list[i]);
115
116 for (j = i+1; j < 32; j++) buf[i] ^= buf[j] & ~crypto_uint64_bitmod_mask(buf[i],s);
117 for (j = i+1; j < 32; j++) buf[j] ^= buf[i] & crypto_uint64_bitmod_mask(buf[j],s);
118 }
119
120 // updating permutation
121
122 for (j = 0; j < 32; j++)
123 for (k = j+1; k < 64; k++)
124 {
125 d = pi[ row + j ] ^ pi[ row + k ];
126 d &= crypto_uint16_equal_mask(k, ctz_list[j]);
127 pi[ row + j ] ^= d;
128 pi[ row + k ] ^= d;
129 }
130
131 // moving columns of mat according to the column indices of pivots
132
133 for (i = 0; i < PK_NROWS; i++)
134 {
135 t = mat[ i ][ block_idx ];
136
137 for (j = 0; j < 32; j++)
138 {
139 d = t >> j;
140 d ^= crypto_uint64_shrmod(t,ctz_list[j]);
141 d = crypto_uint64_bottombit_01(d);
142
143 t ^= crypto_uint64_shlmod(d,ctz_list[j]);
144 t ^= d << j;
145 }
146
147 mat[ i ][ block_idx ] = t;
148 }
149
150 return 0;
151 }
152
153 int pk_gen(unsigned char * pk, const unsigned char * irr, uint32_t * perm, int16_t * pi, uint64_t * pivots)
154 {
155 const int nblocks_H = (SYS_N + 63) / 64;
156 const int nblocks_I = (PK_NROWS + 63) / 64;
157 int tail = PK_NROWS % 64;
158
159 int i, j, k;
160 int row, c;
161
162 uint64_t mat[ PK_NROWS ][ nblocks_H ];
163
164 uint64_t mask;
165
166 vec irr_int[2][ GFBITS ];
167
168 vec consts[ 128 ][ GFBITS ];
169 vec eval[ 128 ][ GFBITS ];
170 vec prod[ 128 ][ GFBITS ];
171 vec tmp[ GFBITS ];
172
173 uint64_t list[1 << GFBITS];
174
175 // compute the inverses
176
177 irr_load(irr_int, irr);
178
179 fft(eval, irr_int);
180
181 vec_copy(prod[0], eval[0]);
182
183 for (i = 1; i < 128; i++)
184 vec_mul(prod[i], prod[i-1], eval[i]);
185
186 vec_inv(tmp, prod[127]);
187
188 for (i = 126; i >= 0; i--)
189 {
190 vec_mul(prod[i+1], prod[i], tmp);
191 vec_mul(tmp, tmp, eval[i+1]);
192 }
193
194 vec_copy(prod[0], tmp);
195
196 // fill matrix
197
198 de_bitslicing(list, prod);
199
200 for (i = 0; i < (1 << GFBITS); i++)
201 {
202 list[i] <<= GFBITS;
203 list[i] |= i;
204 list[i] |= ((uint64_t) perm[i]) << 31;
205 }
206
207 crypto_sort_int64(list, 1 << GFBITS);
208
209 for (i = 1; i < (1 << GFBITS); i++)
210 if (uint64_is_equal_declassify(list[i-1] >> 31,list[i] >> 31))
211 return -1;
212
213 to_bitslicing_2x(consts, prod, list);
214
215 for (i = 0; i < (1 << GFBITS); i++)
216 pi[i] = list[i] & GFMASK;
217
218 for (j = 0; j < nblocks_H; j++)
219 for (k = 0; k < GFBITS; k++)
220 mat[ k ][ j ] = prod[ j ][ k ];
221
222 for (i = 1; i < SYS_T; i++)
223 for (j = 0; j < nblocks_H; j++)
224 {
225 vec_mul(prod[j], prod[j], consts[j]);
226
227 for (k = 0; k < GFBITS; k++)
228 mat[ i*GFBITS + k ][ j ] = prod[ j ][ k ];
229 }
230
231 // gaussian elimination
232
233 for (row = 0; row < PK_NROWS; row++)
234 {
235 i = row >> 6;
236 j = row & 63;
237
238 if (row == PK_NROWS - 32)
239 {
240 if (mov_columns(mat, pi, pivots))
241 return -1;
242 }
243
244 for (k = row + 1; k < PK_NROWS; k++)
245 {
246 mask = ~crypto_uint64_bitmod_mask(mat[ row ][ i ], j);
247
248 for (c = 0; c < nblocks_H; c++)
249 mat[ row ][ c ] ^= mat[ k ][ c ] & mask;
250 }
251
252 mask = crypto_uint64_bitmod_mask(mat[ row ][ i ], j);
253 if ( uint64_is_zero_declassify(mask) ) // return if not systematic
254 {
255 return -1;
256 }
257
258 for (k = 0; k < row; k++)
259 {
260 mask = crypto_uint64_bitmod_mask(mat[ k ][ i ], j);
261
262 for (c = 0; c < nblocks_H; c++)
263 mat[ k ][ c ] ^= mat[ row ][ c ] & mask;
264 }
265
266 for (k = row+1; k < PK_NROWS; k++)
267 {
268 mask = crypto_uint64_bitmod_mask(mat[ k ][ i ], j);
269
270 for (c = 0; c < nblocks_H; c++)
271 mat[ k ][ c ] ^= mat[ row ][ c ] & mask;
272 }
273 }
274
275 for (i = 0; i < PK_NROWS; i++)
276 {
277 store_i(pk, mat[i][ nblocks_I-1 ] >> tail, (64-tail)/8);
278 pk += (64-tail)/8;
279
280 for (j = nblocks_I; j < nblocks_H; j++)
281 {
282 store8(pk, mat[i][j]);
283 pk += 8;
284 }
285 }
286
287 //
288
289 return 0;
290 }
291