nettle  3.7.3
About: Nettle is a low-level cryptographic library.
  Fossies Dox: nettle-3.7.3.tar.gz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

rsa-keygen.c
Go to the documentation of this file.
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
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  {
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 }
void nettle_random_prime(mpz_t p, unsigned bits, int top_bits_set, void *random_ctx, nettle_random_func *random, void *progress_ctx, nettle_progress_func *progress)
void nettle_mpz_random_size(mpz_t x, void *ctx, nettle_random_func *random, unsigned bits)
Definition: bignum-random.c:44
int mpz_cmp_ui(const mpz_t u, unsigned long v)
Definition: mini-gmp.c:1866
void mpz_sub_ui(mpz_t r, const mpz_t a, unsigned long b)
Definition: mini-gmp.c:1947
size_t mpz_sizeinbase(const mpz_t u, int base)
Definition: mini-gmp.c:4167
void mpz_setbit(mpz_t d, mp_bitcnt_t bit_index)
Definition: mini-gmp.c:3747
void mpz_gcd(mpz_t g, const mpz_t u, const mpz_t v)
Definition: mini-gmp.c:2720
void mpz_init(mpz_t r)
Definition: mini-gmp.c:1410
int mpz_invert(mpz_t r, const mpz_t u, const mpz_t m)
Definition: mini-gmp.c:3002
void mpz_mul(mpz_t r, const mpz_t u, const mpz_t v)
Definition: mini-gmp.c:2058
void mpz_fdiv_r(mpz_t r, const mpz_t n, const mpz_t d)
Definition: mini-gmp.c:2329
void mpz_clear(mpz_t r)
Definition: mini-gmp.c:1435
int mpz_tstbit(const mpz_t d, mp_bitcnt_t bit_index)
Definition: mini-gmp.c:3652
__mpz_struct mpz_t[1]
Definition: mini-gmp.h:77
void nettle_random_func(void *ctx, size_t length, uint8_t *dst)
Definition: nettle-types.h:75
void nettle_progress_func(void *ctx, int c)
Definition: nettle-types.h:79
#define RSA_MINIMUM_N_BITS
Definition: rsa.h:112
#define rsa_generate_keypair
Definition: rsa.h:94
#define RSA_MINIMUM_N_OCTETS
Definition: rsa.h:111
mpz_t p
Definition: rsa.h:136
mpz_t d
Definition: rsa.h:133
mpz_t c
Definition: rsa.h:145
size_t size
Definition: rsa.h:129
mpz_t a
Definition: rsa.h:139
mpz_t q
Definition: rsa.h:136
mpz_t b
Definition: rsa.h:142
size_t size
Definition: rsa.h:118
mpz_t e
Definition: rsa.h:124
mpz_t n
Definition: rsa.h:121
static const uint8_t q1[256]
Definition: twofish.c:101