Debian Codegraph @

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