Debian Codegraph @

crypto_kem/6960119pcf/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 11
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, allone = -1, one = 1;
209
210 int row = PK_NROWS - 32;
211 int block_idx = row/64;
212 int tail = 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 ] >> tail) |
218 (mat[ row + i ][ block_idx + 1 ] << (64-tail));
219
220 // compute the column indices of pivots by Gaussian elimination.
221 // the indices are stored in pivot_col
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 ] >> tail) |
251 (mat[ i ][ block_idx + 1 ] << (64-tail));
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 >> (64-tail))) | (t << tail);
264 mat[ i ][ block_idx + 1 ] = (mat[ i ][ block_idx + 1 ] & (allone << tail)) | (t >> (64-tail));
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 // const int nBlocks_I = (PK_NROWS + 255) / 256;
299 const int head = PK_NROWS % 64;
300 const int tail = PK_NCOLS % 64;
301 const uint64_t one = 1;
302
303 int i, j, k, b;
304 int row, c;
305
306 union
307 {
308 uint64_t w[ PK_NROWS ][ nBlocks_I * 4 ];
309 vec256 v[ PK_NROWS ][ nBlocks_I ];
310 } mat;
311
312 union
313 {
314 uint64_t w[ PK_NROWS ][ 44 ];
315 vec256 v[ PK_NROWS ][ 11 ];
316 } par;
317
318 uint16_t m;
319 vec256 mm;
320
321 vec128 sk_int[ GFBITS ];
322
323 vec256 consts[ 32 ][ GFBITS ];
324 vec256 eval[ 32 ][ GFBITS ];
325 vec256 prod[ 32 ][ GFBITS ];
326 vec256 tmp[ GFBITS ];
327
328 uint64_t list[1 << GFBITS];
329 uint64_t buf[ PK_NROWS ];
330 uint64_t t;
331
332 uint16_t ind[ PK_NROWS ];
333 uint16_t ind_inv[ PK_NROWS ];
334
335 // compute the inverses
336
337 irr_load(sk_int, irr);
338
339 fft(eval, sk_int);
340
341 vec256_copy(prod[0], eval[0]);
342
343 for (i = 1; i < 32; i++)
344 vec256_mul(prod[i], prod[i-1], eval[i]);
345
346 vec256_inv(tmp, prod[31]);
347
348 for (i = 30; i >= 0; i--)
349 {
350 vec256_mul(prod[i+1], prod[i], tmp);
351 vec256_mul(tmp, tmp, eval[i+1]);
352 }
353
354 vec256_copy(prod[0], tmp);
355
356 // fill matrix
357
358 de_bitslicing(list, prod);
359
360 for (i = 0; i < (1 << GFBITS); i++)
361 {
362 list[i] <<= GFBITS;
363 list[i] |= i;
364 list[i] |= ((uint64_t) perm[i]) << 31;
365 }
366
367 crypto_sort_int64(list, 1 << GFBITS);
368
369 for (i = 1; i < (1 << GFBITS); i++)
370 if (uint64_is_equal_declassify(list[i-1] >> 31,list[i] >> 31))
371 return -1;
372
373 to_bitslicing_2x(consts, prod, list);
374
375 for (i = 0; i < (1 << GFBITS); i++)
376 pi[i] = list[i] & GFMASK;
377
378 for (j = 0; j < nBlocks_I; j++)
379 for (k = 0; k < GFBITS; k++)
380 mat.v[ k ][ j ] = prod[ j ][ k ];
381
382 for (i = 1; i < SYS_T; i++)
383 for (j = 0; j < nBlocks_I; j++)
384 {
385 vec256_mul(prod[j], prod[j], consts[j]);
386
387 for (k = 0; k < GFBITS; k++)
388 mat.v[ i*GFBITS + k ][ j ] = prod[ j ][ k ];
389 }
390
391 // gaussian elimination to obtain L, U, and P such that LP M = U
392 // L and U are stored in the space of M
393 // P is stored in ind
394
395 for (i = 0; i < PK_NROWS; i++)
396 ind_inv[i] = ind[ i ] = i;
397
398 for (row = 0; row < PK_NROWS; row++)
399 {
400 i = row >> 6;
401 j = row & 63;
402
403 if (row == PK_NROWS - 32)
404 {
405 if (mov_columns(mat.w, pi, pivots))
406 return -1;
407 }
408
409 for (k = row + 1; k < PK_NROWS; k++)
410 {
411 extract_01_masks(&m, mat.w[ row ], mat.w[ k ], row);
412 uint16_cswap(&ind[row], &ind[k], m);
413
414 mm = vec256_set1_16b(m);
415 for (c = 0; c < nBlocks_I; c++)
416 vec256_cswap(&mat.v[ row ][ c ], &mat.v[ k ][ c ], mm);
417 }
418
419 if ( uint64_is_zero_declassify(crypto_int64_bitmod_01(mat.w[ row ][ i ], j)) ) // return if not systematic
420 {
421 return -1;
422 }
423
424 for (k = row+1; k < PK_NROWS; k++)
425 {
426 t = mat.w[ k ][ i ] & (one << j);
427 mm = extract_mask256(mat.w[k], row);
428
429 for (c = 0; c < nBlocks_I; c++)
430 mat.v[ k ][ c ] ^= mat.v[ row ][ c ] & mm;
431
432 mat.w[ k ][ i ] |= t;
433 }
434 }
435
436 // apply M^-1 to the remaining columns
437
438 composeinv(PK_NROWS, ind_inv, ind_inv, ind);
439
440 for (j = 6; j < 28; j += 11)
441 {
442 for (k = 0; k < GFBITS; k++)
443 for (b = 0; b < 11; b++)
444 par.v[ k ][ b ] = prod[ j+b ][ k ];
445
446 for (i = 1; i < SYS_T; i++)
447 {
448 for (b = 0; b < 11; b++)
449 vec256_mul(prod[j+b], prod[j+b], consts[j+b]);
450
451 for (k = 0; k < GFBITS; k++)
452 for (b = 0; b < 11; b++)
453 par.v[ i*GFBITS + k ][ b ] = prod[ j+b ][ k ];
454 }
455
456 // apply P
457
458 for (i = 0; i < PK_NROWS; i++)
459 ind[i] = ind_inv[i];
460
461 sort_rows(PK_NROWS, ind, par.v);
462
463 // apply L
464
465 for (row = PK_NROWS-1; row >= 0; row--)
466 for (i = row-1; i >= 0; i--)
467 {
468 mm = extract_mask256(mat.w[row], i);
469
470 for (k = 0; k < 11; k++)
471 par.v[ row ][ k ] ^= par.v[ i ][ k ] & mm;
472 }
473
474 // apply U^-1
475
476 if (j == 6)
477 {
478 for (i = 0; i < PK_NROWS; i++)
479 par.v[i][0] = mat.v[ i ][ nBlocks_I-1 ];
480 }
481
482 for (row = PK_NROWS-1; row >= 0; row--)
483 for (i = PK_NROWS-1; i > row; i--)
484 {
485 mm = extract_mask256(mat.w[row], i);
486
487 for (k = 0; k < 11; k++)
488 par.v[ row ][ k ] ^= par.v[ i ][ k ] & mm;
489 }
490
491 if (j == 6)
492 {
493 for (row = 0; row < PK_NROWS; row++)
494 {
495 for (i = 0; i < 43; i++)
496 store8(pk + PK_ROW_BYTES * row + i*8, (par.w[row][i] >> head) | (par.w[row][i+1] << (64-head)));
497
498 buf[row] = par.w[row][i] >> head;
499 }
500 }
501 else
502 {
503 for (row = 0; row < PK_NROWS; row++)
504 {
505 store8(pk + PK_ROW_BYTES * row + 43*8, buf[row] | (par.w[row][0] << (64-head)));
506
507 for (i = 0; i < 40; i++)
508 store8(pk + PK_ROW_BYTES * row + (i+44)*8, (par.w[row][i] >> head) | (par.w[row][i+1] << (64-head)));
509
510 par.w[row][i] >>= head;
511 par.w[row][i] &= (one << tail) - 1;
512
513 store_i(pk + PK_ROW_BYTES * row + (i+44)*8, par.w[row][i], (tail + 7)/8);
514 }
515 }
516
517 }
518
519 //
520
521 return 0;
522 }
523