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