src/scepclient/rsakey.c

   1 /**
   2  * @file rsakey.c
   3  * @brief Functions for RSA key generation
   4  */
   5
   6 /*
   7  * Copyright (C) 1999, 2000, 2001  Henry Spencer.
   8  * Copyright (C) 2005 Jan Hutter, Martin Willi
   9  * Hochschule fuer Technik Rapperswil
  10  *
  11  * This program is free software; you can redistribute it and/or modify it
  12  * under the terms of the GNU General Public License as published by the
  13  * Free Software Foundation; either version 2 of the License, or (at your
  14  * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
  15  *
  16  * This program is distributed in the hope that it will be useful, but
  17  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  18  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  19  * for more details.
  20  *
  21  * $Id: rsakey.c,v 1.5 2006/01/04 21:16:30 as Exp $
  22  */
  23
  24
  25 #include <stdlib.h>
  26 #include <sys/types.h>
  27 #include <sys/stat.h>
  28 #include <fcntl.h>
  29 #include <unistd.h>
  30 #include <assert.h>
  31 #include <gmp.h>
  32
  33 #include <freeswan.h>
  34
  35 #include "../pluto/constants.h"
  36 #include "../pluto/defs.h"
  37 #include "../pluto/mp_defs.h"
  38 #include "../pluto/log.h"
  39 #include "../pluto/pkcs1.h"
  40
  41 #include "rsakey.h"
  42
  43 /* Number of times the probabilistic primality test is applied */
  44 #define PRIMECHECK_ROUNDS       30
  45
  46 /* Public exponent used for signature key generation */
  47 #define PUBLIC_EXPONENT         0x10001
  48
  49 #ifndef DEV_RANDOM
  50 #define DEV_RANDOM      "/dev/random"
  51 #endif
  52
  53
  54 /**
  55  * @brief Reads a specific number of bytes from a given device/file
  56  *
  57  * @param[in]           nbytes          number of bytes to read from random device
  58  * @param[out]          buf             pointer to buffer where to write the data in.
  59  *                                      size of buffer has to be at least nbytes.
  60  * @return                              TRUE, if succeeded, FALSE otherwise
  61  */
  62
  63 static bool
  64 get_true_random_bytes(size_t nbytes, char *buf)
  65 {
  66         size_t ndone;
  67         size_t got;
  68         char *device = DEV_RANDOM;
  69
  70         int dev = open(DEV_RANDOM, 0);
  71
  72         if (dev < 0)
  73         {
  74                 fprintf(stderr, "could not open random device %s", device);
  75                 return FALSE;
  76         }
  77
  78         DBG(DBG_CONTROL,
  79                 DBG_log("getting %d bytes from %s...", (int) nbytes, device)
  80         )
  81
  82         ndone = 0;
  83         while (ndone < nbytes)
  84         {
  85                 got = read(dev, buf + ndone, nbytes - ndone);
  86                 if (got < 0)
  87                 {
  88                         fprintf(stderr, "read error on %s", device);
  89                         return FALSE;
  90                 }
  91                 if (got == 0)
  92                 {
  93                         fprintf(stderr, "eof on %s", device);
  94                         return FALSE;
  95                 }
  96                  ndone += got;
  97         }
  98         close(dev);
  99         return TRUE;
 100 }
 101
 102 /**
 103  * @brief initialize an mpz_t to a random number, specified bit count
 104  *
 105  * Converting the random value in a value of type mpz_t is done
 106  * by creating a hexbuffer.
 107  * Converting via hex is a bit weird, but it's the best route GMP gives us.
 108  * Note that highmost and lowmost bits are forced on -- highmost to give a
 109  * number of exactly the specified length, lowmost so it is an odd number.
 110  *
 111  * @param[out]  var uninitialized mpz_t to store th random number in
 112  * @param[in]   nbits length of var in bits (known to be a multiple of BITS_PER_BYTE)
 113  * @return      TRUE on success, FALSE otherwise
 114  */
 115 static bool
 116 init_random(mpz_t var, int nbits)
 117 {
 118         size_t nbytes = (size_t)(nbits/BITS_PER_BYTE);
 119         char random_buf[RSA_MAX_OCTETS/2];
 120
 121         assert(nbytes <= sizeof(random_buf));
 122
 123         if (!get_true_random_bytes(nbytes, random_buf))
 124                 return FALSE;
 125
 126         random_buf[0] |= 01 << (BITS_PER_BYTE-1);   /* force high bit on */
 127         random_buf[nbytes-1] |= 01;                 /* force low bit on */
 128         n_to_mpz(var, random_buf, nbytes);
 129         return TRUE;
 130 }
 131
 132 /**
 133  * @brief initialize an mpz_t to a random prime of specified size
 134  *
 135  * Efficiency tweak: we reject candidates that are 1 higher than a multiple
 136  * of e, since they will make the internal modulus not relatively prime to e.
 137  *
 138  * @param[out]  var mpz_t variable to initialize
 139  * @param[in]   nbits length of given prime in bits (known to be a multiple of BITS_PER_BYTE)
 140  * @param[in]   eval E-Value, 0 means don't bother w. tweak
 141  * @return              1 on success, 0 otherwise
 142  */
 143 static bool
 144 init_prime(mpz_t var, int nbits, int eval)
 145 {
 146         unsigned long tries;
 147         size_t len;
 148
 149         /* get a random value of nbits length */
 150         if (!init_random(var, nbits))
 151                 return FALSE;
 152
 153         /* check if odd number */
 154         assert(mpz_fdiv_ui(var, 2) == 1);
 155         DBG(DBG_CONTROLMORE,
 156                 DBG_log("looking for a prime starting there (can take a while)...")
 157         )
 158
 159         tries = 1;
 160         while (mpz_fdiv_ui(var, eval) == 1
 161            || !mpz_probab_prime_p(var, PRIMECHECK_ROUNDS))
 162         {
 163                 /* not a prime, increase by 2 */
 164                 mpz_add_ui(var, var, 2);
 165                 tries++;
 166         }
 167
 168         len = mpz_sizeinbase(var, 2);
 169
 170         /* check bit length of primee */
 171         assert(len == (size_t)nbits || len == (size_t)(nbits+1));
 172
 173         if (len == (size_t)(nbits+1))
 174         {
 175                 DBG(DBG_CONTROLMORE,
 176                         DBG_log("carry out occurred (!), retrying...")
 177                 )
 178                 mpz_clear(var);
 179                 /* recursive call */
 180                 return init_prime(var, nbits, eval);
 181         }
 182         DBG(DBG_CONTROLMORE,
 183                 DBG_log("found it after %lu tries.",tries)
 184         )
 185         return TRUE;
 186 }
 187
 188 /**
 189  * @brief Generate a RSA key usable for encryption
 190  *
 191  * Generate an RSA key usable for encryption. All the
 192  * values of the RSA key are filled into mpz_t parameters.
 193  * These mpz_t parameters must not be initialized and have
 194  * to be cleared with mpz_clear after using.
 195  *
 196  * @param[in]   nbits size of rsa key in bits
 197  * @return      RSA_public_key_t containing the generated RSA key
 198  */
 199 err_t
 200 generate_rsa_private_key(int nbits, RSA_private_key_t *key)
 201 {
 202         mpz_t p, q, n, e, d, exp1, exp2, coeff;
 203         mpz_t m, q1, t;     /* temporary variables*/
 204
 205          DBG(DBG_CONTROL,
 206                 DBG_log("generating %d bit RSA key:", nbits)
 207         )
 208
 209         if (nbits <= 0)
 210                 return "negative rsa key length!";
 211
 212         /* Get values of primes p and q */
 213         DBG(DBG_CONTROLMORE,
 214                 DBG_log("initialize prime p")
 215         )
 216         if (!init_prime(p, nbits/2, PUBLIC_EXPONENT))
 217                 return "could not generate prime p";
 218
 219         DBG(DBG_CONTROLMORE,
 220                 DBG_log("initialize prime q")
 221         )
 222         if (!init_prime(q, nbits/2, PUBLIC_EXPONENT))
 223                 return "could not generate prime q";
 224
 225         mpz_init(t);
 226
 227         /* Swapping primes so p is larger then q */
 228         if (mpz_cmp(p, q) < 0)
 229         {
 230                 DBG(DBG_CONTROLMORE,
 231                         DBG_log("swapping primes so p is the larger...")
 232                 );
 233                 mpz_set(t, p);
 234                 mpz_set(p, q);
 235                 mpz_set(q, t);
 236         }
 237
 238         DBG(DBG_CONTROLMORE,
 239                 DBG_log("computing modulus...")
 240         )
 241         mpz_init(n);
 242         /* n = p*q */
 243         mpz_mul(n, p, q);
 244
 245         /* Assign e the value of defined PUBLIC_EXPONENT */
 246         mpz_init_set_ui(e, PUBLIC_EXPONENT);
 247
 248         DBG(DBG_CONTROLMORE,
 249                 DBG_log("computing lcm(p-1, q-1)...")
 250         )
 251         /* m = p */
 252         mpz_init_set(m, p);
 253         /* m = m-1 */
 254         mpz_sub_ui(m, m, 1);
 255         /* q1 = q */
 256         mpz_init_set(q1, q);
 257         /* q1 = q1-1 */
 258         mpz_sub_ui(q1, q1, 1);
 259         /* t = gcd(p-1, q-1) */
 260         mpz_gcd(t, m, q1);
 261         /* m = (p-1)*(q-1) */
 262         mpz_mul(m, m, q1);
 263         /* m = m / t */
 264         mpz_divexact(m, m, t);
 265         /* t = gcd(m, e) (greatest common divisor) */
 266         mpz_gcd(t, m, e);
 267         /* m and e relatively prime */
 268         assert(mpz_cmp_ui(t, 1) == 0);
 269
 270         /* decryption key */
 271         DBG(DBG_CONTROLMORE,
 272                 DBG_log("computing d...")
 273         )
 274         mpz_init(d);
 275         /* e has an inverse mod m */
 276         assert(mpz_invert(d, e, m));
 277
 278         /* make sure d is positive */
 279         if (mpz_cmp_ui(d, 0) < 0)
 280                 mpz_add(d, d, m);
 281
 282         /* d has to be positive */
 283         assert(mpz_cmp(d, m) < 0);
 284
 285         /* the speedup hacks */
 286         DBG(DBG_CONTROLMORE,
 287                 DBG_log("computing exp1, exp1, coeff...")
 288         )
 289         mpz_init(exp1);
 290         /* t = p-1 */
 291         mpz_sub_ui(t, p, 1);
 292         /* exp1 = d mod p-1 */
 293         mpz_mod(exp1, d, t);
 294
 295         mpz_init(exp2);
 296         /* t = q-1 */
 297         mpz_sub_ui(t, q, 1);
 298         /* exp2 = d mod q-1 */
 299         mpz_mod(exp2, d, t);
 300
 301         mpz_init(coeff);
 302         /* coeff = q^-1 mod p */
 303         mpz_invert(coeff, q, p);
 304
 305         /* make sure coeff is positive */
 306         if (mpz_cmp_ui(coeff, 0) < 0)
 307                 mpz_add(coeff, coeff, p);
 308
 309         /* coeff has to be positive */
 310         assert(mpz_cmp(coeff, p) < 0);
 311
 312         /* Clear temporary variables */
 313                 mpz_clear(q1);
 314                 mpz_clear(m);
 315                 mpz_clear(t);
 316
 317         /* form FreeS/WAN keyid */
 318         {
 319                 size_t e_len = (mpz_sizeinbase(e,2)+BITS_PER_BYTE-1)/BITS_PER_BYTE;
 320                 size_t n_len = (mpz_sizeinbase(n,2)+BITS_PER_BYTE-1)/BITS_PER_BYTE;
 321                 chunk_t e_ch = mpz_to_n(e, e_len);
 322                 chunk_t n_ch = mpz_to_n(n, n_len);
 323
 324                 form_keyid(e_ch, n_ch, key->pub.keyid, &key->pub.k);
 325                 free(e_ch.ptr);
 326                 free(n_ch.ptr);
 327         }
 328
 329         /* fill in the elements of the RSA private key */
 330         key->p = *p;
 331         key->q = *q;
 332         key->pub.n = *n;
 333         key->pub.e = *e;
 334         key->d = *d;
 335         key->dP = *exp1;
 336         key->dQ = *exp2;
 337         key->qInv = *coeff;
 338
 339         DBG(DBG_CONTROL,
 340                 DBG_log("RSA key *%s generated with %d bits", key->pub.keyid
 341                         , (int)mpz_sizeinbase(n,2))
 342         )
 343
 344 #ifdef DEBUG
 345         DBG(DBG_PRIVATE,
 346                 RSA_show_private_key(key)
 347         )
 348 #endif
 349         return NULL;
 350 }