Logo Search packages:      
Sourcecode: strongswan version File versions  Download package

rsasigkey.c

/*
 * RSA signature key generation
 * Copyright (C) 1999, 2000, 2001  Henry Spencer.
 * 
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation; either version 2 of the License, or (at your
 * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
 * 
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * for more details.
 *
 * RCSID $Id: rsasigkey.c,v 1.2 2005/08/11 10:35:58 as Exp $
 */

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
#include <time.h>
#include <limits.h>
#include <errno.h>
#include <string.h>
#include <assert.h>
#include <getopt.h>
#include <freeswan.h>
#include "gmp.h"

#ifndef DEVICE
#define     DEVICE      "/dev/random"
#endif
#ifndef MAXBITS
#define     MAXBITS     20000
#endif

/* the code in getoldkey() knows about this */
#define     E     3           /* standard public exponent */

char usage[] = "rsasigkey [--verbose] [--random device] nbits";
char usage2[] = "rsasigkey [--verbose] --oldkey filename";
struct option opts[] = {
  {"verbose",     0,    NULL, 'v',},
  {"random",      1,    NULL, 'r',},
  {"rounds",      1,    NULL, 'p',},
  {"oldkey",      1,    NULL, 'o',},
  {"hostname",    1,    NULL, 'H',},
  {"noopt", 0,    NULL, 'n',},
  {"help",  0,    NULL, 'h',},
  {"version",     0,    NULL, 'V',},
  {0,       0,    NULL, 0,}
};
int verbose = 0;        /* narrate the action? */
char *device = DEVICE;        /* where to get randomness */
int nrounds = 30;       /* rounds of prime checking; 25 is good */
mpz_t prime1;                 /* old key's prime1 */
mpz_t prime2;                 /* old key's prime2 */
char outputhostname[1024];    /* hostname for output */
int do_lcm = 1;               /* use lcm(p-1, q-1), not (p-1)*(q-1) */

char me[] = "ipsec rsasigkey";      /* for messages */

/* forwards */
int getoldkey(char *filename);
void rsasigkey(int nbits, int useoldkey);
void initprime(mpz_t var, int nbits, int eval);
void initrandom(mpz_t var, int nbits);
void getrandom(size_t nbytes, char *buf);
char *bundle(int e, mpz_t n, size_t *sizep);
char *conv(char *bits, size_t nbytes, int format);
char *hexout(mpz_t var);
void report(char *msg);

/*
 - main - mostly argument parsing
 */
int main(int argc, char *argv[])
{
      int opt;
      extern int optind;
      extern char *optarg;
      int errflg = 0;
      int i;
      int nbits;
      char *oldkeyfile = NULL;

      while ((opt = getopt_long(argc, argv, "", opts, NULL)) != EOF)
            switch (opt) {
            case 'v':   /* verbose description */
                  verbose = 1;
                  break;
            case 'r':   /* nonstandard /dev/random */
                  device = optarg;
                  break;
            case 'p':   /* number of prime-check rounds */
                  nrounds = atoi(optarg);
                  if (nrounds <= 0) {
                        fprintf(stderr, "%s: rounds must be > 0\n", me);
                        exit(2);
                  }
                  break;
            case 'o':   /* reformat old key */
                  oldkeyfile = optarg;
                  break;
            case 'H':   /* set hostname for output */
                  strcpy(outputhostname, optarg);
                  break;
            case 'n':   /* don't optimize the private key */
                  do_lcm = 0;
                  break;
            case 'h':   /* help */
                  printf("Usage:\t%s\n", usage);
                  printf("\tor\n");
                  printf("\t%s\n", usage2);
                  exit(0);
                  break;
            case 'V':   /* version */
                  printf("%s %s\n", me, ipsec_version_code());
                  exit(0);
                  break;
            case '?':
            default:
                  errflg = 1;
                  break;
            }
      if (errflg || optind != ((oldkeyfile != NULL) ? argc : argc-1)) {
            printf("Usage:\t%s\n", usage);
            printf("\tor\n");
            printf("\t%s\n", usage2);
            exit(2);
      }

      if (outputhostname[0] == '\0') {
            i = gethostname(outputhostname, sizeof(outputhostname));
            if (i < 0) {
                  fprintf(stderr, "%s: gethostname failed (%s)\n",
                        me,
                        strerror(errno));
                  exit(1);
            }
      }

      if (oldkeyfile == NULL) {
            assert(argv[optind] != NULL);
            nbits = atoi(argv[optind]);
      } else
            nbits = getoldkey(oldkeyfile);

      if (nbits <= 0) {
            fprintf(stderr, "%s: invalid bit count (%d)\n", me, nbits);
            exit(1);
      } else if (nbits > MAXBITS) {
            fprintf(stderr, "%s: overlarge bit count (max %d)\n", me,
                                                MAXBITS);
            exit(1);
      } else if (nbits % (CHAR_BIT*2) != 0) {   /* *2 for nbits/2-bit primes */
            fprintf(stderr, "%s: bit count (%d) not multiple of %d\n", me,
                                    nbits, (int)CHAR_BIT*2);
            exit(1);
      }

      rsasigkey(nbits, (oldkeyfile == NULL) ? 0 : 1);
      exit(0);
}

/*
 - getoldkey - fetch an old key's primes
 */
int                     /* nbits */
getoldkey(filename)
char *filename;
{
      FILE *f;
      char line[MAXBITS/2];
      char *p;
      char *value;
      static char pube[] = "PublicExponent:";
      static char pubevalue[] = "0x03";
      static char pr1[] = "Prime1:";
      static char pr2[] = "Prime2:";
#     define      STREQ(a, b) (strcmp(a, b) == 0)
      int sawpube = 0;
      int sawpr1 = 0;
      int sawpr2 = 0;
      int nbits;

      nbits = 0;
 
      if (STREQ(filename, "-"))
            f = stdin;
      else
            f = fopen(filename, "r");
      if (f == NULL) {
            fprintf(stderr, "%s: unable to open file `%s' (%s)\n", me,
                                    filename, strerror(errno));
            exit(1);
      }
      if (verbose)
            fprintf(stderr, "getting old key from %s...\n", filename);

      while (fgets(line, sizeof(line), f) != NULL) {
            p = line + strlen(line) - 1;
            if (*p != '\n') {
                  fprintf(stderr, "%s: over-long line in file `%s'\n",
                                          me, filename);
                  exit(1);
            }
            *p = '\0';

            p = line + strspn(line, " \t");           /* p -> first word */
            value = strpbrk(p, " \t");          /* value -> after it */
            if (value != NULL) {
                  *value++ = '\0';
                  value += strspn(value, " \t");
                  /* value -> second word if any */
            }

            if (value == NULL || *value == '\0') {
                  /* wrong format */
            } else if (STREQ(p, pube)) {
                  sawpube = 1;
                  if (!STREQ(value, pubevalue)) {
                        fprintf(stderr, "%s: wrong public exponent (`%s') in old key\n",
                              me, value);
                        exit(1);
                  }
            } else if (STREQ(p, pr1)) {
                  if (sawpr1) {
                        fprintf(stderr, "%s: duplicate `%s' lines in `%s'\n",
                              me, pr1, filename);
                        exit(1);
                  }
                  sawpr1 = 1;
                  nbits = (strlen(value) - 2) * 4 * 2;
                  if (mpz_init_set_str(prime1, value, 0) < 0) {
                        fprintf(stderr, "%s: conversion error in reading old prime1\n",
                              me);
                        exit(1);
                  }
            } else if (STREQ(p, pr2)) {
                  if (sawpr2) {
                        fprintf(stderr, "%s: duplicate `%s' lines in `%s'\n",
                              me, pr2, filename);
                        exit(1);
                  }
                  sawpr2 = 1;
                  if (mpz_init_set_str(prime2, value, 0) < 0) {
                        fprintf(stderr, "%s: conversion error in reading old prime2\n",
                              me);
                        exit(1);
                  }
            }
      }
      
      if (f != stdin)
            fclose(f);

      if (!sawpube || !sawpr1 || !sawpr2) {
            fprintf(stderr, "%s: old key missing or incomplete\n", me);
            exit(1);
      }

      assert(sawpr1);         /* and thus nbits is known */
      return(nbits);
}

/*
 - rsasigkey - generate an RSA signature key
 * e is fixed at 3, without discussion.  That would not be wise if these
 * keys were to be used for encryption, but for signatures there are some
 * real speed advantages.
 */
void
rsasigkey(nbits, useoldkey)
int nbits;
int useoldkey;                /* take primes from old key? */
{
      mpz_t p;
      mpz_t q;
      mpz_t n;
      mpz_t e;
      mpz_t d;
      mpz_t q1;               /* temporary */
      mpz_t m;                /* internal modulus, (p-1)*(q-1) */
      mpz_t t;                /* temporary */
      mpz_t exp1;
      mpz_t exp2;
      mpz_t coeff;
      char *bundp;
      size_t bs;
      int success;
      time_t now = time((time_t *)NULL);

      /* the easy stuff */
      if (useoldkey) {
            mpz_init_set(p, prime1);
            mpz_init_set(q, prime2);
      } else {
            initprime(p, nbits/2, E);
            initprime(q, nbits/2, E);
      }
      mpz_init(t);
      if (mpz_cmp(p, q) < 0) {
            report("swapping primes so p is the larger...");
            mpz_set(t, p);
            mpz_set(p, q);
            mpz_set(q, t);
      }
      report("computing modulus...");
      mpz_init(n);
      mpz_mul(n, p, q);       /* n = p*q */
      mpz_init_set_ui(e, E);

      /* internal modulus */
      report("computing lcm(p-1, q-1)...");
      mpz_init_set(m, p);
      mpz_sub_ui(m, m, 1);
      mpz_init_set(q1, q);
      mpz_sub_ui(q1, q1, 1);
      mpz_gcd(t, m, q1);            /* t = gcd(p-1, q-1) */
      mpz_mul(m, m, q1);            /* m = (p-1)*(q-1) */
      if (do_lcm)
            mpz_divexact(m, m, t);        /* m = lcm(p-1, q-1) */
      mpz_gcd(t, m, e);
      assert(mpz_cmp_ui(t, 1) == 0);      /* m and e relatively prime */

      /* decryption key */
      report("computing d...");
      mpz_init(d);
      success = mpz_invert(d, e, m);
      assert(success);        /* e has an inverse mod m */
      if (mpz_cmp_ui(d, 0) < 0)
            mpz_add(d, d, m);
      assert(mpz_cmp(d, m) < 0);

      /* the speedup hacks */
      report("computing exp1, exp1, coeff...");
      mpz_init(exp1);
      mpz_sub_ui(t, p, 1);
      mpz_mod(exp1, d, t);          /* exp1 = d mod p-1 */
      mpz_init(exp2);
      mpz_sub_ui(t, q, 1);
      mpz_mod(exp2, d, t);          /* exp2 = d mod q-1 */
      mpz_init(coeff);
      mpz_invert(coeff, q, p);      /* coeff = q^-1 mod p */
      if (mpz_cmp_ui(coeff, 0) < 0)
            mpz_add(coeff, coeff, p);
      assert(mpz_cmp(coeff, p) < 0);

      /* and the output */
      /* note, getoldkey() knows about some of this */
      report("output...\n");        /* deliberate extra newline */
      printf("\t# RSA %d bits   %s   %s", nbits, outputhostname, ctime(&now));
                                          /* ctime provides \n */
      printf("\t# for signatures only, UNSAFE FOR ENCRYPTION\n");
      bundp = bundle(E, n, &bs);
      printf("\t#pubkey=%s\n", conv(bundp, bs, 's')); /* RFC2537ish format */
      printf("\tModulus: %s\n", hexout(n));
      printf("\tPublicExponent: %s\n", hexout(e));
      printf("\t# everything after this point is secret\n");
      printf("\tPrivateExponent: %s\n", hexout(d));
      printf("\tPrime1: %s\n", hexout(p));
      printf("\tPrime2: %s\n", hexout(q));
      printf("\tExponent1: %s\n", hexout(exp1));
      printf("\tExponent2: %s\n", hexout(exp2));
      printf("\tCoefficient: %s\n", hexout(coeff));
}

/*
 - initprime - initialize an mpz_t to a random prime of specified size
 * Efficiency tweak:  we reject candidates that are 1 higher than a multiple
 * of e, since they will make the internal modulus not relatively prime to e.
 */
void
initprime(var, nbits, eval)
mpz_t var;
int nbits;              /* known to be a multiple of CHAR_BIT */
int eval;               /* value of e; 0 means don't bother w. tweak */
{
      unsigned long tries;
      size_t len;
#     define      OKAY(p)     (eval == 0 || mpz_fdiv_ui(p, eval) != 1)

      initrandom(var, nbits);
      assert(mpz_fdiv_ui(var, 2) == 1);   /* odd number */

      report("looking for a prime starting there (can take a while)...");
      tries = 1;
      while (!( OKAY(var) && mpz_probab_prime_p(var, nrounds) )) {
            mpz_add_ui(var, var, 2);
            tries++;
      }

      len = mpz_sizeinbase(var, 2);
      assert(len == (size_t)nbits || len == (size_t)(nbits+1));
      if (len == (size_t)(nbits+1)) {
            report("carry out occurred (!), retrying...");
            mpz_clear(var);
            initprime(var, nbits, eval);
            return;
      }
      if (verbose)
            fprintf(stderr, "found it after %lu tries.\n", tries);
}

/*
 - initrandom - initialize an mpz_t to a random number, specified bit count
 * Converting via hex is a bit weird, but it's the best route GMP gives us.
 * Note that highmost and lowmost bits are forced on -- highmost to give a
 * number of exactly the specified length, lowmost so it is an odd number.
 */
void
initrandom(var, nbits)
mpz_t var;
int nbits;              /* known to be a multiple of CHAR_BIT */
{
      size_t nbytes = (size_t)(nbits / CHAR_BIT);
      static char bitbuf[MAXBITS/CHAR_BIT];
      static char hexbuf[2 + MAXBITS/4 + 1];
      size_t hsize = sizeof(hexbuf);

      assert(nbytes <= sizeof(bitbuf));
      getrandom(nbytes, bitbuf);
      bitbuf[0] |= 01 << (CHAR_BIT-1);    /* force high bit on */
      bitbuf[nbytes-1] |= 01;             /* force low bit on */
      if (datatot(bitbuf, nbytes, 'x', hexbuf, hsize) > hsize) {
            fprintf(stderr, "%s: can't-happen buffer overflow\n", me);
            exit(1);
      }
      if (mpz_init_set_str(var, hexbuf, 0) < 0) {
            fprintf(stderr, "%s: can't-happen hex conversion error\n", me);
            exit(1);
      }
}

/*
 - getrandom - get some random bytes from /dev/random (or wherever)
 */
void
getrandom(nbytes, buf)
size_t nbytes;
char *buf;              /* known to be big enough */
{
      size_t ndone;
      int dev;
      size_t got;

      dev = open(device, 0);
      if (dev < 0) {
            fprintf(stderr, "%s: could not open %s (%s)\n", me,
                                    device, strerror(errno));
            exit(1);
      }

      ndone = 0;
      if (verbose)
            fprintf(stderr, "getting %d random bytes from %s...\n", (int) nbytes,
                                          device);
      while (ndone < nbytes) {
            got = read(dev, buf + ndone, nbytes - ndone);
            if (got < 0) {
                  fprintf(stderr, "%s: read error on %s (%s)\n", me,
                                    device, strerror(errno));
                  exit(1);
            }
            if (got == 0) {
                  fprintf(stderr, "%s: eof on %s!?!\n", me, device);
                  exit(1);
            }
            ndone += got;
      }

      close(dev);
}

/*
 - hexout - prepare hex output, guaranteeing even number of digits
 * (The current FreeS/WAN conversion routines want an even digit count,
 * but mpz_get_str doesn't promise one.)
 */
char *                        /* pointer to static buffer (ick) */
hexout(var)
mpz_t var;
{
      static char hexbuf[3 + MAXBITS/4 + 1];
      char *hexp;

      mpz_get_str(hexbuf+3, 16, var);
      if (strlen(hexbuf+3)%2 == 0)  /* even number of hex digits */
            hexp = hexbuf+1;
      else {                        /* odd, must pad */
            hexp = hexbuf;
            hexp[2] = '0';
      }
      hexp[0] = '0';
      hexp[1] = 'x';

      return hexp;
}

/*
 - bundle - bundle e and n into an RFC2537-format lump
 * Note, calls hexout.
 */
char *                        /* pointer to static buffer (ick) */
bundle(e, n, sizep)
int e;
mpz_t n;
size_t *sizep;
{
      char *hexp = hexout(n);
      static char bundbuf[2 + MAXBITS/8];
      const char *er;
      size_t size;

      assert(e <= 255);
      bundbuf[0] = 1;
      bundbuf[1] = e;
      er = ttodata(hexp, 0, 0, bundbuf+2, sizeof(bundbuf)-2, &size);
      if (er != NULL) {
            fprintf(stderr, "%s: can't-happen bundle convert error `%s'\n",
                                                me, er);
            exit(1);
      }
      if (size > sizeof(bundbuf)-2) {
            fprintf(stderr, "%s: can't-happen bundle overflow (need %d)\n",
                                                me, (int) size);
            exit(1);
      }
      if (sizep != NULL)
            *sizep = size + 2;
      return bundbuf;
}

/*
 - conv - convert bits to output in specified format
 */
char *                        /* pointer to static buffer (ick) */
conv(bits, nbytes, format)
char *bits;
size_t nbytes;
int format;             /* datatot() code */
{
      static char convbuf[MAXBITS/4 + 50];      /* enough for hex */
      size_t n;

      n = datatot(bits, nbytes, format, convbuf, sizeof(convbuf));
      if (n == 0) {
            fprintf(stderr, "%s: can't-happen convert error\n", me);
            exit(1);
      }
      if (n > sizeof(convbuf)) {
            fprintf(stderr, "%s: can't-happen convert overflow (need %d)\n",
                                                me, (int) n);
            exit(1);
      }
      return convbuf;
}

/*
 - report - report progress, if indicated
 */
void
report(msg)
char *msg;
{
      if (!verbose)
            return;
      fprintf(stderr, "%s\n", msg);
}

Generated by  Doxygen 1.6.0   Back to index