freeswan/utils/rsasigkey.c

   1 /*
   2  * RSA signature key generation
   3  * Copyright (C) 1999, 2000, 2001  Henry Spencer.
   4  *
   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>.
   9  *
  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
  13  * for more details.
  14  *
  15  * RCSID $Id: rsasigkey.c,v 1.20 2002/03/08 00:46:57 henry Exp $
  16  */
  17
  18 #include <stdio.h>
  19 #include <stdlib.h>
  20 #include <time.h>
  21 #include <limits.h>
  22 #include <errno.h>
  23 #include <string.h>
  24 #include <assert.h>
  25 #include <getopt.h>
  26 #include <freeswan.h>
  27 #include "gmp.h"
  28
  29 #ifndef DEVICE
  30 #define DEVICE  "/dev/urandom"
  31 #endif
  32 #ifndef MAXBITS
  33 #define MAXBITS 20000
  34 #endif
  35
  36 /* the code in getoldkey() knows about this */
  37 #define E       3               /* standard public exponent */
  38
  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',
  48         "help",         0,      NULL,   'h',
  49         "version",      0,      NULL,   'V',
  50         0,              0,      NULL,   0,
  51 };
  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) */
  60
  61 char me[] = "ipsec rsasigkey";  /* for messages */
  62 char cop[] = "See `ipsec --copyright' for copyright information.";
  63
  64 /* forwards */
  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);
  74
  75 /*
  76  - main - mostly argument parsing
  77  */
  78 main(argc, argv)
  79 int argc;
  80 char *argv[];
  81 {
  82         int opt;
  83         extern int optind;
  84         extern char *optarg;
  85         int errflg = 0;
  86         int i;
  87         int nbits;
  88         char *oldkeyfile = NULL;
  89
  90         while ((opt = getopt_long(argc, argv, "", opts, NULL)) != EOF)
  91                 switch (opt) {
  92                 case 'v':       /* verbose description */
  93                         verbose = 1;
  94                         break;
  95                 case 'r':       /* nonstandard /dev/random */
  96                         device = optarg;
  97                         devicechanged = 1;
  98                         break;
  99                 case 'p':       /* number of prime-check rounds */
 100                         nrounds = atoi(optarg);
 101                         if (nrounds <= 0) {
 102                                 fprintf(stderr, "%s: rounds must be > 0\n", me);
 103                                 exit(2);
 104                         }
 105                         break;
 106                 case 'o':       /* reformat old key */
 107                         oldkeyfile = optarg;
 108                         break;
 109                 case 'H':       /* set hostname for output */
 110                         strcpy(outputhostname, optarg);
 111                         break;
 112                 case 'n':       /* don't optimize the private key */
 113                         do_lcm = 0;
 114                         break;
 115                 case 'h':       /* help */
 116                         printf("Usage:\t%s\n", usage);
 117                         printf("\tor\n");
 118                         printf("\t%s\n", usage2);
 119                         exit(0);
 120                         break;
 121                 case 'V':       /* version */
 122                         printf("%s %s\n", me, ipsec_version_code());
 123                         printf("%s\n", cop);
 124                         exit(0);
 125                         break;
 126                 case '?':
 127                 default:
 128                         errflg = 1;
 129                         break;
 130                 }
 131         if (errflg || optind != ((oldkeyfile != NULL) ? argc : argc-1)) {
 132                 printf("Usage:\t%s\n", usage);
 133                 printf("\tor\n");
 134                 printf("\t%s\n", usage2);
 135                 exit(2);
 136         }
 137
 138         if (outputhostname[0] == '\0') {
 139                 i = gethostname(outputhostname, sizeof(outputhostname));
 140                 if (i < 0) {
 141                         fprintf(stderr, "%s: gethostname failed (%s)\n",
 142                                                 strerror(errno));
 143                         exit(1);
 144                 }
 145         }
 146
 147         if (oldkeyfile == NULL) {
 148                 assert(argv[optind] != NULL);
 149                 nbits = atoi(argv[optind]);
 150         } else
 151                 nbits = getoldkey(oldkeyfile);
 152
 153         if (nbits <= 0) {
 154                 fprintf(stderr, "%s: invalid bit count (%d)\n", me, nbits);
 155                 exit(1);
 156         } else if (nbits > MAXBITS) {
 157                 fprintf(stderr, "%s: overlarge bit count (max %d)\n", me,
 158                                                                 MAXBITS);
 159                 exit(1);
 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);
 163                 exit(1);
 164         }
 165
 166         rsasigkey(nbits, (oldkeyfile == NULL) ? 0 : 1);
 167         exit(0);
 168 }
 169
 170 /*
 171  - getoldkey - fetch an old key's primes
 172  */
 173 int                             /* nbits */
 174 getoldkey(filename)
 175 char *filename;
 176 {
 177         FILE *f;
 178         char line[MAXBITS/2];
 179         char *p;
 180         char *value;
 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)
 186         int sawpube = 0;
 187         int sawpr1 = 0;
 188         int sawpr2 = 0;
 189         int nbits;
 190
 191         if (STREQ(filename, "-"))
 192                 f = stdin;
 193         else
 194                 f = fopen(filename, "r");
 195         if (f == NULL) {
 196                 fprintf(stderr, "%s: unable to open file `%s' (%s)\n", me,
 197                                                 filename, strerror(errno));
 198                 exit(1);
 199         }
 200         if (verbose)
 201                 fprintf(stderr, "getting old key from %s...\n", filename);
 202
 203         while (fgets(line, sizeof(line), f) != NULL) {
 204                 p = line + strlen(line) - 1;
 205                 if (*p != '\n') {
 206                         fprintf(stderr, "%s: over-long line in file `%s'\n",
 207                                                         me, filename);
 208                         exit(1);
 209                 }
 210                 *p = '\0';
 211
 212                 p = line + strspn(line, " \t");         /* p -> first word */
 213                 value = strpbrk(p, " \t");              /* value -> after it */
 214                 if (value != NULL) {
 215                         *value++ = '\0';
 216                         value += strspn(value, " \t");
 217                         /* value -> second word if any */
 218                 }
 219
 220                 if (value == NULL || *value == '\0') {
 221                         /* wrong format */
 222                 } else if (STREQ(p, pube)) {
 223                         sawpube = 1;
 224                         if (!STREQ(value, pubevalue)) {
 225                                 fprintf(stderr, "%s: wrong public exponent (`%s') in old key\n",
 226                                         me, value);
 227                                 exit(1);
 228                         }
 229                 } else if (STREQ(p, pr1)) {
 230                         if (sawpr1) {
 231                                 fprintf(stderr, "%s: duplicate `%s' lines in `%s'\n",
 232                                         me, pr1, filename);
 233                                 exit(1);
 234                         }
 235                         sawpr1 = 1;
 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",
 239                                         me);
 240                                 exit(1);
 241                         }
 242                 } else if (STREQ(p, pr2)) {
 243                         if (sawpr2) {
 244                                 fprintf(stderr, "%s: duplicate `%s' lines in `%s'\n",
 245                                         me, pr2, filename);
 246                                 exit(1);
 247                         }
 248                         sawpr2 = 1;
 249                         if (mpz_init_set_str(prime2, value, 0) < 0) {
 250                                 fprintf(stderr, "%s: conversion error in reading old prime2\n",
 251                                         me);
 252                                 exit(1);
 253                         }
 254                 }
 255         }
 256
 257         if (f != stdin)
 258                 fclose(f);
 259
 260         if (!sawpube || !sawpr1 || !sawpr2) {
 261                 fprintf(stderr, "%s: old key missing or incomplete\n", me);
 262                 exit(1);
 263         }
 264
 265         assert(sawpr1);         /* and thus nbits is known */
 266         return(nbits);
 267 }
 268
 269 /*
 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.
 274  */
 275 void
 276 rsasigkey(nbits, useoldkey)
 277 int nbits;
 278 int useoldkey;                  /* take primes from old key? */
 279 {
 280         mpz_t p;
 281         mpz_t q;
 282         mpz_t n;
 283         mpz_t e;
 284         mpz_t d;
 285         mpz_t q1;                       /* temporary */
 286         mpz_t m;                        /* internal modulus, (p-1)*(q-1) */
 287         mpz_t t;                        /* temporary */
 288         mpz_t exp1;
 289         mpz_t exp2;
 290         mpz_t coeff;
 291         char *bundp;
 292         size_t bs;
 293         char *hexp;
 294         char *b64p;
 295         int success;
 296         time_t now = time((time_t *)NULL);
 297
 298         /* the easy stuff */
 299         if (useoldkey) {
 300                 mpz_init_set(p, prime1);
 301                 mpz_init_set(q, prime2);
 302         } else {
 303                 initprime(p, nbits/2, E);
 304                 initprime(q, nbits/2, E);
 305         }
 306         mpz_init(t);
 307         if (mpz_cmp(p, q) < 0) {
 308                 report("swapping primes so p is the larger...");
 309                 mpz_set(t, p);
 310                 mpz_set(p, q);
 311                 mpz_set(q, t);
 312         }
 313         report("computing modulus...");
 314         mpz_init(n);
 315         mpz_mul(n, p, q);               /* n = p*q */
 316         mpz_init_set_ui(e, E);
 317
 318         /* internal modulus */
 319         report("computing lcm(p-1, q-1)...");
 320         mpz_init_set(m, p);
 321         mpz_sub_ui(m, m, 1);
 322         mpz_init_set(q1, q);
 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) */
 326         if (do_lcm)
 327                 mpz_divexact(m, m, t);          /* m = lcm(p-1, q-1) */
 328         mpz_gcd(t, m, e);
 329         assert(mpz_cmp_ui(t, 1) == 0);  /* m and e relatively prime */
 330
 331         /* decryption key */
 332         report("computing d...");
 333         mpz_init(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 "
 337                                                         "exponent!\n", me);
 338                 if (devicechanged)
 339                         fprintf(stderr, "\t(perhaps random bits are not very "
 340                                                                 "random?)\n");
 341                 exit(1);
 342         }
 343         if (mpz_cmp_ui(d, 0) < 0)
 344                 mpz_add(d, d, m);
 345         assert(mpz_cmp(d, m) < 0);
 346
 347         /* the speedup hacks */
 348         report("computing exp1, exp1, coeff...");
 349         mpz_init(exp1);
 350         mpz_sub_ui(t, p, 1);
 351         mpz_mod(exp1, d, t);            /* exp1 = d mod p-1 */
 352         mpz_init(exp2);
 353         mpz_sub_ui(t, q, 1);
 354         mpz_mod(exp2, d, t);            /* exp2 = d mod q-1 */
 355         mpz_init(coeff);
 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 "
 359                                                         "prime!\n", me);
 360                 if (devicechanged)
 361                         fprintf(stderr, "\t(perhaps random bits are not very "
 362                                                                 "random?)\n");
 363                 exit(1);
 364         }
 365         if (mpz_cmp_ui(coeff, 0) < 0)
 366                 mpz_add(coeff, coeff, p);
 367         assert(mpz_cmp(coeff, p) < 0);
 368
 369         /* and the output */
 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));
 389 }
 390
 391 /*
 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.
 395  */
 396 void
 397 initprime(var, nbits, eval)
 398 mpz_t var;
 399 int nbits;                      /* known to be a multiple of CHAR_BIT */
 400 int eval;                       /* value of e; 0 means don't bother w. tweak */
 401 {
 402         unsigned long tries;
 403         size_t len;
 404 #       define  OKAY(p) (eval == 0 || mpz_fdiv_ui(p, eval) != 1)
 405
 406         initrandom(var, nbits);
 407         assert(mpz_fdiv_ui(var, 2) == 1);       /* odd number */
 408
 409         report("looking for a prime starting there (can take a while)...");
 410         tries = 1;
 411         while (!( OKAY(var) && mpz_probab_prime_p(var, nrounds) )) {
 412                 mpz_add_ui(var, var, 2);
 413                 tries++;
 414         }
 415
 416         len = mpz_sizeinbase(var, 2);
 417         assert(len == nbits || len == nbits+1);
 418         if (len == nbits+1) {
 419                 report("carry out occurred (!), retrying...");
 420                 mpz_clear(var);
 421                 initprime(var, nbits, eval);
 422                 return;
 423         }
 424         if (verbose)
 425                 fprintf(stderr, "found it after %lu tries.\n", tries);
 426 }
 427
 428 /*
 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.
 433  */
 434 void
 435 initrandom(var, nbits)
 436 mpz_t var;
 437 int nbits;                      /* known to be a multiple of CHAR_BIT */
 438 {
 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);
 443
 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);
 450                 exit(1);
 451         }
 452         if (mpz_init_set_str(var, hexbuf, 0) < 0) {
 453                 fprintf(stderr, "%s: can't-happen hex conversion error\n", me);
 454                 exit(1);
 455         }
 456 }
 457
 458 /*
 459  - getrandom - get some random bytes from /dev/random (or wherever)
 460  */
 461 void
 462 getrandom(nbytes, buf)
 463 size_t nbytes;
 464 char *buf;                      /* known to be big enough */
 465 {
 466         size_t ndone;
 467         int dev;
 468         size_t got;
 469
 470         dev = open(device, 0);
 471         if (dev < 0) {
 472                 fprintf(stderr, "%s: could not open %s (%s)\n", me,
 473                                                 device, strerror(errno));
 474                 exit(1);
 475         }
 476
 477         ndone = 0;
 478         if (verbose)
 479                 fprintf(stderr, "getting %d random bytes from %s...\n", nbytes,
 480                                                                 device);
 481         while (ndone < nbytes) {
 482                 got = read(dev, buf + ndone, nbytes - ndone);
 483                 if (got < 0) {
 484                         fprintf(stderr, "%s: read error on %s (%s)\n", me,
 485                                                 device, strerror(errno));
 486                         exit(1);
 487                 }
 488                 if (got == 0) {
 489                         fprintf(stderr, "%s: eof on %s!?!\n", me, device);
 490                         exit(1);
 491                 }
 492                 ndone += got;
 493         }
 494
 495         close(dev);
 496 }
 497
 498 /*
 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.)
 502  */
 503 char *                          /* pointer to static buffer (ick) */
 504 hexout(var)
 505 mpz_t var;
 506 {
 507         static char hexbuf[3 + MAXBITS/4 + 1];
 508         char *hexp;
 509
 510         mpz_get_str(hexbuf+3, 16, var);
 511         if (strlen(hexbuf+3)%2 == 0)    /* even number of hex digits */
 512                 hexp = hexbuf+1;
 513         else {                          /* odd, must pad */
 514                 hexp = hexbuf;
 515                 hexp[2] = '0';
 516         }
 517         hexp[0] = '0';
 518         hexp[1] = 'x';
 519
 520         return hexp;
 521 }
 522
 523 /*
 524  - bundle - bundle e and n into an RFC2537-format lump
 525  * Note, calls hexout.
 526  */
 527 char *                          /* pointer to static buffer (ick) */
 528 bundle(e, n, sizep)
 529 int e;
 530 mpz_t n;
 531 size_t *sizep;
 532 {
 533         char *hexp = hexout(n);
 534         static char bundbuf[2 + MAXBITS/8];
 535         const char *er;
 536         size_t size;
 537
 538         assert(e <= 255);
 539         bundbuf[0] = 1;
 540         bundbuf[1] = e;
 541         er = ttodata(hexp, 0, 0, bundbuf+2, sizeof(bundbuf)-2, &size);
 542         if (er != NULL) {
 543                 fprintf(stderr, "%s: can't-happen bundle convert error `%s'\n",
 544                                                                 me, er);
 545                 exit(1);
 546         }
 547         if (size > sizeof(bundbuf)-2) {
 548                 fprintf(stderr, "%s: can't-happen bundle overflow (need %u)\n",
 549                                                                 me, size);
 550                 exit(1);
 551         }
 552         if (sizep != NULL)
 553                 *sizep = size + 2;
 554         return bundbuf;
 555 }
 556
 557 /*
 558  - conv - convert bits to output in specified format
 559  */
 560 char *                          /* pointer to static buffer (ick) */
 561 conv(bits, nbytes, format)
 562 char *bits;
 563 size_t nbytes;
 564 int format;                     /* datatot() code */
 565 {
 566         static char convbuf[MAXBITS/4 + 50];    /* enough for hex */
 567         size_t n;
 568
 569         n = datatot(bits, nbytes, format, convbuf, sizeof(convbuf));
 570         if (n == 0) {
 571                 fprintf(stderr, "%s: can't-happen convert error\n", me);
 572                 exit(1);
 573         }
 574         if (n > sizeof(convbuf)) {
 575                 fprintf(stderr, "%s: can't-happen convert overflow (need %u)\n",
 576                                                                 me, n);
 577                 exit(1);
 578         }
 579         return convbuf;
 580 }
 581
 582 /*
 583  - report - report progress, if indicated
 584  */
 585 void
 586 report(msg)
 587 char *msg;
 588 {
 589         if (!verbose)
 590                 return;
 591         fprintf(stderr, "%s\n", msg);
 592 }