← Back to branch summary

~ubuntu-branches/ubuntu/saucy/nettle/saucy-proposed

« back to all changes in this revision

Viewing changes to rsa-keygen.c

  • Committer: Bazaar Package Importer
  • Author(s): Marek Habersack
  • Date: 2004-05-04 15:56:02 UTC
  • Revision ID: james.westby@ubuntu.com-20040504155602-7jbhw5mabvwksl3j
Tags: upstream-1.10
Import upstream version 1.10

Show diffs side-by-side

added added

removed removed

Lines of Context:
rsa-keygen.c
 
1
/* rsa-keygen.c
 
2
 *
 
3
 * Generation of RSA keypairs
 
4
 */
 
5
 
 
6
/* nettle, low-level cryptographics library
 
7
 *
 
8
 * Copyright (C) 2002 Niels M�ller
 
9
 *  
 
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.
 
14
 * 
 
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.
 
19
 * 
 
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,
 
23
 * MA 02111-1307, USA.
 
24
 */
 
25
 
 
26
#if HAVE_CONFIG_H
 
27
# include "config.h"
 
28
#endif
 
29
 
 
30
#if WITH_PUBLIC_KEY
 
31
 
 
32
#include <assert.h>
 
33
#include <limits.h>
 
34
#include <stdlib.h>
 
35
 
 
36
#include "rsa.h"
 
37
#include "bignum.h"
 
38
#include "nettle-internal.h"
 
39
 
 
40
#ifndef DEBUG
 
41
# define DEBUG 0
 
42
#endif
 
43
 
 
44
#if DEBUG
 
45
# include <stdio.h>
 
46
#endif
 
47
 
 
48
 
 
49
#define NUMBER_OF_PRIMES 167
 
50
 
 
51
static const unsigned long primes[NUMBER_OF_PRIMES] = {
 
52
  3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
 
53
  71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139,
 
54
  149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211,
 
55
  223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
 
56
  283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367,
 
57
  373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
 
58
  449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523,
 
59
  541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613,
 
60
  617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691,
 
61
  701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787,
 
62
  797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877,
 
63
  881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971,
 
64
  977, 983, 991, 997
 
65
};
 
66
 
 
67
/* NOTE: The mpz_nextprime in current GMP is unoptimized. */
 
68
static void
 
69
bignum_next_prime(mpz_t p, mpz_t n, int count,
 
70
                  void *progress_ctx, nettle_progress_func progress)
 
71
{
 
72
  mpz_t tmp;
 
73
  TMP_DECL(moduli, unsigned long, NUMBER_OF_PRIMES);
 
74
  
 
75
  unsigned long difference;
 
76
  unsigned prime_limit = NUMBER_OF_PRIMES;
 
77
  
 
78
  /* First handle tiny numbers */
 
79
  if (mpz_cmp_ui(n, 2) <= 0)
 
80
    {
 
81
      mpz_set_ui(p, 2);
 
82
      return;
 
83
    }
 
84
  mpz_set(p, n);
 
85
  mpz_setbit(p, 0);
 
86
 
 
87
  if (mpz_cmp_ui(p, 8) < 0)
 
88
    return;
 
89
 
 
90
  mpz_init(tmp);
 
91
 
 
92
  if (mpz_cmp_ui(p, primes[prime_limit-1]) <= 0)
 
93
    /* Use only 3, 5 and 7 */
 
94
    prime_limit = 3;
 
95
  
 
96
  /* Compute residues modulo small odd primes */
 
97
  TMP_ALLOC(moduli, prime_limit);
 
98
  {
 
99
    unsigned i;
 
100
    for (i = 0; i < prime_limit; i++)
 
101
      moduli[i] = mpz_fdiv_ui(p, primes[i]);
 
102
  }
 
103
  
 
104
  for (difference = 0; ; difference += 2)
 
105
    {
 
106
      int composite = 0;
 
107
      unsigned i;
 
108
 
 
109
      if (difference >= ULONG_MAX - 10)
 
110
        { /* Should not happen, at least not very often... */
 
111
          mpz_add_ui(p, p, difference);
 
112
          difference = 0;
 
113
        }
 
114
 
 
115
      /* First check residues */
 
116
      for (i = 0; i < prime_limit; i++)
 
117
        {
 
118
          if (moduli[i] == 0)
 
119
            composite = 1;
 
120
          moduli[i] = (moduli[i] + 2) % primes[i];
 
121
        }
 
122
      if (composite)
 
123
        continue;
 
124
      
 
125
      mpz_add_ui(p, p, difference);
 
126
      difference = 0;
 
127
 
 
128
      if (progress)
 
129
        progress(progress_ctx, '.');
 
130
      
 
131
      /* Fermat test, with respect to 2 */
 
132
      mpz_set_ui(tmp, 2);
 
133
      mpz_powm(tmp, tmp, p, p);
 
134
      if (mpz_cmp_ui(tmp, 2) != 0)
 
135
        continue;
 
136
 
 
137
      if (progress)
 
138
        progress(progress_ctx, '+');
 
139
 
 
140
      /* Miller-Rabin test */
 
141
      if (mpz_probab_prime_p(p, count))
 
142
        break;
 
143
    }
 
144
  mpz_clear(tmp);
 
145
}
 
146
 
 
147
/* Returns a random prime of size BITS */
 
148
static void
 
149
bignum_random_prime(mpz_t x, unsigned bits,
 
150
                    void *random_ctx, nettle_random_func random,
 
151
                    void *progress_ctx, nettle_progress_func progress)
 
152
{
 
153
  assert(bits);
 
154
  
 
155
  for (;;)
 
156
    {
 
157
      nettle_mpz_random_size(x, random_ctx, random, bits);
 
158
      mpz_setbit(x, bits - 1);
 
159
 
 
160
      /* Miller-rabin count of 25 is probably much overkill. */
 
161
      bignum_next_prime(x, x, 25, progress_ctx, progress);
 
162
 
 
163
      if (mpz_sizeinbase(x, 2) == bits)
 
164
        break;
 
165
    }
 
166
}
 
167
 
 
168
int
 
169
rsa_generate_keypair(struct rsa_public_key *pub,
 
170
                     struct rsa_private_key *key,
 
171
                     void *random_ctx, nettle_random_func random,
 
172
                     void *progress_ctx, nettle_progress_func progress,
 
173
                     unsigned n_size,
 
174
                     unsigned e_size)
 
175
{
 
176
  mpz_t p1;
 
177
  mpz_t q1;
 
178
  mpz_t phi;
 
179
  mpz_t tmp;
 
180
 
 
181
  if (e_size)
 
182
    {
 
183
      /* We should choose e randomly. Is the size reasonable? */
 
184
      if ((e_size < 16) || (e_size > n_size) )
 
185
        return 0;
 
186
    }
 
187
  else
 
188
    {
 
189
      /* We have a fixed e. Check that it makes sense */
 
190
 
 
191
      /* It must be odd */
 
192
      if (!mpz_tstbit(pub->e, 0))
 
193
        return 0;
 
194
 
 
195
      /* And 3 or larger */
 
196
      if (mpz_cmp_ui(pub->e, 3) < 0)
 
197
        return 0;
 
198
    }
 
199
  
 
200
  if (n_size < RSA_MINIMUM_N_BITS)
 
201
    return 0;
 
202
  
 
203
  mpz_init(p1); mpz_init(q1); mpz_init(phi); mpz_init(tmp);
 
204
 
 
205
  /* Generate primes */
 
206
  for (;;)
 
207
    {
 
208
      /* Generate p, such that gcd(p-1, e) = 1 */
 
209
      for (;;)
 
210
        {
 
211
          bignum_random_prime(key->p, (n_size+1)/2,
 
212
                              random_ctx, random,
 
213
                              progress_ctx, progress);
 
214
          mpz_sub_ui(p1, key->p, 1);
 
215
      
 
216
          /* If e was given, we must chose p such that p-1 has no factors in
 
217
           * common with e. */
 
218
          if (e_size)
 
219
            break;
 
220
          
 
221
          mpz_gcd(tmp, pub->e, p1);
 
222
 
 
223
          if (mpz_cmp_ui(tmp, 1) == 0)
 
224
            break;
 
225
          else if (progress) progress(progress_ctx, 'c');
 
226
        } 
 
227
 
 
228
      if (progress)
 
229
        progress(progress_ctx, '\n');
 
230
      
 
231
      /* Generate q, such that gcd(q-1, e) = 1 */
 
232
      for (;;)
 
233
        {
 
234
          bignum_random_prime(key->q, n_size/2,
 
235
                              random_ctx, random,
 
236
                              progress_ctx, progress);
 
237
          mpz_sub_ui(q1, key->q, 1);
 
238
      
 
239
          /* If e was given, we must chose q such that q-1 has no factors in
 
240
           * common with e. */
 
241
          if (e_size)
 
242
            break;
 
243
          
 
244
          mpz_gcd(tmp, pub->e, q1);
 
245
 
 
246
          if (mpz_cmp_ui(tmp, 1) == 0)
 
247
            break;
 
248
          else if (progress) progress(progress_ctx, 'c');
 
249
        }
 
250
 
 
251
      /* Now we have the primes. Is the product of the right size? */
 
252
      mpz_mul(pub->n, key->p, key->q);
 
253
      
 
254
      if (mpz_sizeinbase(pub->n, 2) != n_size)
 
255
        /* We might get an n of size n_size-1. Then just try again. */
 
256
        {
 
257
#if DEBUG
 
258
          fprintf(stderr,
 
259
                  "\nWanted size: %d, p-size: %d, q-size: %d, n-size: %d\n",
 
260
                  n_size,
 
261
                  mpz_sizeinbase(key->p,2),
 
262
                  mpz_sizeinbase(key->q,2),
 
263
                  mpz_sizeinbase(pub->n,2));
 
264
#endif
 
265
          if (progress)
 
266
            {
 
267
              progress(progress_ctx, 'b');
 
268
              progress(progress_ctx, '\n');
 
269
            }
 
270
          continue;
 
271
        }
 
272
      
 
273
      if (progress)
 
274
        progress(progress_ctx, '\n');
 
275
 
 
276
      /* c = q^{-1} (mod p) */
 
277
      if (mpz_invert(key->c, key->q, key->p))
 
278
        /* This should succeed everytime. But if it doesn't,
 
279
         * we try again. */
 
280
        break;
 
281
      else if (progress) progress(progress_ctx, '?');
 
282
    }
 
283
 
 
284
  mpz_mul(phi, p1, q1);
 
285
  
 
286
  /* If we didn't have a given e, generate one now. */
 
287
  if (e_size)
 
288
    {
 
289
      int retried = 0;
 
290
      for (;;)
 
291
        {
 
292
          nettle_mpz_random_size(pub->e,
 
293
                                 random_ctx, random,
 
294
                                 e_size);
 
295
        
 
296
          /* Make sure it's odd and that the most significant bit is
 
297
           * set */
 
298
          mpz_setbit(pub->e, 0);
 
299
          mpz_setbit(pub->e, e_size - 1);
 
300
 
 
301
          /* Needs gmp-3, or inverse might be negative. */
 
302
          if (mpz_invert(key->d, pub->e, phi))
 
303
            break;
 
304
 
 
305
          if (progress) progress(progress_ctx, 'e');
 
306
          retried = 1;
 
307
        }
 
308
      if (retried && progress)
 
309
        progress(progress_ctx, '\n');   
 
310
    }
 
311
  else
 
312
    {
 
313
      /* Must always succeed, as we already that e
 
314
       * doesn't have any common factor with p-1 or q-1. */
 
315
      int res = mpz_invert(key->d, pub->e, phi);
 
316
      assert(res);
 
317
    }
 
318
 
 
319
  /* Done! Almost, we must compute the auxillary private values. */
 
320
  /* a = d % (p-1) */
 
321
  mpz_fdiv_r(key->a, key->d, p1);
 
322
 
 
323
  /* b = d % (q-1) */
 
324
  mpz_fdiv_r(key->b, key->d, q1);
 
325
 
 
326
  /* c was computed earlier */
 
327
 
 
328
  pub->size = key->size = (mpz_sizeinbase(pub->n, 2) + 7) / 8;
 
329
  assert(pub->size >= RSA_MINIMUM_N_OCTETS);
 
330
  
 
331
  mpz_clear(p1); mpz_clear(q1); mpz_clear(phi); mpz_clear(tmp);
 
332
 
 
333
  return 1;
 
334
}
 
335
 
 
336
#endif /* WITH_PUBLIC_KEY */