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 #include "vec.h"
14 
15 #include <stdio.h>
16 
17 static void scaling(vec out[][GFBITS], vec inv[][GFBITS], const unsigned char *sk, const vec *recv) {
18     int i, j;
19 
20     vec irr_int[2][ GFBITS ];
21     vec eval[128][ GFBITS ];
22     vec tmp[ GFBITS ];
23 
24     //
25 
26     PQCLEAN_MCELIECE460896_VEC_irr_load(irr_int, sk);
27 
28     PQCLEAN_MCELIECE460896_VEC_fft(eval, irr_int);
29 
30     for (i = 0; i < 128; i++) {
31         PQCLEAN_MCELIECE460896_VEC_vec_sq(eval[i], eval[i]);
32     }
33 
34     PQCLEAN_MCELIECE460896_VEC_vec_copy(inv[0], eval[0]);
35 
36     for (i = 1; i < 128; i++) {
37         PQCLEAN_MCELIECE460896_VEC_vec_mul(inv[i], inv[i - 1], eval[i]);
38     }
39 
40     PQCLEAN_MCELIECE460896_VEC_vec_inv(tmp, inv[127]);
41 
42     for (i = 126; i >= 0; i--) {
43         PQCLEAN_MCELIECE460896_VEC_vec_mul(inv[i + 1], tmp, inv[i]);
44         PQCLEAN_MCELIECE460896_VEC_vec_mul(tmp, tmp, eval[i + 1]);
45     }
46 
47     PQCLEAN_MCELIECE460896_VEC_vec_copy(inv[0], tmp);
48 
49     //
50 
51     for (i = 0; i < 128; i++) {
52         for (j = 0; j < GFBITS; j++) {
53             out[i][j] = inv[i][j] & recv[i];
54         }
55     }
56 }
57 
58 static void preprocess(vec *recv, const unsigned char *s) {
59     int i;
60     unsigned char r[ 1024 ];
61 
62     for (i = 0; i < SYND_BYTES; i++) {
63         r[i] = s[i];
64     }
65 
66     for (i = SYND_BYTES; i < 1024; i++) {
67         r[i] = 0;
68     }
69 
70     for (i = 0; i < 128; i++) {
71         recv[i] = PQCLEAN_MCELIECE460896_VEC_load8(r + i * 8);
72     }
73 }
74 
75 static void postprocess(unsigned char *e, vec *err) {
76     int i;
77     unsigned char error8[ (1 << GFBITS) / 8 ];
78 
79     for (i = 0; i < 128; i++) {
80         PQCLEAN_MCELIECE460896_VEC_store8(error8 + i * 8, err[i]);
81     }
82 
83     for (i = 0; i < SYS_N / 8; i++) {
84         e[i] = error8[i];
85     }
86 }
87 
88 static void scaling_inv(vec out[][GFBITS], vec inv[][GFBITS], const vec *recv) {
89     int i, j;
90 
91     for (i = 0; i < 128; i++) {
92         for (j = 0; j < GFBITS; j++) {
93             out[i][j] = inv[i][j] & recv[i];
94         }
95     }
96 }
97 
98 static int weight_check(const unsigned char *e, const vec *error) {
99     int i;
100     uint16_t w0 = 0;
101     uint16_t w1 = 0;
102     uint16_t check;
103 
104     for (i = 0; i < (1 << GFBITS); i++) {
105         w0 += (error[i / 64] >> (i % 64)) & 1;
106     }
107 
108     for (i = 0; i < SYS_N; i++) {
109         w1 += (e[i / 8] >> (i % 8)) & 1;
110     }
111 
112     check = (w0 ^ SYS_T) | (w1 ^ SYS_T);
113     check -= 1;
114     check >>= 15;
115 
116     return check;
117 }
118 
119 static uint16_t synd_cmp(vec s0[][ GFBITS ], vec s1[][ GFBITS ]) {
120     int i, j;
121     vec diff = 0;
122 
123     for (i = 0; i < 4; i++) {
124         for (j = 0; j < GFBITS; j++) {
125             diff |= (s0[i][j] ^ s1[i][j]);
126         }
127     }
128 
129     return (uint16_t)PQCLEAN_MCELIECE460896_VEC_vec_testz(diff);
130 }
131 
132 /* Niederreiter decryption with the Berlekamp decoder */
133 /* intput: sk, secret key */
134 /*         c, ciphertext (syndrome) */
135 /* output: e, error vector */
136 /* return: 0 for success; 1 for failure */
137 int PQCLEAN_MCELIECE460896_VEC_decrypt(unsigned char *e, const unsigned char *sk, const unsigned char *c) {
138     int i;
139 
140     uint16_t check_synd;
141     uint16_t check_weight;
142 
143     vec inv[ 128 ][ GFBITS ];
144     vec scaled[ 128 ][ GFBITS ];
145     vec eval[ 128 ][ GFBITS ];
146 
147     vec error[ 128 ];
148 
149     vec s_priv[ 4 ][ GFBITS ];
150     vec s_priv_cmp[ 4 ][ GFBITS ];
151     vec locator[2][ GFBITS ];
152 
153     vec recv[ 128 ];
154     vec allone;
155 
156     // Berlekamp decoder
157 
158     preprocess(recv, c);
159 
160     PQCLEAN_MCELIECE460896_VEC_benes(recv, sk + IRR_BYTES, 1);
161     scaling(scaled, inv, sk, recv);
162     PQCLEAN_MCELIECE460896_VEC_fft_tr(s_priv, scaled);
163     PQCLEAN_MCELIECE460896_VEC_bm(locator, s_priv);
164 
165     PQCLEAN_MCELIECE460896_VEC_fft(eval, locator);
166 
167     // reencryption and weight check
168 
169     allone = PQCLEAN_MCELIECE460896_VEC_vec_setbits(1);
170 
171     for (i = 0; i < 128; i++) {
172         error[i] = PQCLEAN_MCELIECE460896_VEC_vec_or_reduce(eval[i]);
173         error[i] ^= allone;
174     }
175 
176     scaling_inv(scaled, inv, error);
177     PQCLEAN_MCELIECE460896_VEC_fft_tr(s_priv_cmp, scaled);
178 
179     check_synd = synd_cmp(s_priv, s_priv_cmp);
180 
181     //
182 
183     PQCLEAN_MCELIECE460896_VEC_benes(error, sk + IRR_BYTES, 0);
184 
185     postprocess(e, error);
186 
187     check_weight = (uint16_t)weight_check(e, error);
188 
189     return 1 - (check_synd & check_weight);
190 }
191 
192