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 >= (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 static 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 }
 240
 241 int makekey(unsigned char *data, struct RSAKey *result,
 242             unsigned char **keystr) {
 243     unsigned char *p = data;
 244     Bignum bn[2];
 245     int i, j;
 246     int w, b;
 247
 248     result->bits = 0;
 249     for (i=0; i<4; i++)
 250         result->bits = (result->bits << 8) + *p++;
 251
 252     for (j=0; j<2; j++) {
 253
 254         w = 0;
 255         for (i=0; i<2; i++)
 256             w = (w << 8) + *p++;
 257
 258         result->bytes = b = (w+7)/8;   /* bits -> bytes */
 259         w = (w+15)/16;                 /* bits -> words */
 260
 261         bn[j] = newbn(w);
 262
 263         if (keystr) *keystr = p;       /* point at key string, second time */
 264
 265         for (i=1; i<=w; i++)
 266             bn[j][i] = 0;
 267         for (i=b; i-- ;) {
 268             unsigned char byte = *p++;
 269             if (i & 1)
 270                 bn[j][1+i/2] |= byte<<8;
 271             else
 272                 bn[j][1+i/2] |= byte;
 273         }
 274
 275         debug(bn[j]);
 276
 277     }
 278
 279     result->exponent = bn[0];
 280     result->modulus = bn[1];
 281
 282     return p - data;
 283 }
 284
 285 void rsaencrypt(unsigned char *data, int length, struct RSAKey *key) {
 286     Bignum b1, b2;
 287     int w, i;
 288     unsigned char *p;
 289
 290     debug(key->exponent);
 291
 292     memmove(data+key->bytes-length, data, length);
 293     data[0] = 0;
 294     data[1] = 2;
 295
 296     for (i = 2; i < key->bytes-length-1; i++) {
 297         do {
 298             data[i] = random_byte();
 299         } while (data[i] == 0);
 300     }
 301     data[key->bytes-length-1] = 0;
 302
 303     w = (key->bytes+1)/2;
 304
 305     b1 = newbn(w);
 306     b2 = newbn(w);
 307
 308     p = data;
 309     for (i=1; i<=w; i++)
 310         b1[i] = 0;
 311     for (i=key->bytes; i-- ;) {
 312         unsigned char byte = *p++;
 313         if (i & 1)
 314             b1[1+i/2] |= byte<<8;
 315         else
 316             b1[1+i/2] |= byte;
 317     }
 318
 319     debug(b1);
 320
 321     modpow(b1, key->exponent, key->modulus, b2);
 322
 323     debug(b2);
 324
 325     p = data;
 326     for (i=key->bytes; i-- ;) {
 327         unsigned char b;
 328         if (i & 1)
 329             b = b2[1+i/2] >> 8;
 330         else
 331             b = b2[1+i/2] & 0xFF;
 332         *p++ = b;
 333     }
 334
 335     freebn(b1);
 336     freebn(b2);
 337 }
 338
 339 int rsastr_len(struct RSAKey *key) {
 340     Bignum md, ex;
 341
 342     md = key->modulus;
 343     ex = key->exponent;
 344     return 4 * (ex[0]+md[0]) + 10;
 345 }
 346
 347 void rsastr_fmt(char *str, struct RSAKey *key) {
 348     Bignum md, ex;
 349     int len = 0, i;
 350
 351     md = key->modulus;
 352     ex = key->exponent;
 353
 354     for (i=1; i<=ex[0]; i++) {
 355         sprintf(str+len, "%04x", ex[i]);
 356         len += strlen(str+len);
 357     }
 358     str[len++] = '/';
 359     for (i=1; i<=md[0]; i++) {
 360         sprintf(str+len, "%04x", md[i]);
 361         len += strlen(str+len);
 362     }
 363     str[len] = '\0';
 364 }
 365
 366 #ifdef TESTMODE
 367
 368 #ifndef NODDY
 369 #define p1 10007
 370 #define p2 10069
 371 #define p3 10177
 372 #else
 373 #define p1 3
 374 #define p2 7
 375 #define p3 13
 376 #endif
 377
 378 unsigned short P1[2] = { 1, p1 };
 379 unsigned short P2[2] = { 1, p2 };
 380 unsigned short P3[2] = { 1, p3 };
 381 unsigned short bigmod[5] = { 4, 0, 0, 0, 32768U };
 382 unsigned short mod[5] = { 4, 0, 0, 0, 0 };
 383 unsigned short a[5] = { 4, 0, 0, 0, 0 };
 384 unsigned short b[5] = { 4, 0, 0, 0, 0 };
 385 unsigned short c[5] = { 4, 0, 0, 0, 0 };
 386 unsigned short One[2] = { 1, 1 };
 387 unsigned short Two[2] = { 1, 2 };
 388
 389 int main(void) {
 390     modmult(P1, P2, bigmod, a);   debug(a);
 391     modmult(a, P3, bigmod, mod);  debug(mod);
 392
 393     sub(P1, One, a);              debug(a);
 394     sub(P2, One, b);              debug(b);
 395     modmult(a, b, bigmod, c);     debug(c);
 396     sub(P3, One, a);              debug(a);
 397     modmult(a, c, bigmod, b);     debug(b);
 398
 399     modpow(Two, b, mod, a);       debug(a);
 400
 401     return 0;
 402 }
 403
 404 #endif