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

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