Debian Codegraph @

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