putty/SSHDSSG.C

   1 /*\r
   2  * DSS key generation.\r
   3  */\r
   4 \r
   5 #include "misc.h"\r
   6 #include "ssh.h"\r
   7 \r
   8 int dsa_generate(struct dss_key *key, int bits, progfn_t pfn,\r
   9                  void *pfnparam)\r
  10 {\r
  11     Bignum qm1, power, g, h, tmp;\r
  12     unsigned pfirst, qfirst;\r
  13     int progress;\r
  14 \r
  15     /*\r
  16      * Set up the phase limits for the progress report. We do this\r
  17      * by passing minus the phase number.\r
  18      *\r
  19      * For prime generation: our initial filter finds things\r
  20      * coprime to everything below 2^16. Computing the product of\r
  21      * (p-1)/p for all prime p below 2^16 gives about 20.33; so\r
  22      * among B-bit integers, one in every 20.33 will get through\r
  23      * the initial filter to be a candidate prime.\r
  24      *\r
  25      * Meanwhile, we are searching for primes in the region of 2^B;\r
  26      * since pi(x) ~ x/log(x), when x is in the region of 2^B, the\r
  27      * prime density will be d/dx pi(x) ~ 1/log(B), i.e. about\r
  28      * 1/0.6931B. So the chance of any given candidate being prime\r
  29      * is 20.33/0.6931B, which is roughly 29.34 divided by B.\r
  30      *\r
  31      * So now we have this probability P, we're looking at an\r
  32      * exponential distribution with parameter P: we will manage in\r
  33      * one attempt with probability P, in two with probability\r
  34      * P(1-P), in three with probability P(1-P)^2, etc. The\r
  35      * probability that we have still not managed to find a prime\r
  36      * after N attempts is (1-P)^N.\r
  37      * \r
  38      * We therefore inform the progress indicator of the number B\r
  39      * (29.34/B), so that it knows how much to increment by each\r
  40      * time. We do this in 16-bit fixed point, so 29.34 becomes\r
  41      * 0x1D.57C4.\r
  42      */\r
  43     pfn(pfnparam, PROGFN_PHASE_EXTENT, 1, 0x2800);\r
  44     pfn(pfnparam, PROGFN_EXP_PHASE, 1, -0x1D57C4 / 160);\r
  45     pfn(pfnparam, PROGFN_PHASE_EXTENT, 2, 0x40 * bits);\r
  46     pfn(pfnparam, PROGFN_EXP_PHASE, 2, -0x1D57C4 / bits);\r
  47 \r
  48     /*\r
  49      * In phase three we are finding an order-q element of the\r
  50      * multiplicative group of p, by finding an element whose order\r
  51      * is _divisible_ by q and raising it to the power of (p-1)/q.\r
  52      * _Most_ elements will have order divisible by q, since for a\r
  53      * start phi(p) of them will be primitive roots. So\r
  54      * realistically we don't need to set this much below 1 (64K).\r
  55      * Still, we'll set it to 1/2 (32K) to be on the safe side.\r
  56      */\r
  57     pfn(pfnparam, PROGFN_PHASE_EXTENT, 3, 0x2000);\r
  58     pfn(pfnparam, PROGFN_EXP_PHASE, 3, -32768);\r
  59 \r
  60     /*\r
  61      * In phase four we are finding an element x between 1 and q-1\r
  62      * (exclusive), by inventing 160 random bits and hoping they\r
  63      * come out to a plausible number; so assuming q is uniformly\r
  64      * distributed between 2^159 and 2^160, the chance of any given\r
  65      * attempt succeeding is somewhere between 0.5 and 1. Lacking\r
  66      * the energy to arrange to be able to specify this probability\r
  67      * _after_ generating q, we'll just set it to 0.75.\r
  68      */\r
  69     pfn(pfnparam, PROGFN_PHASE_EXTENT, 4, 0x2000);\r
  70     pfn(pfnparam, PROGFN_EXP_PHASE, 4, -49152);\r
  71 \r
  72     pfn(pfnparam, PROGFN_READY, 0, 0);\r
  73 \r
  74     invent_firstbits(&pfirst, &qfirst);\r
  75     /*\r
  76      * Generate q: a prime of length 160.\r
  77      */\r
  78     key->q = primegen(160, 2, 2, NULL, 1, pfn, pfnparam, qfirst);\r
  79     /*\r
  80      * Now generate p: a prime of length `bits', such that p-1 is\r
  81      * divisible by q.\r
  82      */\r
  83     key->p = primegen(bits-160, 2, 2, key->q, 2, pfn, pfnparam, pfirst);\r
  84 \r
  85     /*\r
  86      * Next we need g. Raise 2 to the power (p-1)/q modulo p, and\r
  87      * if that comes out to one then try 3, then 4 and so on. As\r
  88      * soon as we hit a non-unit (and non-zero!) one, that'll do\r
  89      * for g.\r
  90      */\r
  91     power = bigdiv(key->p, key->q);    /* this is floor(p/q) == (p-1)/q */\r
  92     h = bignum_from_long(1);\r
  93     progress = 0;\r
  94     while (1) {\r
  95         pfn(pfnparam, PROGFN_PROGRESS, 3, ++progress);\r
  96         g = modpow(h, power, key->p);\r
  97         if (bignum_cmp(g, One) > 0)\r
  98             break;                     /* got one */\r
  99         tmp = h;\r
 100         h = bignum_add_long(h, 1);\r
 101         freebn(tmp);\r
 102     }\r
 103     key->g = g;\r
 104     freebn(h);\r
 105 \r
 106     /*\r
 107      * Now we're nearly done. All we need now is our private key x,\r
 108      * which should be a number between 1 and q-1 exclusive, and\r
 109      * our public key y = g^x mod p.\r
 110      */\r
 111     qm1 = copybn(key->q);\r
 112     decbn(qm1);\r
 113     progress = 0;\r
 114     while (1) {\r
 115         int i, v, byte, bitsleft;\r
 116         Bignum x;\r
 117 \r
 118         pfn(pfnparam, PROGFN_PROGRESS, 4, ++progress);\r
 119         x = bn_power_2(159);\r
 120         byte = 0;\r
 121         bitsleft = 0;\r
 122 \r
 123         for (i = 0; i < 160; i++) {\r
 124             if (bitsleft <= 0)\r
 125                 bitsleft = 8, byte = random_byte();\r
 126             v = byte & 1;\r
 127             byte >>= 1;\r
 128             bitsleft--;\r
 129             bignum_set_bit(x, i, v);\r
 130         }\r
 131 \r
 132         if (bignum_cmp(x, One) <= 0 || bignum_cmp(x, qm1) >= 0) {\r
 133             freebn(x);\r
 134             continue;\r
 135         } else {\r
 136             key->x = x;\r
 137             break;\r
 138         }\r
 139     }\r
 140     freebn(qm1);\r
 141 \r
 142     key->y = modpow(key->g, key->x, key->p);\r
 143 \r
 144     return 1;\r
 145 }\r