sshbn.c

   1 /*
   2  * Bignum routines for RSA and DH and stuff.
   3  */
   4
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7 #include <string.h>
   8
   9 #include "ssh.h"
  10
  11 static unsigned short Zero[1] = { 0 };
  12
  13 #if defined TESTMODE || defined RSADEBUG
  14 #ifndef DLVL
  15 #define DLVL 10000
  16 #endif
  17 #define debug(x) bndebug(#x,x)
  18 static int level = 0;
  19 static void bndebug(char *name, Bignum b) {
  20     int i;
  21     int w = 50-level-strlen(name)-5*b[0];
  22     if (level >= DLVL)
  23         return;
  24     if (w < 0) w = 0;
  25     dprintf("%*s%s%*s", level, "", name, w, "");
  26     for (i=b[0]; i>0; i--)
  27         dprintf(" %04x", b[i]);
  28     dprintf("\n");
  29 }
  30 #define dmsg(x) do {if(level<DLVL){dprintf("%*s",level,"");printf x;}} while(0)
  31 #define enter(x) do { dmsg(x); level += 4; } while(0)
  32 #define leave(x) do { level -= 4; dmsg(x); } while(0)
  33 #else
  34 #define debug(x)
  35 #define dmsg(x)
  36 #define enter(x)
  37 #define leave(x)
  38 #endif
  39
  40 Bignum newbn(int length) {
  41     Bignum b = malloc((length+1)*sizeof(unsigned short));
  42     if (!b)
  43         abort();                       /* FIXME */
  44     memset(b, 0, (length+1)*sizeof(*b));
  45     b[0] = length;
  46     return b;
  47 }
  48
  49 void freebn(Bignum b) {
  50     /*
  51      * Burn the evidence, just in case.
  52      */
  53     memset(b, 0, sizeof(b[0]) * (b[0] + 1));
  54     free(b);
  55 }
  56
  57 /*
  58  * Compute c = a * b.
  59  * Input is in the first len words of a and b.
  60  * Result is returned in the first 2*len words of c.
  61  */
  62 static void bigmul(unsigned short *a, unsigned short *b, unsigned short *c,
  63                    int len)
  64 {
  65     int i, j;
  66     unsigned long ai, t;
  67
  68     for (j = len - 1; j >= 0; j--)
  69         c[j+len] = 0;
  70
  71     for (i = len - 1; i >= 0; i--) {
  72         ai = a[i];
  73         t = 0;
  74         for (j = len - 1; j >= 0; j--) {
  75             t += ai * (unsigned long) b[j];
  76             t += (unsigned long) c[i+j+1];
  77             c[i+j+1] = (unsigned short)t;
  78             t = t >> 16;
  79         }
  80         c[i] = (unsigned short)t;
  81     }
  82 }
  83
  84 /*
  85  * Compute a = a % m.
  86  * Input in first 2*len words of a and first len words of m.
  87  * Output in first 2*len words of a (of which first len words will be zero).
  88  * The MSW of m MUST have its high bit set.
  89  */
  90 static void bigmod(unsigned short *a, unsigned short *m, int len)
  91 {
  92     unsigned short m0, m1;
  93     unsigned int h;
  94     int i, k;
  95
  96     /* Special case for len == 1 */
  97     if (len == 1) {
  98         a[1] = (((long) a[0] << 16) + a[1]) % m[0];
  99         a[0] = 0;
 100         return;
 101     }
 102
 103     m0 = m[0];
 104     m1 = m[1];
 105
 106     for (i = 0; i <= len; i++) {
 107         unsigned long t;
 108         unsigned int q, r, c;
 109
 110         if (i == 0) {
 111             h = 0;
 112         } else {
 113             h = a[i-1];
 114             a[i-1] = 0;
 115         }
 116
 117         /* Find q = h:a[i] / m0 */
 118         t = ((unsigned long) h << 16) + a[i];
 119         q = t / m0;
 120         r = t % m0;
 121
 122         /* Refine our estimate of q by looking at
 123          h:a[i]:a[i+1] / m0:m1 */
 124         t = (long) m1 * (long) q;
 125         if (t > ((unsigned long) r << 16) + a[i+1]) {
 126             q--;
 127             t -= m1;
 128             r = (r + m0) & 0xffff; /* overflow? */
 129             if (r >= (unsigned long)m0 &&
 130                 t > ((unsigned long) r << 16) + a[i+1])
 131                 q--;
 132         }
 133
 134         /* Substract q * m from a[i...] */
 135         c = 0;
 136         for (k = len - 1; k >= 0; k--) {
 137             t = (long) q * (long) m[k];
 138             t += c;
 139             c = t >> 16;
 140             if ((unsigned short) t > a[i+k]) c++;
 141             a[i+k] -= (unsigned short) t;
 142         }
 143
 144         /* Add back m in case of borrow */
 145         if (c != h) {
 146             t = 0;
 147             for (k = len - 1; k >= 0; k--) {
 148                 t += m[k];
 149                 t += a[i+k];
 150                 a[i+k] = (unsigned short)t;
 151                 t = t >> 16;
 152             }
 153         }
 154     }
 155 }
 156
 157 /*
 158  * Compute (base ^ exp) % mod.
 159  * The base MUST be smaller than the modulus.
 160  * The most significant word of mod MUST be non-zero.
 161  * We assume that the result array is the same size as the mod array.
 162  */
 163 void modpow(Bignum base, Bignum exp, Bignum mod, Bignum result)
 164 {
 165     unsigned short *a, *b, *n, *m;
 166     int mshift;
 167     int mlen, i, j;
 168
 169     /* Allocate m of size mlen, copy mod to m */
 170     /* We use big endian internally */
 171     mlen = mod[0];
 172     m = malloc(mlen * sizeof(unsigned short));
 173     for (j = 0; j < mlen; j++) m[j] = mod[mod[0] - j];
 174
 175     /* Shift m left to make msb bit set */
 176     for (mshift = 0; mshift < 15; mshift++)
 177         if ((m[0] << mshift) & 0x8000) break;
 178     if (mshift) {
 179         for (i = 0; i < mlen - 1; i++)
 180             m[i] = (m[i] << mshift) | (m[i+1] >> (16-mshift));
 181         m[mlen-1] = m[mlen-1] << mshift;
 182     }
 183
 184     /* Allocate n of size mlen, copy base to n */
 185     n = malloc(mlen * sizeof(unsigned short));
 186     i = mlen - base[0];
 187     for (j = 0; j < i; j++) n[j] = 0;
 188     for (j = 0; j < base[0]; j++) n[i+j] = base[base[0] - j];
 189
 190     /* Allocate a and b of size 2*mlen. Set a = 1 */
 191     a = malloc(2 * mlen * sizeof(unsigned short));
 192     b = malloc(2 * mlen * sizeof(unsigned short));
 193     for (i = 0; i < 2*mlen; i++) a[i] = 0;
 194     a[2*mlen-1] = 1;
 195
 196     /* Skip leading zero bits of exp. */
 197     i = 0; j = 15;
 198     while (i < exp[0] && (exp[exp[0] - i] & (1 << j)) == 0) {
 199         j--;
 200         if (j < 0) { i++; j = 15; }
 201     }
 202
 203     /* Main computation */
 204     while (i < exp[0]) {
 205         while (j >= 0) {
 206             bigmul(a + mlen, a + mlen, b, mlen);
 207             bigmod(b, m, mlen);
 208             if ((exp[exp[0] - i] & (1 << j)) != 0) {
 209                 bigmul(b + mlen, n, a, mlen);
 210                 bigmod(a, m, mlen);
 211             } else {
 212                 unsigned short *t;
 213                 t = a;  a = b;  b = t;
 214             }
 215             j--;
 216         }
 217         i++; j = 15;
 218     }
 219
 220     /* Fixup result in case the modulus was shifted */
 221     if (mshift) {
 222         for (i = mlen - 1; i < 2*mlen - 1; i++)
 223             a[i] = (a[i] << mshift) | (a[i+1] >> (16-mshift));
 224         a[2*mlen-1] = a[2*mlen-1] << mshift;
 225         bigmod(a, m, mlen);
 226         for (i = 2*mlen - 1; i >= mlen; i--)
 227             a[i] = (a[i] >> mshift) | (a[i-1] << (16-mshift));
 228     }
 229
 230     /* Copy result to buffer */
 231     for (i = 0; i < mlen; i++)
 232         result[result[0] - i] = a[i+mlen];
 233
 234     /* Free temporary arrays */
 235     for (i = 0; i < 2*mlen; i++) a[i] = 0; free(a);
 236     for (i = 0; i < 2*mlen; i++) b[i] = 0; free(b);
 237     for (i = 0; i < mlen; i++) m[i] = 0; free(m);
 238     for (i = 0; i < mlen; i++) n[i] = 0; free(n);
 239 }