Debian Codegraph @

crypto_kem/6688128pcf/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 use of cryptoint
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, allone = -1, 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 + 0 ] >> 32) |
217 (mat[ row + i ][ block_idx + 1 ] << 32);
218
219 // compute the column indices of pivots by Gaussian elimination.
220 // the indices are stored in pivot_col
221
222 *pivots = 0;
223
224 for (i = 0; i < 32; i++)
225 {
226 t = buf[i];
227 for (j = i+1; j < 32; j++)
228 t |= buf[j];
229
230 if (uint64_is_zero_declassify(t)) return -1; // return if buf is not full rank
231
232 pivot_col[i] = crypto_uint64_bottomzeros_num(t);
233 *pivots |= crypto_uint64_shlmod(one,pivot_col[i]);
234
235 for (j = i+1; j < 32; j++) buf[i] ^= buf[j] & ~crypto_uint64_bitmod_mask(buf[i],pivot_col[i]);
236 for (j = i+1; j < 32; j++) buf[j] ^= buf[i] & crypto_uint64_bitmod_mask(buf[j],pivot_col[i]);
237 }
238
239 // updating permutation
240
241 for (i = 0; i < 32; i++)
242 for (j = i+1; j < 64; j++)
243 int16_cswap(&pi[ row + i ], &pi[ row + j ], crypto_int16_equal_mask(j, pivot_col[i]));
244
245 // moving columns of mat according to the column indices of pivots
246
247 for (i = 0; i < PK_NROWS; i++)
248 {
249 t = (mat[ i ][ block_idx + 0 ] >> 32) |
250 (mat[ i ][ block_idx + 1 ] << 32);
251
252 for (j = 0; j < 32; j++)
253 {
254 d = t >> j;
255 d ^= crypto_uint64_shrmod(t,pivot_col[j]);
256 d = crypto_uint64_bottombit_01(d);
257
258 t ^= crypto_uint64_shlmod(d,pivot_col[j]);
259 t ^= d << j;
260 }
261
262 mat[ i ][ block_idx + 0 ] = (mat[ i ][ block_idx + 0 ] & (allone >> 32)) | (t << 32);
263 mat[ i ][ block_idx + 1 ] = (mat[ i ][ block_idx + 1 ] & (allone << 32)) | (t >> 32);
264 }
265
266 return 0;
267 }
268
269 /* y[pi[i]] = x[i] */
270 /* requires pi to be a permutation */
271 static void composeinv(int n, uint16_t y[n], uint16_t x[n], uint16_t pi[n])
272 {
273 int i;
274 int32_t t[n];
275
276 for (i = 0;i < n;++i)
277 {
278 t[i] = pi[i];
279 t[i] <<= 16;
280 t[i] |= x[i];
281 }
282
283 crypto_sort_int32(t,n);
284
285 for (i = 0;i < n;++i)
286 y[i] = t[i] & 0xFFFF;
287 }
288
289 /* input: irr, an irreducible polynomial */
290 /* perm, a permutation represented as an array of 32-bit numbers */
291 /* pi, same permutation represented as an array of 16-bit numbers */
292 /* output: pk, the public key*/
293 /* pivots, positions of pivots in the 32 x 64 matrix */
294 /* return: 0 if pk is successfully generated, -1 otherwise */
295 int pk_gen(unsigned char * pk, const unsigned char * irr, uint32_t * perm, int16_t * pi, uint64_t * pivots)
296 {
297 int i, j, k, b;
298 int row, c;
299
300 union
301 {
302 uint64_t w[ PK_NROWS ][ nBlocks_I * 4 ];
303 vec256 v[ PK_NROWS ][ nBlocks_I ];
304 } mat;
305
306 union
307 {
308 uint64_t w[ PK_NROWS ][ 28 ];
309 vec256 v[ PK_NROWS ][ 7 ];
310 } par;
311
312 uint16_t m;
313 vec256 mm;
314
315 vec128 sk_int[ GFBITS ];
316
317 vec256 consts[ 32 ][ GFBITS ];
318 vec256 eval[ 32 ][ GFBITS ];
319 vec256 prod[ 32 ][ GFBITS ];
320 vec256 tmp[ GFBITS ];
321
322 uint64_t list[1 << GFBITS];
323 uint64_t one = 1;
324 uint64_t t;
325
326 uint16_t ind[ PK_NROWS ];
327 uint16_t ind_inv[ PK_NROWS ];
328
329 // compute the inverses
330
331 irr_load(sk_int, irr);
332
333 fft(eval, sk_int);
334
335 vec256_copy(prod[0], eval[0]);
336
337 for (i = 1; i < 32; i++)
338 vec256_mul(prod[i], prod[i-1], eval[i]);
339
340 vec256_inv(tmp, prod[31]);
341
342 for (i = 30; i >= 0; i--)
343 {
344 vec256_mul(prod[i+1], prod[i], tmp);
345 vec256_mul(tmp, tmp, eval[i+1]);
346 }
347
348 vec256_copy(prod[0], tmp);
349
350 // fill matrix
351
352 de_bitslicing(list, prod);
353
354 for (i = 0; i < (1 << GFBITS); i++)
355 {
356 list[i] <<= GFBITS;
357 list[i] |= i;
358 list[i] |= ((uint64_t) perm[i]) << 31;
359 }
360
361 crypto_sort_int64(list, 1 << GFBITS);
362
363 for (i = 1; i < (1 << GFBITS); i++)
364 if (uint64_is_equal_declassify(list[i-1] >> 31,list[i] >> 31))
365 return -1;
366
367 to_bitslicing_2x(consts, prod, list);
368
369 for (i = 0; i < (1 << GFBITS); i++)
370 pi[i] = list[i] & GFMASK;
371
372 for (j = 0; j < nBlocks_I; j++)
373 for (k = 0; k < GFBITS; k++)
374 mat.v[ k ][ j ] = prod[ j ][ k ];
375
376 for (i = 1; i < SYS_T; i++)
377 for (j = 0; j < nBlocks_I; j++)
378 {
379 vec256_mul(prod[j], prod[j], consts[j]);
380
381 for (k = 0; k < GFBITS; k++)
382 mat.v[ i*GFBITS + k ][ j ] = prod[ j ][ k ];
383 }
384
385 // gaussian elimination to obtain L, U, and P such that LP M = U
386 // L and U are stored in the space of M
387 // P is stored in ind
388
389 for (i = 0; i < PK_NROWS; i++)
390 ind_inv[i] = ind[ i ] = i;
391
392 for (row = 0; row < PK_NROWS; row++)
393 {
394 i = row >> 6;
395 j = row & 63;
396
397 if (row == PK_NROWS - 32)
398 {
399 if (mov_columns(mat.w, pi, pivots))
400 return -1;
401 }
402
403 for (k = row + 1; k < PK_NROWS; k++)
404 {
405 extract_01_masks(&m, mat.w[ row ], mat.w[ k ], row);
406 uint16_cswap(&ind[row], &ind[k], m);
407
408 mm = vec256_set1_16b(m);
409 for (c = 0; c < nBlocks_I; c++)
410 vec256_cswap(&mat.v[ row ][ c ], &mat.v[ k ][ c ], mm);
411 }
412
413 if ( uint64_is_zero_declassify(crypto_int64_bitmod_01(mat.w[ row ][ i ], j)) ) // return if not systematic
414 {
415 return -1;
416 }
417
418 for (k = row+1; k < PK_NROWS; k++)
419 {
420 t = mat.w[ k ][ i ] & (one << j);
421 mm = extract_mask256(mat.w[k], row);
422
423 for (c = 0; c < nBlocks_I; c++)
424 mat.v[ k ][ c ] ^= mat.v[ row ][ c ] & mm;
425
426 mat.w[ k ][ i ] |= t;
427 }
428 }
429
430 // apply M^-1 to the remaining columns
431
432 composeinv(PK_NROWS, ind_inv, ind_inv, ind);
433
434 for (j = 6; j < 27; j += par_width)
435 {
436 for (k = 0; k < GFBITS; k++)
437 for (b = 0; b < par_width; b++)
438 par.v[ k ][ b ] = prod[ j+b ][ k ];
439
440 for (i = 1; i < SYS_T; i++)
441 {
442 for (b = 0; b < par_width; b++)
443 vec256_mul(prod[ j+b ], prod[ j+b ], consts[ j+b ]);
444
445 for (k = 0; k < GFBITS; k++)
446 for (b = 0; b < par_width; b++)
447 par.v[ i*GFBITS + k ][ b ] = prod[ j+b ][ k ];
448 }
449
450 // apply P
451
452 for (i = 0; i < PK_NROWS; i++)
453 ind[i] = ind_inv[i];
454
455 sort_rows(PK_NROWS, ind, par.v);
456
457 // apply L
458
459 for (row = PK_NROWS-1; row >= 0; row--)
460 for (i = row-1; i >= 0; i--)
461 {
462 mm = extract_mask256(mat.w[row], i);
463
464 for (k = 0; k < par_width; k++)
465 par.v[ row ][ k ] ^= par.v[ i ][ k ] & mm;
466 }
467
468 // apply U^-1
469
470 if (j == 6)
471 {
472 for (i = 0; i < PK_NROWS; i++)
473 par.v[i][0] = mat.v[i][ nBlocks_I-1 ];
474 }
475
476 for (row = PK_NROWS-1; row >= 0; row--)
477 for (i = PK_NROWS-1; i > row; i--)
478 {
479 mm = extract_mask256(mat.w[row], i);
480
481 for (k = 0; k < par_width; k++)
482 par.v[ row ][ k ] ^= par.v[ i ][ k ] & mm;
483 }
484
485 //
486
487 if (j + par_width < 27)
488 {
489 for (row = 0; row < PK_NROWS; row++)
490 for (k = (j == 6)? 2 : 0; k < 28; k++)
491 store8(pk + PK_ROW_BYTES * row + j*32 + k*8 - 13*16, par.w[row][k]);
492 }
493 else
494 {
495 for (row = 0; row < PK_NROWS; row++)
496 {
497 for (k = 0; k < 24; k++)
498 store8(pk + PK_ROW_BYTES * row + j*32 + k*8 - 13*16, par.w[row][k]);
499
500 store_i(pk + PK_ROW_BYTES * row + j*32 + k*8 - 13*16, par.w[row][k], 4);
501 }
502 }
503 }
504
505 //
506
507 return 0;
508 }
509