Mercurial > dropbear

comparison genrsa.c @ 389:5ff8218bcee9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 2af95f00ebd5bb7a28b3817db1218442c935388e) to branch 'au.asn.ucc.matt.dropbear' (head ecd779509ef23a8cdf64888904fc9b31d78aa933)
author Matt Johnston <matt@ucc.asn.au>
date Thu, 11 Jan 2007 03:14:55 +0000
parents c9483550701b
children 740e782679be 657c045054ab
comparison
equal deleted inserted replaced
388:fb54020f78e1 389:5ff8218bcee9
1 /*
2 * Dropbear - a SSH2 server
3 *
4 * Copyright (c) 2002,2003 Matt Johnston
5 * All rights reserved.
6 *
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:
13 *
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
16 *
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
23 * SOFTWARE. */
24
25 #include "includes.h"
26 #include "dbutil.h"
27 #include "bignum.h"
28 #include "random.h"
29 #include "rsa.h"
30 #include "genrsa.h"
31
32 #define RSA_E 65537
33
34 #ifdef DROPBEAR_RSA
35
36 static void getrsaprime(mp_int* prime, mp_int *primeminus,
37 mp_int* rsa_e, unsigned int size);
38
39 /* mostly taken from libtomcrypt's rsa key generation routine */
40 rsa_key * gen_rsa_priv_key(unsigned int size) {
41
42 rsa_key * key;
43 DEF_MP_INT(pminus);
44 DEF_MP_INT(qminus);
45 DEF_MP_INT(lcm);
46
47 key = (rsa_key*)m_malloc(sizeof(rsa_key));
48
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));
54
55 m_mp_init_multi(key->e, key->n, key->d, key->p, key->q,
56 &pminus, &lcm, &qminus, NULL);
57
58 seedrandom();
59
60 if (mp_set_int(key->e, RSA_E) != MP_OKAY) {
61 fprintf(stderr, "rsa generation failed\n");
62 exit(1);
63 }
64
65 /* PuTTY doesn't like it if the modulus isn't a multiple of 8 bits,
66 * so we just generate them until we get one which is OK */
67 getrsaprime(key->p, &pminus, key->e, size/2);
68 do {
69 getrsaprime(key->q, &qminus, key->e, size/2);
70
71 if (mp_mul(key->p, key->q, key->n) != MP_OKAY) {
72 fprintf(stderr, "rsa generation failed\n");
73 exit(1);
74 }
75 } while (mp_count_bits(key->n) % 8 != 0);
76
77 /* lcm(p-1, q-1) */
78 if (mp_lcm(&pminus, &qminus, &lcm) != MP_OKAY) {
79 fprintf(stderr, "rsa generation failed\n");
80 exit(1);
81 }
82
83 /* de = 1 mod lcm(p-1,q-1) */
84 /* therefore d = (e^-1) mod lcm(p-1,q-1) */
85 if (mp_invmod(key->e, &lcm, key->d) != MP_OKAY) {
86 fprintf(stderr, "rsa generation failed\n");
87 exit(1);
88 }
89
90 mp_clear_multi(&pminus, &qminus, &lcm, NULL);
91
92 return key;
93 }
94
95 /* return a prime suitable for p or q */
96 static void getrsaprime(mp_int* prime, mp_int *primeminus,
97 mp_int* rsa_e, unsigned int size) {
98
99 unsigned char *buf;
100 DEF_MP_INT(temp_gcd);
101
102 buf = (unsigned char*)m_malloc(size+1);
103
104 m_mp_init(&temp_gcd);
105 do {
106 /* generate a random odd number with MSB set, then find the
107 the next prime above it */
108 genrandom(buf, size+1);
109 buf[0] |= 0x80; /* MSB set */
110
111 bytes_to_mp(prime, buf, size+1);
112
113 /* find the next integer which is prime, 8 round of miller-rabin */
114 if (mp_prime_next_prime(prime, 8, 0) != MP_OKAY) {
115 fprintf(stderr, "rsa generation failed\n");
116 exit(1);
117 }
118
119 /* subtract one to get p-1 */
120 if (mp_sub_d(prime, 1, primeminus) != MP_OKAY) {
121 fprintf(stderr, "rsa generation failed\n");
122 exit(1);
123 }
124 /* check relative primality to e */
125 if (mp_gcd(primeminus, rsa_e, &temp_gcd) != MP_OKAY) {
126 fprintf(stderr, "rsa generation failed\n");
127 exit(1);
128 }
129 } while (mp_cmp_d(&temp_gcd, 1) != MP_EQ); /* while gcd(p-1, e) != 1 */
130
131 /* now we have a good value for result */
132 mp_clear(&temp_gcd);
133 m_burn(buf, size+1);
134 m_free(buf);
135 }
136
137 #endif /* DROPBEAR_RSA */