Debian Codegraph @

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