00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021 #include <stdlib.h>
00022 #include <string.h>
00023 #include "sizes.h"
00024 #include "gf.h"
00025 #include "poly.h"
00026 #include "dicho.h"
00027 #include "randomize.h"
00028
00029 extern precomp_t cwdata;
00030
00031 poly_t g, sqrtmod[NB_ERRORS];
00032 gf_t * Linv;
00033 unsigned long * coeffs;
00034
00035 void sk_from_string(const unsigned char * sk)
00036 {
00037 int i;
00038
00039
00040
00041
00042 coeffs = (unsigned long *) sk;
00043 sk += LENGTH * BITS_TO_LONG(CODIMENSION) * sizeof (long);
00044
00045 Linv = (gf_t *) sk;
00046 sk += LENGTH * sizeof (gf_t);
00047
00048 g = poly_alloc_from_string(NB_ERRORS, sk);
00049 poly_set_deg(g, NB_ERRORS);
00050 sk += (NB_ERRORS + 1) * sizeof (gf_t);
00051
00052 for (i = 0; i < NB_ERRORS; ++i) {
00053 sqrtmod[i] = poly_alloc_from_string(NB_ERRORS - 1, sk);
00054 poly_set_deg(sqrtmod[i], NB_ERRORS - 1);
00055 sk += NB_ERRORS * sizeof (gf_t);
00056 }
00057 }
00058
00059 void sk_free()
00060 {
00061 int i;
00062
00063 free(g);
00064 for (i = 0; i < NB_ERRORS; ++i) {
00065 free(sqrtmod[i]);
00066 }
00067 }
00068
00069 void xor(unsigned long * a, unsigned long * b) {
00070 int i;
00071
00072 for (i = 0; i < BITS_TO_LONG(CODIMENSION); ++i)
00073 a[i] ^= b[i];
00074 }
00075
00076
00077 poly_t syndrome(const unsigned char * b)
00078 {
00079 int i, j, k, l;
00080 poly_t R;
00081 gf_t a;
00082 unsigned long c[BITS_TO_LONG(CODIMENSION)];
00083
00084 memset(c, 0, BITS_TO_LONG(CODIMENSION) * sizeof (long));
00085
00086 R = poly_alloc(NB_ERRORS - 1);
00087 for (j = 0; j < LENGTH; j++)
00088 {
00089 if ((b[j / 8] >> (j % 8)) & 1)
00090 xor(c, coeffs + j * BITS_TO_LONG(CODIMENSION));
00091 }
00092
00093
00094
00095 for (l = 0; l < NB_ERRORS; ++l) {
00096 k = (l * EXT_DEGREE) / BIT_SIZE_OF_LONG;
00097 j = (l * EXT_DEGREE) % BIT_SIZE_OF_LONG;
00098 a = c[k] >> j;
00099 if (j + EXT_DEGREE > BIT_SIZE_OF_LONG)
00100 a ^= c[k + 1] << (BIT_SIZE_OF_LONG - j);
00101 a &= ((1 << EXT_DEGREE) - 1);
00102 poly_set_coeff(R, l, a);
00103 }
00104
00105 poly_calcule_deg(R);
00106 return R;
00107 }
00108
00109 int roots_berl_aux(poly_t sigma, int d, poly_t * tr_aux, poly_t * tr, int e, gf_t * res) {
00110 poly_t gcd1, gcd2;
00111 int i, j;
00112 gf_t a;
00113
00114 if (d == 0) {
00115 return 0;
00116 }
00117
00118 if (d == 1) {
00119 *res = gf_div(poly_coeff(sigma, 0), poly_coeff(sigma, 1));
00120 return 1;
00121 }
00122
00123
00124 if (e >= EXT_DEGREE) {
00125 return 0;
00126 }
00127
00128 if (tr[e] == NULL) {
00129 tr[e] = poly_alloc(NB_ERRORS - 1);
00130 a = gf_exp(e);
00131 for (i = 0; i < EXT_DEGREE; ++i) {
00132 for (j = 0; j < NB_ERRORS; ++j)
00133 poly_addto_coeff(tr[e], j, gf_mul(poly_coeff(tr_aux[i], j), a));
00134 a = gf_square(a);
00135 }
00136 poly_calcule_deg(tr[e]);
00137 }
00138 gcd1 = poly_gcd(tr[e], sigma);
00139 gcd2 = poly_quo(sigma, gcd1);
00140
00141 i = poly_deg(gcd1);
00142
00143 j = roots_berl_aux(gcd1, i, tr_aux, tr, e + 1, res);
00144 j += roots_berl_aux(gcd2, d - i, tr_aux, tr, e + 1, res + j);
00145
00146 poly_free(gcd1);
00147 poly_free(gcd2);
00148
00149 return j;
00150 }
00151
00152 int roots_berl(poly_t sigma, gf_t * res) {
00153 poly_t * sq_aux, * tr, * tr_aux;
00154 int i, j, d;
00155 gf_t a;
00156
00157 sq_aux = malloc(NB_ERRORS * sizeof (poly_t));
00158 tr_aux = malloc(EXT_DEGREE * sizeof (poly_t));
00159 tr = malloc(EXT_DEGREE * sizeof (poly_t));
00160 for (i = 0; i < NB_ERRORS; ++i)
00161 sq_aux[i] = poly_alloc(NB_ERRORS + 1);
00162 for (i = 0; i < EXT_DEGREE; ++i)
00163 tr_aux[i] = poly_alloc(NB_ERRORS - 1);
00164 for (i = 0; i < EXT_DEGREE; ++i)
00165 tr[i] = NULL;
00166
00167 poly_sqmod_init(sigma, sq_aux);
00168 poly_set_coeff(tr_aux[0], 1, gf_unit());
00169 poly_set_deg(tr_aux[0], 1);
00170 tr[0] = poly_alloc(NB_ERRORS - 1);
00171 poly_set_coeff(tr[0], 1, gf_unit());
00172 for (i = 1; i < EXT_DEGREE; ++i) {
00173 poly_sqmod(tr_aux[i], tr_aux[i - 1], sq_aux, NB_ERRORS);
00174 for (j = 0; j < NB_ERRORS; ++j)
00175 poly_addto_coeff(tr[0], j, poly_coeff(tr_aux[i], j));
00176 }
00177 poly_calcule_deg(tr[0]);
00178 for (i = 0; i < NB_ERRORS; ++i)
00179 poly_free(sq_aux[i]);
00180 free(sq_aux);
00181 d = roots_berl_aux(sigma, NB_ERRORS, tr_aux, tr, 0, res);
00182 for (i = 0; i < EXT_DEGREE; ++i)
00183 poly_free(tr_aux[i]);
00184 free(tr_aux);
00185 for (i = 0; i < EXT_DEGREE; ++i)
00186 if (tr[i] != NULL)
00187 poly_free(tr[i]);
00188 free(tr);
00189
00190 return d;
00191 }
00192
00193 int partition (int * tableau, int gauche, int droite, int pivot) {
00194 int i, temp;
00195 for (i = gauche; i < droite; i++)
00196 if (tableau[i] <= pivot) {
00197 temp = tableau[i];
00198 tableau[i] = tableau[gauche];
00199 tableau[gauche] = temp;
00200 ++gauche;
00201 }
00202 return gauche;
00203 }
00204
00205 void quickSort(int * tableau, int gauche, int droite, int min, int max) {
00206 if (gauche < droite - 1) {
00207 int milieu = partition(tableau, gauche, droite, (max + min) / 2);
00208 quickSort(tableau, gauche, milieu, min, (max + min) / 2);
00209 quickSort(tableau, milieu, droite, (max + min) / 2, max);
00210 }
00211 }
00212
00213 int decode(const unsigned char * b, int * e)
00214 {
00215 int i,j,d;
00216 poly_t u,v,h,sigma,R,S,aux;
00217 gf_t a, res[NB_ERRORS];
00218
00219 gf_init(EXT_DEGREE);
00220 R = syndrome(b);
00221
00222
00223
00224
00225
00226 poly_eeaux(&h ,&aux, R, g, 1);
00227 a = gf_inv(poly_coeff(aux,0));
00228 for (i = 0; i <= poly_deg(h); ++i)
00229 poly_set_coeff(h,i,gf_mul_fast(a,poly_coeff(h,i)));
00230 poly_free(aux);
00231 poly_free(R);
00232
00233
00234 poly_addto_coeff(h, 1, gf_unit());
00235
00236
00237 S = poly_alloc(NB_ERRORS - 1);
00238 for(i=0;i<NB_ERRORS;i++) {
00239 a = gf_sqrt(poly_coeff(h,i));
00240 if (a != gf_zero()) {
00241 if (i & 1) {
00242 for(j=0;j<NB_ERRORS;j++)
00243 poly_addto_coeff(S, j, gf_mul_fast(a, poly_coeff(sqrtmod[i],j)));
00244 }
00245 else
00246 poly_addto_coeff(S, i/2, a);
00247 }
00248 }
00249 poly_calcule_deg(S);
00250 poly_free(h);
00251
00252
00253 poly_eeaux(&v, &u, S, g, NB_ERRORS/2+1);
00254 poly_free(S);
00255
00256
00257 sigma = poly_alloc(NB_ERRORS);
00258 for (i = 0; i <= poly_deg(u); ++i) {
00259 poly_set_coeff(sigma, 2*i, gf_square(poly_coeff(u,i)));
00260 }
00261 for (i = 0; i <= poly_deg(v); ++i) {
00262 poly_set_coeff(sigma, 2*i+1, gf_square(poly_coeff(v,i)));
00263 }
00264 poly_free(u);
00265 poly_free(v);
00266
00267 poly_calcule_deg(sigma);
00268
00269 d = poly_deg(sigma);
00270 if (d != NB_ERRORS) {
00271 poly_free(sigma);
00272 return -1;
00273 }
00274
00275 d = roots_berl(sigma, res);
00276 if (d != NB_ERRORS) {
00277 poly_free(sigma);
00278 return -1;
00279 }
00280
00281 for (i = 0; i < d; ++i)
00282 e[i] = Linv[res[i]];
00283
00284
00285 quickSort(e, 0, NB_ERRORS, 0, 1 << EXT_DEGREE);
00286
00287 poly_free(sigma);
00288
00289 return d;
00290 }
00291
00292 int decrypt_block(unsigned char *cleartext, unsigned char *ciphertext, const unsigned char * sk)
00293 {
00294 int i, j, k, l, e[NB_ERRORS];
00295 unsigned char c;
00296
00297 sk_from_string(sk);
00298
00299
00300 i = decode(ciphertext, e);
00301 sk_free();
00302
00303 if (i < 0)
00304 return -1;
00305
00306
00307 for (i = 0; i < NB_ERRORS; i++)
00308 ciphertext[e[i] / 8] ^= (1 << (e[i] % 8));
00309
00310 memcpy(cleartext, ciphertext, BITS_TO_BYTES(DIMENSION));
00311
00312
00313
00314
00315 i = dicho_cw2b(e, cleartext,
00316 DIMENSION, ERROR_SIZE,
00317 LOG_LENGTH, ERROR_WEIGHT, cwdata);
00318
00319
00320
00321 if (i < 0)
00322 return -1;
00323
00324 return 1;
00325 }
00326
00327
00328
00329
00330 int decrypt_block_ss(unsigned char *message, unsigned char *ciphertext, const unsigned char * sk)
00331 {
00332 int i;
00333 unsigned char cleartext[CLEARTEXT_LENGTH];
00334
00335 i = decrypt_block(cleartext, ciphertext, sk);
00336
00337 if (i > 0)
00338
00339 return unrandomize(message, cleartext);
00340
00341 return i;
00342 }