sshrsa.c

   1 /*
   2  * RSA implementation for PuTTY.
   3  */
   4
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7 #include <string.h>
   8 #include <assert.h>
   9
  10 #include "ssh.h"
  11 #include "misc.h"
  12
  13 #define GET_32BIT(cp) \
  14     (((unsigned long)(unsigned char)(cp)[0] << 24) | \
  15     ((unsigned long)(unsigned char)(cp)[1] << 16) | \
  16     ((unsigned long)(unsigned char)(cp)[2] << 8) | \
  17     ((unsigned long)(unsigned char)(cp)[3]))
  18
  19 #define PUT_32BIT(cp, value) { \
  20     (cp)[0] = (unsigned char)((value) >> 24); \
  21     (cp)[1] = (unsigned char)((value) >> 16); \
  22     (cp)[2] = (unsigned char)((value) >> 8); \
  23     (cp)[3] = (unsigned char)(value); }
  24
  25 int makekey(unsigned char *data, int len, struct RSAKey *result,
  26             unsigned char **keystr, int order)
  27 {
  28     unsigned char *p = data;
  29     int i, n;
  30
  31     if (len < 4)
  32         return -1;
  33
  34     if (result) {
  35         result->bits = 0;
  36         for (i = 0; i < 4; i++)
  37             result->bits = (result->bits << 8) + *p++;
  38     } else
  39         p += 4;
  40
  41     len -= 4;
  42
  43     /*
  44      * order=0 means exponent then modulus (the keys sent by the
  45      * server). order=1 means modulus then exponent (the keys
  46      * stored in a keyfile).
  47      */
  48
  49     if (order == 0) {
  50         n = ssh1_read_bignum(p, len, result ? &result->exponent : NULL);
  51         if (n < 0) return -1;
  52         p += n;
  53         len -= n;
  54     }
  55
  56     n = ssh1_read_bignum(p, len, result ? &result->modulus : NULL);
  57     if (n < 0 || (result && bignum_bitcount(result->modulus) == 0)) return -1;
  58     if (result)
  59         result->bytes = n - 2;
  60     if (keystr)
  61         *keystr = p + 2;
  62     p += n;
  63     len -= n;
  64
  65     if (order == 1) {
  66         n = ssh1_read_bignum(p, len, result ? &result->exponent : NULL);
  67         if (n < 0) return -1;
  68         p += n;
  69         len -= n;
  70     }
  71     return p - data;
  72 }
  73
  74 int makeprivate(unsigned char *data, int len, struct RSAKey *result)
  75 {
  76     return ssh1_read_bignum(data, len, &result->private_exponent);
  77 }
  78
  79 int rsaencrypt(unsigned char *data, int length, struct RSAKey *key)
  80 {
  81     Bignum b1, b2;
  82     int i;
  83     unsigned char *p;
  84
  85     if (key->bytes < length + 4)
  86         return 0;                      /* RSA key too short! */
  87
  88     memmove(data + key->bytes - length, data, length);
  89     data[0] = 0;
  90     data[1] = 2;
  91
  92     for (i = 2; i < key->bytes - length - 1; i++) {
  93         do {
  94             data[i] = random_byte();
  95         } while (data[i] == 0);
  96     }
  97     data[key->bytes - length - 1] = 0;
  98
  99     b1 = bignum_from_bytes(data, key->bytes);
 100
 101     b2 = modpow(b1, key->exponent, key->modulus);
 102
 103     p = data;
 104     for (i = key->bytes; i--;) {
 105         *p++ = bignum_byte(b2, i);
 106     }
 107
 108     freebn(b1);
 109     freebn(b2);
 110
 111     return 1;
 112 }
 113
 114 static void sha512_mpint(SHA512_State * s, Bignum b)
 115 {
 116     unsigned char lenbuf[4];
 117     int len;
 118     len = (bignum_bitcount(b) + 8) / 8;
 119     PUT_32BIT(lenbuf, len);
 120     SHA512_Bytes(s, lenbuf, 4);
 121     while (len-- > 0) {
 122         lenbuf[0] = bignum_byte(b, len);
 123         SHA512_Bytes(s, lenbuf, 1);
 124     }
 125     memset(lenbuf, 0, sizeof(lenbuf));
 126 }
 127
 128 /*
 129  * This function is a wrapper on modpow(). It has the same effect
 130  * as modpow(), but employs RSA blinding to protect against timing
 131  * attacks.
 132  */
 133 static Bignum rsa_privkey_op(Bignum input, struct RSAKey *key)
 134 {
 135     Bignum random, random_encrypted, random_inverse;
 136     Bignum input_blinded, ret_blinded;
 137     Bignum ret;
 138
 139     SHA512_State ss;
 140     unsigned char digest512[64];
 141     int digestused = lenof(digest512);
 142     int hashseq = 0;
 143
 144     /*
 145      * Start by inventing a random number chosen uniformly from the
 146      * range 2..modulus-1. (We do this by preparing a random number
 147      * of the right length and retrying if it's greater than the
 148      * modulus, to prevent any potential Bleichenbacher-like
 149      * attacks making use of the uneven distribution within the
 150      * range that would arise from just reducing our number mod n.
 151      * There are timing implications to the potential retries, of
 152      * course, but all they tell you is the modulus, which you
 153      * already knew.)
 154      *
 155      * To preserve determinism and avoid Pageant needing to share
 156      * the random number pool, we actually generate this `random'
 157      * number by hashing stuff with the private key.
 158      */
 159     while (1) {
 160         int bits, byte, bitsleft, v;
 161         random = copybn(key->modulus);
 162         /*
 163          * Find the topmost set bit. (This function will return its
 164          * index plus one.) Then we'll set all bits from that one
 165          * downwards randomly.
 166          */
 167         bits = bignum_bitcount(random);
 168         byte = 0;
 169         bitsleft = 0;
 170         while (bits--) {
 171             if (bitsleft <= 0) {
 172                 bitsleft = 8;
 173                 /*
 174                  * Conceptually the following few lines are equivalent to
 175                  *    byte = random_byte();
 176                  */
 177                 if (digestused >= lenof(digest512)) {
 178                     unsigned char seqbuf[4];
 179                     PUT_32BIT(seqbuf, hashseq);
 180                     SHA512_Init(&ss);
 181                     SHA512_Bytes(&ss, "RSA deterministic blinding", 26);
 182                     SHA512_Bytes(&ss, seqbuf, sizeof(seqbuf));
 183                     sha512_mpint(&ss, key->private_exponent);
 184                     SHA512_Final(&ss, digest512);
 185                     hashseq++;
 186
 187                     /*
 188                      * Now hash that digest plus the signature
 189                      * input.
 190                      */
 191                     SHA512_Init(&ss);
 192                     SHA512_Bytes(&ss, digest512, sizeof(digest512));
 193                     sha512_mpint(&ss, input);
 194                     SHA512_Final(&ss, digest512);
 195
 196                     digestused = 0;
 197                 }
 198                 byte = digest512[digestused++];
 199             }
 200             v = byte & 1;
 201             byte >>= 1;
 202             bitsleft--;
 203             bignum_set_bit(random, bits, v);
 204         }
 205
 206         /*
 207          * Now check that this number is strictly greater than
 208          * zero, and strictly less than modulus.
 209          */
 210         if (bignum_cmp(random, Zero) <= 0 ||
 211             bignum_cmp(random, key->modulus) >= 0) {
 212             freebn(random);
 213             continue;
 214         } else {
 215             break;
 216         }
 217     }
 218
 219     /*
 220      * RSA blinding relies on the fact that (xy)^d mod n is equal
 221      * to (x^d mod n) * (y^d mod n) mod n. We invent a random pair
 222      * y and y^d; then we multiply x by y, raise to the power d mod
 223      * n as usual, and divide by y^d to recover x^d. Thus an
 224      * attacker can't correlate the timing of the modpow with the
 225      * input, because they don't know anything about the number
 226      * that was input to the actual modpow.
 227      *
 228      * The clever bit is that we don't have to do a huge modpow to
 229      * get y and y^d; we will use the number we just invented as
 230      * _y^d_, and use the _public_ exponent to compute (y^d)^e = y
 231      * from it, which is much faster to do.
 232      */
 233     random_encrypted = modpow(random, key->exponent, key->modulus);
 234     random_inverse = modinv(random, key->modulus);
 235     input_blinded = modmul(input, random_encrypted, key->modulus);
 236     ret_blinded = modpow(input_blinded, key->private_exponent, key->modulus);
 237     ret = modmul(ret_blinded, random_inverse, key->modulus);
 238
 239     freebn(ret_blinded);
 240     freebn(input_blinded);
 241     freebn(random_inverse);
 242     freebn(random_encrypted);
 243     freebn(random);
 244
 245     return ret;
 246 }
 247
 248 Bignum rsadecrypt(Bignum input, struct RSAKey *key)
 249 {
 250     return rsa_privkey_op(input, key);
 251 }
 252
 253 int rsastr_len(struct RSAKey *key)
 254 {
 255     Bignum md, ex;
 256     int mdlen, exlen;
 257
 258     md = key->modulus;
 259     ex = key->exponent;
 260     mdlen = (bignum_bitcount(md) + 15) / 16;
 261     exlen = (bignum_bitcount(ex) + 15) / 16;
 262     return 4 * (mdlen + exlen) + 20;
 263 }
 264
 265 void rsastr_fmt(char *str, struct RSAKey *key)
 266 {
 267     Bignum md, ex;
 268     int len = 0, i, nibbles;
 269     static const char hex[] = "0123456789abcdef";
 270
 271     md = key->modulus;
 272     ex = key->exponent;
 273
 274     len += sprintf(str + len, "0x");
 275
 276     nibbles = (3 + bignum_bitcount(ex)) / 4;
 277     if (nibbles < 1)
 278         nibbles = 1;
 279     for (i = nibbles; i--;)
 280         str[len++] = hex[(bignum_byte(ex, i / 2) >> (4 * (i % 2))) & 0xF];
 281
 282     len += sprintf(str + len, ",0x");
 283
 284     nibbles = (3 + bignum_bitcount(md)) / 4;
 285     if (nibbles < 1)
 286         nibbles = 1;
 287     for (i = nibbles; i--;)
 288         str[len++] = hex[(bignum_byte(md, i / 2) >> (4 * (i % 2))) & 0xF];
 289
 290     str[len] = '\0';
 291 }
 292
 293 /*
 294  * Generate a fingerprint string for the key. Compatible with the
 295  * OpenSSH fingerprint code.
 296  */
 297 void rsa_fingerprint(char *str, int len, struct RSAKey *key)
 298 {
 299     struct MD5Context md5c;
 300     unsigned char digest[16];
 301     char buffer[16 * 3 + 40];
 302     int numlen, slen, i;
 303
 304     MD5Init(&md5c);
 305     numlen = ssh1_bignum_length(key->modulus) - 2;
 306     for (i = numlen; i--;) {
 307         unsigned char c = bignum_byte(key->modulus, i);
 308         MD5Update(&md5c, &c, 1);
 309     }
 310     numlen = ssh1_bignum_length(key->exponent) - 2;
 311     for (i = numlen; i--;) {
 312         unsigned char c = bignum_byte(key->exponent, i);
 313         MD5Update(&md5c, &c, 1);
 314     }
 315     MD5Final(digest, &md5c);
 316
 317     sprintf(buffer, "%d ", bignum_bitcount(key->modulus));
 318     for (i = 0; i < 16; i++)
 319         sprintf(buffer + strlen(buffer), "%s%02x", i ? ":" : "",
 320                 digest[i]);
 321     strncpy(str, buffer, len);
 322     str[len - 1] = '\0';
 323     slen = strlen(str);
 324     if (key->comment && slen < len - 1) {
 325         str[slen] = ' ';
 326         strncpy(str + slen + 1, key->comment, len - slen - 1);
 327         str[len - 1] = '\0';
 328     }
 329 }
 330
 331 /*
 332  * Verify that the public data in an RSA key matches the private
 333  * data. We also check the private data itself: we ensure that p >
 334  * q and that iqmp really is the inverse of q mod p.
 335  */
 336 int rsa_verify(struct RSAKey *key)
 337 {
 338     Bignum n, ed, pm1, qm1;
 339     int cmp;
 340
 341     /* n must equal pq. */
 342     n = bigmul(key->p, key->q);
 343     cmp = bignum_cmp(n, key->modulus);
 344     freebn(n);
 345     if (cmp != 0)
 346         return 0;
 347
 348     /* e * d must be congruent to 1, modulo (p-1) and modulo (q-1). */
 349     pm1 = copybn(key->p);
 350     decbn(pm1);
 351     ed = modmul(key->exponent, key->private_exponent, pm1);
 352     cmp = bignum_cmp(ed, One);
 353     sfree(ed);
 354     if (cmp != 0)
 355         return 0;
 356
 357     qm1 = copybn(key->q);
 358     decbn(qm1);
 359     ed = modmul(key->exponent, key->private_exponent, qm1);
 360     cmp = bignum_cmp(ed, One);
 361     sfree(ed);
 362     if (cmp != 0)
 363         return 0;
 364
 365     /*
 366      * Ensure p > q.
 367      */
 368     if (bignum_cmp(key->p, key->q) <= 0)
 369         return 0;
 370
 371     /*
 372      * Ensure iqmp * q is congruent to 1, modulo p.
 373      */
 374     n = modmul(key->iqmp, key->q, key->p);
 375     cmp = bignum_cmp(n, One);
 376     sfree(n);
 377     if (cmp != 0)
 378         return 0;
 379
 380     return 1;
 381 }
 382
 383 /* Public key blob as used by Pageant: exponent before modulus. */
 384 unsigned char *rsa_public_blob(struct RSAKey *key, int *len)
 385 {
 386     int length, pos;
 387     unsigned char *ret;
 388
 389     length = (ssh1_bignum_length(key->modulus) +
 390               ssh1_bignum_length(key->exponent) + 4);
 391     ret = snewn(length, unsigned char);
 392
 393     PUT_32BIT(ret, bignum_bitcount(key->modulus));
 394     pos = 4;
 395     pos += ssh1_write_bignum(ret + pos, key->exponent);
 396     pos += ssh1_write_bignum(ret + pos, key->modulus);
 397
 398     *len = length;
 399     return ret;
 400 }
 401
 402 /* Given a public blob, determine its length. */
 403 int rsa_public_blob_len(void *data, int maxlen)
 404 {
 405     unsigned char *p = (unsigned char *)data;
 406     int n;
 407
 408     if (maxlen < 4)
 409         return -1;
 410     p += 4;                            /* length word */
 411     maxlen -= 4;
 412
 413     n = ssh1_read_bignum(p, maxlen, NULL);    /* exponent */
 414     if (n < 0)
 415         return -1;
 416     p += n;
 417
 418     n = ssh1_read_bignum(p, maxlen, NULL);    /* modulus */
 419     if (n < 0)
 420         return -1;
 421     p += n;
 422
 423     return p - (unsigned char *)data;
 424 }
 425
 426 void freersakey(struct RSAKey *key)
 427 {
 428     if (key->modulus)
 429         freebn(key->modulus);
 430     if (key->exponent)
 431         freebn(key->exponent);
 432     if (key->private_exponent)
 433         freebn(key->private_exponent);
 434     if (key->comment)
 435         sfree(key->comment);
 436 }
 437
 438 /* ----------------------------------------------------------------------
 439  * Implementation of the ssh-rsa signing key type.
 440  */
 441
 442 static void getstring(char **data, int *datalen, char **p, int *length)
 443 {
 444     *p = NULL;
 445     if (*datalen < 4)
 446         return;
 447     *length = GET_32BIT(*data);
 448     *datalen -= 4;
 449     *data += 4;
 450     if (*datalen < *length)
 451         return;
 452     *p = *data;
 453     *data += *length;
 454     *datalen -= *length;
 455 }
 456 static Bignum getmp(char **data, int *datalen)
 457 {
 458     char *p;
 459     int length;
 460     Bignum b;
 461
 462     getstring(data, datalen, &p, &length);
 463     if (!p)
 464         return NULL;
 465     b = bignum_from_bytes((unsigned char *)p, length);
 466     return b;
 467 }
 468
 469 static void *rsa2_newkey(char *data, int len)
 470 {
 471     char *p;
 472     int slen;
 473     struct RSAKey *rsa;
 474
 475     rsa = snew(struct RSAKey);
 476     if (!rsa)
 477         return NULL;
 478     getstring(&data, &len, &p, &slen);
 479
 480     if (!p || slen != 7 || memcmp(p, "ssh-rsa", 7)) {
 481         sfree(rsa);
 482         return NULL;
 483     }
 484     rsa->exponent = getmp(&data, &len);
 485     rsa->modulus = getmp(&data, &len);
 486     rsa->private_exponent = NULL;
 487     rsa->comment = NULL;
 488
 489     return rsa;
 490 }
 491
 492 static void rsa2_freekey(void *key)
 493 {
 494     struct RSAKey *rsa = (struct RSAKey *) key;
 495     freersakey(rsa);
 496     sfree(rsa);
 497 }
 498
 499 static char *rsa2_fmtkey(void *key)
 500 {
 501     struct RSAKey *rsa = (struct RSAKey *) key;
 502     char *p;
 503     int len;
 504
 505     len = rsastr_len(rsa);
 506     p = snewn(len, char);
 507     rsastr_fmt(p, rsa);
 508     return p;
 509 }
 510
 511 static unsigned char *rsa2_public_blob(void *key, int *len)
 512 {
 513     struct RSAKey *rsa = (struct RSAKey *) key;
 514     int elen, mlen, bloblen;
 515     int i;
 516     unsigned char *blob, *p;
 517
 518     elen = (bignum_bitcount(rsa->exponent) + 8) / 8;
 519     mlen = (bignum_bitcount(rsa->modulus) + 8) / 8;
 520
 521     /*
 522      * string "ssh-rsa", mpint exp, mpint mod. Total 19+elen+mlen.
 523      * (three length fields, 12+7=19).
 524      */
 525     bloblen = 19 + elen + mlen;
 526     blob = snewn(bloblen, unsigned char);
 527     p = blob;
 528     PUT_32BIT(p, 7);
 529     p += 4;
 530     memcpy(p, "ssh-rsa", 7);
 531     p += 7;
 532     PUT_32BIT(p, elen);
 533     p += 4;
 534     for (i = elen; i--;)
 535         *p++ = bignum_byte(rsa->exponent, i);
 536     PUT_32BIT(p, mlen);
 537     p += 4;
 538     for (i = mlen; i--;)
 539         *p++ = bignum_byte(rsa->modulus, i);
 540     assert(p == blob + bloblen);
 541     *len = bloblen;
 542     return blob;
 543 }
 544
 545 static unsigned char *rsa2_private_blob(void *key, int *len)
 546 {
 547     struct RSAKey *rsa = (struct RSAKey *) key;
 548     int dlen, plen, qlen, ulen, bloblen;
 549     int i;
 550     unsigned char *blob, *p;
 551
 552     dlen = (bignum_bitcount(rsa->private_exponent) + 8) / 8;
 553     plen = (bignum_bitcount(rsa->p) + 8) / 8;
 554     qlen = (bignum_bitcount(rsa->q) + 8) / 8;
 555     ulen = (bignum_bitcount(rsa->iqmp) + 8) / 8;
 556
 557     /*
 558      * mpint private_exp, mpint p, mpint q, mpint iqmp. Total 16 +
 559      * sum of lengths.
 560      */
 561     bloblen = 16 + dlen + plen + qlen + ulen;
 562     blob = snewn(bloblen, unsigned char);
 563     p = blob;
 564     PUT_32BIT(p, dlen);
 565     p += 4;
 566     for (i = dlen; i--;)
 567         *p++ = bignum_byte(rsa->private_exponent, i);
 568     PUT_32BIT(p, plen);
 569     p += 4;
 570     for (i = plen; i--;)
 571         *p++ = bignum_byte(rsa->p, i);
 572     PUT_32BIT(p, qlen);
 573     p += 4;
 574     for (i = qlen; i--;)
 575         *p++ = bignum_byte(rsa->q, i);
 576     PUT_32BIT(p, ulen);
 577     p += 4;
 578     for (i = ulen; i--;)
 579         *p++ = bignum_byte(rsa->iqmp, i);
 580     assert(p == blob + bloblen);
 581     *len = bloblen;
 582     return blob;
 583 }
 584
 585 static void *rsa2_createkey(unsigned char *pub_blob, int pub_len,
 586                             unsigned char *priv_blob, int priv_len)
 587 {
 588     struct RSAKey *rsa;
 589     char *pb = (char *) priv_blob;
 590
 591     rsa = rsa2_newkey((char *) pub_blob, pub_len);
 592     rsa->private_exponent = getmp(&pb, &priv_len);
 593     rsa->p = getmp(&pb, &priv_len);
 594     rsa->q = getmp(&pb, &priv_len);
 595     rsa->iqmp = getmp(&pb, &priv_len);
 596
 597     if (!rsa_verify(rsa)) {
 598         rsa2_freekey(rsa);
 599         return NULL;
 600     }
 601
 602     return rsa;
 603 }
 604
 605 static void *rsa2_openssh_createkey(unsigned char **blob, int *len)
 606 {
 607     char **b = (char **) blob;
 608     struct RSAKey *rsa;
 609
 610     rsa = snew(struct RSAKey);
 611     if (!rsa)
 612         return NULL;
 613     rsa->comment = NULL;
 614
 615     rsa->modulus = getmp(b, len);
 616     rsa->exponent = getmp(b, len);
 617     rsa->private_exponent = getmp(b, len);
 618     rsa->iqmp = getmp(b, len);
 619     rsa->p = getmp(b, len);
 620     rsa->q = getmp(b, len);
 621
 622     if (!rsa->modulus || !rsa->exponent || !rsa->private_exponent ||
 623         !rsa->iqmp || !rsa->p || !rsa->q) {
 624         sfree(rsa->modulus);
 625         sfree(rsa->exponent);
 626         sfree(rsa->private_exponent);
 627         sfree(rsa->iqmp);
 628         sfree(rsa->p);
 629         sfree(rsa->q);
 630         sfree(rsa);
 631         return NULL;
 632     }
 633
 634     return rsa;
 635 }
 636
 637 static int rsa2_openssh_fmtkey(void *key, unsigned char *blob, int len)
 638 {
 639     struct RSAKey *rsa = (struct RSAKey *) key;
 640     int bloblen, i;
 641
 642     bloblen =
 643         ssh2_bignum_length(rsa->modulus) +
 644         ssh2_bignum_length(rsa->exponent) +
 645         ssh2_bignum_length(rsa->private_exponent) +
 646         ssh2_bignum_length(rsa->iqmp) +
 647         ssh2_bignum_length(rsa->p) + ssh2_bignum_length(rsa->q);
 648
 649     if (bloblen > len)
 650         return bloblen;
 651
 652     bloblen = 0;
 653 #define ENC(x) \
 654     PUT_32BIT(blob+bloblen, ssh2_bignum_length((x))-4); bloblen += 4; \
 655     for (i = ssh2_bignum_length((x))-4; i-- ;) blob[bloblen++]=bignum_byte((x),i);
 656     ENC(rsa->modulus);
 657     ENC(rsa->exponent);
 658     ENC(rsa->private_exponent);
 659     ENC(rsa->iqmp);
 660     ENC(rsa->p);
 661     ENC(rsa->q);
 662
 663     return bloblen;
 664 }
 665
 666 static int rsa2_pubkey_bits(void *blob, int len)
 667 {
 668     struct RSAKey *rsa;
 669     int ret;
 670
 671     rsa = rsa2_newkey((char *) blob, len);
 672     ret = bignum_bitcount(rsa->modulus);
 673     rsa2_freekey(rsa);
 674
 675     return ret;
 676 }
 677
 678 static char *rsa2_fingerprint(void *key)
 679 {
 680     struct RSAKey *rsa = (struct RSAKey *) key;
 681     struct MD5Context md5c;
 682     unsigned char digest[16], lenbuf[4];
 683     char buffer[16 * 3 + 40];
 684     char *ret;
 685     int numlen, i;
 686
 687     MD5Init(&md5c);
 688     MD5Update(&md5c, (unsigned char *)"\0\0\0\7ssh-rsa", 11);
 689
 690 #define ADD_BIGNUM(bignum) \
 691     numlen = (bignum_bitcount(bignum)+8)/8; \
 692     PUT_32BIT(lenbuf, numlen); MD5Update(&md5c, lenbuf, 4); \
 693     for (i = numlen; i-- ;) { \
 694         unsigned char c = bignum_byte(bignum, i); \
 695         MD5Update(&md5c, &c, 1); \
 696     }
 697     ADD_BIGNUM(rsa->exponent);
 698     ADD_BIGNUM(rsa->modulus);
 699 #undef ADD_BIGNUM
 700
 701     MD5Final(digest, &md5c);
 702
 703     sprintf(buffer, "ssh-rsa %d ", bignum_bitcount(rsa->modulus));
 704     for (i = 0; i < 16; i++)
 705         sprintf(buffer + strlen(buffer), "%s%02x", i ? ":" : "",
 706                 digest[i]);
 707     ret = snewn(strlen(buffer) + 1, char);
 708     if (ret)
 709         strcpy(ret, buffer);
 710     return ret;
 711 }
 712
 713 /*
 714  * This is the magic ASN.1/DER prefix that goes in the decoded
 715  * signature, between the string of FFs and the actual SHA hash
 716  * value. The meaning of it is:
 717  *
 718  * 00 -- this marks the end of the FFs; not part of the ASN.1 bit itself
 719  *
 720  * 30 21 -- a constructed SEQUENCE of length 0x21
 721  *    30 09 -- a constructed sub-SEQUENCE of length 9
 722  *       06 05 -- an object identifier, length 5
 723  *          2B 0E 03 02 1A -- object id { 1 3 14 3 2 26 }
 724  *                            (the 1,3 comes from 0x2B = 43 = 40*1+3)
 725  *       05 00 -- NULL
 726  *    04 14 -- a primitive OCTET STRING of length 0x14
 727  *       [0x14 bytes of hash data follows]
 728  *
 729  * The object id in the middle there is listed as `id-sha1' in
 730  * ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-1/pkcs-1v2-1d2.asn (the
 731  * ASN module for PKCS #1) and its expanded form is as follows:
 732  *
 733  * id-sha1                OBJECT IDENTIFIER ::= {
 734  *    iso(1) identified-organization(3) oiw(14) secsig(3)
 735  *    algorithms(2) 26 }
 736  */
 737 static const unsigned char asn1_weird_stuff[] = {
 738     0x00, 0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2B,
 739     0x0E, 0x03, 0x02, 0x1A, 0x05, 0x00, 0x04, 0x14,
 740 };
 741
 742 #define ASN1_LEN ( (int) sizeof(asn1_weird_stuff) )
 743
 744 static int rsa2_verifysig(void *key, char *sig, int siglen,
 745                           char *data, int datalen)
 746 {
 747     struct RSAKey *rsa = (struct RSAKey *) key;
 748     Bignum in, out;
 749     char *p;
 750     int slen;
 751     int bytes, i, j, ret;
 752     unsigned char hash[20];
 753
 754     getstring(&sig, &siglen, &p, &slen);
 755     if (!p || slen != 7 || memcmp(p, "ssh-rsa", 7)) {
 756         return 0;
 757     }
 758     in = getmp(&sig, &siglen);
 759     out = modpow(in, rsa->exponent, rsa->modulus);
 760     freebn(in);
 761
 762     ret = 1;
 763
 764     bytes = (bignum_bitcount(rsa->modulus)+7) / 8;
 765     /* Top (partial) byte should be zero. */
 766     if (bignum_byte(out, bytes - 1) != 0)
 767         ret = 0;
 768     /* First whole byte should be 1. */
 769     if (bignum_byte(out, bytes - 2) != 1)
 770         ret = 0;
 771     /* Most of the rest should be FF. */
 772     for (i = bytes - 3; i >= 20 + ASN1_LEN; i--) {
 773         if (bignum_byte(out, i) != 0xFF)
 774             ret = 0;
 775     }
 776     /* Then we expect to see the asn1_weird_stuff. */
 777     for (i = 20 + ASN1_LEN - 1, j = 0; i >= 20; i--, j++) {
 778         if (bignum_byte(out, i) != asn1_weird_stuff[j])
 779             ret = 0;
 780     }
 781     /* Finally, we expect to see the SHA-1 hash of the signed data. */
 782     SHA_Simple(data, datalen, hash);
 783     for (i = 19, j = 0; i >= 0; i--, j++) {
 784         if (bignum_byte(out, i) != hash[j])
 785             ret = 0;
 786     }
 787     freebn(out);
 788
 789     return ret;
 790 }
 791
 792 static unsigned char *rsa2_sign(void *key, char *data, int datalen,
 793                                 int *siglen)
 794 {
 795     struct RSAKey *rsa = (struct RSAKey *) key;
 796     unsigned char *bytes;
 797     int nbytes;
 798     unsigned char hash[20];
 799     Bignum in, out;
 800     int i, j;
 801
 802     SHA_Simple(data, datalen, hash);
 803
 804     nbytes = (bignum_bitcount(rsa->modulus) - 1) / 8;
 805     bytes = snewn(nbytes, unsigned char);
 806
 807     bytes[0] = 1;
 808     for (i = 1; i < nbytes - 20 - ASN1_LEN; i++)
 809         bytes[i] = 0xFF;
 810     for (i = nbytes - 20 - ASN1_LEN, j = 0; i < nbytes - 20; i++, j++)
 811         bytes[i] = asn1_weird_stuff[j];
 812     for (i = nbytes - 20, j = 0; i < nbytes; i++, j++)
 813         bytes[i] = hash[j];
 814
 815     in = bignum_from_bytes(bytes, nbytes);
 816     sfree(bytes);
 817
 818     out = rsa_privkey_op(in, rsa);
 819     freebn(in);
 820
 821     nbytes = (bignum_bitcount(out) + 7) / 8;
 822     bytes = snewn(4 + 7 + 4 + nbytes, unsigned char);
 823     PUT_32BIT(bytes, 7);
 824     memcpy(bytes + 4, "ssh-rsa", 7);
 825     PUT_32BIT(bytes + 4 + 7, nbytes);
 826     for (i = 0; i < nbytes; i++)
 827         bytes[4 + 7 + 4 + i] = bignum_byte(out, nbytes - 1 - i);
 828     freebn(out);
 829
 830     *siglen = 4 + 7 + 4 + nbytes;
 831     return bytes;
 832 }
 833
 834 const struct ssh_signkey ssh_rsa = {
 835     rsa2_newkey,
 836     rsa2_freekey,
 837     rsa2_fmtkey,
 838     rsa2_public_blob,
 839     rsa2_private_blob,
 840     rsa2_createkey,
 841     rsa2_openssh_createkey,
 842     rsa2_openssh_fmtkey,
 843     rsa2_pubkey_bits,
 844     rsa2_fingerprint,
 845     rsa2_verifysig,
 846     rsa2_sign,
 847     "ssh-rsa",
 848     "rsa2"
 849 };