3 * Generation of RSA keypairs
6 /* nettle, low-level cryptographics library
8 * Copyright (C) 2002 Niels Möller
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.
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.
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., 59 Temple Place - Suite 330, Boston,
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,
60 /* We should choose e randomly. Is the size reasonable? */
61 if ((e_size < 16) || (e_size >= n_size) )
66 /* We have a fixed e. Check that it makes sense */
69 if (!mpz_tstbit(pub->e, 0))
73 if (mpz_cmp_ui(pub->e, 3) < 0)
76 /* And size less than n */
77 if (mpz_sizeinbase(pub->e, 2) >= n_size)
81 if (n_size < RSA_MINIMUM_N_BITS)
84 mpz_init(p1); mpz_init(q1); mpz_init(phi); mpz_init(tmp);
89 /* Generate p, such that gcd(p-1, e) = 1 */
92 nettle_random_prime(key->p, (n_size+1)/2, 1,
94 progress_ctx, progress);
96 mpz_sub_ui(p1, key->p, 1);
98 /* If e was given, we must chose p such that p-1 has no factors in
103 mpz_gcd(tmp, pub->e, p1);
105 if (mpz_cmp_ui(tmp, 1) == 0)
107 else if (progress) progress(progress_ctx, 'c');
111 progress(progress_ctx, '\n');
113 /* Generate q, such that gcd(q-1, e) = 1 */
116 nettle_random_prime(key->q, n_size/2, 1,
118 progress_ctx, progress);
121 if (mpz_cmp (key->q, key->p) == 0)
124 mpz_sub_ui(q1, key->q, 1);
126 /* If e was given, we must chose q such that q-1 has no factors in
131 mpz_gcd(tmp, pub->e, q1);
133 if (mpz_cmp_ui(tmp, 1) == 0)
135 else if (progress) progress(progress_ctx, 'c');
138 /* Now we have the primes. Is the product of the right size? */
139 mpz_mul(pub->n, key->p, key->q);
141 assert (mpz_sizeinbase(pub->n, 2) == n_size);
144 progress(progress_ctx, '\n');
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,
151 else if (progress) progress(progress_ctx, '?');
154 mpz_mul(phi, p1, q1);
156 /* If we didn't have a given e, generate one now. */
162 nettle_mpz_random_size(pub->e,
166 /* Make sure it's odd and that the most significant bit is
168 mpz_setbit(pub->e, 0);
169 mpz_setbit(pub->e, e_size - 1);
171 /* Needs gmp-3, or inverse might be negative. */
172 if (mpz_invert(key->d, pub->e, phi))
175 if (progress) progress(progress_ctx, 'e');
178 if (retried && progress)
179 progress(progress_ctx, '\n');
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);
189 /* Done! Almost, we must compute the auxillary private values. */
191 mpz_fdiv_r(key->a, key->d, p1);
194 mpz_fdiv_r(key->b, key->d, q1);
196 /* c was computed earlier */
198 pub->size = key->size = (n_size + 7) / 8;
199 assert(pub->size >= RSA_MINIMUM_N_OCTETS);
201 mpz_clear(p1); mpz_clear(q1); mpz_clear(phi); mpz_clear(tmp);