Debian Codegraph @

crypto_kem/348864pcf/vec/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 // 20240715 djb: more use of crypto_*_mask
7 // 20240611 djb: using crypto_uint64_bottomzeros_num
8 // 20240608 djb: using crypto_*_mask
9 // 20240508 djb: switch to crypto_sort_int64
10 // 20221231 djb: remove unused min definition
11 // 20221231 djb: more 0 initialization to clarify data flow; tnx thom wiggers
12 // 20221230 djb: add linker lines
13
14 // linker define pk_gen
15 // linker use fft vec_inv vec_mul
16
17 #include "pk_gen.h"
18
19 #include "controlbits.h"
20 #include "crypto_sort_int64.h"
21 #include "transpose.h"
22 #include "params.h"
23 #include "benes.h"
24 #include "util.h"
25 #include "fft.h"
26 #include "crypto_declassify.h"
27 #include "crypto_uint16.h"
28 #include "crypto_uint64.h"
29 #include "crypto_int64.h"
30
31 static crypto_uint64 uint64_is_equal_declassify(uint64_t t,uint64_t u)
32 {
33 crypto_uint64 mask = crypto_uint64_equal_mask(t,u);
34 crypto_declassify(&mask,sizeof mask);
35 return mask;
36 }
37
38 static crypto_uint64 uint64_is_zero_declassify(uint64_t t)
39 {
40 crypto_uint64 mask = crypto_uint64_zero_mask(t);
41 crypto_declassify(&mask,sizeof mask);
42 return mask;
43 }
44
45 #include <stdint.h>
46
47 static void de_bitslicing(uint64_t * out, const vec in[][GFBITS])
48 {
49 int i, j, r;
50
51 for (i = 0; i < (1 << GFBITS); i++)
52 out[i] = 0 ;
53
54 for (i = 0; i < 64; i++)
55 for (j = GFBITS-1; j >= 0; j--)
56 for (r = 0; r < 64; r++)
57 {
58 out[i*64 + r] <<= 1;
59 out[i*64 + r] |= crypto_int64_bitmod_01(in[i][j], r);
60 }
61 }
62
63 static void to_bitslicing_2x(vec out0[][GFBITS], vec out1[][GFBITS], const uint64_t * in)
64 {
65 int i, j, r;
66
67 for (i = 0; i < 64; i++)
68 {
69 for (j = 0;j < GFBITS;++j) out0[i][j] = out1[i][j] = 0;
70
71 for (j = GFBITS-1; j >= 0; j--)
72 for (r = 63; r >= 0; r--)
73 {
74 out1[i][j] <<= 1;
75 out1[i][j] |= crypto_int64_bitmod_01(in[i*64 + r], j + GFBITS);
76 }
77
78 for (j = GFBITS-1; j >= 0; j--)
79 for (r = 63; r >= 0; r--)
80 {
81 out0[i][GFBITS-1-j] <<= 1;
82 out0[i][GFBITS-1-j] |= crypto_int64_bitmod_01(in[i*64 + r], j);
83 }
84 }
85 }
86
87 static int mov_columns(uint64_t mat[][ ((SYS_N + 63) / 64) ], int16_t * pi, uint64_t * pivots)
88 {
89 int i, j, k, s, block_idx, row;
90 uint64_t buf[64], ctz_list[32], t, d, allone = -1, one = 1;
91
92 row = PK_NROWS - 32;
93 block_idx = row/64;
94
95 // extract the 32x64 matrix
96
97 for (i = 0; i < 32; i++)
98 buf[i] = (mat[ row + i ][ block_idx + 0 ] >> 32) |
99 (mat[ row + i ][ block_idx + 1 ] << 32);
100
101 // compute the column indices of pivots by Gaussian elimination.
102 // the indices are stored in ctz_list
103
104 *pivots = 0;
105
106 for (i = 0; i < 32; i++)
107 {
108 t = buf[i];
109 for (j = i+1; j < 32; j++)
110 t |= buf[j];
111
112 if (uint64_is_zero_declassify(t)) return -1; // return if buf is not full rank
113
114 ctz_list[i] = s = crypto_uint64_bottomzeros_num(t);
115 *pivots |= crypto_uint64_shlmod(one,ctz_list[i]);
116
117 for (j = i+1; j < 32; j++) buf[i] ^= buf[j] & ~crypto_uint64_bitmod_mask(buf[i],s);
118 for (j = i+1; j < 32; j++) buf[j] ^= buf[i] & crypto_uint64_bitmod_mask(buf[j],s);
119 }
120
121 // updating permutation
122
123 for (j = 0; j < 32; j++)
124 for (k = j+1; k < 64; k++)
125 {
126 d = pi[ row + j ] ^ pi[ row + k ];
127 d &= crypto_uint16_equal_mask(k, ctz_list[j]) & 0xFFFF;
128 pi[ row + j ] ^= d;
129 pi[ row + k ] ^= d;
130 }
131
132 // moving columns of mat according to the column indices of pivots
133
134 for (i = 0; i < PK_NROWS; i++)
135 {
136 t = (mat[ i ][ block_idx + 0 ] >> 32) |
137 (mat[ i ][ block_idx + 1 ] << 32);
138
139 for (j = 0; j < 32; j++)
140 {
141 d = t >> j;
142 d ^= crypto_uint64_shrmod(t,ctz_list[j]);
143 d = crypto_uint64_bottombit_01(d);
144
145 t ^= crypto_uint64_shlmod(d,ctz_list[j]);
146 t ^= d << j;
147 }
148
149 mat[ i ][ block_idx + 0 ] = (mat[ i ][ block_idx + 0 ] & (allone >> 32)) | (t << 32);
150 mat[ i ][ block_idx + 1 ] = (mat[ i ][ block_idx + 1 ] & (allone << 32)) | (t >> 32);
151 }
152
153 return 0;
154 }
155
156 int pk_gen(unsigned char * pk, const unsigned char * irr, uint32_t * perm, int16_t * pi, uint64_t * pivots)
157 {
158 const int nblocks_H = (SYS_N + 63) / 64;
159 const int nblocks_I = (PK_NROWS + 63) / 64;
160
161 int i, j, k;
162 int row, c;
163
164 uint64_t mat[ PK_NROWS ][ nblocks_H ];
165 uint64_t ops[ PK_NROWS ][ nblocks_I ];
166
167 uint64_t mask;
168
169 uint64_t irr_int[ GFBITS ];
170
171 vec consts[64][ GFBITS ];
172 vec eval[ 64 ][ GFBITS ];
173 vec prod[ 64 ][ GFBITS ];
174 vec tmp[ GFBITS ];
175
176 uint64_t list[1 << GFBITS];
177
178 // compute the inverses
179
180 irr_load(irr_int, irr);
181
182 fft(eval, irr_int);
183
184 vec_copy(prod[0], eval[0]);
185
186 for (i = 1; i < 64; i++)
187 vec_mul(prod[i], prod[i-1], eval[i]);
188
189 vec_inv(tmp, prod[63]);
190
191 for (i = 62; i >= 0; i--)
192 {
193 vec_mul(prod[i+1], prod[i], tmp);
194 vec_mul(tmp, tmp, eval[i+1]);
195 }
196
197 vec_copy(prod[0], tmp);
198
199 // fill matrix
200
201 de_bitslicing(list, prod);
202
203 for (i = 0; i < (1 << GFBITS); i++)
204 {
205 list[i] <<= GFBITS;
206 list[i] |= i;
207 list[i] |= ((uint64_t) perm[i]) << 31;
208 }
209
210 crypto_sort_int64(list, 1 << GFBITS);
211
212 for (i = 1; i < (1 << GFBITS); i++)
213 if (uint64_is_equal_declassify(list[i-1] >> 31,list[i] >> 31))
214 return -1;
215
216 to_bitslicing_2x(consts, prod, list);
217
218 for (i = 0; i < (1 << GFBITS); i++)
219 pi[i] = list[i] & GFMASK;
220
221 for (j = 0; j < nblocks_H; j++)
222 for (k = 0; k < GFBITS; k++)
223 mat[ k ][ j ] = prod[ j ][ k ];
224
225 for (i = 1; i < SYS_T; i++)
226 for (j = 0; j < nblocks_H; j++)
227 {
228 vec_mul(prod[j], prod[j], consts[j]);
229
230 for (k = 0; k < GFBITS; k++)
231 mat[ i*GFBITS + k ][ j ] = prod[ j ][ k ];
232 }
233
234 // gaussian elimination
235
236 for (i = 0; i < PK_NROWS; i++)
237 for (j = 0; j < nblocks_I; j++)
238 ops[ i ][ j ] = 0;
239
240 for (i = 0; i < PK_NROWS; i++)
241 {
242 ops[ i ][ i / 64 ] = 1;
243 ops[ i ][ i / 64 ] <<= (i % 64);
244 }
245
246 for (row = 0; row < PK_NROWS; row++)
247 {
248 i = row >> 6;
249 j = row & 63;
250
251 if (row == PK_NROWS - 32)
252 {
253 if (mov_columns(mat, pi, pivots))
254 return -1;
255 }
256
257 for (k = row + 1; k < PK_NROWS; k++)
258 {
259 mask = ~crypto_uint64_bitmod_mask(mat[ row ][ i ], j);
260
261 for (c = 0; c < nblocks_H; c++)
262 mat[ row ][ c ] ^= mat[ k ][ c ] & mask;
263 }
264
265 mask = crypto_uint64_bitmod_mask(mat[ row ][ i ], j);
266 if ( uint64_is_zero_declassify(mask) ) // return if not systematic
267 {
268 return -1;
269 }
270
271 for (k = 0; k < row; k++)
272 {
273 mask = crypto_uint64_bitmod_mask(mat[ k ][ i ], j);
274
275 for (c = 0; c < nblocks_H; c++)
276 mat[ k ][ c ] ^= mat[ row ][ c ] & mask;
277 }
278
279 for (k = row+1; k < PK_NROWS; k++)
280 {
281 mask = crypto_uint64_bitmod_mask(mat[ k ][ i ], j);
282
283 for (c = 0; c < nblocks_H; c++)
284 mat[ k ][ c ] ^= mat[ row ][ c ] & mask;
285 }
286 }
287
288 for (i = 0; i < PK_NROWS; i++)
289 {
290 for (j = nblocks_I; j < nblocks_H-1; j++)
291 {
292 store8(pk, mat[i][j]);
293 pk += 8;
294 }
295
296 store_i(pk, mat[i][j], PK_ROW_BYTES % 8);
297
298 pk += PK_ROW_BYTES % 8;
299 }
300
301 //
302
303 return 0;
304 }
305