source: trunk/third/ssh/rsa.c @ 12646

Revision 12646, 20.9 KB checked in by danw, 26 years ago (diff)
This commit was generated by cvs2svn to compensate for changes in r12645, which included commits to RCS files with non-trunk default branches.
Line 
1/*
2
3rsa.c
4
5Author: Tatu Ylonen <ylo@cs.hut.fi>
6
7Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
8                   All rights reserved
9
10Created: Fri Mar  3 22:07:06 1995 ylo
11
12Description of the RSA algorithm can be found e.g. from the following sources:
13
14  Bruce Schneier: Applied Cryptography.  John Wiley & Sons, 1994.
15
16  Jennifer Seberry and Josed Pieprzyk: Cryptography: An Introduction to
17    Computer Security.  Prentice-Hall, 1989.
18
19  Man Young Rhee: Cryptography and Secure Data Communications.  McGraw-Hill,
20    1994.
21
22  R. Rivest, A. Shamir, and L. M. Adleman: Cryptographic Communications
23    System and Method.  US Patent 4,405,829, 1983.
24
25  Hans Riesel: Prime Numbers and Computer Methods for Factorization. 
26    Birkhauser, 1994.
27
28  The RSA Frequently Asked Questions document by RSA Data Security, Inc., 1995.
29
30  RSA in 3 lines of perl by Adam Back <aba@atlax.ex.ac.uk>, 1995, as included
31    below:
32    #!/usr/local/bin/perl -s-- -export-a-crypto-system-sig -RSA-in-3-lines-PERL
33    ($k,$n)=@ARGV;$m=unpack(H.$w,$m."\0"x$w),$_=`echo "16do$w 2+4Oi0$d*-^1[d2%
34    Sa2/d0<X+d*La1=z\U$n%0]SX$k"[$m*]\EszlXx++p|dc`,s/^.|\W//g,print pack('H*'
35    ,$_)while read(STDIN,$m,($w=2*$d-1+length($n||die"$0 [-d] k n\n")&~1)/2)
36
37*/
38
39/*
40 * $Id: rsa.c,v 1.1.1.2 1999-03-08 17:43:10 danw Exp $
41 * $Log: not supported by cvs2svn $
42 * Revision 1.5  1998/07/08 14:54:26  tri
43 *      Print progress identification in rsa key generation
44 *      to stderr instead of stdout.
45 *
46 * Revision 1.4  1998/05/23 20:23:56  kivinen
47 *      Changed () -> (void). Added #include "ssh.h".
48 *
49 * Revision 1.3  1997/08/21  22:26:55  ylo
50 *      Set the two highest bits of the prime to one to ensure that we
51 *      end up with the right number of bits for the generated key.
52 *      (Bug reported by Ian Goldberg.)
53 *
54 * Revision 1.2  1997/04/27 21:53:46  kivinen
55 *      Added check that mpz_set_str succeed.
56 *
57 * Revision 1.1.1.1  1996/02/18 21:38:12  ylo
58 *      Imported ssh-1.2.13.
59 *
60 * Revision 1.3  1995/09/06  16:00:12  ylo
61 *      Added missing xfree in rsa_free.
62 *
63 * Revision 1.2  1995/07/13  01:31:25  ylo
64 *      Removed "Last modified" header.
65 *      Added cvs log.
66 *
67 * $Endlog$
68 */
69
70#include "includes.h"
71#include "ssh.h"
72#include <gmp.h>
73#include "xmalloc.h"
74#include "rsa.h"
75
76int rsa_verbose = 1;
77
78#define MAX_PRIMES_IN_TABLE 1050 /* must be more than # primes */
79
80static const unsigned int small_primes[MAX_PRIMES_IN_TABLE + 1] =
81{   /* 2 is eliminated by trying only odd numbers. */
82  3, 5, 7, 11, 13, 17, 19,
83  23, 29, 31, 37, 41, 43, 47, 53,
84  59, 61, 67, 71, 73, 79, 83, 89,
85  97, 101, 103, 107, 109, 113, 127, 131,
86  137, 139, 149, 151, 157, 163, 167, 173,
87  179, 181, 191, 193, 197, 199, 211, 223,
88  227, 229, 233, 239, 241, 251, 257, 263,
89  269, 271, 277, 281, 283, 293, 307, 311,
90  313, 317, 331, 337, 347, 349, 353, 359,
91  367, 373, 379, 383, 389, 397, 401, 409,
92  419, 421, 431, 433, 439, 443, 449, 457,
93  461, 463, 467, 479, 487, 491, 499, 503,
94  509, 521, 523, 541, 547, 557, 563, 569,
95  571, 577, 587, 593, 599, 601, 607, 613,
96  617, 619, 631, 641, 643, 647, 653, 659,
97  661, 673, 677, 683, 691, 701, 709, 719,
98  727, 733, 739, 743, 751, 757, 761, 769,
99  773, 787, 797, 809, 811, 821, 823, 827,
100  829, 839, 853, 857, 859, 863, 877, 881,
101  883, 887, 907, 911, 919, 929, 937, 941,
102  947, 953, 967, 971, 977, 983, 991, 997,
103  1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049,
104  1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097,
105  1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163,
106  1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223,
107  1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283,
108  1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321,
109  1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423,
110  1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459,
111  1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511,
112  1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571,
113  1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619,
114  1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693,
115  1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747,
116  1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811,
117  1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877,
118  1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949,
119  1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003,
120  2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069,
121  2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129,
122  2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203,
123  2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267,
124  2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311,
125  2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377,
126  2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423,
127  2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503,
128  2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579,
129  2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657,
130  2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693,
131  2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741,
132  2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801,
133  2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861,
134  2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939,
135  2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011,
136  3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079,
137  3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167,
138  3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221,
139  3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301,
140  3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347,
141  3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413,
142  3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491,
143  3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541,
144  3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607,
145  3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671,
146  3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727,
147  3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797,
148  3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863,
149  3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923,
150  3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003,
151  4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057,
152  4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129,
153  4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211,
154  4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259,
155  4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337,
156  4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409,
157  4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481,
158  4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547,
159  4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621,
160  4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673,
161  4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751,
162  4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813,
163  4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909,
164  4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967,
165  4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011,
166  5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087,
167  5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167,
168  5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233,
169  5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309,
170  5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399,
171  5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443,
172  5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507,
173  5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573,
174  5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653,
175  5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711,
176  5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791,
177  5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849,
178  5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897,
179  5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007,
180  6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073,
181  6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133,
182  6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211,
183  6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271,
184  6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329,
185  6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379,
186  6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473,
187  6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563,
188  6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637,
189  6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701,
190  6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779,
191  6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833,
192  6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907,
193  6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971,
194  6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027,
195  7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121,
196  7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207,
197  7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253,
198  7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349,
199  7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457,
200  7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517,
201  7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561,
202  7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621,
203  7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691,
204  7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757,
205  7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853,
206  7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919,
207  7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009,
208  8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087,
209  8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161,
210  8167, 8171, 8179, 8191,
211  0};
212
213/* Generate a random number of the desired number of bits.  */
214
215void rsa_random_integer(MP_INT *ret, RandomState *state, unsigned int bits)
216{
217  unsigned int bytes = (bits + 7) / 8;
218  char *str = xmalloc(bytes * 2 + 1);
219  unsigned int i;
220
221  /* We first create a random hex number of the desired size, and then
222     convert it to a mp-int. */
223  for (i = 0; i < bytes; i++)
224    sprintf(str + 2 * i, "%02x", random_get_byte(state));
225
226  /* Convert it to the internal representation. */
227  if (mpz_set_str(ret, str, 16) < 0)
228    fatal("Intenal error, mpz_set_str returned error");
229
230  /* Clear extra data. */
231  memset(str, 0, 2 * bytes);
232  xfree(str);
233
234  /* Reduce it to the desired number of bits. */
235  mpz_mod_2exp(ret, ret, bits);
236}
237
238/* Returns a prime number of the specified number of bits.  The number
239   will have the highest bit set and two lowest bits set. */
240
241void rsa_random_prime(MP_INT *ret, RandomState *state, unsigned int bits)
242{
243  MP_INT start, aux;
244  unsigned int num_primes;
245  int *moduli;
246  long difference;
247
248  mpz_init(&start);
249  mpz_init(&aux);
250
251 retry:
252
253  /* Pick a random integer of the appropriate size. */
254  rsa_random_integer(&start, state, bits);
255
256  /* Set the two highest bits. */
257  mpz_set_ui(&aux, 3);
258  mpz_mul_2exp(&aux, &aux, bits - 2);
259  mpz_ior(&start, &start, &aux);
260  /* Set the lowest bit to make it odd. */
261  mpz_set_ui(&aux, 1);
262  mpz_ior(&start, &start, &aux);
263
264  /* Initialize moduli of the small primes with respect to the given
265     random number. */
266  moduli = xmalloc(MAX_PRIMES_IN_TABLE * sizeof(moduli[0]));
267  if (bits < 16)
268    num_primes = 0; /* Don\'t use the table for very small numbers. */
269  else
270    {
271      for (num_primes = 0; small_primes[num_primes] != 0; num_primes++)
272        {
273          mpz_mod_ui(&aux, &start, small_primes[num_primes]);
274          moduli[num_primes] = mpz_get_ui(&aux);
275        }
276    }
277
278  /* Look for numbers that are not evenly divisible by any of the small
279     primes. */
280  for (difference = 0; ; difference += 2)
281    {
282      unsigned int i;
283
284      if (difference > 0x70000000)
285        { /* Should never happen, I think... */
286          if (rsa_verbose)
287            fprintf(stderr,
288                    "rsa_random_prime: failed to find a prime, retrying.\n");
289          xfree(moduli);
290          goto retry;
291        }
292
293      /* Check if it is a multiple of any small prime.  Note that this
294         updates the moduli into negative values as difference grows. */
295      for (i = 0; i < num_primes; i++)
296        {
297          while (moduli[i] + difference >= small_primes[i])
298            moduli[i] -= small_primes[i];
299          if (moduli[i] + difference == 0)
300            break;
301        }
302      if (i < num_primes)
303        continue; /* Multiple of a known prime. */
304
305      /* It passed the small prime test (not divisible by any of them). */
306      if (rsa_verbose)
307        {
308          fprintf(stderr, ".");
309        }
310
311      /* Compute the number in question. */
312      mpz_add_ui(ret, &start, difference);
313
314      /* Perform the fermat test for witness 2.  This means:
315         it is not prime if 2^n mod n != 2. */
316      mpz_set_ui(&aux, 2);
317      mpz_powm(&aux, &aux, ret, ret);
318      if (mpz_cmp_ui(&aux, 2) == 0)
319        {
320          /* Passed the fermat test for witness 2. */
321          if (rsa_verbose)
322            {
323              fprintf(stderr, "+");
324            }
325          /* Perform a more tests.  These are probably unnecessary. */
326          if (mpz_probab_prime_p(ret, 20))
327            break; /* It is a prime with probability 1 - 2^-40. */
328        }
329    }
330
331  /* Found a (probable) prime.  It is in ret. */
332  if (rsa_verbose)
333    {
334      fprintf(stderr, "+ (distance %ld)\n", difference);
335    }
336
337  /* Free the small prime moduli; they are no longer needed. */
338  xfree(moduli);
339
340  /* Sanity check: does it still have the high bit set (we might have
341     wrapped around)? */
342  mpz_div_2exp(&aux, ret, bits - 1);
343  if (mpz_get_ui(&aux) != 1)
344    {
345      if (rsa_verbose)
346        fprintf(stderr, "rsa_random_prime: high bit not set, retrying.\n");
347      goto retry;
348    }
349  mpz_clear(&start);
350  mpz_clear(&aux);
351  /* Return value already set in ret. */
352}
353
354/* Computes the multiplicative inverse of a number using Euclids algorithm.
355   Computes x such that a * x mod n = 1, where 0 < a < n. */
356
357static void mpz_mod_inverse(MP_INT *x, MP_INT *a, MP_INT *n)
358{
359  MP_INT g0, g1, v0, v1, div, mod, aux;
360  mpz_init_set(&g0, n);
361  mpz_init_set(&g1, a);
362  mpz_init_set_ui(&v0, 0);
363  mpz_init_set_ui(&v1, 1);
364  mpz_init(&div);
365  mpz_init(&mod);
366  mpz_init(&aux);
367  while (mpz_cmp_ui(&g1, 0) != 0)
368    {
369      mpz_divmod(&div, &mod, &g0, &g1);
370      mpz_mul(&aux, &div, &v1);
371      mpz_sub(&aux, &v0, &aux);
372      mpz_set(&v0, &v1);
373      mpz_set(&v1, &aux);
374      mpz_set(&g0, &g1);
375      mpz_set(&g1, &mod);
376    }
377  if (mpz_cmp_ui(&v0, 0) < 0)
378    mpz_add(x, &v0, n);
379  else
380    mpz_set(x, &v0);
381
382  mpz_clear(&g0);
383  mpz_clear(&g1);
384  mpz_clear(&v0);
385  mpz_clear(&v1);
386  mpz_clear(&div);
387  mpz_clear(&mod);
388  mpz_clear(&aux);
389}
390
391/* Given mutual primes p and q, derives RSA key components n, e, d, and u.
392   The exponent e will be at least ebits bits in size.
393   p must be smaller than q. */
394
395static void derive_rsa_keys(MP_INT *n, MP_INT *e, MP_INT *d, MP_INT *u,
396                            MP_INT *p, MP_INT *q,
397                            unsigned int ebits)
398{
399  MP_INT p_minus_1, q_minus_1, aux, phi, G, F;
400
401  assert(mpz_cmp(p, q) < 0);
402
403  mpz_init(&p_minus_1);
404  mpz_init(&q_minus_1);
405  mpz_init(&aux);
406  mpz_init(&phi);
407  mpz_init(&G);
408  mpz_init(&F);
409
410  /* Compute p-1 and q-1. */
411  mpz_sub_ui(&p_minus_1, p, 1);
412  mpz_sub_ui(&q_minus_1, q, 1);
413
414  /* phi = (p - 1) * (q - 1); the number of positive integers less than p*q
415     that are relatively prime to p*q. */
416  mpz_mul(&phi, &p_minus_1, &q_minus_1);
417
418  /* G is the number of "spare key sets" for a given modulus n.  The smaller
419     G is, the better.  The smallest G can get is 2. */
420  mpz_gcd(&G, &p_minus_1, &q_minus_1);
421
422  if (rsa_verbose)
423    {
424      if (mpz_cmp_ui(&G, 100) >= 0)
425        {
426          fprintf(stderr, "Warning: G=");
427          mpz_out_str(stdout, 10, &G);
428          fprintf(stderr, " is large (many spare key sets); key may be bad!\n");
429        }
430    }
431
432  /* F = phi / G; the number of relative prime numbers per spare key set. */
433  mpz_div(&F, &phi, &G);
434
435  /* Find a suitable e (the public exponent). */
436  mpz_set_ui(e, 1);
437  mpz_mul_2exp(e, e, ebits);
438  mpz_sub_ui(e, e, 1); /* make lowest bit 1, and substract 2. */
439  /* Keep adding 2 until it is relatively prime to (p-1)(q-1). */
440  do
441    {
442      mpz_add_ui(e, e, 2);
443      mpz_gcd(&aux, e, &phi);
444    }
445  while (mpz_cmp_ui(&aux, 1) != 0);
446
447  /* d is the multiplicative inverse of e, mod F.  Could also be mod
448     (p-1)(q-1); however, we try to choose the smallest possible d. */
449  mpz_mod_inverse(d, e, &F);
450
451  /* u is the multiplicative inverse of p, mod q, if p < q.  It is used
452     when doing private key RSA operations using the chinese remainder
453     theorem method. */
454  mpz_mod_inverse(u, p, q);
455
456  /* n = p * q (the public modulus). */
457  mpz_mul(n, p, q);
458
459  /* Clear auxiliary variables. */
460  mpz_clear(&p_minus_1);
461  mpz_clear(&q_minus_1);
462  mpz_clear(&aux);
463  mpz_clear(&phi);
464  mpz_clear(&G);
465  mpz_clear(&F);
466}
467
468/* Generates RSA public and private keys.  This initializes the data
469   structures; they should be freed with rsa_clear_private_key and
470   rsa_clear_public_key. */
471
472void rsa_generate_key(RSAPrivateKey *prv, RSAPublicKey *pub,
473                      RandomState *state, unsigned int bits)
474{
475  MP_INT test, aux;
476  unsigned int pbits, qbits;
477  int ret;
478
479  mpz_init(&prv->q);
480  mpz_init(&prv->p);
481  mpz_init(&prv->e);
482  mpz_init(&prv->d);
483  mpz_init(&prv->u);
484  mpz_init(&prv->n);
485  mpz_init(&test);
486  mpz_init(&aux);
487
488  /* Compute the number of bits in each prime. */
489  pbits = bits / 2;
490  qbits = bits - pbits;
491
492#ifndef RSAREF
493 retry0:
494#endif /* !RSAREF */
495
496  if (rsa_verbose)
497    {
498      fprintf(stderr, "Generating p:  ");
499    }
500
501  /* Generate random number p. */
502  rsa_random_prime(&prv->p, state, pbits);
503
504 retry:
505
506  if (rsa_verbose)
507    {
508      fprintf(stderr, "Generating q:  ");
509    }
510
511  /* Generate random number q. */
512  rsa_random_prime(&prv->q, state, qbits);
513
514  /* Sort them so that p < q. */
515  ret = mpz_cmp(&prv->p, &prv->q);
516  if (ret == 0)
517    {
518      if (rsa_verbose)
519        fprintf(stderr, "Generated the same prime twice!\n");
520      goto retry;
521    }
522  if (ret > 0)
523    {
524      mpz_set(&aux, &prv->p);
525      mpz_set(&prv->p, &prv->q);
526      mpz_set(&prv->q, &aux);
527    }
528
529  /* Make sure that p and q are not too close together (I am not sure if this
530     is important). */
531  mpz_sub(&aux, &prv->q, &prv->p);
532  mpz_div_2exp(&test, &prv->q, 10);
533  if (mpz_cmp(&aux, &test) < 0)
534    {
535      if (rsa_verbose)
536        fprintf(stderr, "The primes are too close together.\n");
537      goto retry;
538    }
539
540  /* Make certain p and q are relatively prime (in case one or both were false
541     positives...  Though this is quite impossible). */
542  mpz_gcd(&aux, &prv->p, &prv->q);
543  if (mpz_cmp_ui(&aux, 1) != 0)
544    {
545      if (rsa_verbose)
546        fprintf(stderr, "The primes are not relatively prime!\n");
547      goto retry;
548    }
549 
550  /* Derive the RSA private key from the primes. */
551  if (rsa_verbose)
552    fprintf(stderr, "Computing the keys...\n");
553  derive_rsa_keys(&prv->n, &prv->e, &prv->d, &prv->u, &prv->p, &prv->q, 5);
554  prv->bits = bits;
555
556  /* Initialize the public key with public data from the private key. */
557  pub->bits = bits;
558  mpz_init_set(&pub->n, &prv->n);
559  mpz_init_set(&pub->e, &prv->e);
560
561#ifndef RSAREF /* I don't want to kludge these to work with RSAREF. */
562  /* Test that the key really works.  This should never fail (I think). */
563  if (rsa_verbose)
564    fprintf(stderr, "Testing the keys...\n");
565  rsa_random_integer(&test, state, bits);
566  mpz_mod(&test, &test, &pub->n); /* must be less than n. */
567  rsa_private(&aux, &test, prv);
568  rsa_public(&aux, &aux, pub);
569  if (mpz_cmp(&aux, &test) != 0)
570    {
571      if (rsa_verbose)
572        fprintf(stderr, "**** private+public failed to decrypt.\n");
573      goto retry0;
574    }
575
576  rsa_public(&aux, &test, pub);
577  rsa_private(&aux, &aux, prv);
578  if (mpz_cmp(&aux, &test) != 0)
579    {
580      if (rsa_verbose)
581        fprintf(stderr, "**** public+private failed to decrypt.\n");
582      goto retry0;
583    }
584#endif /* !RSAREF */
585
586  mpz_clear(&aux);
587  mpz_clear(&test);
588 
589  if (rsa_verbose)
590    fprintf(stderr, "Key generation complete.\n");
591}
592
593/* Frees any memory associated with the private key. */
594
595void rsa_clear_private_key(RSAPrivateKey *prv)
596{
597  prv->bits = 0;
598  mpz_clear(&prv->n);
599  mpz_clear(&prv->e);
600  mpz_clear(&prv->d);
601  mpz_clear(&prv->u);
602  mpz_clear(&prv->p);
603  mpz_clear(&prv->q);
604}
605
606/* Frees any memory associated with the public key. */
607
608void rsa_clear_public_key(RSAPublicKey *pub)
609{
610  pub->bits = 0;
611  mpz_clear(&pub->e);
612  mpz_clear(&pub->n);
613}
614
615#ifndef RSAREF
616
617/* Performs a private-key RSA operation (encrypt/decrypt).  The computation
618   is done using the Chinese Remainder Theorem, which is faster than
619   direct modular exponentiation. */
620
621void rsa_private(MP_INT *output, MP_INT *input, RSAPrivateKey *prv)
622{
623  MP_INT dp, dq, p2, q2, k;
624
625  /* Initialize temporary variables. */
626  mpz_init(&dp);
627  mpz_init(&dq);
628  mpz_init(&p2);
629  mpz_init(&q2);
630  mpz_init(&k);
631
632  /* Compute dp = d mod p-1. */
633  mpz_sub_ui(&dp, &prv->p, 1);
634  mpz_mod(&dp, &prv->d, &dp);
635
636  /* Compute dq = d mod q-1. */
637  mpz_sub_ui(&dq, &prv->q, 1);
638  mpz_mod(&dq, &prv->d, &dq);
639
640  /* Compute p2 = (input mod p) ^ dp mod p. */
641  mpz_mod(&p2, input, &prv->p);
642  mpz_powm(&p2, &p2, &dp, &prv->p);
643 
644  /* Compute q2 = (input mod q) ^ dq mod q. */
645  mpz_mod(&q2, input, &prv->q);
646  mpz_powm(&q2, &q2, &dq, &prv->q);
647
648  /* Compute k = ((q2 - p2) mod q) * u mod q. */
649  mpz_sub(&k, &q2, &p2);
650  mpz_mul(&k, &k, &prv->u);
651  mpz_mmod(&k, &k, &prv->q);
652
653  /* Compute output = p2 + p * k. */
654  mpz_mul(output, &prv->p, &k);
655  mpz_add(output, output, &p2);
656
657  /* Clear temporary variables. */
658  mpz_clear(&dp);
659  mpz_clear(&dq);
660  mpz_clear(&p2);
661  mpz_clear(&q2);
662  mpz_clear(&k);
663}
664
665/* Performs a public-key RSA operation (encrypt/decrypt). */
666
667void rsa_public(MP_INT *output, MP_INT *input, RSAPublicKey *pub)
668{
669  mpz_powm(output, input, &pub->e, &pub->n);
670}
671
672#endif /* !RSAREF */
673
674/* Special realloc that zeroes the old memory before freeing it. */
675
676static void *rsa_realloc(void *ptr, size_t old_size, size_t new_size)
677{
678  int s;
679  void *p = xmalloc(new_size);
680  s = old_size;
681  if (old_size > new_size)
682    s = new_size;
683  memcpy(p, ptr, s);
684  memset(ptr, 0, old_size);
685  xfree(ptr);
686  return p;
687}
688
689/* Special free that zeroes the memory before freeing it. */
690
691static void rsa_free(void *ptr, size_t size)
692{
693  memset(ptr, 0, size);
694  xfree(ptr);
695}
696
697/* Sets MP_INT memory allocation routines to ones that clear any memory
698   when freed. */
699
700void rsa_set_mp_memory_allocation(void)
701{
702  mp_set_memory_functions(xmalloc, rsa_realloc, rsa_free);
703}
704
705/* Set whether to output verbose messages during key generation. */
706
707void rsa_set_verbose(int verbose)
708{
709  rsa_verbose = verbose;
710}
Note: See TracBrowser for help on using the repository browser.