2 * Dropbear - a SSH2 server
4 * Copyright (c) 2002,2003 Matt Johnston
7 * Permission is hereby granted, free of charge, to any person obtaining a copy
8 * of this software and associated documentation files (the "Software"), to deal
9 * in the Software without restriction, including without limitation the rights
10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the Software is
12 * furnished to do so, subject to the following conditions:
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
36 static void getrsaprime(mp_int
* prime
, mp_int
*primeminus
,
37 mp_int
* rsa_e
, unsigned int size
);
39 /* mostly taken from libtomcrypt's rsa key generation routine */
40 dropbear_rsa_key
* gen_rsa_priv_key(unsigned int size
) {
42 dropbear_rsa_key
* key
;
47 key
= m_malloc(sizeof(*key
));
49 key
->e
= (mp_int
*)m_malloc(sizeof(mp_int
));
50 key
->n
= (mp_int
*)m_malloc(sizeof(mp_int
));
51 key
->d
= (mp_int
*)m_malloc(sizeof(mp_int
));
52 key
->p
= (mp_int
*)m_malloc(sizeof(mp_int
));
53 key
->q
= (mp_int
*)m_malloc(sizeof(mp_int
));
55 m_mp_init_multi(key
->e
, key
->n
, key
->d
, key
->p
, key
->q
,
56 &pminus
, &lcm
, &qminus
, NULL
);
60 if (mp_set_int(key
->e
, RSA_E
) != MP_OKAY
) {
61 fprintf(stderr
, "RSA generation failed\n");
65 getrsaprime(key
->p
, &pminus
, key
->e
, size
/2);
66 getrsaprime(key
->q
, &qminus
, key
->e
, size
/2);
68 if (mp_mul(key
->p
, key
->q
, key
->n
) != MP_OKAY
) {
69 fprintf(stderr
, "RSA generation failed\n");
74 if (mp_lcm(&pminus
, &qminus
, &lcm
) != MP_OKAY
) {
75 fprintf(stderr
, "RSA generation failed\n");
79 /* de = 1 mod lcm(p-1,q-1) */
80 /* therefore d = (e^-1) mod lcm(p-1,q-1) */
81 if (mp_invmod(key
->e
, &lcm
, key
->d
) != MP_OKAY
) {
82 fprintf(stderr
, "RSA generation failed\n");
86 mp_clear_multi(&pminus
, &qminus
, &lcm
, NULL
);
91 /* return a prime suitable for p or q */
92 static void getrsaprime(mp_int
* prime
, mp_int
*primeminus
,
93 mp_int
* rsa_e
, unsigned int size
) {
98 buf
= (unsigned char*)m_malloc(size
+1);
100 m_mp_init(&temp_gcd
);
102 /* generate a random odd number with MSB set, then find the
103 the next prime above it */
104 genrandom(buf
, size
+1);
105 buf
[0] |= 0x80; /* MSB set */
107 bytes_to_mp(prime
, buf
, size
+1);
109 /* find the next integer which is prime, 8 round of miller-rabin */
110 if (mp_prime_next_prime(prime
, 8, 0) != MP_OKAY
) {
111 fprintf(stderr
, "RSA generation failed\n");
115 /* subtract one to get p-1 */
116 if (mp_sub_d(prime
, 1, primeminus
) != MP_OKAY
) {
117 fprintf(stderr
, "RSA generation failed\n");
120 /* check relative primality to e */
121 if (mp_gcd(primeminus
, rsa_e
, &temp_gcd
) != MP_OKAY
) {
122 fprintf(stderr
, "RSA generation failed\n");
125 } while (mp_cmp_d(&temp_gcd
, 1) != MP_EQ
); /* while gcd(p-1, e) != 1 */
127 /* now we have a good value for result */
133 #endif /* DROPBEAR_RSA */