Debian Codegraph @

crypto_kem/8192128/vec/pk_gen.c

raw
1 /*
2 This file is for public-key generation
3 */
4 // 20240805 djb: more use of cryptoint
5 // 20240715 djb: more use of crypto_*_mask
6 // 20240508 djb: switch to crypto_sort_int64
7 // 20221231 djb: more 0 initialization to clarify data flow; tnx thom wiggers
8 // 20221230 djb: add linker lines
9
10 // linker define pk_gen
11 // linker use fft vec_inv vec_mul
12
13 #include "pk_gen.h"
14
15 #include "controlbits.h"
16 #include "crypto_sort_int64.h"
17 #include "params.h"
18 #include "benes.h"
19 #include "util.h"
20 #include "fft.h"
21 #include "crypto_declassify.h"
22 #include "crypto_uint64.h"
23 #include "crypto_int64.h"
24
25 static crypto_uint64 uint64_is_equal_declassify(uint64_t t,uint64_t u)
26 {
27 crypto_uint64 mask = crypto_uint64_equal_mask(t,u);
28 crypto_declassify(&mask,sizeof mask);
29 return mask;
30 }
31
32 static crypto_uint64 uint64_is_zero_declassify(uint64_t t)
33 {
34 crypto_uint64 mask = crypto_uint64_zero_mask(t);
35 crypto_declassify(&mask,sizeof mask);
36 return mask;
37 }
38
39 #include <stdint.h>
40
41 static void de_bitslicing(uint64_t * out, const vec in[][GFBITS])
42 {
43 int i, j, r;
44
45 for (i = 0; i < (1 << GFBITS); i++)
46 out[i] = 0 ;
47
48 for (i = 0; i < 128; i++)
49 for (j = GFBITS-1; j >= 0; j--)
50 for (r = 0; r < 64; r++)
51 {
52 out[i*64 + r] <<= 1;
53 out[i*64 + r] |= crypto_int64_bitmod_01(in[i][j], r);
54 }
55 }
56
57 static void to_bitslicing_2x(vec out0[][GFBITS], vec out1[][GFBITS], const uint64_t * in)
58 {
59 int i, j, r;
60
61 for (i = 0; i < 128; i++)
62 {
63 for (j = 0;j < GFBITS;++j) out0[i][j] = out1[i][j] = 0;
64
65 for (j = GFBITS-1; j >= 0; j--)
66 for (r = 63; r >= 0; r--)
67 {
68 out1[i][j] <<= 1;
69 out1[i][j] |= crypto_int64_bitmod_01(in[i*64 + r], j + GFBITS);
70 }
71
72 for (j = GFBITS-1; j >= 0; j--)
73 for (r = 63; r >= 0; r--)
74 {
75 out0[i][GFBITS-1-j] <<= 1;
76 out0[i][GFBITS-1-j] |= crypto_int64_bitmod_01(in[i*64 + r], j);
77 }
78 }
79 }
80
81 int pk_gen(unsigned char * pk, const unsigned char * irr, uint32_t * perm, int16_t * pi)
82 {
83 int i, j, k;
84 int row, c, d;
85
86 uint64_t mat[ PK_NROWS ][ 128 ];
87 uint64_t ops[ PK_NROWS ][ PK_NROWS / 64 ];
88
89 uint64_t mask;
90
91 vec irr_int[2][ GFBITS ];
92
93 vec consts[ 128 ][ GFBITS ];
94 vec eval[ 128 ][ GFBITS ];
95 vec prod[ 128 ][ GFBITS ];
96 vec tmp[ GFBITS ];
97
98 uint64_t list[1 << GFBITS];
99 uint64_t one_row[ PK_NCOLS/64 ];
100
101 // compute the inverses
102
103 irr_load(irr_int, irr);
104
105 fft(eval, irr_int);
106
107 vec_copy(prod[0], eval[0]);
108
109 for (i = 1; i < 128; i++)
110 vec_mul(prod[i], prod[i-1], eval[i]);
111
112 vec_inv(tmp, prod[127]);
113
114 for (i = 126; i >= 0; i--)
115 {
116 vec_mul(prod[i+1], prod[i], tmp);
117 vec_mul(tmp, tmp, eval[i+1]);
118 }
119
120 vec_copy(prod[0], tmp);
121
122 // fill matrix
123
124 de_bitslicing(list, prod);
125
126 for (i = 0; i < (1 << GFBITS); i++)
127 {
128 list[i] <<= GFBITS;
129 list[i] |= i;
130 list[i] |= ((uint64_t) perm[i]) << 31;
131 }
132
133 crypto_sort_int64(list, 1 << GFBITS);
134
135 for (i = 1; i < (1 << GFBITS); i++)
136 if (uint64_is_equal_declassify(list[i-1] >> 31,list[i] >> 31))
137 return -1;
138
139 to_bitslicing_2x(consts, prod, list);
140
141 for (i = 0; i < (1 << GFBITS); i++)
142 pi[i] = list[i] & GFMASK;
143
144 for (j = 0; j < (PK_NROWS + 63)/64; j++)
145 for (k = 0; k < GFBITS; k++)
146 mat[ k ][ j ] = prod[ j ][ k ];
147
148 for (i = 1; i < SYS_T; i++)
149 for (j = 0; j < (PK_NROWS + 63)/64; j++)
150 {
151 vec_mul(prod[j], prod[j], consts[j]);
152
153 for (k = 0; k < GFBITS; k++)
154 mat[ i*GFBITS + k ][ j ] = prod[ j ][ k ];
155 }
156
157 // gaussian elimination to obtain an upper triangular matrix
158 // and keep track of the operations in ops
159
160 for (i = 0; i < PK_NROWS / 64; i++)
161 for (j = 0; j < 64; j++)
162 {
163 row = i*64 + j;
164 for (c = 0; c < PK_NROWS / 64; c++)
165 ops[ row ][ c ] = 0;
166 }
167
168 for (i = 0; i < PK_NROWS / 64; i++)
169 for (j = 0; j < 64; j++)
170 {
171 row = i*64 + j;
172
173 ops[ row ][ i ] = 1;
174 ops[ row ][ i ] <<= j;
175 }
176
177 for (i = 0; i < PK_NROWS / 64; i++)
178 for (j = 0; j < 64; j++)
179 {
180 row = i*64 + j;
181
182 for (k = row + 1; k < PK_NROWS; k++)
183 {
184 mask = ~crypto_uint64_bitmod_mask(mat[ row ][ i ], j);
185
186 for (c = 0; c < PK_NROWS / 64; c++)
187 {
188 mat[ row ][ c ] ^= mat[ k ][ c ] & mask;
189 ops[ row ][ c ] ^= ops[ k ][ c ] & mask;
190 }
191 }
192
193 mask = crypto_uint64_bitmod_mask(mat[ row ][ i ], j);
194 if ( uint64_is_zero_declassify(mask) ) // return if not systematic
195 {
196 return -1;
197 }
198
199 for (k = row+1; k < PK_NROWS; k++)
200 {
201 mask = crypto_uint64_bitmod_mask(mat[ k ][ i ], j);
202
203 for (c = 0; c < PK_NROWS / 64; c++)
204 {
205 mat[ k ][ c ] ^= mat[ row ][ c ] & mask;
206 ops[ k ][ c ] ^= ops[ row ][ c ] & mask;
207 }
208 }
209 }
210
211 // computing the lineaer map required to obatin the systematic form
212
213 for (i = PK_NROWS / 64 - 1; i >= 0; i--)
214 for (j = 63; j >= 0; j--)
215 {
216 row = i*64 + j;
217
218 for (k = 0; k < row; k++)
219 {
220 {
221 mask = crypto_uint64_bitmod_mask(mat[ k ][ i ], j);
222
223 for (c = 0; c < PK_NROWS / 64; c++)
224 ops[ k ][ c ] ^= ops[ row ][ c ] & mask;
225 }
226 }
227 }
228
229 // apply the linear map to the non-systematic part
230
231 for (j = (PK_NROWS + 63)/64; j < 128; j++)
232 for (k = 0; k < GFBITS; k++)
233 mat[ k ][ j ] = prod[ j ][ k ];
234
235 for (i = 1; i < SYS_T; i++)
236 for (j = (PK_NROWS + 63)/64; j < 128; j++)
237 {
238 vec_mul(prod[j], prod[j], consts[j]);
239
240 for (k = 0; k < GFBITS; k++)
241 mat[ i*GFBITS + k ][ j ] = prod[ j ][ k ];
242 }
243
244 for (i = 0; i < PK_NROWS / 64; i++)
245 for (j = 0; j < 64; j++)
246 {
247 row = i*64 + j;
248
249 for (k = 0; k < PK_NCOLS/64; k++)
250 one_row[ k ] = 0;
251
252 for (c = 0; c < PK_NROWS / 64; c++)
253 for (d = 0; d < 64; d++)
254 {
255 mask = crypto_uint64_bitmod_mask(ops[ row ][ c ], d);
256
257 for (k = 0; k < PK_NCOLS/64; k++)
258 one_row[ k ] ^= mat[ c*64 + d ][ k + PK_NROWS/64 ] & mask;
259 }
260
261 for (k = 0; k < PK_NCOLS/64; k++)
262 {
263 store8(pk, one_row[ k ]);
264 pk += 8;
265 }
266 }
267
268 //
269
270 return 0;
271 }
272