Debian Codegraph @

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