1 /*
2 This file is for Niederreiter decryption
3 */
4
5 #include "decrypt.h"
6
7 #include "benes.h"
8 #include "bm.h"
9 #include "fft.h"
10 #include "fft_tr.h"
11 #include "params.h"
12 #include "util.h"
13
14 #include <stdio.h>
15
scaling(vec256 out[][GFBITS],vec256 inv[][GFBITS],const unsigned char * sk,vec256 * recv)16 static void scaling(vec256 out[][GFBITS], vec256 inv[][GFBITS], const unsigned char *sk, vec256 *recv) {
17 int i, j;
18
19 uint64_t sk_int[ GFBITS ];
20 vec256 eval[16][ GFBITS ];
21 vec256 tmp[ GFBITS ];
22
23 // computing inverses
24
25 PQCLEAN_MCELIECE348864F_AVX_irr_load(sk_int, sk);
26
27 PQCLEAN_MCELIECE348864F_AVX_fft(eval, sk_int);
28
29 for (i = 0; i < 16; i++) {
30 PQCLEAN_MCELIECE348864F_AVX_vec256_sq(eval[i], eval[i]);
31 }
32
33 PQCLEAN_MCELIECE348864F_AVX_vec256_copy(inv[0], eval[0]);
34
35 for (i = 1; i < 16; i++) {
36 PQCLEAN_MCELIECE348864F_AVX_vec256_mul(inv[i], inv[i - 1], eval[i]);
37 }
38
39 PQCLEAN_MCELIECE348864F_AVX_vec256_inv(tmp, inv[15]);
40
41 for (i = 14; i >= 0; i--) {
42 PQCLEAN_MCELIECE348864F_AVX_vec256_mul(inv[i + 1], tmp, inv[i]);
43 PQCLEAN_MCELIECE348864F_AVX_vec256_mul(tmp, tmp, eval[i + 1]);
44 }
45
46 PQCLEAN_MCELIECE348864F_AVX_vec256_copy(inv[0], tmp);
47
48 //
49
50 for (i = 0; i < 16; i++) {
51 for (j = 0; j < GFBITS; j++) {
52 out[i][j] = PQCLEAN_MCELIECE348864F_AVX_vec256_and(inv[i][j], recv[i]);
53 }
54 }
55 }
56
preprocess(vec128 * recv,const unsigned char * s)57 static void preprocess(vec128 *recv, const unsigned char *s) {
58 int i;
59 unsigned char r[ 512 ];
60
61 for (i = 0; i < SYND_BYTES; i++) {
62 r[i] = s[i];
63 }
64
65 for (i = SYND_BYTES; i < 512; i++) {
66 r[i] = 0;
67 }
68
69 for (i = 0; i < 32; i++) {
70 recv[i] = PQCLEAN_MCELIECE348864F_AVX_load16(r + i * 16);
71 }
72 }
73
postprocess(unsigned char * e,vec128 * err)74 static void postprocess(unsigned char *e, vec128 *err) {
75 int i;
76 unsigned char error8[ (1 << GFBITS) / 8 ];
77 uint64_t v[2];
78
79 for (i = 0; i < 32; i++) {
80 v[0] = PQCLEAN_MCELIECE348864F_AVX_vec128_extract(err[i], 0);
81 v[1] = PQCLEAN_MCELIECE348864F_AVX_vec128_extract(err[i], 1);
82
83 PQCLEAN_MCELIECE348864F_AVX_store8(error8 + i * 16 + 0, v[0]);
84 PQCLEAN_MCELIECE348864F_AVX_store8(error8 + i * 16 + 8, v[1]);
85 }
86
87 for (i = 0; i < SYS_N / 8; i++) {
88 e[i] = error8[i];
89 }
90 }
91
scaling_inv(vec256 out[][GFBITS],vec256 inv[][GFBITS],vec256 * recv)92 static void scaling_inv(vec256 out[][GFBITS], vec256 inv[][GFBITS], vec256 *recv) {
93 int i, j;
94
95 for (i = 0; i < 16; i++) {
96 for (j = 0; j < GFBITS; j++) {
97 out[i][j] = PQCLEAN_MCELIECE348864F_AVX_vec256_and(inv[i][j], recv[i]);
98 }
99 }
100 }
101
weight_check(unsigned char * e,vec128 * error)102 static uint16_t weight_check(unsigned char *e, vec128 *error) {
103 int i;
104 uint16_t w0 = 0;
105 uint16_t w1 = 0;
106 uint16_t check;
107
108 for (i = 0; i < 32; i++) {
109 w0 += _mm_popcnt_u64( PQCLEAN_MCELIECE348864F_AVX_vec128_extract(error[i], 0) );
110 w0 += _mm_popcnt_u64( PQCLEAN_MCELIECE348864F_AVX_vec128_extract(error[i], 1) );
111 }
112
113 for (i = 0; i < SYS_N / 8; i++) {
114 w1 += _mm_popcnt_u64( e[i] );
115 }
116
117 check = (w0 ^ SYS_T) | (w1 ^ SYS_T);
118 check -= 1;
119 check >>= 15;
120
121 return check;
122 }
123
synd_cmp(vec128 * s0,vec128 * s1)124 static uint16_t synd_cmp(vec128 *s0, vec128 *s1) {
125 int i;
126 vec128 diff;
127
128 diff = PQCLEAN_MCELIECE348864F_AVX_vec128_xor(s0[0], s1[0]);
129
130 for (i = 1; i < GFBITS; i++) {
131 diff = PQCLEAN_MCELIECE348864F_AVX_vec128_or(diff, PQCLEAN_MCELIECE348864F_AVX_vec128_xor(s0[i], s1[i]));
132 }
133
134 return (uint16_t)PQCLEAN_MCELIECE348864F_AVX_vec128_testz(diff);
135 }
136
reformat_128to256(vec256 * out,vec128 * in)137 static void reformat_128to256(vec256 *out, vec128 *in) {
138 int i;
139 uint64_t v[4];
140
141 for (i = 0; i < 16; i++) {
142 v[0] = PQCLEAN_MCELIECE348864F_AVX_vec128_extract(in[2 * i + 0], 0);
143 v[1] = PQCLEAN_MCELIECE348864F_AVX_vec128_extract(in[2 * i + 0], 1);
144 v[2] = PQCLEAN_MCELIECE348864F_AVX_vec128_extract(in[2 * i + 1], 0);
145 v[3] = PQCLEAN_MCELIECE348864F_AVX_vec128_extract(in[2 * i + 1], 1);
146
147 out[i] = PQCLEAN_MCELIECE348864F_AVX_vec256_set4x(v[0], v[1], v[2], v[3]);
148 }
149 }
150
reformat_256to128(vec128 * out,vec256 * in)151 static void reformat_256to128(vec128 *out, vec256 *in) {
152 int i;
153 uint64_t v[4];
154
155 for (i = 0; i < 16; i++) {
156 v[0] = PQCLEAN_MCELIECE348864F_AVX_vec256_extract(in[i], 0);
157 v[1] = PQCLEAN_MCELIECE348864F_AVX_vec256_extract(in[i], 1);
158 v[2] = PQCLEAN_MCELIECE348864F_AVX_vec256_extract(in[i], 2);
159 v[3] = PQCLEAN_MCELIECE348864F_AVX_vec256_extract(in[i], 3);
160
161 out[2 * i + 0] = PQCLEAN_MCELIECE348864F_AVX_vec128_set2x(v[0], v[1]);
162 out[2 * i + 1] = PQCLEAN_MCELIECE348864F_AVX_vec128_set2x(v[2], v[3]);
163 }
164 }
165
166 /* Niederreiter decryption with the Berlekamp decoder */
167 /* intput: sk, secret key */
168 /* c, ciphertext (syndrome) */
169 /* output: e, error vector */
170 /* return: 0 for success; 1 for failure */
PQCLEAN_MCELIECE348864F_AVX_decrypt(unsigned char * e,const unsigned char * sk,const unsigned char * c)171 int PQCLEAN_MCELIECE348864F_AVX_decrypt(unsigned char *e, const unsigned char *sk, const unsigned char *c) {
172 int i;
173
174 uint16_t check_synd;
175 uint16_t check_weight;
176
177 vec256 inv[ 16 ][ GFBITS ];
178 vec256 scaled[ 16 ][ GFBITS ];
179 vec256 eval[16][ GFBITS ];
180
181 vec128 error128[ 32 ];
182 vec256 error256[ 16 ];
183
184 vec128 s_priv[ GFBITS ];
185 vec128 s_priv_cmp[ GFBITS ];
186 uint64_t locator[ GFBITS ];
187
188 vec128 recv128[ 32 ];
189 vec256 recv256[ 16 ];
190 vec256 allone;
191
192 uint64_t bits_int[23][32];
193
194 // Berlekamp decoder
195
196 preprocess(recv128, c);
197
198 PQCLEAN_MCELIECE348864F_AVX_load_bits(bits_int, sk + IRR_BYTES);
199 PQCLEAN_MCELIECE348864F_AVX_benes((uint64_t *) recv128, bits_int, 1);
200
201 reformat_128to256(recv256, recv128);
202
203 scaling(scaled, inv, sk, recv256);
204 PQCLEAN_MCELIECE348864F_AVX_fft_tr(s_priv, scaled);
205 PQCLEAN_MCELIECE348864F_AVX_bm(locator, s_priv);
206
207 PQCLEAN_MCELIECE348864F_AVX_fft(eval, locator);
208
209 // reencryption and weight check
210
211 allone = PQCLEAN_MCELIECE348864F_AVX_vec256_set1_16b(0xFFFF);
212
213 for (i = 0; i < 16; i++) {
214 error256[i] = PQCLEAN_MCELIECE348864F_AVX_vec256_or_reduce(eval[i]);
215 error256[i] = PQCLEAN_MCELIECE348864F_AVX_vec256_xor(error256[i], allone);
216 }
217
218 scaling_inv(scaled, inv, error256);
219 PQCLEAN_MCELIECE348864F_AVX_fft_tr(s_priv_cmp, scaled);
220
221 check_synd = synd_cmp(s_priv, s_priv_cmp);
222
223 //
224
225 reformat_256to128(error128, error256);
226 PQCLEAN_MCELIECE348864F_AVX_benes((uint64_t *) error128, bits_int, 0);
227
228 postprocess(e, error128);
229
230 check_weight = weight_check(e, error128);
231
232 return 1 - (check_synd & check_weight);
233 }
234
235