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