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