Debian Codegraph @

crypto_kem/6688128pc/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 const int nblocks_H = (SYS_N + 63) / 64;
84 const int nblocks_I = (PK_NROWS + 63) / 64;
85 const int block_idx = nblocks_I;
86
87 int i, j, k;
88 int row, c;
89
90 uint64_t mat[ PK_NROWS ][ nblocks_H ];
91 uint64_t ops[ PK_NROWS ][ nblocks_I ];
92
93 uint64_t mask;
94
95 vec irr_int[2][ GFBITS ];
96
97 vec consts[ 128 ][ GFBITS ];
98 vec eval[ 128 ][ GFBITS ];
99 vec prod[ 128 ][ GFBITS ];
100 vec tmp[ GFBITS ];
101
102 uint64_t list[1 << GFBITS];
103 uint64_t one_row[ 128 ];
104
105 // compute the inverses
106
107 irr_load(irr_int, irr);
108
109 fft(eval, irr_int);
110
111 vec_copy(prod[0], eval[0]);
112
113 for (i = 1; i < 128; i++)
114 vec_mul(prod[i], prod[i-1], eval[i]);
115
116 vec_inv(tmp, prod[127]);
117
118 for (i = 126; i >= 0; i--)
119 {
120 vec_mul(prod[i+1], prod[i], tmp);
121 vec_mul(tmp, tmp, eval[i+1]);
122 }
123
124 vec_copy(prod[0], tmp);
125
126 // fill matrix
127
128 de_bitslicing(list, prod);
129
130 for (i = 0; i < (1 << GFBITS); i++)
131 {
132 list[i] <<= GFBITS;
133 list[i] |= i;
134 list[i] |= ((uint64_t) perm[i]) << 31;
135 }
136
137 crypto_sort_int64(list, 1 << GFBITS);
138
139 for (i = 1; i < (1 << GFBITS); i++)
140 if (uint64_is_equal_declassify(list[i-1] >> 31,list[i] >> 31))
141 return -1;
142
143 to_bitslicing_2x(consts, prod, list);
144
145 for (i = 0; i < (1 << GFBITS); i++)
146 pi[i] = list[i] & GFMASK;
147
148 for (j = 0; j < nblocks_I; j++)
149 for (k = 0; k < GFBITS; k++)
150 mat[ k ][ j ] = prod[ j ][ k ];
151
152 for (i = 1; i < SYS_T; i++)
153 for (j = 0; j < nblocks_I; j++)
154 {
155 vec_mul(prod[j], prod[j], consts[j]);
156
157 for (k = 0; k < GFBITS; k++)
158 mat[ i*GFBITS + k ][ j ] = prod[ j ][ k ];
159 }
160
161 // gaussian elimination to obtain an upper triangular matrix
162 // and keep track of the operations in ops
163
164 for (i = 0; i < PK_NROWS; i++)
165 for (j = 0; j < nblocks_I; j++)
166 ops[ i ][ j ] = 0;
167
168 for (i = 0; i < PK_NROWS; i++)
169 {
170 ops[ i ][ i / 64 ] = 1;
171 ops[ i ][ i / 64 ] <<= (i % 64);
172 }
173
174 for (row = 0; row < PK_NROWS; row++)
175 {
176 i = row >> 6;
177 j = row & 63;
178
179 for (k = row + 1; k < PK_NROWS; k++)
180 {
181 mask = ~crypto_uint64_bitmod_mask(mat[ row ][ i ], j);
182
183 for (c = 0; c < nblocks_I; c++)
184 {
185 mat[ row ][ c ] ^= mat[ k ][ c ] & mask;
186 ops[ row ][ c ] ^= ops[ k ][ c ] & mask;
187 }
188 }
189
190 mask = crypto_uint64_bitmod_mask(mat[ row ][ i ], j);
191 if ( uint64_is_zero_declassify(mask) ) // return if not systematic
192 {
193 return -1;
194 }
195
196 for (k = row+1; k < PK_NROWS; k++)
197 {
198 mask = crypto_uint64_bitmod_mask(mat[ k ][ i ], j);
199
200 for (c = 0; c < nblocks_I; c++)
201 {
202 mat[ k ][ c ] ^= mat[ row ][ c ] & mask;
203 ops[ k ][ c ] ^= ops[ row ][ c ] & mask;
204 }
205 }
206 }
207
208 // computing the lineaer map required to obatin the systematic form
209
210 for (row = PK_NROWS-1; row >= 0; row--)
211 for (k = 0; k < row; k++)
212 {
213 mask = crypto_uint64_bitmod_mask(mat[ k ][ row/64 ], row);
214
215 for (c = 0; c < nblocks_I; c++)
216 ops[ k ][ c ] ^= ops[ row ][ c ] & mask;
217 }
218
219 // apply the linear map to the non-systematic part
220
221 for (j = nblocks_I; 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 = nblocks_I; 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 for (row = 0; row < PK_NROWS; row++)
235 {
236 i = row >> 6;
237 j = row & 63;
238
239 for (k = 0; k < nblocks_H; k++)
240 one_row[ k ] = 0;
241
242 for (c = 0; c < PK_NROWS; c++)
243 {
244 mask = crypto_uint64_bitmod_mask(ops[ row ][ c >> 6 ], c);
245
246 for (k = block_idx; k < nblocks_H; k++){
247 one_row[ k ] ^= mat[ c ][ k ] & mask;
248 }
249 }
250
251 for (k = block_idx; k < nblocks_H - 1; k++)
252 {
253 store8(pk, one_row[k]);
254 pk += 8;
255 }
256
257 store_i(pk, one_row[k], PK_ROW_BYTES % 8);
258
259 pk += PK_ROW_BYTES % 8;
260 }
261
262 //
263
264 return 0;
265 }
266