Debian Codegraph @

crypto_kem/348864f/avx/pk_gen.c

raw
1 /*
2 This file is for public-key generation
3 */
4 // 20240822 djb: more cryptoint usage
5 // 20240805 djb: more cryptoint usage
6 // 20240611 djb: using crypto_uint64_bottomzeros_num
7 // 20240608 djb: using crypto_*_mask
8 // 20240508 djb: switch to crypto_sort_int32
9 // 20240508 djb: switch to crypto_sort_int64
10 // 20230105 tony: use merge exchange in sort_rows(); fewer lines for minmax_rows()
11 // 20221231 djb: remove unused min definition
12 // 20221231 djb: more 0 initialization to clarify data flow; tnx thom wiggers
13 // 20221230 djb: add linker lines
14
15 // linker define pk_gen
16 // linker use fft vec256_inv vec256_mul_asm
17
18 #include "pk_gen.h"
19
20 #include "controlbits.h"
21 #include "transpose.h"
22 #include "crypto_sort_int64.h"
23 #include "crypto_sort_int32.h"
24 #include "params.h"
25 #include "util.h"
26 #include "fft.h"
27 #include "crypto_declassify.h"
28 #include "crypto_int16.h"
29 #include "crypto_uint64.h"
30 #include "crypto_uint16.h"
31 #include "crypto_int64.h"
32
33 static crypto_uint64 uint64_is_equal_declassify(uint64_t t,uint64_t u)
34 {
35 crypto_uint64 mask = crypto_uint64_equal_mask(t,u);
36 crypto_declassify(&mask,sizeof mask);
37 return mask;
38 }
39
40 static crypto_uint64 uint64_is_zero_declassify(uint64_t t)
41 {
42 crypto_uint64 mask = crypto_uint64_zero_mask(t);
43 crypto_declassify(&mask,sizeof mask);
44 return mask;
45 }
46
47 #include <stdint.h>
48
49 #define nBlocks_I ((PK_NROWS + 255) / 256)
50 #define par_width 11
51
52 /* set m to 11...1 if the i-th bit of x is 0 and the i-th bit of y is 1 */
53 /* set m to 00...0 otherwise */
54 static inline void extract_01_masks(uint16_t *m, uint64_t *x, uint64_t *y, int i)
55 {
56 *m = crypto_uint64_bitmod_mask(y[ i>>6 ] & ~x[ i>>6 ], i);
57 }
58
59 /* return a 128-bit vector of which each bits is set to the i-th bit of v */
60 static inline vec256 extract_mask256(uint64_t v[], int i)
61 {
62 uint32_t mask = crypto_uint64_bitmod_mask(v[ i>>6 ], i);
63
64 return vec256_set1_32b(mask);
65 }
66
67 // swap x and y if m = 11...1
68 static inline void int16_cswap(int16_t *x, int16_t *y, uint16_t m)
69 {
70 int16_t d;
71
72 d = *x ^ *y;
73 d &= m;
74 *x ^= d;
75 *y ^= d;
76 }
77
78 // swap x and y if m = 11...1
79 static inline void uint16_cswap(uint16_t *x, uint16_t *y, uint16_t m)
80 {
81 uint16_t d;
82
83 d = *x ^ *y;
84 d &= m;
85 *x ^= d;
86 *y ^= d;
87 }
88
89 // swap x and y if m = 11...1
90 static inline void vec256_cswap(vec256 *x, vec256 *y, vec256 m)
91 {
92 vec256 d;
93
94 d = *x ^ *y;
95 d &= m;
96 *x ^= d;
97 *y ^= d;
98 }
99
100 /* swap x[i0] and x[i1] if x[i1] < x[i0] */
101 /* swap mat[i0] and mat[i1] if x[i1] < x[i0] */
102 static inline void minmax_rows(uint16_t *x, vec256 (*mat)[par_width], int i0, int i1)
103 {
104 int i;
105 uint16_t m;
106 vec256 mm;
107
108 m = crypto_uint16_smaller_mask(x[i1], x[i0]);
109 mm = vec256_set1_16b(m);
110
111 uint16_cswap(&x[i0], &x[i1], m);
112
113 for (i = 0; i < par_width; i++)
114 vec256_cswap(&mat[i0][i], &mat[i1][i], mm);
115 }
116
117 static void sort_rows(int n, uint16_t *x, vec256 (*mat)[par_width])
118 {
119 int t = 1;
120
121 while ((1 << t)*2 < n) t++;
122
123 for (int j = t-1; j >= 0; j--)
124 {
125 int p = 1 << j, q = 1 << (t-1), r = 0, d = p;
126
127 while (1)
128 {
129 for (int i = 0; i < n-d; i++)
130 if ((i & p) == r)
131 minmax_rows(x, mat, i, i+d);
132
133 if (q != p) { d = q - p; q = q / 2; r = p; }
134 else break;
135 }
136 }
137 }
138
139 /* extract numbers represented in bitsliced form */
140 static void de_bitslicing(uint64_t * out, const vec256 in[][GFBITS])
141 {
142 int i, j, r;
143 uint64_t u = 0;
144
145 for (i = 0; i < (1 << GFBITS); i++)
146 out[i] = 0 ;
147
148 for (i = 0; i < 16; i++)
149 for (j = GFBITS-1; j >= 0; j--) {
150 u = vec256_extract(in[i][j], 0);
151 for (r = 0; r < 64; r++)
152 {
153 out[i*256 + 0*64 + r] <<= 1;
154 out[i*256 + 0*64 + r] |= crypto_int64_bitmod_01(u, r);
155 }
156 u = vec256_extract(in[i][j], 1);
157 for (r = 0; r < 64; r++)
158 {
159 out[i*256 + 1*64 + r] <<= 1;
160 out[i*256 + 1*64 + r] |= crypto_int64_bitmod_01(u, r);
161 }
162 u = vec256_extract(in[i][j], 2);
163 for (r = 0; r < 64; r++)
164 {
165 out[i*256 + 2*64 + r] <<= 1;
166 out[i*256 + 2*64 + r] |= crypto_int64_bitmod_01(u, r);
167 }
168 u = vec256_extract(in[i][j], 3);
169 for (r = 0; r < 64; r++)
170 {
171 out[i*256 + 3*64 + r] <<= 1;
172 out[i*256 + 3*64 + r] |= crypto_int64_bitmod_01(u, r);
173 }
174 }
175 }
176
177 /* convert numbers into bitsliced form */
178 static void to_bitslicing_2x(vec256 out0[][GFBITS], vec256 out1[][GFBITS], const uint64_t * in)
179 {
180 int i, j, k, r;
181 uint64_t u[2][4];
182
183 for (j = 0;j < 2;++j) for (k = 0;k < 4;++k) u[j][k] = 0;
184
185 for (i = 0; i < 16; i++)
186 for (j = GFBITS-1; j >= 0; j--)
187 {
188 for (k = 0; k < 4; k++)
189 for (r = 63; r >= 0; r--)
190 {
191 u[0][k] <<= 1;
192 u[0][k] |= crypto_int64_bitmod_01(in[i*256 + k*64 + r], GFBITS-1-j);
193
194 u[1][k] <<= 1;
195 u[1][k] |= crypto_int64_bitmod_01(in[i*256 + k*64 + r], j + GFBITS);
196 }
197
198 out0[i][j] = vec256_set4x(u[0][0], u[0][1], u[0][2], u[0][3]);
199 out1[i][j] = vec256_set4x(u[1][0], u[1][1], u[1][2], u[1][3]);
200 }
201 }
202
203 /* swap columns on mat based on the pivots in the 32 x 64 matrix */
204 /* update permutation pi*/
205 /* store the positions of pivots in pivots */
206 static int mov_columns(uint64_t mat[][ (nBlocks_I+1)*4 ], int16_t * pi, uint64_t * pivots)
207 {
208 int i, j, pivot_col[32];
209 uint64_t buf[32], t, d, allone = -1, one = 1;
210
211 int row = PK_NROWS - 32;
212 int block_idx = row/64;
213
214 // extract the 32x64 matrix
215
216 for (i = 0; i < 32; i++)
217 buf[i] = (mat[ row + i ][ block_idx + 0 ] >> 32) |
218 (mat[ row + i ][ block_idx + 1 ] << 32);
219
220 // compute the column indices of pivots by Gaussian elimination.
221 // the indices are stored in ctz_list
222
223 *pivots = 0;
224
225 for (i = 0; i < 32; i++)
226 {
227 t = buf[i];
228 for (j = i+1; j < 32; j++)
229 t |= buf[j];
230
231 if (uint64_is_zero_declassify(t)) return -1; // return if buf is not full rank
232
233 pivot_col[i] = crypto_uint64_bottomzeros_num(t);
234 *pivots |= crypto_uint64_shlmod(one,pivot_col[i]);
235
236 for (j = i+1; j < 32; j++) buf[i] ^= buf[j] & ~crypto_uint64_bitmod_mask(buf[i],pivot_col[i]);
237 for (j = i+1; j < 32; j++) buf[j] ^= buf[i] & crypto_uint64_bitmod_mask(buf[j],pivot_col[i]);
238 }
239
240 // updating permutation
241
242 for (i = 0; i < 32; i++)
243 for (j = i+1; j < 64; j++)
244 int16_cswap(&pi[ row + i ], &pi[ row + j ], crypto_int16_equal_mask(j, pivot_col[i]));
245
246 // moving columns of mat according to the column indices of pivots
247
248 for (i = 0; i < PK_NROWS; i++)
249 {
250 t = (mat[ i ][ block_idx + 0 ] >> 32) |
251 (mat[ i ][ block_idx + 1 ] << 32);
252
253 for (j = 0; j < 32; j++)
254 {
255 d = t >> j;
256 d ^= crypto_uint64_shrmod(t,pivot_col[j]);
257 d = crypto_uint64_bottombit_01(d);
258
259 t ^= crypto_uint64_shlmod(d,pivot_col[j]);
260 t ^= d << j;
261 }
262
263 mat[ i ][ block_idx + 0 ] = (mat[ i ][ block_idx + 0 ] & (allone >> 32)) | (t << 32);
264 mat[ i ][ block_idx + 1 ] = (mat[ i ][ block_idx + 1 ] & (allone << 32)) | (t >> 32);
265 }
266
267 return 0;
268 }
269
270 /* y[pi[i]] = x[i] */
271 /* requires pi to be a permutation */
272 static void composeinv(int n, uint16_t y[n], uint16_t x[n], uint16_t pi[n])
273 {
274 int i;
275 int32_t t[n];
276
277 for (i = 0;i < n;++i)
278 {
279 t[i] = pi[i];
280 t[i] <<= 16;
281 t[i] |= x[i];
282 }
283
284 crypto_sort_int32(t,n);
285
286 for (i = 0;i < n;++i)
287 y[i] = t[i] & 0xFFFF;
288 }
289
290 /* input: irr, an irreducible polynomial */
291 /* perm, a permutation represented as an array of 32-bit numbers */
292 /* pi, same permutation represented as an array of 16-bit numbers */
293 /* output: pk, the public key*/
294 /* pivots, positions of pivots in the 32 x 64 matrix */
295 /* return: 0 if pk is successfully generated, -1 otherwise */
296 int pk_gen(unsigned char * pk, const unsigned char * irr, uint32_t * perm, int16_t * pi, uint64_t * pivots)
297 {
298 int i, j, k, b;
299 int row, c;
300
301 union
302 {
303 uint64_t w[ PK_NROWS ][ (nBlocks_I+1)*4 ];
304 vec256 v[ PK_NROWS ][ nBlocks_I+1 ];
305 } mat;
306
307 union
308 {
309 uint64_t w[ PK_NROWS ][ par_width*4 ];
310 vec256 v[ PK_NROWS ][ par_width ];
311 } par;
312
313 uint16_t m;
314 vec256 mm;
315
316 uint64_t sk_int[ GFBITS ];
317
318 vec256 consts[ 16 ][ GFBITS ];
319 vec256 eval[ 16 ][ GFBITS ];
320 vec256 prod[ 16 ][ GFBITS ];
321 vec256 tmp[ GFBITS ];
322
323 uint64_t list[1 << GFBITS];
324 uint64_t one = 1;
325 uint64_t t;
326
327 uint16_t ind[ PK_NROWS ];
328 uint16_t ind_inv[ PK_NROWS ];
329
330 // compute the inverses
331
332 irr_load(sk_int, irr);
333
334 fft(eval, sk_int);
335
336 vec256_copy(prod[0], eval[0]);
337
338 for (i = 1; i < 16; i++)
339 vec256_mul(prod[i], prod[i-1], eval[i]);
340
341 vec256_inv(tmp, prod[15]);
342
343 for (i = 14; i >= 0; i--)
344 {
345 vec256_mul(prod[i+1], prod[i], tmp);
346 vec256_mul(tmp, tmp, eval[i+1]);
347 }
348
349 vec256_copy(prod[0], tmp);
350
351 // fill matrix
352
353 de_bitslicing(list, prod);
354
355 for (i = 0; i < (1 << GFBITS); i++)
356 {
357 list[i] <<= GFBITS;
358 list[i] |= i;
359 list[i] |= ((uint64_t) perm[i]) << 31;
360 }
361
362 crypto_sort_int64(list, 1 << GFBITS);
363
364 for (i = 1; i < (1 << GFBITS); i++)
365 if (uint64_is_equal_declassify(list[i-1] >> 31,list[i] >> 31))
366 return -1;
367
368 to_bitslicing_2x(consts, prod, list);
369
370 for (i = 0; i < (1 << GFBITS); i++)
371 pi[i] = list[i] & GFMASK;
372
373 for (j = 0; j < nBlocks_I+1; j++)
374 for (k = 0; k < GFBITS; k++)
375 mat.v[ k ][ j ] = prod[ j ][ k ];
376
377 for (i = 1; i < SYS_T; i++)
378 for (j = 0; j < nBlocks_I+1; j++)
379 {
380 vec256_mul(prod[j], prod[j], consts[j]);
381
382 for (k = 0; k < GFBITS; k++)
383 mat.v[ i*GFBITS + k ][ j ] = prod[ j ][ k ];
384 }
385
386 // Gaussian elimination + column swaps to obtain L, U, and P such that LP M = U
387 // L and U are stored in the space of M
388 // P is stored in ind
389
390 for (i = 0; i < PK_NROWS; i++)
391 ind_inv[i] = ind[ i ] = i;
392
393 for (row = 0; row < PK_NROWS; row++)
394 {
395 i = row >> 6;
396 j = row & 63;
397
398 if (row == PK_NROWS - 32)
399 {
400 if (mov_columns(mat.w, pi, pivots))
401 return -1;
402 }
403
404 for (k = row + 1; k < PK_NROWS; k++)
405 {
406 extract_01_masks(&m, mat.w[ row ], mat.w[ k ], row);
407 uint16_cswap(&ind[row], &ind[k], m);
408
409 mm = vec256_set1_16b(m);
410 for (c = 0; c < nBlocks_I+1; c++)
411 vec256_cswap(&mat.v[ row ][ c ], &mat.v[ k ][ c ], mm);
412 }
413
414 if ( uint64_is_zero_declassify(crypto_int64_bitmod_01(mat.w[ row ][ i ], j)) ) // return if not systematic
415 {
416 return -1;
417 }
418
419 for (k = row+1; k < PK_NROWS; k++)
420 {
421 t = mat.w[ k ][ i ] & (one << j);
422 mm = extract_mask256(mat.w[k], row);
423
424 for (c = 0; c < nBlocks_I+1; c++)
425 mat.v[ k ][ c ] ^= mat.v[ row ][ c ] & mm;
426
427 mat.w[ k ][ i ] |= t;
428 }
429 }
430
431 // apply M^-1 to the remaining columns
432
433 composeinv(PK_NROWS, ind_inv, ind_inv, ind);
434
435 for (k = 0; k < GFBITS; k++)
436 {
437 for (b = 1; b < par_width; b++)
438 par.v[ k ][ b ] = prod[nBlocks_I + b][ k ];
439 }
440
441 for (i = 1; i < SYS_T; i++)
442 {
443 for (b = 1; b < par_width; b++)
444 vec256_mul(prod[nBlocks_I + b], prod[nBlocks_I + b], consts[nBlocks_I + b]);
445
446 for (k = 0; k < GFBITS; k++)
447 for (b = 1; b < par_width; b++)
448 par.v[ i*GFBITS + k ][ b ] = prod[nBlocks_I + b][ k ];
449 }
450
451 // apply P
452
453 for (i = 0; i < PK_NROWS; i++)
454 ind[i] = ind_inv[i];
455
456 sort_rows(PK_NROWS, ind, par.v);
457
458 // apply L
459
460 for (row = PK_NROWS-1; row >= 0; row--)
461 for (i = row-1; i >= 0; i--)
462 {
463 mm = extract_mask256(mat.w[row], i);
464
465 for (k = 1; k < par_width; k++)
466 par.v[ row ][ k ] ^= par.v[ i ][ k ] & mm;
467 }
468
469 // apply U^-1
470
471 for (i = 0; i < PK_NROWS; i++)
472 par.v[i][0] = mat.v[i][nBlocks_I];
473
474 for (row = PK_NROWS-1; row >= 0; row--)
475 for (i = PK_NROWS-1; i > row; i--)
476 {
477 mm = extract_mask256(mat.w[row], i);
478
479 for (k = 0; k < par_width; k++)
480 par.v[ row ][ k ] ^= par.v[ i ][ k ] & mm;
481 }
482
483 for (row = 0; row < PK_NROWS; row++)
484 {
485 for (k = 0; k < 42; k++)
486 store8(pk + PK_ROW_BYTES * row + k*8, par.w[row][k]);
487
488 store_i(pk + PK_ROW_BYTES * row + k*8, par.w[row][k], 4);
489 }
490
491 //
492
493 return 0;
494 }
495