rsa-keygen.c

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