Debian Codegraph @

crypto_kem/6688128/avx/pk_gen.c

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