Debian Codegraph @

crypto_kem/6688128pcf/avx/sk_gen.c

raw
1 /*
2 This file is for secret-key generation
3 */
4 // 20240805 djb: more cryptoint usage
5 // 20221230 djb: add linker lines
6
7 // linker define genpoly_gen
8 // linker use gf_mul gf_inv
9 // linker use vec128_mul_GF
10 // linker use vec128_mul_asm
11 // linker use transpose_64x64_asm
12
13 #include "sk_gen.h"
14
15 #include "randombytes.h"
16 #include "controlbits.h"
17 #include "transpose.h"
18 #include "params.h"
19 #include "vec128.h"
20 #include "util.h"
21 #include "gf.h"
22 #include "crypto_declassify.h"
23 #include "crypto_uint16.h"
24 #include "crypto_int64.h"
25
26 static inline crypto_uint16 gf_is_zero_declassify(gf t)
27 {
28 crypto_uint16 mask = crypto_uint16_zero_mask(t);
29 crypto_declassify(&mask,sizeof mask);
30 return mask;
31 }
32
33 /* input: v, a list of GF(2^m) elements in bitsliced form */
34 /* input: idx, an index */
35 /* return: the idx-th element in v */
36 static inline gf extract_gf(uint64_t v[GFBITS][2], int idx)
37 {
38 int i;
39 gf ret;
40
41 ret = 0;
42 for (i = GFBITS-1; i >= 0; i--)
43 {
44 ret <<= 1;
45 ret |= crypto_int64_bitmod_01(v[i][idx/64], idx);
46 }
47
48 return ret;
49 }
50
51 /* same as extract_gf but reduces return value to 1 bit */
52 static inline uint64_t extract_bit(uint64_t v[GFBITS][2], int idx)
53 {
54 int i;
55 uint64_t ret;
56
57 ret = 0;
58 for (i = GFBITS-1; i >= 0; i--)
59 ret |= v[i][idx/64];
60
61 return crypto_int64_bitmod_01(ret, idx);
62 }
63
64 static void transpose_128x128(uint64_t (*in)[2])
65 {
66 int i, j, k;
67 uint64_t m[2][2][64], t;
68
69 for (i = 0; i < 2; i++)
70 for (j = 0; j < 2; j++)
71 for (k = 0; k < 64; k++)
72 m[i][j][k] = in[64*i + k][j];
73
74 for (k = 0; k < 64; k++)
75 {
76 t = m[0][1][k];
77 m[0][1][k] = m[1][0][k];
78 m[1][0][k] = t;
79 }
80
81 for (i = 0; i < 2; i++)
82 for (j = 0; j < 2; j++)
83 transpose_64x64(m[i][j]);
84
85 for (i = 0; i < 2; i++)
86 for (j = 0; j < 2; j++)
87 for (k = 0; k < 64; k++)
88 in[64*i + k][j] = m[i][j][k];
89 }
90
91 /* input: f, element in GF((2^m)^t) */
92 /* output: out, minimal polynomial of f */
93 /* return: 0 for success and -1 for failure */
94 int genpoly_gen(gf *out, gf *f)
95 {
96 int i, j, k;
97
98 gf t, inv;
99
100 uint64_t m;
101 vec128 mask;
102
103 union
104 {
105 uint64_t d[ GFBITS ][ 128 ][2];
106 vec128 v[ GFBITS ][ 128 ];
107 } buf;
108
109 union
110 {
111 uint64_t d[GFBITS][2];
112 vec128 v[GFBITS];
113 } v;
114
115 union
116 {
117 uint64_t d[SYS_T][GFBITS][2];
118 vec128 v[SYS_T][GFBITS];
119 } mat;
120
121 // fill matrix
122
123 buf.v[0][0] = vec128_set2x(1, 0);
124 for (i = 1; i < GFBITS; i++)
125 buf.v[i][0] = vec128_setzero();
126
127 for (j = 0; j < GFBITS; j++)
128 {
129 v.v[j] = vec128_setzero();
130
131 for (i = SYS_T-1; i >= 0; i--)
132 {
133 v.d[j][1] <<= 1;
134 v.d[j][1] |= crypto_int64_negative_01(v.d[j][0]);
135 v.d[j][0] <<= 1;
136 v.d[j][0] |= crypto_int64_bitmod_01(f[i], j);
137 }
138 }
139
140 for (i = 0; i < GFBITS; i++)
141 buf.v[i][1] = v.v[i];
142
143 for (k = 2; k <= SYS_T; k++)
144 {
145 vec128_mul_GF(v.v, v.v, f);
146
147 if (k < SYS_T)
148 {
149 for (i = 0; i < GFBITS; i++)
150 buf.v[i][k] = v.v[i];
151 }
152 else
153 {
154 for (i = 0; i < SYS_T; i++)
155 out[i] = extract_gf(v.d, i);
156 }
157 }
158
159 for (i = 0; i < GFBITS; i++)
160 transpose_128x128(buf.d[i]);
161
162 for (j = 0; j < SYS_T; j++)
163 for (i = 0; i < GFBITS; i++)
164 mat.v[j][i] = buf.v[i][j];
165
166 // gaussian
167
168 for (i = 0; i < SYS_T; i++)
169 {
170 for (j = i+1; j < SYS_T; j++)
171 {
172 m = extract_bit(mat.d[i], i);
173 m -= 1;
174 mask = vec128_set2x(m, m);
175
176 for (k = 0; k < GFBITS; k++)
177 mat.v[i][k] ^= mat.v[j][k] & mask;
178
179 out[i] ^= out[j] & m;
180 }
181
182 //
183
184 t = extract_gf(mat.d[i], i);
185
186 if (gf_is_zero_declassify(t)) return -1; // return if not systematic
187
188 //
189
190 inv = gf_inv(t);
191 vec128_mul_gf(mat.v[i], mat.v[i], inv);
192
193 out[i] = gf_mul(out[i], inv);
194
195 for (j = 0; j < SYS_T; j++)
196 {
197 if (j != i)
198 {
199 t = extract_gf(mat.d[j], i);
200
201 vec128_mul_gf(v.v, mat.v[i], t);
202 vec128_add(mat.v[j], mat.v[j], v.v);
203
204 out[j] ^= gf_mul(out[i], t);
205 }
206 }
207 }
208
209 return 0;
210 }
211