Debian Codegraph @

crypto_kem/6960119pcf/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 < 128; 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 < 128; 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, tail;
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 tail = row % 64;
95
96 // extract the 32x64 matrix
97
98 for (i = 0; i < 32; i++)
99 buf[i] = (mat[ row + i ][ block_idx + 0 ] >> tail) |
100 (mat[ row + i ][ block_idx + 1 ] << (64-tail));
101
102 // compute the column indices of pivots by Gaussian elimination.
103 // the indices are stored in ctz_list
104
105 *pivots = 0;
106
107 for (i = 0; i < 32; i++)
108 {
109 t = buf[i];
110 for (j = i+1; j < 32; j++)
111 t |= buf[j];
112
113 if (uint64_is_zero_declassify(t)) return -1; // return if buf is not full rank
114
115 ctz_list[i] = s = crypto_uint64_bottomzeros_num(t);
116 *pivots |= crypto_uint64_shlmod(one,ctz_list[i]);
117
118 for (j = i+1; j < 32; j++) buf[i] ^= buf[j] & ~crypto_uint64_bitmod_mask(buf[i],s);
119 for (j = 0; j < i; j++) buf[j] ^= buf[i] & crypto_uint64_bitmod_mask(buf[j],s);
120 for (j = i+1; j < 32; j++) buf[j] ^= buf[i] & crypto_uint64_bitmod_mask(buf[j],s);
121 }
122
123 // updating permutation
124
125 for (j = 0; j < 32; j++)
126 for (k = j+1; k < 64; k++)
127 {
128 d = pi[ row + j ] ^ pi[ row + k ];
129 d &= crypto_uint16_equal_mask(k, ctz_list[j]);
130 pi[ row + j ] ^= d;
131 pi[ row + k ] ^= d;
132 }
133
134 // moving columns of mat according to the column indices of pivots
135
136 for (i = 0; i < PK_NROWS; i++)
137 {
138 t = (mat[ i ][ block_idx + 0 ] >> tail) |
139 (mat[ i ][ block_idx + 1 ] << (64-tail));
140
141 for (j = 0; j < 32; j++)
142 {
143 d = t >> j;
144 d ^= crypto_uint64_shrmod(t,ctz_list[j]);
145 d = crypto_uint64_bottombit_01(d);
146
147 t ^= crypto_uint64_shlmod(d,ctz_list[j]);
148 t ^= d << j;
149 }
150
151 mat[ i ][ block_idx + 0 ] = (mat[ i ][ block_idx + 0 ] & (allone >> (64-tail))) | (t << tail);
152 mat[ i ][ block_idx + 1 ] = (mat[ i ][ block_idx + 1 ] & (allone << tail)) | (t >> (64-tail));
153 }
154
155 return 0;
156 }
157
158 int pk_gen(unsigned char * pk, const unsigned char * irr, uint32_t * perm, int16_t * pi, uint64_t * pivots)
159 {
160 const int nblocks_H = (SYS_N + 63) / 64;
161 const int nblocks_I = (PK_NROWS + 63) / 64;
162 const int block_idx = nblocks_I - 1;
163 int tail = PK_NROWS % 64;
164
165 int i, j, k;
166 int row, c;
167
168 uint64_t mat[ PK_NROWS ][ nblocks_H ];
169
170 uint64_t mask;
171
172 vec irr_int[2][ GFBITS ];
173
174 vec consts[ 128 ][ GFBITS ];
175 vec eval[ 128 ][ GFBITS ];
176 vec prod[ 128 ][ GFBITS ];
177 vec tmp[ GFBITS ];
178
179 uint64_t list[1 << GFBITS];
180
181 // compute the inverses
182
183 irr_load(irr_int, irr);
184
185 fft(eval, irr_int);
186
187 vec_copy(prod[0], eval[0]);
188
189 for (i = 1; i < 128; i++)
190 vec_mul(prod[i], prod[i-1], eval[i]);
191
192 vec_inv(tmp, prod[127]);
193
194 for (i = 126; i >= 0; i--)
195 {
196 vec_mul(prod[i+1], prod[i], tmp);
197 vec_mul(tmp, tmp, eval[i+1]);
198 }
199
200 vec_copy(prod[0], tmp);
201
202 // fill matrix
203
204 de_bitslicing(list, prod);
205
206 for (i = 0; i < (1 << GFBITS); i++)
207 {
208 list[i] <<= GFBITS;
209 list[i] |= i;
210 list[i] |= ((uint64_t) perm[i]) << 31;
211 }
212
213 crypto_sort_int64(list, 1 << GFBITS);
214
215 for (i = 1; i < (1 << GFBITS); i++)
216 if (uint64_is_equal_declassify(list[i-1] >> 31,list[i] >> 31))
217 return -1;
218
219 to_bitslicing_2x(consts, prod, list);
220
221 for (i = 0; i < (1 << GFBITS); i++)
222 pi[i] = list[i] & GFMASK;
223
224 for (j = 0; j < nblocks_H; j++)
225 for (k = 0; k < GFBITS; k++)
226 mat[ k ][ j ] = prod[ j ][ k ];
227
228 for (i = 1; i < SYS_T; i++)
229 for (j = 0; j < nblocks_H; j++)
230 {
231 vec_mul(prod[j], prod[j], consts[j]);
232
233 for (k = 0; k < GFBITS; k++)
234 mat[ i*GFBITS + k ][ j ] = prod[ j ][ k ];
235 }
236
237 // gaussian elimination
238
239 for (row = 0; row < PK_NROWS; row++)
240 {
241 i = row >> 6;
242 j = row & 63;
243
244 if (row == PK_NROWS - 32)
245 {
246 if (mov_columns(mat, pi, pivots))
247 return -1;
248 }
249
250 for (k = row + 1; k < PK_NROWS; k++)
251 {
252 mask = ~crypto_uint64_bitmod_mask(mat[ row ][ i ], j);
253
254 for (c = 0; c < nblocks_H; c++)
255 mat[ row ][ c ] ^= mat[ k ][ c ] & mask;
256 }
257
258 mask = crypto_uint64_bitmod_mask(mat[ row ][ i ], j);
259 if ( uint64_is_zero_declassify(mask) ) // return if not systematic
260 {
261 return -1;
262 }
263
264 for (k = 0; k < row; k++)
265 {
266 mask = crypto_uint64_bitmod_mask(mat[ k ][ i ], j);
267
268 for (c = 0; c < nblocks_H; c++)
269 mat[ k ][ c ] ^= mat[ row ][ c ] & mask;
270 }
271
272 for (k = row+1; k < PK_NROWS; k++)
273 {
274 mask = crypto_uint64_bitmod_mask(mat[ k ][ i ], j);
275
276 for (c = 0; c < nblocks_H; c++)
277 mat[ k ][ c ] ^= mat[ row ][ c ] & mask;
278 }
279 }
280
281 for (row = 0; row < PK_NROWS; row++)
282 {
283 for (k = block_idx; k < nblocks_H - 1; k++)
284 {
285 mat[row][k] = (mat[row][k] >> tail) | (mat[row][k+1] << (64-tail));
286 store8(pk, mat[row][k]);
287 pk += 8;
288 }
289
290 mat[row][k] >>= tail;
291 store_i(pk, mat[row][k], PK_ROW_BYTES % 8);
292
293 pk[ (PK_ROW_BYTES % 8)-1 ] &= (1 << (PK_NCOLS % 8)) - 1; // removing redundant bits
294
295 pk += PK_ROW_BYTES % 8;
296 }
297
298 //
299
300 return 0;
301 }
302