rsa-keygen.c

   1 /* rsa-keygen.c
   2  *
   3  * Generation of RSA keypairs
   4  */
   5
   6 /* nettle, low-level cryptographics library
   7  *
   8  * Copyright (C) 2002 Niels Möller
   9  *
  10  * The nettle library is free software; you can redistribute it and/or modify
  11  * it under the terms of the GNU Lesser General Public License as published by
  12  * the Free Software Foundation; either version 2.1 of the License, or (at your
  13  * option) any later version.
  14  *
  15  * The nettle library is distributed in the hope that it will be useful, but
  16  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  17  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  18  * License for more details.
  19  *
  20  * You should have received a copy of the GNU Lesser General Public License
  21  * along with the nettle library; see the file COPYING.LIB.  If not, write to
  22  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  23  * MA 02111-1301, USA.
  24  */
  25
  26 #if HAVE_CONFIG_H
  27 # include "config.h"
  28 #endif
  29
  30 #include <assert.h>
  31 #include <stdlib.h>
  32
  33 #include "rsa.h"
  34 #include "bignum.h"
  35
  36 #ifndef DEBUG
  37 # define DEBUG 0
  38 #endif
  39
  40 #if DEBUG
  41 # include <stdio.h>
  42 #endif
  43
  44
  45 int
  46 rsa_generate_keypair(struct rsa_public_key *pub,
  47                      struct rsa_private_key *key,
  48                      void *random_ctx, nettle_random_func *random,
  49                      void *progress_ctx, nettle_progress_func *progress,
  50                      unsigned n_size,
  51                      unsigned e_size)
  52 {
  53   mpz_t p1;
  54   mpz_t q1;
  55   mpz_t phi;
  56   mpz_t tmp;
  57
  58   if (e_size)
  59     {
  60       /* We should choose e randomly. Is the size reasonable? */
  61       if ((e_size < 16) || (e_size >= n_size) )
  62         return 0;
  63     }
  64   else
  65     {
  66       /* We have a fixed e. Check that it makes sense */
  67
  68       /* It must be odd */
  69       if (!mpz_tstbit(pub->e, 0))
  70         return 0;
  71
  72       /* And 3 or larger */
  73       if (mpz_cmp_ui(pub->e, 3) < 0)
  74         return 0;
  75
  76       /* And size less than n */
  77       if (mpz_sizeinbase(pub->e, 2) >= n_size)
  78         return 0;
  79     }
  80
  81   if (n_size < RSA_MINIMUM_N_BITS)
  82     return 0;
  83
  84   mpz_init(p1); mpz_init(q1); mpz_init(phi); mpz_init(tmp);
  85
  86   /* Generate primes */
  87   for (;;)
  88     {
  89       /* Generate p, such that gcd(p-1, e) = 1 */
  90       for (;;)
  91         {
  92           nettle_random_prime(key->p, (n_size+1)/2, 1,
  93                               random_ctx, random,
  94                               progress_ctx, progress);
  95
  96           mpz_sub_ui(p1, key->p, 1);
  97
  98           /* If e was given, we must chose p such that p-1 has no factors in
  99            * common with e. */
 100           if (e_size)
 101             break;
 102
 103           mpz_gcd(tmp, pub->e, p1);
 104
 105           if (mpz_cmp_ui(tmp, 1) == 0)
 106             break;
 107           else if (progress) progress(progress_ctx, 'c');
 108         }
 109
 110       if (progress)
 111         progress(progress_ctx, '\n');
 112
 113       /* Generate q, such that gcd(q-1, e) = 1 */
 114       for (;;)
 115         {
 116           nettle_random_prime(key->q, n_size/2, 1,
 117                               random_ctx, random,
 118                               progress_ctx, progress);
 119
 120           /* Very unlikely. */
 121           if (mpz_cmp (key->q, key->p) == 0)
 122             continue;
 123
 124           mpz_sub_ui(q1, key->q, 1);
 125
 126           /* If e was given, we must chose q such that q-1 has no factors in
 127            * common with e. */
 128           if (e_size)
 129             break;
 130
 131           mpz_gcd(tmp, pub->e, q1);
 132
 133           if (mpz_cmp_ui(tmp, 1) == 0)
 134             break;
 135           else if (progress) progress(progress_ctx, 'c');
 136         }
 137
 138       /* Now we have the primes. Is the product of the right size? */
 139       mpz_mul(pub->n, key->p, key->q);
 140
 141       assert (mpz_sizeinbase(pub->n, 2) == n_size);
 142
 143       if (progress)
 144         progress(progress_ctx, '\n');
 145
 146       /* c = q^{-1} (mod p) */
 147       if (mpz_invert(key->c, key->q, key->p))
 148         /* This should succeed everytime. But if it doesn't,
 149          * we try again. */
 150         break;
 151       else if (progress) progress(progress_ctx, '?');
 152     }
 153
 154   mpz_mul(phi, p1, q1);
 155
 156   /* If we didn't have a given e, generate one now. */
 157   if (e_size)
 158     {
 159       int retried = 0;
 160       for (;;)
 161         {
 162           nettle_mpz_random_size(pub->e,
 163                                  random_ctx, random,
 164                                  e_size);
 165
 166           /* Make sure it's odd and that the most significant bit is
 167            * set */
 168           mpz_setbit(pub->e, 0);
 169           mpz_setbit(pub->e, e_size - 1);
 170
 171           /* Needs gmp-3, or inverse might be negative. */
 172           if (mpz_invert(key->d, pub->e, phi))
 173             break;
 174
 175           if (progress) progress(progress_ctx, 'e');
 176           retried = 1;
 177         }
 178       if (retried && progress)
 179         progress(progress_ctx, '\n');
 180     }
 181   else
 182     {
 183       /* Must always succeed, as we already that e
 184        * doesn't have any common factor with p-1 or q-1. */
 185       int res = mpz_invert(key->d, pub->e, phi);
 186       assert(res);
 187     }
 188
 189   /* Done! Almost, we must compute the auxillary private values. */
 190   /* a = d % (p-1) */
 191   mpz_fdiv_r(key->a, key->d, p1);
 192
 193   /* b = d % (q-1) */
 194   mpz_fdiv_r(key->b, key->d, q1);
 195
 196   /* c was computed earlier */
 197
 198   pub->size = key->size = (n_size + 7) / 8;
 199   assert(pub->size >= RSA_MINIMUM_N_OCTETS);
 200
 201   mpz_clear(p1); mpz_clear(q1); mpz_clear(phi); mpz_clear(tmp);
 202
 203   return 1;
 204 }