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 "matrix.h"
00027
00028 __inline int u8rnd() { return random() & 0xff; }
00029
00030 __inline unsigned int u32rnd() { return u8rnd() ^ (u8rnd()<<8) ^ (u8rnd()<<16) ^ (u8rnd()<<24); }
00031
00032
00034
00035
00036
00037
00038 void gop_supr(int n,gf_t *L)
00039 {
00040 unsigned int i, j;
00041 gf_t tmp;
00042
00043 for (i = 0; i < n; ++i)
00044 {
00045 j = i + u32rnd() % (n - i);
00046
00047 tmp = L[j];
00048 L[j] = L[i];
00049 L[i] = tmp;
00050 }
00051 }
00052
00053
00054 binmat_t key_genmat(gf_t *L, poly_t g)
00055 {
00056
00057
00058
00059
00060
00061 gf_t x,y;
00062 binmat_t H,R;
00063 int i,j,k,r,n;
00064 int * perm, Laux[LENGTH];
00065
00066 n=LENGTH;
00067 r=NB_ERRORS*EXT_DEGREE;
00068
00069 H=mat_ini(r,n);
00070 mat_set_to_zero(H);
00071
00072 for(i=0;i< n;i++)
00073 {
00074 x = poly_eval(g,L[i]);
00075 x = gf_inv(x);
00076 y = x;
00077 for(j=0;j<NB_ERRORS;j++)
00078 {
00079 for(k=0;k<EXT_DEGREE;k++)
00080 {
00081 if(y & (1<<k))
00082 mat_set_coeff_to_one(H,j*EXT_DEGREE + k,i);
00083 }
00084 y = gf_mul(y,L[i]);
00085 }
00086 }
00087
00088 perm = mat_rref(H);
00089 if (perm == NULL) {
00090 mat_free(H);
00091 return NULL;
00092 }
00093
00094 R = mat_ini(n-r,r);
00095 mat_set_to_zero(R);
00096 for (i = 0; i < R->rown; ++i)
00097 for (j = 0; j < R->coln; ++j)
00098 if (mat_coeff(H,j,perm[i]))
00099 mat_change_coeff(R,i,j);
00100
00101 for (i = 0; i < LENGTH; ++i)
00102 Laux[i] = L[perm[i]];
00103 for (i = 0; i < LENGTH; ++i)
00104 L[i] = Laux[i];
00105
00106 mat_free(H);
00107 free(perm);
00108
00109 return (R);
00110 }
00111
00112 int keypair(unsigned char * sk, unsigned char * pk)
00113 {
00114 int i, j, k, l;
00115 unsigned long * pt;
00116 gf_t *L, *Linv;
00117 poly_t g, *sqrtmod, *F;
00118 binmat_t R;
00119
00120 gf_init(EXT_DEGREE);
00121
00122
00123 L = malloc(LENGTH * sizeof(gf_t));
00124
00125 for(i=0;i<LENGTH;i++)
00126 L[i]=i;
00127 gop_supr(LENGTH,L);
00128
00129 do {
00130
00131 g = poly_randgen_irred(NB_ERRORS, u8rnd);
00132 R = key_genmat(L,g);
00133 if (R == NULL)
00134 poly_free(g);
00135 } while (R == NULL);
00136
00137 sqrtmod = poly_sqrtmod_init(g);
00138 F = poly_syndrome_init(g, L, LENGTH);
00139
00140
00141
00142
00143
00144
00145 for (i = 0; i < LENGTH; ++i) {
00146 memset(sk, 0, BITS_TO_LONG(CODIMENSION) * sizeof (long));
00147 pt = (unsigned long *) sk;
00148 for (l = 0; l < NB_ERRORS; ++l) {
00149 k = (l * EXT_DEGREE) / BIT_SIZE_OF_LONG;
00150 j = (l * EXT_DEGREE) % BIT_SIZE_OF_LONG;
00151 pt[k] ^= poly_coeff(F[i], l) << j;
00152 if (j + EXT_DEGREE > BIT_SIZE_OF_LONG)
00153 pt[k + 1] ^= poly_coeff(F[i], l) >> (BIT_SIZE_OF_LONG - j);
00154 }
00155 sk += BITS_TO_LONG(CODIMENSION) * sizeof (long);
00156 poly_free(F[i]);
00157 }
00158 free(F);
00159
00160
00161
00162 Linv = malloc(LENGTH * sizeof (gf_t));
00163 for (i = 0; i < LENGTH; ++i)
00164 Linv[L[i]] = i;
00165 memcpy(sk, Linv, LENGTH * sizeof (gf_t));
00166 sk += LENGTH * sizeof (gf_t);
00167 free(L);
00168 free(Linv);
00169
00170 memcpy(sk, g->coeff, (NB_ERRORS + 1) * sizeof (gf_t));
00171 sk += (NB_ERRORS + 1) * sizeof (gf_t);
00172 poly_free(g);
00173
00174 for (i = 0; i < NB_ERRORS; ++i) {
00175 memcpy(sk, sqrtmod[i]->coeff, NB_ERRORS * sizeof (gf_t));
00176 sk += NB_ERRORS * sizeof (gf_t);
00177 poly_free(sqrtmod[i]);
00178 }
00179 free(sqrtmod);
00180
00181 memcpy(pk, R->elem, R->alloc_size);
00182 mat_free(R);
00183
00184 return 1;
00185 }