src/TortoisePlink/SSHDSS.C

   1 /*\r
   2  * Digital Signature Standard implementation for PuTTY.\r
   3  */\r
   4 \r
   5 #include <stdio.h>\r
   6 #include <stdlib.h>\r
   7 #include <assert.h>\r
   8 \r
   9 #include "ssh.h"\r
  10 #include "misc.h"\r
  11 \r
  12 static void sha_mpint(SHA_State * s, Bignum b)\r
  13 {\r
  14     unsigned char lenbuf[4];\r
  15     int len;\r
  16     len = (bignum_bitcount(b) + 8) / 8;\r
  17     PUT_32BIT(lenbuf, len);\r
  18     SHA_Bytes(s, lenbuf, 4);\r
  19     while (len-- > 0) {\r
  20         lenbuf[0] = bignum_byte(b, len);\r
  21         SHA_Bytes(s, lenbuf, 1);\r
  22     }\r
  23     memset(lenbuf, 0, sizeof(lenbuf));\r
  24 }\r
  25 \r
  26 static void sha512_mpint(SHA512_State * s, Bignum b)\r
  27 {\r
  28     unsigned char lenbuf[4];\r
  29     int len;\r
  30     len = (bignum_bitcount(b) + 8) / 8;\r
  31     PUT_32BIT(lenbuf, len);\r
  32     SHA512_Bytes(s, lenbuf, 4);\r
  33     while (len-- > 0) {\r
  34         lenbuf[0] = bignum_byte(b, len);\r
  35         SHA512_Bytes(s, lenbuf, 1);\r
  36     }\r
  37     memset(lenbuf, 0, sizeof(lenbuf));\r
  38 }\r
  39 \r
  40 static void getstring(char **data, int *datalen, char **p, int *length)\r
  41 {\r
  42     *p = NULL;\r
  43     if (*datalen < 4)\r
  44         return;\r
  45     *length = GET_32BIT(*data);\r
  46     *datalen -= 4;\r
  47     *data += 4;\r
  48     if (*datalen < *length)\r
  49         return;\r
  50     *p = *data;\r
  51     *data += *length;\r
  52     *datalen -= *length;\r
  53 }\r
  54 static Bignum getmp(char **data, int *datalen)\r
  55 {\r
  56     char *p;\r
  57     int length;\r
  58     Bignum b;\r
  59 \r
  60     getstring(data, datalen, &p, &length);\r
  61     if (!p)\r
  62         return NULL;\r
  63     if (p[0] & 0x80)\r
  64         return NULL;                   /* negative mp */\r
  65     b = bignum_from_bytes((unsigned char *)p, length);\r
  66     return b;\r
  67 }\r
  68 \r
  69 static Bignum get160(char **data, int *datalen)\r
  70 {\r
  71     Bignum b;\r
  72 \r
  73     b = bignum_from_bytes((unsigned char *)*data, 20);\r
  74     *data += 20;\r
  75     *datalen -= 20;\r
  76 \r
  77     return b;\r
  78 }\r
  79 \r
  80 static void *dss_newkey(char *data, int len)\r
  81 {\r
  82     char *p;\r
  83     int slen;\r
  84     struct dss_key *dss;\r
  85 \r
  86     dss = snew(struct dss_key);\r
  87     if (!dss)\r
  88         return NULL;\r
  89     getstring(&data, &len, &p, &slen);\r
  90 \r
  91 #ifdef DEBUG_DSS\r
  92     {\r
  93         int i;\r
  94         printf("key:");\r
  95         for (i = 0; i < len; i++)\r
  96             printf("  %02x", (unsigned char) (data[i]));\r
  97         printf("\n");\r
  98     }\r
  99 #endif\r
 100 \r
 101     if (!p || memcmp(p, "ssh-dss", 7)) {\r
 102         sfree(dss);\r
 103         return NULL;\r
 104     }\r
 105     dss->p = getmp(&data, &len);\r
 106     dss->q = getmp(&data, &len);\r
 107     dss->g = getmp(&data, &len);\r
 108     dss->y = getmp(&data, &len);\r
 109 \r
 110     return dss;\r
 111 }\r
 112 \r
 113 static void dss_freekey(void *key)\r
 114 {\r
 115     struct dss_key *dss = (struct dss_key *) key;\r
 116     freebn(dss->p);\r
 117     freebn(dss->q);\r
 118     freebn(dss->g);\r
 119     freebn(dss->y);\r
 120     sfree(dss);\r
 121 }\r
 122 \r
 123 static char *dss_fmtkey(void *key)\r
 124 {\r
 125     struct dss_key *dss = (struct dss_key *) key;\r
 126     char *p;\r
 127     int len, i, pos, nibbles;\r
 128     static const char hex[] = "0123456789abcdef";\r
 129     if (!dss->p)\r
 130         return NULL;\r
 131     len = 8 + 4 + 1;                   /* 4 x "0x", punctuation, \0 */\r
 132     len += 4 * (bignum_bitcount(dss->p) + 15) / 16;\r
 133     len += 4 * (bignum_bitcount(dss->q) + 15) / 16;\r
 134     len += 4 * (bignum_bitcount(dss->g) + 15) / 16;\r
 135     len += 4 * (bignum_bitcount(dss->y) + 15) / 16;\r
 136     p = snewn(len, char);\r
 137     if (!p)\r
 138         return NULL;\r
 139 \r
 140     pos = 0;\r
 141     pos += sprintf(p + pos, "0x");\r
 142     nibbles = (3 + bignum_bitcount(dss->p)) / 4;\r
 143     if (nibbles < 1)\r
 144         nibbles = 1;\r
 145     for (i = nibbles; i--;)\r
 146         p[pos++] =\r
 147             hex[(bignum_byte(dss->p, i / 2) >> (4 * (i % 2))) & 0xF];\r
 148     pos += sprintf(p + pos, ",0x");\r
 149     nibbles = (3 + bignum_bitcount(dss->q)) / 4;\r
 150     if (nibbles < 1)\r
 151         nibbles = 1;\r
 152     for (i = nibbles; i--;)\r
 153         p[pos++] =\r
 154             hex[(bignum_byte(dss->q, i / 2) >> (4 * (i % 2))) & 0xF];\r
 155     pos += sprintf(p + pos, ",0x");\r
 156     nibbles = (3 + bignum_bitcount(dss->g)) / 4;\r
 157     if (nibbles < 1)\r
 158         nibbles = 1;\r
 159     for (i = nibbles; i--;)\r
 160         p[pos++] =\r
 161             hex[(bignum_byte(dss->g, i / 2) >> (4 * (i % 2))) & 0xF];\r
 162     pos += sprintf(p + pos, ",0x");\r
 163     nibbles = (3 + bignum_bitcount(dss->y)) / 4;\r
 164     if (nibbles < 1)\r
 165         nibbles = 1;\r
 166     for (i = nibbles; i--;)\r
 167         p[pos++] =\r
 168             hex[(bignum_byte(dss->y, i / 2) >> (4 * (i % 2))) & 0xF];\r
 169     p[pos] = '\0';\r
 170     return p;\r
 171 }\r
 172 \r
 173 static char *dss_fingerprint(void *key)\r
 174 {\r
 175     struct dss_key *dss = (struct dss_key *) key;\r
 176     struct MD5Context md5c;\r
 177     unsigned char digest[16], lenbuf[4];\r
 178     char buffer[16 * 3 + 40];\r
 179     char *ret;\r
 180     int numlen, i;\r
 181 \r
 182     MD5Init(&md5c);\r
 183     MD5Update(&md5c, (unsigned char *)"\0\0\0\7ssh-dss", 11);\r
 184 \r
 185 #define ADD_BIGNUM(bignum) \\r
 186     numlen = (bignum_bitcount(bignum)+8)/8; \\r
 187     PUT_32BIT(lenbuf, numlen); MD5Update(&md5c, lenbuf, 4); \\r
 188     for (i = numlen; i-- ;) { \\r
 189         unsigned char c = bignum_byte(bignum, i); \\r
 190         MD5Update(&md5c, &c, 1); \\r
 191     }\r
 192     ADD_BIGNUM(dss->p);\r
 193     ADD_BIGNUM(dss->q);\r
 194     ADD_BIGNUM(dss->g);\r
 195     ADD_BIGNUM(dss->y);\r
 196 #undef ADD_BIGNUM\r
 197 \r
 198     MD5Final(digest, &md5c);\r
 199 \r
 200     sprintf(buffer, "ssh-dss %d ", bignum_bitcount(dss->p));\r
 201     for (i = 0; i < 16; i++)\r
 202         sprintf(buffer + strlen(buffer), "%s%02x", i ? ":" : "",\r
 203                 digest[i]);\r
 204     ret = snewn(strlen(buffer) + 1, char);\r
 205     if (ret)\r
 206         strcpy(ret, buffer);\r
 207     return ret;\r
 208 }\r
 209 \r
 210 static int dss_verifysig(void *key, char *sig, int siglen,\r
 211                          char *data, int datalen)\r
 212 {\r
 213     struct dss_key *dss = (struct dss_key *) key;\r
 214     char *p;\r
 215     int slen;\r
 216     char hash[20];\r
 217     Bignum r, s, w, gu1p, yu2p, gu1yu2p, u1, u2, sha, v;\r
 218     int ret;\r
 219 \r
 220     if (!dss->p)\r
 221         return 0;\r
 222 \r
 223 #ifdef DEBUG_DSS\r
 224     {\r
 225         int i;\r
 226         printf("sig:");\r
 227         for (i = 0; i < siglen; i++)\r
 228             printf("  %02x", (unsigned char) (sig[i]));\r
 229         printf("\n");\r
 230     }\r
 231 #endif\r
 232     /*\r
 233      * Commercial SSH (2.0.13) and OpenSSH disagree over the format\r
 234      * of a DSA signature. OpenSSH is in line with the IETF drafts:\r
 235      * it uses a string "ssh-dss", followed by a 40-byte string\r
 236      * containing two 160-bit integers end-to-end. Commercial SSH\r
 237      * can't be bothered with the header bit, and considers a DSA\r
 238      * signature blob to be _just_ the 40-byte string containing\r
 239      * the two 160-bit integers. We tell them apart by measuring\r
 240      * the length: length 40 means the commercial-SSH bug, anything\r
 241      * else is assumed to be IETF-compliant.\r
 242      */\r
 243     if (siglen != 40) {                /* bug not present; read admin fields */\r
 244         getstring(&sig, &siglen, &p, &slen);\r
 245         if (!p || slen != 7 || memcmp(p, "ssh-dss", 7)) {\r
 246             return 0;\r
 247         }\r
 248         sig += 4, siglen -= 4;         /* skip yet another length field */\r
 249     }\r
 250     r = get160(&sig, &siglen);\r
 251     s = get160(&sig, &siglen);\r
 252     if (!r || !s)\r
 253         return 0;\r
 254 \r
 255     /*\r
 256      * Step 1. w <- s^-1 mod q.\r
 257      */\r
 258     w = modinv(s, dss->q);\r
 259 \r
 260     /*\r
 261      * Step 2. u1 <- SHA(message) * w mod q.\r
 262      */\r
 263     SHA_Simple(data, datalen, (unsigned char *)hash);\r
 264     p = hash;\r
 265     slen = 20;\r
 266     sha = get160(&p, &slen);\r
 267     u1 = modmul(sha, w, dss->q);\r
 268 \r
 269     /*\r
 270      * Step 3. u2 <- r * w mod q.\r
 271      */\r
 272     u2 = modmul(r, w, dss->q);\r
 273 \r
 274     /*\r
 275      * Step 4. v <- (g^u1 * y^u2 mod p) mod q.\r
 276      */\r
 277     gu1p = modpow(dss->g, u1, dss->p);\r
 278     yu2p = modpow(dss->y, u2, dss->p);\r
 279     gu1yu2p = modmul(gu1p, yu2p, dss->p);\r
 280     v = modmul(gu1yu2p, One, dss->q);\r
 281 \r
 282     /*\r
 283      * Step 5. v should now be equal to r.\r
 284      */\r
 285 \r
 286     ret = !bignum_cmp(v, r);\r
 287 \r
 288     freebn(w);\r
 289     freebn(sha);\r
 290     freebn(gu1p);\r
 291     freebn(yu2p);\r
 292     freebn(gu1yu2p);\r
 293     freebn(v);\r
 294     freebn(r);\r
 295     freebn(s);\r
 296 \r
 297     return ret;\r
 298 }\r
 299 \r
 300 static unsigned char *dss_public_blob(void *key, int *len)\r
 301 {\r
 302     struct dss_key *dss = (struct dss_key *) key;\r
 303     int plen, qlen, glen, ylen, bloblen;\r
 304     int i;\r
 305     unsigned char *blob, *p;\r
 306 \r
 307     plen = (bignum_bitcount(dss->p) + 8) / 8;\r
 308     qlen = (bignum_bitcount(dss->q) + 8) / 8;\r
 309     glen = (bignum_bitcount(dss->g) + 8) / 8;\r
 310     ylen = (bignum_bitcount(dss->y) + 8) / 8;\r
 311 \r
 312     /*\r
 313      * string "ssh-dss", mpint p, mpint q, mpint g, mpint y. Total\r
 314      * 27 + sum of lengths. (five length fields, 20+7=27).\r
 315      */\r
 316     bloblen = 27 + plen + qlen + glen + ylen;\r
 317     blob = snewn(bloblen, unsigned char);\r
 318     p = blob;\r
 319     PUT_32BIT(p, 7);\r
 320     p += 4;\r
 321     memcpy(p, "ssh-dss", 7);\r
 322     p += 7;\r
 323     PUT_32BIT(p, plen);\r
 324     p += 4;\r
 325     for (i = plen; i--;)\r
 326         *p++ = bignum_byte(dss->p, i);\r
 327     PUT_32BIT(p, qlen);\r
 328     p += 4;\r
 329     for (i = qlen; i--;)\r
 330         *p++ = bignum_byte(dss->q, i);\r
 331     PUT_32BIT(p, glen);\r
 332     p += 4;\r
 333     for (i = glen; i--;)\r
 334         *p++ = bignum_byte(dss->g, i);\r
 335     PUT_32BIT(p, ylen);\r
 336     p += 4;\r
 337     for (i = ylen; i--;)\r
 338         *p++ = bignum_byte(dss->y, i);\r
 339     assert(p == blob + bloblen);\r
 340     *len = bloblen;\r
 341     return blob;\r
 342 }\r
 343 \r
 344 static unsigned char *dss_private_blob(void *key, int *len)\r
 345 {\r
 346     struct dss_key *dss = (struct dss_key *) key;\r
 347     int xlen, bloblen;\r
 348     int i;\r
 349     unsigned char *blob, *p;\r
 350 \r
 351     xlen = (bignum_bitcount(dss->x) + 8) / 8;\r
 352 \r
 353     /*\r
 354      * mpint x, string[20] the SHA of p||q||g. Total 4 + xlen.\r
 355      */\r
 356     bloblen = 4 + xlen;\r
 357     blob = snewn(bloblen, unsigned char);\r
 358     p = blob;\r
 359     PUT_32BIT(p, xlen);\r
 360     p += 4;\r
 361     for (i = xlen; i--;)\r
 362         *p++ = bignum_byte(dss->x, i);\r
 363     assert(p == blob + bloblen);\r
 364     *len = bloblen;\r
 365     return blob;\r
 366 }\r
 367 \r
 368 static void *dss_createkey(unsigned char *pub_blob, int pub_len,\r
 369                            unsigned char *priv_blob, int priv_len)\r
 370 {\r
 371     struct dss_key *dss;\r
 372     char *pb = (char *) priv_blob;\r
 373     char *hash;\r
 374     int hashlen;\r
 375     SHA_State s;\r
 376     unsigned char digest[20];\r
 377     Bignum ytest;\r
 378 \r
 379     dss = dss_newkey((char *) pub_blob, pub_len);\r
 380     dss->x = getmp(&pb, &priv_len);\r
 381 \r
 382     /*\r
 383      * Check the obsolete hash in the old DSS key format.\r
 384      */\r
 385     hashlen = -1;\r
 386     getstring(&pb, &priv_len, &hash, &hashlen);\r
 387     if (hashlen == 20) {\r
 388         SHA_Init(&s);\r
 389         sha_mpint(&s, dss->p);\r
 390         sha_mpint(&s, dss->q);\r
 391         sha_mpint(&s, dss->g);\r
 392         SHA_Final(&s, digest);\r
 393         if (0 != memcmp(hash, digest, 20)) {\r
 394             dss_freekey(dss);\r
 395             return NULL;\r
 396         }\r
 397     }\r
 398 \r
 399     /*\r
 400      * Now ensure g^x mod p really is y.\r
 401      */\r
 402     ytest = modpow(dss->g, dss->x, dss->p);\r
 403     if (0 != bignum_cmp(ytest, dss->y)) {\r
 404         dss_freekey(dss);\r
 405         return NULL;\r
 406     }\r
 407     freebn(ytest);\r
 408 \r
 409     return dss;\r
 410 }\r
 411 \r
 412 static void *dss_openssh_createkey(unsigned char **blob, int *len)\r
 413 {\r
 414     char **b = (char **) blob;\r
 415     struct dss_key *dss;\r
 416 \r
 417     dss = snew(struct dss_key);\r
 418     if (!dss)\r
 419         return NULL;\r
 420 \r
 421     dss->p = getmp(b, len);\r
 422     dss->q = getmp(b, len);\r
 423     dss->g = getmp(b, len);\r
 424     dss->y = getmp(b, len);\r
 425     dss->x = getmp(b, len);\r
 426 \r
 427     if (!dss->p || !dss->q || !dss->g || !dss->y || !dss->x) {\r
 428         sfree(dss->p);\r
 429         sfree(dss->q);\r
 430         sfree(dss->g);\r
 431         sfree(dss->y);\r
 432         sfree(dss->x);\r
 433         sfree(dss);\r
 434         return NULL;\r
 435     }\r
 436 \r
 437     return dss;\r
 438 }\r
 439 \r
 440 static int dss_openssh_fmtkey(void *key, unsigned char *blob, int len)\r
 441 {\r
 442     struct dss_key *dss = (struct dss_key *) key;\r
 443     int bloblen, i;\r
 444 \r
 445     bloblen =\r
 446         ssh2_bignum_length(dss->p) +\r
 447         ssh2_bignum_length(dss->q) +\r
 448         ssh2_bignum_length(dss->g) +\r
 449         ssh2_bignum_length(dss->y) +\r
 450         ssh2_bignum_length(dss->x);\r
 451 \r
 452     if (bloblen > len)\r
 453         return bloblen;\r
 454 \r
 455     bloblen = 0;\r
 456 #define ENC(x) \\r
 457     PUT_32BIT(blob+bloblen, ssh2_bignum_length((x))-4); bloblen += 4; \\r
 458     for (i = ssh2_bignum_length((x))-4; i-- ;) blob[bloblen++]=bignum_byte((x),i);\r
 459     ENC(dss->p);\r
 460     ENC(dss->q);\r
 461     ENC(dss->g);\r
 462     ENC(dss->y);\r
 463     ENC(dss->x);\r
 464 \r
 465     return bloblen;\r
 466 }\r
 467 \r
 468 static int dss_pubkey_bits(void *blob, int len)\r
 469 {\r
 470     struct dss_key *dss;\r
 471     int ret;\r
 472 \r
 473     dss = dss_newkey((char *) blob, len);\r
 474     ret = bignum_bitcount(dss->p);\r
 475     dss_freekey(dss);\r
 476 \r
 477     return ret;\r
 478 }\r
 479 \r
 480 static unsigned char *dss_sign(void *key, char *data, int datalen, int *siglen)\r
 481 {\r
 482     /*\r
 483      * The basic DSS signing algorithm is:\r
 484      * \r
 485      *  - invent a random k between 1 and q-1 (exclusive).\r
 486      *  - Compute r = (g^k mod p) mod q.\r
 487      *  - Compute s = k^-1 * (hash + x*r) mod q.\r
 488      * \r
 489      * This has the dangerous properties that:\r
 490      * \r
 491      *  - if an attacker in possession of the public key _and_ the\r
 492      *    signature (for example, the host you just authenticated\r
 493      *    to) can guess your k, he can reverse the computation of s\r
 494      *    and work out x = r^-1 * (s*k - hash) mod q. That is, he\r
 495      *    can deduce the private half of your key, and masquerade\r
 496      *    as you for as long as the key is still valid.\r
 497      * \r
 498      *  - since r is a function purely of k and the public key, if\r
 499      *    the attacker only has a _range of possibilities_ for k\r
 500      *    it's easy for him to work through them all and check each\r
 501      *    one against r; he'll never be unsure of whether he's got\r
 502      *    the right one.\r
 503      * \r
 504      *  - if you ever sign two different hashes with the same k, it\r
 505      *    will be immediately obvious because the two signatures\r
 506      *    will have the same r, and moreover an attacker in\r
 507      *    possession of both signatures (and the public key of\r
 508      *    course) can compute k = (hash1-hash2) * (s1-s2)^-1 mod q,\r
 509      *    and from there deduce x as before.\r
 510      * \r
 511      *  - the Bleichenbacher attack on DSA makes use of methods of\r
 512      *    generating k which are significantly non-uniformly\r
 513      *    distributed; in particular, generating a 160-bit random\r
 514      *    number and reducing it mod q is right out.\r
 515      * \r
 516      * For this reason we must be pretty careful about how we\r
 517      * generate our k. Since this code runs on Windows, with no\r
 518      * particularly good system entropy sources, we can't trust our\r
 519      * RNG itself to produce properly unpredictable data. Hence, we\r
 520      * use a totally different scheme instead.\r
 521      * \r
 522      * What we do is to take a SHA-512 (_big_) hash of the private\r
 523      * key x, and then feed this into another SHA-512 hash that\r
 524      * also includes the message hash being signed. That is:\r
 525      * \r
 526      *   proto_k = SHA512 ( SHA512(x) || SHA160(message) )\r
 527      * \r
 528      * This number is 512 bits long, so reducing it mod q won't be\r
 529      * noticeably non-uniform. So\r
 530      * \r
 531      *   k = proto_k mod q\r
 532      * \r
 533      * This has the interesting property that it's _deterministic_:\r
 534      * signing the same hash twice with the same key yields the\r
 535      * same signature.\r
 536      * \r
 537      * Despite this determinism, it's still not predictable to an\r
 538      * attacker, because in order to repeat the SHA-512\r
 539      * construction that created it, the attacker would have to\r
 540      * know the private key value x - and by assumption he doesn't,\r
 541      * because if he knew that he wouldn't be attacking k!\r
 542      *\r
 543      * (This trick doesn't, _per se_, protect against reuse of k.\r
 544      * Reuse of k is left to chance; all it does is prevent\r
 545      * _excessively high_ chances of reuse of k due to entropy\r
 546      * problems.)\r
 547      * \r
 548      * Thanks to Colin Plumb for the general idea of using x to\r
 549      * ensure k is hard to guess, and to the Cambridge University\r
 550      * Computer Security Group for helping to argue out all the\r
 551      * fine details.\r
 552      */\r
 553     struct dss_key *dss = (struct dss_key *) key;\r
 554     SHA512_State ss;\r
 555     unsigned char digest[20], digest512[64];\r
 556     Bignum proto_k, k, gkp, hash, kinv, hxr, r, s;\r
 557     unsigned char *bytes;\r
 558     int nbytes, i;\r
 559 \r
 560     SHA_Simple(data, datalen, digest);\r
 561 \r
 562     /*\r
 563      * Hash some identifying text plus x.\r
 564      */\r
 565     SHA512_Init(&ss);\r
 566     SHA512_Bytes(&ss, "DSA deterministic k generator", 30);\r
 567     sha512_mpint(&ss, dss->x);\r
 568     SHA512_Final(&ss, digest512);\r
 569 \r
 570     /*\r
 571      * Now hash that digest plus the message hash.\r
 572      */\r
 573     SHA512_Init(&ss);\r
 574     SHA512_Bytes(&ss, digest512, sizeof(digest512));\r
 575     SHA512_Bytes(&ss, digest, sizeof(digest));\r
 576     SHA512_Final(&ss, digest512);\r
 577 \r
 578     memset(&ss, 0, sizeof(ss));\r
 579 \r
 580     /*\r
 581      * Now convert the result into a bignum, and reduce it mod q.\r
 582      */\r
 583     proto_k = bignum_from_bytes(digest512, 64);\r
 584     k = bigmod(proto_k, dss->q);\r
 585     freebn(proto_k);\r
 586 \r
 587     memset(digest512, 0, sizeof(digest512));\r
 588 \r
 589     /*\r
 590      * Now we have k, so just go ahead and compute the signature.\r
 591      */\r
 592     gkp = modpow(dss->g, k, dss->p);   /* g^k mod p */\r
 593     r = bigmod(gkp, dss->q);           /* r = (g^k mod p) mod q */\r
 594     freebn(gkp);\r
 595 \r
 596     hash = bignum_from_bytes(digest, 20);\r
 597     kinv = modinv(k, dss->q);          /* k^-1 mod q */\r
 598     hxr = bigmuladd(dss->x, r, hash);  /* hash + x*r */\r
 599     s = modmul(kinv, hxr, dss->q);     /* s = k^-1 * (hash + x*r) mod q */\r
 600     freebn(hxr);\r
 601     freebn(kinv);\r
 602     freebn(hash);\r
 603 \r
 604     /*\r
 605      * Signature blob is\r
 606      * \r
 607      *   string  "ssh-dss"\r
 608      *   string  two 20-byte numbers r and s, end to end\r
 609      * \r
 610      * i.e. 4+7 + 4+40 bytes.\r
 611      */\r
 612     nbytes = 4 + 7 + 4 + 40;\r
 613     bytes = snewn(nbytes, unsigned char);\r
 614     PUT_32BIT(bytes, 7);\r
 615     memcpy(bytes + 4, "ssh-dss", 7);\r
 616     PUT_32BIT(bytes + 4 + 7, 40);\r
 617     for (i = 0; i < 20; i++) {\r
 618         bytes[4 + 7 + 4 + i] = bignum_byte(r, 19 - i);\r
 619         bytes[4 + 7 + 4 + 20 + i] = bignum_byte(s, 19 - i);\r
 620     }\r
 621     freebn(r);\r
 622     freebn(s);\r
 623 \r
 624     *siglen = nbytes;\r
 625     return bytes;\r
 626 }\r
 627 \r
 628 const struct ssh_signkey ssh_dss = {\r
 629     dss_newkey,\r
 630     dss_freekey,\r
 631     dss_fmtkey,\r
 632     dss_public_blob,\r
 633     dss_private_blob,\r
 634     dss_createkey,\r
 635     dss_openssh_createkey,\r
 636     dss_openssh_fmtkey,\r
 637     dss_pubkey_bits,\r
 638     dss_fingerprint,\r
 639     dss_verifysig,\r
 640     dss_sign,\r
 641     "ssh-dss",\r
 642     "dss"\r
 643 };\r