Debian Codegraph @

crypto_kem/8192128pcf/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 "vec.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[][ 128 ], 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, 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,s);
116
117 for (j = i+1; j < 32; j++) buf[i] ^= buf[j] & ~crypto_uint64_bitmod_mask(buf[i],s);
118 for (j = 0; j < i; j++) buf[j] ^= buf[i] & crypto_uint64_bitmod_mask(buf[j],s);
119 for (j = i+1; j < 32; j++) buf[j] ^= buf[i] & crypto_uint64_bitmod_mask(buf[j],s);
120 }
121
122 // updating permutation
123
124 for (j = 0; j < 32; j++)
125 for (k = j+1; k < 64; k++)
126 {
127 d = pi[ row + j ] ^ pi[ row + k ];
128 d &= crypto_uint16_equal_mask(k, ctz_list[j]);
129 pi[ row + j ] ^= d;
130 pi[ row + k ] ^= d;
131 }
132
133 // moving columns of mat according to the column indices of pivots
134
135 for (i = 0; i < PK_NROWS; i++)
136 {
137 t = (mat[ i ][ block_idx + 0 ] >> 32) |
138 (mat[ i ][ block_idx + 1 ] << 32);
139
140 for (j = 0; j < 32; j++)
141 {
142 d = t >> j;
143 d ^= crypto_uint64_shrmod(t,ctz_list[j]);
144 d = crypto_uint64_bottombit_01(d);
145
146 t ^= crypto_uint64_shlmod(d,ctz_list[j]);
147 t ^= d << j;
148 }
149
150 mat[ i ][ block_idx + 0 ] = (mat[ i ][ block_idx + 0 ] << 32 >> 32) | (t << 32);
151 mat[ i ][ block_idx + 1 ] = (mat[ i ][ block_idx + 1 ] >> 32 << 32) | (t >> 32);
152 }
153
154 return 0;
155 }
156
157 int pk_gen(unsigned char * pk, const unsigned char * irr, uint32_t * perm, int16_t * pi, uint64_t * pivots)
158 {
159 const int nblocks_H = (SYS_N + 63) / 64;
160 const int nblocks_I = (PK_NROWS + 63) / 64;
161
162 int i, j, k;
163 int row, c;
164
165 uint64_t mat[ PK_NROWS ][ 128 ];
166
167 uint64_t mask;
168
169 vec irr_int[2][ GFBITS ];
170
171 vec consts[ 128 ][ GFBITS ];
172 vec eval[ 128 ][ GFBITS ];
173 vec prod[ 128 ][ 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 < 128; i++)
187 vec_mul(prod[i], prod[i-1], eval[i]);
188
189 vec_inv(tmp, prod[127]);
190
191 for (i = 126; 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 / 64; i++)
237 for (j = 0; j < 64; j++)
238 {
239 row = i*64 + j;
240
241 if (row == PK_NROWS - 32)
242 {
243 if (mov_columns(mat, pi, pivots))
244 return -1;
245 }
246
247 for (k = row + 1; k < PK_NROWS; k++)
248 {
249 mask = ~crypto_uint64_bitmod_mask(mat[ row ][ i ], j);
250
251 for (c = 0; c < 128; c++)
252 mat[ row ][ c ] ^= mat[ k ][ c ] & mask;
253 }
254
255 mask = crypto_uint64_bitmod_mask(mat[ row ][ i ], j);
256 if ( uint64_is_zero_declassify(mask) ) // return if not systematic
257 {
258 return -1;
259 }
260
261 for (k = 0; k < row; k++)
262 {
263 mask = crypto_uint64_bitmod_mask(mat[ k ][ i ], j);
264
265 for (c = 0; c < 128; c++)
266 mat[ k ][ c ] ^= mat[ row ][ c ] & mask;
267 }
268 for (k = row+1; k < PK_NROWS; k++)
269 {
270 mask = crypto_uint64_bitmod_mask(mat[ k ][ i ], j);
271
272 for (c = 0; c < 128; c++)
273 mat[ k ][ c ] ^= mat[ row ][ c ] & mask;
274 }
275 }
276
277 for (i = 0; i < PK_NROWS; i++)
278 for (j = nblocks_I; j < 128; j++)
279 {
280 store8(pk, mat[i][j]);
281 pk += 8;
282 }
283
284 //
285
286 return 0;
287 }
288