2 * RSA signature key generation
3 * Copyright (C) 1999, 2000, 2001 Henry Spencer.
5 * This program is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License as published by the
7 * Free Software Foundation; either version 2 of the License, or (at your
8 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 * RCSID $Id: rsasigkey.c,v 1.20 2002/03/08 00:46:57 henry Exp $
30 #define DEVICE "/dev/urandom"
36 /* the code in getoldkey() knows about this */
37 #define E 3 /* standard public exponent */
39 char usage[] = "rsasigkey [--verbose] [--random device] nbits";
40 char usage2[] = "rsasigkey [--verbose] --oldkey filename";
41 struct option opts[] = {
42 "verbose", 0, NULL, 'v',
43 "random", 1, NULL, 'r',
44 "rounds", 1, NULL, 'p',
45 "oldkey", 1, NULL, 'o',
46 "hostname", 1, NULL, 'H',
47 "noopt", 0, NULL, 'n',
49 "version", 0, NULL, 'V',
52 int verbose = 0; /* narrate the action? */
53 char *device = DEVICE; /* where to get randomness */
54 int devicechanged = 0; /* did user supply his own device? */
55 int nrounds = 30; /* rounds of prime checking; 25 is good */
56 mpz_t prime1; /* old key's prime1 */
57 mpz_t prime2; /* old key's prime2 */
58 char outputhostname[1024]; /* hostname for output */
59 int do_lcm = 1; /* use lcm(p-1, q-1), not (p-1)*(q-1) */
61 char me[] = "ipsec rsasigkey"; /* for messages */
62 char cop[] = "See `ipsec --copyright' for copyright information.";
65 int getoldkey(char *filename);
66 void rsasigkey(int nbits, int useoldkey);
67 void initprime(mpz_t var, int nbits, int eval);
68 void initrandom(mpz_t var, int nbits);
69 void getrandom(size_t nbytes, char *buf);
70 char *bundle(int e, mpz_t n, size_t *sizep);
71 char *conv(char *bits, size_t nbytes, int format);
72 char *hexout(mpz_t var);
73 void report(char *msg);
76 - main - mostly argument parsing
88 char *oldkeyfile = NULL;
90 while ((opt = getopt_long(argc, argv, "", opts, NULL)) != EOF)
92 case 'v': /* verbose description */
95 case 'r': /* nonstandard /dev/random */
99 case 'p': /* number of prime-check rounds */
100 nrounds = atoi(optarg);
102 fprintf(stderr, "%s: rounds must be > 0\n", me);
106 case 'o': /* reformat old key */
109 case 'H': /* set hostname for output */
110 strcpy(outputhostname, optarg);
112 case 'n': /* don't optimize the private key */
116 printf("Usage:\t%s\n", usage);
118 printf("\t%s\n", usage2);
121 case 'V': /* version */
122 printf("%s %s\n", me, ipsec_version_code());
131 if (errflg || optind != ((oldkeyfile != NULL) ? argc : argc-1)) {
132 printf("Usage:\t%s\n", usage);
134 printf("\t%s\n", usage2);
138 if (outputhostname[0] == '\0') {
139 i = gethostname(outputhostname, sizeof(outputhostname));
141 fprintf(stderr, "%s: gethostname failed (%s)\n",
147 if (oldkeyfile == NULL) {
148 assert(argv[optind] != NULL);
149 nbits = atoi(argv[optind]);
151 nbits = getoldkey(oldkeyfile);
154 fprintf(stderr, "%s: invalid bit count (%d)\n", me, nbits);
156 } else if (nbits > MAXBITS) {
157 fprintf(stderr, "%s: overlarge bit count (max %d)\n", me,
160 } else if (nbits % (CHAR_BIT*2) != 0) { /* *2 for nbits/2-bit primes */
161 fprintf(stderr, "%s: bit count (%d) not multiple of %d\n", me,
162 nbits, (int)CHAR_BIT*2);
166 rsasigkey(nbits, (oldkeyfile == NULL) ? 0 : 1);
171 - getoldkey - fetch an old key's primes
178 char line[MAXBITS/2];
181 static char pube[] = "PublicExponent:";
182 static char pubevalue[] = "0x03";
183 static char pr1[] = "Prime1:";
184 static char pr2[] = "Prime2:";
185 # define STREQ(a, b) (strcmp(a, b) == 0)
191 if (STREQ(filename, "-"))
194 f = fopen(filename, "r");
196 fprintf(stderr, "%s: unable to open file `%s' (%s)\n", me,
197 filename, strerror(errno));
201 fprintf(stderr, "getting old key from %s...\n", filename);
203 while (fgets(line, sizeof(line), f) != NULL) {
204 p = line + strlen(line) - 1;
206 fprintf(stderr, "%s: over-long line in file `%s'\n",
212 p = line + strspn(line, " \t"); /* p -> first word */
213 value = strpbrk(p, " \t"); /* value -> after it */
216 value += strspn(value, " \t");
217 /* value -> second word if any */
220 if (value == NULL || *value == '\0') {
222 } else if (STREQ(p, pube)) {
224 if (!STREQ(value, pubevalue)) {
225 fprintf(stderr, "%s: wrong public exponent (`%s') in old key\n",
229 } else if (STREQ(p, pr1)) {
231 fprintf(stderr, "%s: duplicate `%s' lines in `%s'\n",
236 nbits = (strlen(value) - 2) * 4 * 2;
237 if (mpz_init_set_str(prime1, value, 0) < 0) {
238 fprintf(stderr, "%s: conversion error in reading old prime1\n",
242 } else if (STREQ(p, pr2)) {
244 fprintf(stderr, "%s: duplicate `%s' lines in `%s'\n",
249 if (mpz_init_set_str(prime2, value, 0) < 0) {
250 fprintf(stderr, "%s: conversion error in reading old prime2\n",
260 if (!sawpube || !sawpr1 || !sawpr2) {
261 fprintf(stderr, "%s: old key missing or incomplete\n", me);
265 assert(sawpr1); /* and thus nbits is known */
270 - rsasigkey - generate an RSA signature key
271 * e is fixed at 3, without discussion. That would not be wise if these
272 * keys were to be used for encryption, but for signatures there are some
273 * real speed advantages.
276 rsasigkey(nbits, useoldkey)
278 int useoldkey; /* take primes from old key? */
285 mpz_t q1; /* temporary */
286 mpz_t m; /* internal modulus, (p-1)*(q-1) */
287 mpz_t t; /* temporary */
296 time_t now = time((time_t *)NULL);
300 mpz_init_set(p, prime1);
301 mpz_init_set(q, prime2);
303 initprime(p, nbits/2, E);
304 initprime(q, nbits/2, E);
307 if (mpz_cmp(p, q) < 0) {
308 report("swapping primes so p is the larger...");
313 report("computing modulus...");
315 mpz_mul(n, p, q); /* n = p*q */
316 mpz_init_set_ui(e, E);
318 /* internal modulus */
319 report("computing lcm(p-1, q-1)...");
323 mpz_sub_ui(q1, q1, 1);
324 mpz_gcd(t, m, q1); /* t = gcd(p-1, q-1) */
325 mpz_mul(m, m, q1); /* m = (p-1)*(q-1) */
327 mpz_divexact(m, m, t); /* m = lcm(p-1, q-1) */
329 assert(mpz_cmp_ui(t, 1) == 0); /* m and e relatively prime */
332 report("computing d...");
334 success = mpz_invert(d, e, m);
335 if (!success) { /* e has no inverse mod m (!) */
336 fprintf(stderr, "%s: fatal error: unable to invert public "
339 fprintf(stderr, "\t(perhaps random bits are not very "
343 if (mpz_cmp_ui(d, 0) < 0)
345 assert(mpz_cmp(d, m) < 0);
347 /* the speedup hacks */
348 report("computing exp1, exp1, coeff...");
351 mpz_mod(exp1, d, t); /* exp1 = d mod p-1 */
354 mpz_mod(exp2, d, t); /* exp2 = d mod q-1 */
356 success = mpz_invert(coeff, q, p); /* coeff = q^-1 mod p */
357 if (!success) { /* q has no inverse mod p (!) */
358 fprintf(stderr, "%s: fatal error: unable to invert second "
361 fprintf(stderr, "\t(perhaps random bits are not very "
365 if (mpz_cmp_ui(coeff, 0) < 0)
366 mpz_add(coeff, coeff, p);
367 assert(mpz_cmp(coeff, p) < 0);
370 /* note, getoldkey() knows about some of this */
371 report("output...\n"); /* deliberate extra newline */
372 printf("\t# RSA %d bits %s %s", nbits, outputhostname, ctime(&now));
373 /* ctime provides \n */
374 printf("\t# for signatures only, UNSAFE FOR ENCRYPTION\n");
375 bundp = bundle(E, n, &bs);
376 printf("\t#pubkey=%s\n", conv(bundp, bs, 's')); /* RFC2537ish format */
377 printf("\t#IN KEY 0x4200 4 1 %s\n",
378 conv(bundp, bs, 's')+2); /* RFC2537 */
379 printf("\t# (0x4200 = auth-only host-level, 4 = IPSec, 1 = RSA)\n");
380 printf("\tModulus: %s\n", hexout(n));
381 printf("\tPublicExponent: %s\n", hexout(e));
382 printf("\t# everything after this point is secret\n");
383 printf("\tPrivateExponent: %s\n", hexout(d));
384 printf("\tPrime1: %s\n", hexout(p));
385 printf("\tPrime2: %s\n", hexout(q));
386 printf("\tExponent1: %s\n", hexout(exp1));
387 printf("\tExponent2: %s\n", hexout(exp2));
388 printf("\tCoefficient: %s\n", hexout(coeff));
392 - initprime - initialize an mpz_t to a random prime of specified size
393 * Efficiency tweak: we reject candidates that are 1 higher than a multiple
394 * of e, since they will make the internal modulus not relatively prime to e.
397 initprime(var, nbits, eval)
399 int nbits; /* known to be a multiple of CHAR_BIT */
400 int eval; /* value of e; 0 means don't bother w. tweak */
404 # define OKAY(p) (eval == 0 || mpz_fdiv_ui(p, eval) != 1)
406 initrandom(var, nbits);
407 assert(mpz_fdiv_ui(var, 2) == 1); /* odd number */
409 report("looking for a prime starting there (can take a while)...");
411 while (!( OKAY(var) && mpz_probab_prime_p(var, nrounds) )) {
412 mpz_add_ui(var, var, 2);
416 len = mpz_sizeinbase(var, 2);
417 assert(len == nbits || len == nbits+1);
418 if (len == nbits+1) {
419 report("carry out occurred (!), retrying...");
421 initprime(var, nbits, eval);
425 fprintf(stderr, "found it after %lu tries.\n", tries);
429 - initrandom - initialize an mpz_t to a random number, specified bit count
430 * Converting via hex is a bit weird, but it's the best route GMP gives us.
431 * Note that highmost and lowmost bits are forced on -- highmost to give a
432 * number of exactly the specified length, lowmost so it is an odd number.
435 initrandom(var, nbits)
437 int nbits; /* known to be a multiple of CHAR_BIT */
439 size_t nbytes = (size_t)(nbits / CHAR_BIT);
440 static char bitbuf[MAXBITS/CHAR_BIT];
441 static char hexbuf[2 + MAXBITS/4 + 1];
442 size_t hsize = sizeof(hexbuf);
444 assert(nbytes <= sizeof(bitbuf));
445 getrandom(nbytes, bitbuf);
446 bitbuf[0] |= 01 << (CHAR_BIT-1); /* force high bit on */
447 bitbuf[nbytes-1] |= 01; /* force low bit on */
448 if (datatot(bitbuf, nbytes, 'x', hexbuf, hsize) > hsize) {
449 fprintf(stderr, "%s: can't-happen buffer overflow\n", me);
452 if (mpz_init_set_str(var, hexbuf, 0) < 0) {
453 fprintf(stderr, "%s: can't-happen hex conversion error\n", me);
459 - getrandom - get some random bytes from /dev/random (or wherever)
462 getrandom(nbytes, buf)
464 char *buf; /* known to be big enough */
470 dev = open(device, 0);
472 fprintf(stderr, "%s: could not open %s (%s)\n", me,
473 device, strerror(errno));
479 fprintf(stderr, "getting %d random bytes from %s...\n", nbytes,
481 while (ndone < nbytes) {
482 got = read(dev, buf + ndone, nbytes - ndone);
484 fprintf(stderr, "%s: read error on %s (%s)\n", me,
485 device, strerror(errno));
489 fprintf(stderr, "%s: eof on %s!?!\n", me, device);
499 - hexout - prepare hex output, guaranteeing even number of digits
500 * (The current FreeS/WAN conversion routines want an even digit count,
501 * but mpz_get_str doesn't promise one.)
503 char * /* pointer to static buffer (ick) */
507 static char hexbuf[3 + MAXBITS/4 + 1];
510 mpz_get_str(hexbuf+3, 16, var);
511 if (strlen(hexbuf+3)%2 == 0) /* even number of hex digits */
513 else { /* odd, must pad */
524 - bundle - bundle e and n into an RFC2537-format lump
525 * Note, calls hexout.
527 char * /* pointer to static buffer (ick) */
533 char *hexp = hexout(n);
534 static char bundbuf[2 + MAXBITS/8];
541 er = ttodata(hexp, 0, 0, bundbuf+2, sizeof(bundbuf)-2, &size);
543 fprintf(stderr, "%s: can't-happen bundle convert error `%s'\n",
547 if (size > sizeof(bundbuf)-2) {
548 fprintf(stderr, "%s: can't-happen bundle overflow (need %u)\n",
558 - conv - convert bits to output in specified format
560 char * /* pointer to static buffer (ick) */
561 conv(bits, nbytes, format)
564 int format; /* datatot() code */
566 static char convbuf[MAXBITS/4 + 50]; /* enough for hex */
569 n = datatot(bits, nbytes, format, convbuf, sizeof(convbuf));
571 fprintf(stderr, "%s: can't-happen convert error\n", me);
574 if (n > sizeof(convbuf)) {
575 fprintf(stderr, "%s: can't-happen convert overflow (need %u)\n",
583 - report - report progress, if indicated
591 fprintf(stderr, "%s\n", msg);