git.samba.org - gd/nettle/blob - 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 "rsa-internal.h"
  43 #include "bignum.h"
  44
  45 #ifndef DEBUG
  46 # define DEBUG 0
  47 #endif
  48
  49 #if DEBUG
  50 # include <stdio.h>
  51 #endif
  52
  53
  54 int
  55 rsa_generate_keypair(struct rsa_public_key *pub,
  56                      struct rsa_private_key *key,
  57                      void *random_ctx, nettle_random_func *random,
  58                      void *progress_ctx, nettle_progress_func *progress,
  59                      unsigned n_size,
  60                      unsigned e_size)
  61 {
  62   mpz_t p1;
  63   mpz_t q1;
  64   mpz_t phi;
  65   mpz_t tmp;
  66
  67   if (e_size)
  68     {
  69       /* We should choose e randomly. Is the size reasonable? */
  70       if ((e_size < 16) || (e_size >= n_size) )
  71         return 0;
  72     }
  73   else
  74     {
  75       /* We have a fixed e. Check that it makes sense */
  76
  77       /* It must be odd */
  78       if (!mpz_tstbit(pub->e, 0))
  79         return 0;
  80
  81       /* And 3 or larger */
  82       if (mpz_cmp_ui(pub->e, 3) < 0)
  83         return 0;
  84
  85       /* And size less than n */
  86       if (mpz_sizeinbase(pub->e, 2) >= n_size)
  87         return 0;
  88     }
  89
  90   if (n_size < RSA_MINIMUM_N_BITS)
  91     return 0;
  92
  93   mpz_init(p1); mpz_init(q1); mpz_init(phi); mpz_init(tmp);
  94
  95   /* Generate primes */
  96   for (;;)
  97     {
  98       /* Generate p, such that gcd(p-1, e) = 1 */
  99       for (;;)
 100         {
 101           nettle_random_prime(key->p, (n_size+1)/2, 1,
 102                               random_ctx, random,
 103                               progress_ctx, progress);
 104
 105           mpz_sub_ui(p1, key->p, 1);
 106
 107           /* If e was given, we must choose p such that p-1 has no factors in
 108            * common with e. */
 109           if (e_size)
 110             break;
 111
 112           mpz_gcd(tmp, pub->e, p1);
 113
 114           if (mpz_cmp_ui(tmp, 1) == 0)
 115             break;
 116           else if (progress) progress(progress_ctx, 'c');
 117         }
 118
 119       if (progress)
 120         progress(progress_ctx, '\n');
 121
 122       /* Generate q, such that gcd(q-1, e) = 1 */
 123       for (;;)
 124         {
 125           nettle_random_prime(key->q, n_size/2, 1,
 126                               random_ctx, random,
 127                               progress_ctx, progress);
 128
 129           mpz_sub_ui(q1, key->q, 1);
 130
 131           /* If e was given, we must choose q such that q-1 has no factors in
 132            * common with e. */
 133           if (e_size)
 134             break;
 135
 136           mpz_gcd(tmp, pub->e, q1);
 137
 138           if (mpz_cmp_ui(tmp, 1) == 0)
 139             break;
 140           else if (progress) progress(progress_ctx, 'c');
 141         }
 142
 143       /* Now we have the primes. Is the product of the right size? */
 144       mpz_mul(pub->n, key->p, key->q);
 145
 146       assert (mpz_sizeinbase(pub->n, 2) == n_size);
 147
 148       if (progress)
 149         progress(progress_ctx, '\n');
 150
 151       /* c = q^{-1} (mod p) */
 152       if (mpz_invert(key->c, key->q, key->p))
 153         /* This should succeed everytime. But if it doesn't,
 154          * we try again. */
 155         break;
 156       else if (progress) progress(progress_ctx, '?');
 157     }
 158
 159   mpz_mul(phi, p1, q1);
 160
 161   /* If we didn't have a given e, generate one now. */
 162   if (e_size)
 163     {
 164       int retried = 0;
 165       for (;;)
 166         {
 167           nettle_mpz_random_size(pub->e,
 168                                  random_ctx, random,
 169                                  e_size);
 170
 171           /* Make sure it's odd and that the most significant bit is
 172            * set */
 173           mpz_setbit(pub->e, 0);
 174           mpz_setbit(pub->e, e_size - 1);
 175
 176           /* Needs gmp-3, or inverse might be negative. */
 177           if (mpz_invert(key->d, pub->e, phi))
 178             break;
 179
 180           if (progress) progress(progress_ctx, 'e');
 181           retried = 1;
 182         }
 183       if (retried && progress)
 184         progress(progress_ctx, '\n');
 185     }
 186   else
 187     {
 188       /* Must always succeed, as we already that e
 189        * doesn't have any common factor with p-1 or q-1. */
 190       int res = mpz_invert(key->d, pub->e, phi);
 191       assert(res);
 192     }
 193
 194   /* Done! Almost, we must compute the auxillary private values. */
 195   /* a = d % (p-1) */
 196   mpz_fdiv_r(key->a, key->d, p1);
 197
 198   /* b = d % (q-1) */
 199   mpz_fdiv_r(key->b, key->d, q1);
 200
 201   /* c was computed earlier */
 202
 203   pub->size = key->size = (n_size + 7) / 8;
 204   assert(pub->size >= RSA_MINIMUM_N_OCTETS);
 205
 206   mpz_clear(p1); mpz_clear(q1); mpz_clear(phi); mpz_clear(tmp);
 207
 208   return 1;
 209 }