Debian Codegraph @

crypto_kem/348864f/avx/sk_gen.c

raw
1 /*
2 This file is for secret-key generation
3 */
4 // 20240805 djb: more use of cryptoint
5 // 20240508 djb: switch to vec_mul_gf_using_64
6 // 20221230 djb: add linker lines
7
8 // linker define genpoly_gen
9 // linker use gf_mul gf_inv
10 // linker use vec_GF_mul
11 // linker use vec_mul_asm
12 // linker use transpose_64x64_asm
13
14 #include "sk_gen.h"
15
16 #include "randombytes.h"
17 #include "controlbits.h"
18 #include "transpose.h"
19 #include "params.h"
20 #include "util.h"
21 #include "vec.h"
22 #include "gf.h"
23 #include "crypto_declassify.h"
24 #include "crypto_uint16.h"
25 #include "crypto_int64.h"
26
27 static inline crypto_uint16 gf_is_zero_declassify(gf t)
28 {
29 crypto_uint16 mask = crypto_uint16_zero_mask(t);
30 crypto_declassify(&mask,sizeof mask);
31 return mask;
32 }
33
34 /* input: v, a list of GF(2^m) elements in bitsliced form */
35 /* input: idx, an index */
36 /* return: the idx-th element in v */
37 static inline gf extract_gf(vec v[GFBITS], int idx)
38 {
39 int i;
40 gf ret;
41
42 ret = 0;
43 for (i = GFBITS-1; i >= 0; i--)
44 {
45 ret <<= 1;
46 ret |= crypto_int64_bitmod_01(v[i], idx);
47 }
48
49 return ret;
50 }
51
52 /* same as extract_gf but reduces return value to 1 bit */
53 static inline vec extract_bit(vec v[GFBITS], int idx)
54 {
55 int i;
56 vec ret;
57
58 ret = 0;
59 for (i = GFBITS-1; i >= 0; i--)
60 ret |= v[i];
61
62 return crypto_int64_bitmod_01(ret, idx);
63 }
64
65 /* input: f, element in GF((2^m)^t) */
66 /* output: out, minimal polynomial of f */
67 /* return: 0 for success and -1 for failure */
68 int genpoly_gen(gf *out, gf *f)
69 {
70 int i, j, k;
71
72 gf t, inv;
73
74 vec v[ GFBITS ], buf[ GFBITS ][ 64 ], mat[ 64 ][ GFBITS ], mask;
75
76 // fill matrix
77
78 buf[0][0] = 1;
79 for (i = 1; i < GFBITS; i++)
80 buf[i][0] = 0;
81
82 for (j = 0; j < GFBITS; j++)
83 for (i = SYS_T-1; i >= 0; i--)
84 {
85 v[j] <<= 1;
86 v[j] |= crypto_int64_bitmod_01(f[i], j);
87 }
88
89 for (i = 0; i < GFBITS; i++)
90 buf[i][1] = v[i];
91
92 for (k = 2; k <= SYS_T; k++)
93 {
94 vec_GF_mul(v, v, f);
95
96 if (k < SYS_T)
97 {
98 for (i = 0; i < GFBITS; i++)
99 buf[i][k] = v[i];
100 }
101 else
102 {
103 for (i = 0; i < SYS_T; i++)
104 out[i] = extract_gf(v, i);
105 }
106 }
107
108 for (i = 0; i < GFBITS; i++)
109 transpose_64x64(buf[i]);
110
111 for (j = 0; j < SYS_T; j++)
112 for (i = 0; i < GFBITS; i++)
113 mat[j][i] = buf[i][j];
114
115 // gaussian
116
117 for (i = 0; i < SYS_T; i++)
118 {
119 for (j = i+1; j < SYS_T; j++)
120 {
121 mask = extract_bit(mat[i], i);
122 mask -= 1;
123
124 for (k = 0; k < GFBITS; k++)
125 mat[i][k] ^= mat[j][k] & mask;
126
127 out[i] ^= out[j] & mask;
128 }
129
130 //
131
132 t = extract_gf(mat[i], i);
133
134 if (gf_is_zero_declassify(t)) return -1; // return if not systematic
135
136 //
137
138 inv = gf_inv(t);
139 vec_mul_gf_using_64(mat[i], mat[i], inv);
140
141 out[i] = gf_mul(out[i], inv);
142
143 for (j = 0; j < SYS_T; j++)
144 {
145 if (j != i)
146 {
147 t = extract_gf(mat[j], i);
148
149 vec_mul_gf_using_64(v, mat[i], t);
150 vec_add(mat[j], mat[j], v);
151
152 out[j] ^= gf_mul(out[i], t);
153 }
154 }
155 }
156
157 return 0;
158 }
159