sshdssg.c

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