sshrsa.c

   1 /*
   2  * RSA implementation just sufficient for ssh client-side
   3  * initialisation step
   4  *
   5  * Rewritten for more speed by Joris van Rantwijk, Jun 1999.
   6  */
   7
   8 #include <stdio.h>
   9 #include <stdlib.h>
  10 #include <string.h>
  11
  12 #include "ssh.h"
  13
  14 typedef unsigned short *Bignum;
  15
  16 static unsigned short Zero[1] = { 0 };
  17
  18 #if defined TESTMODE || defined RSADEBUG
  19 #ifndef DLVL
  20 #define DLVL 10000
  21 #endif
  22 #define debug(x) bndebug(#x,x)
  23 static int level = 0;
  24 static void bndebug(char *name, Bignum b) {
  25     int i;
  26     int w = 50-level-strlen(name)-5*b[0];
  27     if (level >= DLVL)
  28         return;
  29     if (w < 0) w = 0;
  30     dprintf("%*s%s%*s", level, "", name, w, "");
  31     for (i=b[0]; i>0; i--)
  32         dprintf(" %04x", b[i]);
  33     dprintf("\n");
  34 }
  35 #define dmsg(x) do {if(level<DLVL){dprintf("%*s",level,"");printf x;}} while(0)
  36 #define enter(x) do { dmsg(x); level += 4; } while(0)
  37 #define leave(x) do { level -= 4; dmsg(x); } while(0)
  38 #else
  39 #define debug(x)
  40 #define dmsg(x)
  41 #define enter(x)
  42 #define leave(x)
  43 #endif
  44
  45 static Bignum newbn(int length) {
  46     Bignum b = malloc((length+1)*sizeof(unsigned short));
  47     if (!b)
  48         abort();                       /* FIXME */
  49     b[0] = length;
  50     return b;
  51 }
  52
  53 static void freebn(Bignum b) {
  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 >= m0 && t > ((unsigned long) r << 16) + a[i+1])
 130                 q--;
 131         }
 132
 133         /* Substract q * m from a[i...] */
 134         c = 0;
 135         for (k = len - 1; k >= 0; k--) {
 136             t = (long) q * (long) m[k];
 137             t += c;
 138             c = t >> 16;
 139             if ((unsigned short) t > a[i+k]) c++;
 140             a[i+k] -= (unsigned short) t;
 141         }
 142
 143         /* Add back m in case of borrow */
 144         if (c != h) {
 145             t = 0;
 146             for (k = len - 1; k >= 0; k--) {
 147                 t += m[k];
 148                 t += a[i+k];
 149                 a[i+k] = (unsigned short)t;
 150                 t = t >> 16;
 151             }
 152         }
 153     }
 154 }
 155
 156 /*
 157  * Compute (base ^ exp) % mod.
 158  * The base MUST be smaller than the modulus.
 159  * The most significant word of mod MUST be non-zero.
 160  * We assume that the result array is the same size as the mod array.
 161  */
 162 static void modpow(Bignum base, Bignum exp, Bignum mod, Bignum result)
 163 {
 164     unsigned short *a, *b, *n, *m;
 165     int mshift;
 166     int mlen, i, j;
 167
 168     /* Allocate m of size mlen, copy mod to m */
 169     /* We use big endian internally */
 170     mlen = mod[0];
 171     m = malloc(mlen * sizeof(unsigned short));
 172     for (j = 0; j < mlen; j++) m[j] = mod[mod[0] - j];
 173
 174     /* Shift m left to make msb bit set */
 175     for (mshift = 0; mshift < 15; mshift++)
 176         if ((m[0] << mshift) & 0x8000) break;
 177     if (mshift) {
 178         for (i = 0; i < mlen - 1; i++)
 179             m[i] = (m[i] << mshift) | (m[i+1] >> (16-mshift));
 180         m[mlen-1] = m[mlen-1] << mshift;
 181     }
 182
 183     /* Allocate n of size mlen, copy base to n */
 184     n = malloc(mlen * sizeof(unsigned short));
 185     i = mlen - base[0];
 186     for (j = 0; j < i; j++) n[j] = 0;
 187     for (j = 0; j < base[0]; j++) n[i+j] = base[base[0] - j];
 188
 189     /* Allocate a and b of size 2*mlen. Set a = 1 */
 190     a = malloc(2 * mlen * sizeof(unsigned short));
 191     b = malloc(2 * mlen * sizeof(unsigned short));
 192     for (i = 0; i < 2*mlen; i++) a[i] = 0;
 193     a[2*mlen-1] = 1;
 194
 195     /* Skip leading zero bits of exp. */
 196     i = 0; j = 15;
 197     while (i < exp[0] && (exp[exp[0] - i] & (1 << j)) == 0) {
 198         j--;
 199         if (j < 0) { i++; j = 15; }
 200     }
 201
 202     /* Main computation */
 203     while (i < exp[0]) {
 204         while (j >= 0) {
 205             bigmul(a + mlen, a + mlen, b, mlen);
 206             bigmod(b, m, mlen);
 207             if ((exp[exp[0] - i] & (1 << j)) != 0) {
 208                 bigmul(b + mlen, n, a, mlen);
 209                 bigmod(a, m, mlen);
 210             } else {
 211                 unsigned short *t;
 212                 t = a;  a = b;  b = t;
 213             }
 214             j--;
 215         }
 216         i++; j = 15;
 217     }
 218
 219     /* Fixup result in case the modulus was shifted */
 220     if (mshift) {
 221         for (i = mlen - 1; i < 2*mlen - 1; i++)
 222             a[i] = (a[i] << mshift) | (a[i+1] >> (16-mshift));
 223         a[2*mlen-1] = a[2*mlen-1] << mshift;
 224         bigmod(a, m, mlen);
 225         for (i = 2*mlen - 1; i >= mlen; i--)
 226             a[i] = (a[i] >> mshift) | (a[i-1] << (16-mshift));
 227     }
 228
 229     /* Copy result to buffer */
 230     for (i = 0; i < mlen; i++)
 231         result[result[0] - i] = a[i+mlen];
 232
 233     /* Free temporary arrays */
 234     for (i = 0; i < 2*mlen; i++) a[i] = 0; free(a);
 235     for (i = 0; i < 2*mlen; i++) b[i] = 0; free(b);
 236     for (i = 0; i < mlen; i++) m[i] = 0; free(m);
 237     for (i = 0; i < mlen; i++) n[i] = 0; free(n);
 238 }
 239
 240 int makekey(unsigned char *data, struct RSAKey *result,
 241             unsigned char **keystr) {
 242     unsigned char *p = data;
 243     Bignum bn[2];
 244     int i, j;
 245     int w, b;
 246
 247     result->bits = 0;
 248     for (i=0; i<4; i++)
 249         result->bits = (result->bits << 8) + *p++;
 250
 251     for (j=0; j<2; j++) {
 252
 253         w = 0;
 254         for (i=0; i<2; i++)
 255             w = (w << 8) + *p++;
 256
 257         result->bytes = b = (w+7)/8;   /* bits -> bytes */
 258         w = (w+15)/16;                 /* bits -> words */
 259
 260         bn[j] = newbn(w);
 261
 262         if (keystr) *keystr = p;       /* point at key string, second time */
 263
 264         for (i=1; i<=w; i++)
 265             bn[j][i] = 0;
 266         for (i=0; i<b; i++) {
 267             unsigned char byte = *p++;
 268             if ((b-i) & 1)
 269                 bn[j][w-i/2] |= byte;
 270             else
 271                 bn[j][w-i/2] |= byte<<8;
 272         }
 273
 274         debug(bn[j]);
 275
 276     }
 277
 278     result->exponent = bn[0];
 279     result->modulus = bn[1];
 280
 281     return p - data;
 282 }
 283
 284 void rsaencrypt(unsigned char *data, int length, struct RSAKey *key) {
 285     Bignum b1, b2;
 286     int w, i;
 287     unsigned char *p;
 288
 289     debug(key->exponent);
 290
 291     memmove(data+key->bytes-length, data, length);
 292     data[0] = 0;
 293     data[1] = 2;
 294
 295     for (i = 2; i < key->bytes-length-1; i++) {
 296         do {
 297             data[i] = random_byte();
 298         } while (data[i] == 0);
 299     }
 300     data[key->bytes-length-1] = 0;
 301
 302     w = (key->bytes+1)/2;
 303
 304     b1 = newbn(w);
 305     b2 = newbn(w);
 306
 307     p = data;
 308     for (i=1; i<=w; i++)
 309         b1[i] = 0;
 310     for (i=0; i<key->bytes; i++) {
 311         unsigned char byte = *p++;
 312         if ((key->bytes-i) & 1)
 313             b1[w-i/2] |= byte;
 314         else
 315             b1[w-i/2] |= byte<<8;
 316     }
 317
 318     debug(b1);
 319
 320     modpow(b1, key->exponent, key->modulus, b2);
 321
 322     debug(b2);
 323
 324     p = data;
 325     for (i=0; i<key->bytes; i++) {
 326         unsigned char b;
 327         if (i & 1)
 328             b = b2[w-i/2] & 0xFF;
 329         else
 330             b = b2[w-i/2] >> 8;
 331         *p++ = b;
 332     }
 333
 334     freebn(b1);
 335     freebn(b2);
 336 }
 337
 338 int rsastr_len(struct RSAKey *key) {
 339     Bignum md, ex;
 340
 341     md = key->modulus;
 342     ex = key->exponent;
 343     return 4 * (ex[0]+md[0]) + 10;
 344 }
 345
 346 void rsastr_fmt(char *str, struct RSAKey *key) {
 347     Bignum md, ex;
 348     int len = 0, i;
 349
 350     md = key->modulus;
 351     ex = key->exponent;
 352
 353     for (i=1; i<=ex[0]; i++) {
 354         sprintf(str+len, "%04x", ex[i]);
 355         len += strlen(str+len);
 356     }
 357     str[len++] = '/';
 358     for (i=1; i<=md[0]; i++) {
 359         sprintf(str+len, "%04x", md[i]);
 360         len += strlen(str+len);
 361     }
 362     str[len] = '\0';
 363 }
 364
 365 #ifdef TESTMODE
 366
 367 #ifndef NODDY
 368 #define p1 10007
 369 #define p2 10069
 370 #define p3 10177
 371 #else
 372 #define p1 3
 373 #define p2 7
 374 #define p3 13
 375 #endif
 376
 377 unsigned short P1[2] = { 1, p1 };
 378 unsigned short P2[2] = { 1, p2 };
 379 unsigned short P3[2] = { 1, p3 };
 380 unsigned short bigmod[5] = { 4, 0, 0, 0, 32768U };
 381 unsigned short mod[5] = { 4, 0, 0, 0, 0 };
 382 unsigned short a[5] = { 4, 0, 0, 0, 0 };
 383 unsigned short b[5] = { 4, 0, 0, 0, 0 };
 384 unsigned short c[5] = { 4, 0, 0, 0, 0 };
 385 unsigned short One[2] = { 1, 1 };
 386 unsigned short Two[2] = { 1, 2 };
 387
 388 int main(void) {
 389     modmult(P1, P2, bigmod, a);   debug(a);
 390     modmult(a, P3, bigmod, mod);  debug(mod);
 391
 392     sub(P1, One, a);              debug(a);
 393     sub(P2, One, b);              debug(b);
 394     modmult(a, b, bigmod, c);     debug(c);
 395     sub(P3, One, a);              debug(a);
 396     modmult(a, c, bigmod, b);     debug(b);
 397
 398     modpow(Two, b, mod, a);       debug(a);
 399
 400     return 0;
 401 }
 402
 403 #endif