polly/lib/External/isl/imath/examples/rsakey.c

   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
  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
 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
 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
 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
 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
 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
 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 */