userapps/opensource/sshd/libtomcrypt/gf.c

   1 /* polynomial basis GF(2^w) routines */
   2 #include "mycrypt.h"
   3
   4 #ifdef GF
   5
   6 #define FORLOOP for (i = 0; i < LSIZE; i++)
   7
   8 /* c = a + b */
   9 void gf_add(gf_intp a, gf_intp b, gf_intp c)
  10 {
  11    int i;
  12    FORLOOP c[i] = a[i]^b[i];
  13 }
  14
  15 /* b = a */
  16 void gf_copy(gf_intp a, gf_intp b)
  17 {
  18    int i;
  19    FORLOOP b[i] = a[i];
  20 }
  21
  22 /* a = 0 */
  23 void gf_zero(gf_intp a)
  24 {
  25    int i;
  26    FORLOOP a[i] = 0;
  27 }
  28
  29 /* is a zero? */
  30 int gf_iszero(gf_intp a)
  31 {
  32    int i;
  33    FORLOOP if (a[i]) {
  34       return 0;
  35    }
  36    return 1;
  37 }
  38
  39 /* is a one? */
  40 int gf_isone(gf_intp a)
  41 {
  42    int i;
  43    for (i = 1; i < LSIZE; i++) {
  44        if (a[i]) {
  45           return 0;
  46        }
  47    }
  48    return a[0] == 1;
  49 }
  50
  51 /* b = a << 1*/
  52 void gf_shl(gf_intp a, gf_intp b)
  53 {
  54    int i;
  55    gf_int tmp;
  56
  57    gf_copy(a, tmp);
  58    for (i = LSIZE-1; i > 0; i--)
  59        b[i] = ((tmp[i]<<1)|((tmp[i-1]&0xFFFFFFFFUL)>>31))&0xFFFFFFFFUL;
  60    b[0] = (tmp[0] << 1)&0xFFFFFFFFUL;
  61    gf_zero(tmp);
  62 }
  63
  64 /* b = a >> 1 */
  65 void gf_shr(gf_intp a, gf_intp b)
  66 {
  67    int i;
  68    gf_int tmp;
  69
  70    gf_copy(a, tmp);
  71    for (i = 0; i < LSIZE-1; i++)
  72        b[i] = (((tmp[i]&0xFFFFFFFFUL)>>1)|(tmp[i+1]<<31))&0xFFFFFFFFUL;
  73    b[LSIZE-1] = (tmp[LSIZE-1]&0xFFFFFFFFUL)>>1;
  74    gf_zero(tmp);
  75 }
  76
  77 /* returns -1 if its zero, otherwise degree of a */
  78 int gf_deg(gf_intp a)
  79 {
  80    int i, ii;
  81    unsigned long t;
  82
  83    ii = -1;
  84    for (i = LSIZE-1; i >= 0; i--)
  85        if (a[i]) {
  86           for (t = a[i], ii = 0; t; t >>= 1, ++ii);
  87           break;
  88        }
  89    if (i == -1) i = 0;
  90    return (i<<5)+ii;
  91 }
  92
  93 /* c = ab */
  94 void gf_mul(gf_intp a, gf_intp b, gf_intp c)
  95 {
  96    gf_int ta, tb;
  97    int i, n;
  98
  99    gf_copy(a, ta);
 100    gf_copy(b, tb);
 101    gf_zero(c);
 102    n = gf_deg(ta)+1;
 103    for (i = 0; i < n; i++) {
 104        if (ta[i>>5]&(1<<(i&31)))
 105           gf_add(c, tb, c);
 106        gf_shl(tb, tb);
 107    }
 108    gf_zero(ta);
 109    gf_zero(tb);
 110 }
 111
 112 /* q = a/b, r = a%b */
 113 void gf_div(gf_intp a, gf_intp b, gf_intp q, gf_intp r)
 114 {
 115    gf_int ta, tb, shifts[LSIZE*32];
 116    int i, magb, mag;
 117
 118    mag  = gf_deg(a);
 119    magb = gf_deg(b);
 120
 121    /* special cases */
 122    if (magb > mag) {
 123       gf_copy(a, r);
 124       gf_zero(q);
 125       return;
 126    }
 127    if (magb == -1) {
 128       return;
 129    }
 130
 131    /* copy locally */
 132    gf_copy(a, ta);
 133    gf_copy(b, tb);
 134    gf_zero(q);
 135
 136    /* make shifted versions of "b" */
 137    gf_copy(tb, shifts[0]);
 138    for (i = 1; i <= (mag-magb); i++)
 139        gf_shl(shifts[i-1], shifts[i]);
 140
 141    while (mag >= magb) {
 142        i = (mag - magb);
 143        q[i>>5] |= (1<<(i&31));
 144        gf_add(ta, shifts[i], ta);
 145        mag = gf_deg(ta);
 146    }
 147    gf_copy(ta, r);
 148    gf_zero(ta);
 149    gf_zero(tb);
 150    zeromem(shifts, sizeof(shifts));
 151 }
 152
 153 /* b = a mod m */
 154 void gf_mod(gf_intp a, gf_intp m, gf_intp b)
 155 {
 156    gf_int tmp;
 157    gf_div(a,m,tmp,b);
 158    gf_zero(tmp);
 159 }
 160
 161 /* c = ab (mod m) */
 162 void gf_mulmod(gf_intp a, gf_intp b, gf_intp m, gf_intp c)
 163 {
 164    gf_int tmp;
 165    gf_mul(a, b, tmp);
 166    gf_mod(tmp, m, c);
 167    gf_zero(tmp);
 168 }
 169
 170 /* B = 1/A mod M */
 171 void gf_invmod(gf_intp A, gf_intp M, gf_intp B)
 172 {
 173   gf_int m, n, p0, p1, p2, r, q, tmp;
 174
 175   /* put all variables in known setup state */
 176   gf_zero(p0);
 177   gf_zero(p2);
 178   gf_copy(M, m);
 179   gf_copy(A, n);
 180   p0[0] = 1;
 181   gf_div(m, n, p1, r);
 182   gf_copy(p1, q);
 183
 184   /* loop until r == 0 */
 185   while (!gf_iszero(r)) {
 186      gf_copy(n, m);
 187      gf_copy(r, n);
 188      gf_div(m, n, q, r);
 189      gf_mul(q, p1, tmp);
 190      gf_add(tmp, p0, p2);
 191      gf_copy(p1, p0);
 192      gf_copy(p2, p1);
 193   }
 194   gf_copy(p0, B);
 195   gf_zero(p0);
 196 }
 197
 198 /* find a square root modulo a prime.  Note the number of
 199  * elements is 2^k - 1, so we must square k-2 times to get the
 200  * square root..
 201  */
 202 void gf_sqrt(gf_intp a, gf_intp M, gf_intp b)
 203 {
 204    int k;
 205    k = gf_deg(M)-2;
 206    gf_copy(a, b);
 207    while (k--)
 208       gf_mulmod(b, b, M, b);
 209 }
 210
 211 /* c = gcd(A,B) */
 212 void gf_gcd(gf_intp A, gf_intp B, gf_intp c)
 213 {
 214    gf_int a, b, r;
 215    int n;
 216
 217    gf_add(A, B, r);
 218    n = gf_deg(r);
 219    if (gf_deg(A) > n) {
 220       gf_copy(A, a);
 221       gf_copy(B, b);
 222    } else {
 223       gf_copy(A, b);
 224       gf_copy(B, a);
 225    }
 226
 227    do {
 228       gf_mod(a, b, r);
 229       gf_copy(b, a);
 230       gf_copy(r, b);
 231    } while (!gf_iszero(r));
 232    gf_copy(a, c);
 233    gf_zero(a);
 234    gf_zero(b);
 235 }
 236
 237 /* returns non-zero if 'a' is irreducible */
 238 int gf_is_prime(gf_intp a)
 239 {
 240    gf_int u, tmp;
 241    int m, n;
 242
 243    gf_zero(u);
 244    u[0] = 2;                    /* u(x) = x */
 245    m = gf_deg(a);
 246    for (n = 0; n < (m/2); n++) {
 247        gf_mulmod(u, u, a, u);   /* u(x) = u(x)^2 mod a(x) */
 248        gf_copy(u, tmp);
 249        tmp[0] ^= 2;             /* tmp(x) = u(x) - x */
 250        gf_gcd(tmp, a, tmp);     /* tmp(x) = gcd(a(x), u(x) - x) */
 251        if (!gf_isone(tmp)) {
 252           return 0;
 253        }
 254    }
 255    return 1;
 256 }
 257
 258 /* returns bytes required to store a gf_int */
 259 int gf_size(gf_intp a)
 260 {
 261    int n;
 262
 263    n = gf_deg(a);
 264    if (n == -1) {
 265       return 4;
 266    }
 267    n = n + (32 - (n&31));
 268    return n/8;
 269 }
 270
 271 /* store a gf_int */
 272 void gf_toraw(gf_intp a, unsigned char *dst)
 273 {
 274    int x, n;
 275    n = gf_size(a)/4;
 276    for (x = 0; x < n; x++) {
 277        STORE32L(a[x], dst);
 278        dst += 4;
 279    }
 280 }
 281
 282 /* read a gf_int (len == in bytes) */
 283 void gf_readraw(gf_intp a, unsigned char *str, int len)
 284 {
 285    int x;
 286    gf_zero(a);
 287    for (x = 0; x < len/4; x++) {
 288        LOAD32L(a[x], str);
 289        str += 4;
 290    }
 291 }
 292
 293 #endif
 294
 295