1 /*\r
2  * RSA key generation.\r
3  */\r
4 \r
5 #include "ssh.h"\r
6 \r
7 #define RSA_EXPONENT 37                /* we like this prime */\r
8 \r
9 int rsa_generate(struct RSAKey *key, int bits, progfn_t pfn,\r
10                  void *pfnparam)\r
11 {\r
12     Bignum pm1, qm1, phi_n;\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, 0x10000);\r
43     pfn(pfnparam, PROGFN_EXP_PHASE, 1, -0x1D57C4 / (bits / 2));\r
44     pfn(pfnparam, PROGFN_PHASE_EXTENT, 2, 0x10000);\r
45     pfn(pfnparam, PROGFN_EXP_PHASE, 2, -0x1D57C4 / (bits - bits / 2));\r
46     pfn(pfnparam, PROGFN_PHASE_EXTENT, 3, 0x4000);\r
47     pfn(pfnparam, PROGFN_LIN_PHASE, 3, 5);\r
49 \r
50     /*\r
51      * We don't generate e; we just use a standard one always.\r
52      */\r
53     key->exponent = bignum_from_long(RSA_EXPONENT);\r
54 \r
55     /*\r
56      * Generate p and q: primes with combined length `bits', not\r
57      * congruent to 1 modulo e. (Strictly speaking, we wanted (p-1)\r
58      * and e to be coprime, and (q-1) and e to be coprime, but in\r
59      * general that's slightly more fiddly to arrange. By choosing\r
60      * a prime e, we can simplify the criterion.)\r
61      */\r
62     key->p = primegen(bits / 2, RSA_EXPONENT, 1, NULL,\r
63                       1, pfn, pfnparam);\r
64     key->q = primegen(bits - bits / 2, RSA_EXPONENT, 1, NULL,\r
65                       2, pfn, pfnparam);\r
66 \r
67     /*\r
68      * Ensure p > q, by swapping them if not.\r
69      */\r
70     if (bignum_cmp(key->p, key->q) < 0) {\r
71         Bignum t = key->p;\r
72         key->p = key->q;\r
73         key->q = t;\r
74     }\r
75 \r
76     /*\r
77      * Now we have p, q and e. All we need to do now is work out\r
78      * the other helpful quantities: n=pq, d=e^-1 mod (p-1)(q-1),\r
79      * and (q^-1 mod p).\r
80      */\r
81     pfn(pfnparam, PROGFN_PROGRESS, 3, 1);\r
82     key->modulus = bigmul(key->p, key->q);\r
83     pfn(pfnparam, PROGFN_PROGRESS, 3, 2);\r
84     pm1 = copybn(key->p);\r
85     decbn(pm1);\r
86     qm1 = copybn(key->q);\r
87     decbn(qm1);\r
88     phi_n = bigmul(pm1, qm1);\r
89     pfn(pfnparam, PROGFN_PROGRESS, 3, 3);\r
90     freebn(pm1);\r
91     freebn(qm1);\r
92     key->private_exponent = modinv(key->exponent, phi_n);\r
93     pfn(pfnparam, PROGFN_PROGRESS, 3, 4);\r
94     key->iqmp = modinv(key->q, key->p);\r
95     pfn(pfnparam, PROGFN_PROGRESS, 3, 5);\r
96 \r
97     /*\r
98      * Clean up temporary numbers.\r
99      */\r
100     freebn(phi_n);\r
101 \r
102     return 1;\r
103 }\r