1 /*
2 Name: rsakey.c
3 Purpose: Generate keys for the RSA cryptosystem.
4 Author: M. J. Fromberger
5
6 Usage: rsakey [-e <expt>] <modbits> [<outfile>]
7
8 Generates an RSA key pair with a modulus having <modbits> significant bits,
9 and writes it to the specified output file, or to the standard output. The
10 -e option allows the user to specify an encryption exponent; otherwise, an
11 encryption exponent is chosen at random.
12
13 Primes p and q are obtained by reading random bits from /dev/random, setting
14 the low-order bit, and testing for primality. If the first candidate is not
15 prime, successive odd candidates are tried until a probable prime is found.
16
17 Copyright (C) 2002-2008 Michael J. Fromberger, All Rights Reserved.
18
19 Permission is hereby granted, free of charge, to any person obtaining a copy
20 of this software and associated documentation files (the "Software"), to deal
21 in the Software without restriction, including without limitation the rights
22 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
23 copies of the Software, and to permit persons to whom the Software is
24 furnished to do so, subject to the following conditions:
25
26 The above copyright notice and this permission notice shall be included in
27 all copies or substantial portions of the Software.
28
29 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
30 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
31 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
32 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
33 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
34 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
35 SOFTWARE.
36 */
37
38 #include <errno.h>
39 #include <limits.h>
40 #include <stdio.h>
41 #include <stdlib.h>
42 #include <string.h>
43
44 #include <getopt.h>
45 #include <unistd.h>
46
47 #include "imath.h"
48 #include "iprime.h"
49
50 typedef struct {
51 mpz_t p;
52 mpz_t q;
53 mpz_t n;
54 mpz_t e;
55 mpz_t d;
56 } rsa_key;
57
58 /* Load the specified buffer with random bytes */
59 int randomize(unsigned char *buf, size_t len);
60
61 /* Overwrite the specified value with n_bits random bits */
62 mp_result mp_int_randomize(mp_int a, mp_size n_bits);
63
64 /* Find a prime starting from the given odd seed */
65 mp_result find_prime(mp_int seed, FILE *fb);
66
67 /* Initialize/destroy an rsa_key structure */
68 mp_result rsa_key_init(rsa_key *kp);
69 void rsa_key_clear(rsa_key *kp);
70 void rsa_key_write(rsa_key *kp, FILE *ofp);
71
main(int argc,char * argv[])72 int main(int argc, char *argv[]) {
73 int opt, modbits;
74 FILE *ofp = stdout;
75 char *expt = NULL;
76 rsa_key the_key;
77 mp_result res;
78
79 /* Process command-line arguments */
80 while ((opt = getopt(argc, argv, "e:")) != EOF) {
81 switch (opt) {
82 case 'e':
83 expt = optarg;
84 break;
85 default:
86 fprintf(stderr, "Usage: rsakey [-e <expt>] <modbits> [<outfile>]\n");
87 return 1;
88 }
89 }
90
91 if (optind >= argc) {
92 fprintf(stderr, "Error: You must specify the number of modulus bits.\n");
93 fprintf(stderr, "Usage: rsakey [-e <expt>] <modbits> [<outfile>]\n");
94 return 1;
95 }
96 modbits = (int)strtol(argv[optind++], NULL, 0);
97 if (modbits < CHAR_BIT) {
98 fprintf(stderr, "Error: Invalid value for number of modulus bits.\n");
99 return 1;
100 }
101 if (modbits % 2 == 1) ++modbits;
102
103 /* Check if output file is specified */
104 if (optind < argc) {
105 if ((ofp = fopen(argv[optind], "wt")) == NULL) {
106 fprintf(stderr,
107 "Error: Unable to open output file for writing.\n"
108 " - Filename: %s\n"
109 " - Error: %s\n",
110 argv[optind], strerror(errno));
111 return 1;
112 }
113 }
114
115 if ((res = rsa_key_init(&the_key)) != MP_OK) {
116 fprintf(stderr,
117 "Error initializing RSA key structure:\n"
118 " - %s (%d)\n",
119 mp_error_string(res), res);
120 return 1;
121 }
122
123 /* If specified, try to load the key exponent */
124 if (expt != NULL) {
125 if ((res = mp_int_read_string(&(the_key.e), 10, expt)) != MP_OK) {
126 fprintf(stderr,
127 "Error: Invalid value for encryption exponent.\n"
128 " - %s (%d)\n",
129 mp_error_string(res), res);
130 goto EXIT;
131 }
132 }
133
134 if ((res = mp_int_randomize(&(the_key.p), (modbits / 2))) != MP_OK) {
135 fprintf(stderr,
136 "Error: Unable to randomize first prime.\n"
137 " - %s (%d)\n",
138 mp_error_string(res), res);
139 goto EXIT;
140 }
141 fprintf(stderr, "p: ");
142 find_prime(&(the_key.p), stderr);
143
144 if ((res = mp_int_randomize(&(the_key.q), (modbits / 2))) != MP_OK) {
145 fprintf(stderr,
146 "Error: Unable to randomize second prime.\n"
147 " - %s (%d)\n",
148 mp_error_string(res), res);
149 goto EXIT;
150 }
151 fprintf(stderr, "\nq: ");
152 find_prime(&(the_key.q), stderr);
153 fputc('\n', stderr);
154
155 /* Temporarily, the key's "n" field will be (p - 1) * (q - 1) for
156 purposes of computing the decryption exponent.
157 */
158 mp_int_mul(&(the_key.p), &(the_key.q), &(the_key.n));
159 mp_int_sub(&(the_key.n), &(the_key.p), &(the_key.n));
160 mp_int_sub(&(the_key.n), &(the_key.q), &(the_key.n));
161 mp_int_add_value(&(the_key.n), 1, &(the_key.n));
162
163 if (expt == NULL &&
164 (res = mp_int_randomize(&(the_key.e), (modbits / 2))) != MP_OK) {
165 fprintf(stderr,
166 "Error: Unable to randomize encryption exponent.\n"
167 " - %s (%d)\n",
168 mp_error_string(res), res);
169 goto EXIT;
170 }
171 while ((res = mp_int_invmod(&(the_key.e), &(the_key.n), &(the_key.d))) !=
172 MP_OK) {
173 if (expt != NULL) {
174 fprintf(stderr,
175 "Error: Unable to compute decryption exponent.\n"
176 " - %s (%d)\n",
177 mp_error_string(res), res);
178 goto EXIT;
179 }
180 if ((res = mp_int_randomize(&(the_key.e), (modbits / 2))) != MP_OK) {
181 fprintf(stderr,
182 "Error: Unable to re-randomize encryption exponent.\n"
183 " - %s (%d)\n",
184 mp_error_string(res), res);
185 goto EXIT;
186 }
187 }
188
189 /* Recompute the real modulus, now that exponents are done. */
190 mp_int_mul(&(the_key.p), &(the_key.q), &(the_key.n));
191
192 /* Write completed key to the specified output file */
193 rsa_key_write(&the_key, ofp);
194
195 EXIT:
196 fclose(ofp);
197 rsa_key_clear(&the_key);
198 return 0;
199 }
200
randomize(unsigned char * buf,size_t len)201 int randomize(unsigned char *buf, size_t len) {
202 FILE *rnd = fopen("/dev/random", "rb");
203 size_t nr;
204
205 if (rnd == NULL) return -1;
206
207 nr = fread(buf, sizeof(*buf), len, rnd);
208 fclose(rnd);
209
210 return (int)nr;
211 }
212
mp_int_randomize(mp_int a,mp_size n_bits)213 mp_result mp_int_randomize(mp_int a, mp_size n_bits) {
214 mp_size n_bytes = (n_bits + CHAR_BIT - 1) / CHAR_BIT;
215 unsigned char *buf;
216 mp_result res = MP_OK;
217
218 if ((buf = malloc(n_bytes)) == NULL) return MP_MEMORY;
219
220 if ((mp_size)randomize(buf, n_bytes) != n_bytes) {
221 res = MP_TRUNC;
222 goto CLEANUP;
223 }
224
225 /* Clear bits beyond the number requested */
226 if (n_bits % CHAR_BIT != 0) {
227 unsigned char b_mask = (1 << (n_bits % CHAR_BIT)) - 1;
228 unsigned char t_mask = (1 << (n_bits % CHAR_BIT)) >> 1;
229
230 buf[0] &= b_mask;
231 buf[0] |= t_mask;
232 }
233
234 /* Set low-order bit to insure value is odd */
235 buf[n_bytes - 1] |= 1;
236
237 res = mp_int_read_unsigned(a, buf, n_bytes);
238
239 CLEANUP:
240 memset(buf, 0, n_bytes);
241 free(buf);
242
243 return res;
244 }
245
find_prime(mp_int seed,FILE * fb)246 mp_result find_prime(mp_int seed, FILE *fb) {
247 mp_result res;
248 int count = 0;
249
250 if (mp_int_is_even(seed))
251 if ((res = mp_int_add_value(seed, 1, seed)) != MP_OK) return res;
252
253 while ((res = mp_int_is_prime(seed)) == MP_FALSE) {
254 ++count;
255
256 if (fb != NULL && (count % 50) == 0) fputc('.', fb);
257
258 if ((res = mp_int_add_value(seed, 2, seed)) != MP_OK) return res;
259 }
260
261 if (res == MP_TRUE && fb != NULL) fputc('+', fb);
262
263 return res;
264 }
265
rsa_key_init(rsa_key * kp)266 mp_result rsa_key_init(rsa_key *kp) {
267 mp_int_init(&(kp->p));
268 mp_int_init(&(kp->q));
269 mp_int_init(&(kp->n));
270 mp_int_init(&(kp->e));
271 mp_int_init(&(kp->d));
272
273 return MP_OK;
274 }
275
rsa_key_clear(rsa_key * kp)276 void rsa_key_clear(rsa_key *kp) {
277 mp_int_clear(&(kp->p));
278 mp_int_clear(&(kp->q));
279 mp_int_clear(&(kp->n));
280 mp_int_clear(&(kp->e));
281 mp_int_clear(&(kp->d));
282 }
283
rsa_key_write(rsa_key * kp,FILE * ofp)284 void rsa_key_write(rsa_key *kp, FILE *ofp) {
285 int len;
286 char *obuf;
287
288 len = mp_int_string_len(&(kp->n), 10);
289 obuf = malloc(len);
290 mp_int_to_string(&(kp->p), 10, obuf, len);
291 fprintf(ofp, "p = %s\n", obuf);
292 mp_int_to_string(&(kp->q), 10, obuf, len);
293 fprintf(ofp, "q = %s\n", obuf);
294 mp_int_to_string(&(kp->e), 10, obuf, len);
295 fprintf(ofp, "e = %s\n", obuf);
296 mp_int_to_string(&(kp->d), 10, obuf, len);
297 fprintf(ofp, "d = %s\n", obuf);
298 mp_int_to_string(&(kp->n), 10, obuf, len);
299 fprintf(ofp, "n = %s\n", obuf);
300
301 free(obuf);
302 }
303
304 /* Here there be dragons */
305