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_bytes
);
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 if (size
< 512 || size
> 4096 || (size
% 8 != 0)) {
48 dropbear_exit("Bits must satisfy 512 <= bits <= 4096, and be a"
52 key
= m_malloc(sizeof(*key
));
53 m_mp_alloc_init_multi(&key
->e
, &key
->n
, &key
->d
, &key
->p
, &key
->q
, NULL
);
54 m_mp_init_multi(&pminus
, &lcm
, &qminus
, NULL
);
56 if (mp_set_int(key
->e
, RSA_E
) != MP_OKAY
) {
57 fprintf(stderr
, "RSA generation failed\n");
62 getrsaprime(key
->p
, &pminus
, key
->e
, size
/16);
63 getrsaprime(key
->q
, &qminus
, key
->e
, size
/16);
65 if (mp_mul(key
->p
, key
->q
, key
->n
) != MP_OKAY
) {
66 fprintf(stderr
, "RSA generation failed\n");
70 if ((unsigned int)mp_count_bits(key
->n
) == size
) {
76 if (mp_lcm(&pminus
, &qminus
, &lcm
) != MP_OKAY
) {
77 fprintf(stderr
, "RSA generation failed\n");
81 /* de = 1 mod lcm(p-1,q-1) */
82 /* therefore d = (e^-1) mod lcm(p-1,q-1) */
83 if (mp_invmod(key
->e
, &lcm
, key
->d
) != MP_OKAY
) {
84 fprintf(stderr
, "RSA generation failed\n");
88 mp_clear_multi(&pminus
, &qminus
, &lcm
, NULL
);
93 /* return a prime suitable for p or q */
94 static void getrsaprime(mp_int
* prime
, mp_int
*primeminus
,
95 mp_int
* rsa_e
, unsigned int size_bytes
) {
100 buf
= (unsigned char*)m_malloc(size_bytes
);
102 m_mp_init(&temp_gcd
);
104 /* generate a random odd number with MSB set, then find the
105 the next prime above it */
106 genrandom(buf
, size_bytes
);
109 bytes_to_mp(prime
, buf
, size_bytes
);
111 /* find the next integer which is prime, 8 round of miller-rabin */
112 if (mp_prime_next_prime(prime
, 8, 0) != MP_OKAY
) {
113 fprintf(stderr
, "RSA generation failed\n");
117 /* subtract one to get p-1 */
118 if (mp_sub_d(prime
, 1, primeminus
) != MP_OKAY
) {
119 fprintf(stderr
, "RSA generation failed\n");
122 /* check relative primality to e */
123 if (mp_gcd(primeminus
, rsa_e
, &temp_gcd
) != MP_OKAY
) {
124 fprintf(stderr
, "RSA generation failed\n");
127 } while (mp_cmp_d(&temp_gcd
, 1) != MP_EQ
); /* while gcd(p-1, e) != 1 */
129 /* now we have a good value for result */
131 m_burn(buf
, size_bytes
);
135 #endif /* DROPBEAR_RSA */