]>
Commit | Line | Data |
---|---|---|
1c1af145 | 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 | } |