e679c7c8224991b97fd50e36072af8707c9bbdc3
[openssl.git] / crypto / bn / bn_prime.c
1 /* crypto/bn/bn_prime.c */
2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3  * All rights reserved.
4  *
5  * This package is an SSL implementation written
6  * by Eric Young (eay@cryptsoft.com).
7  * The implementation was written so as to conform with Netscapes SSL.
8  * 
9  * This library is free for commercial and non-commercial use as long as
10  * the following conditions are aheared to.  The following conditions
11  * apply to all code found in this distribution, be it the RC4, RSA,
12  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
13  * included with this distribution is covered by the same copyright terms
14  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15  * 
16  * Copyright remains Eric Young's, and as such any Copyright notices in
17  * the code are not to be removed.
18  * If this package is used in a product, Eric Young should be given attribution
19  * as the author of the parts of the library used.
20  * This can be in the form of a textual message at program startup or
21  * in documentation (online or textual) provided with the package.
22  * 
23  * Redistribution and use in source and binary forms, with or without
24  * modification, are permitted provided that the following conditions
25  * are met:
26  * 1. Redistributions of source code must retain the copyright
27  *    notice, this list of conditions and the following disclaimer.
28  * 2. Redistributions in binary form must reproduce the above copyright
29  *    notice, this list of conditions and the following disclaimer in the
30  *    documentation and/or other materials provided with the distribution.
31  * 3. All advertising materials mentioning features or use of this software
32  *    must display the following acknowledgement:
33  *    "This product includes cryptographic software written by
34  *     Eric Young (eay@cryptsoft.com)"
35  *    The word 'cryptographic' can be left out if the rouines from the library
36  *    being used are not cryptographic related :-).
37  * 4. If you include any Windows specific code (or a derivative thereof) from 
38  *    the apps directory (application code) you must include an acknowledgement:
39  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40  * 
41  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51  * SUCH DAMAGE.
52  * 
53  * The licence and distribution terms for any publically available version or
54  * derivative of this code cannot be changed.  i.e. this code cannot simply be
55  * copied and put under another distribution licence
56  * [including the GNU Public Licence.]
57  */
58
59 #include <stdio.h>
60 #include <time.h>
61 #include "cryptlib.h"
62 #include "bn_lcl.h"
63 #include <openssl/rand.h>
64
65 /* The quick sieve algorithm approach to weeding out primes is
66  * Philip Zimmermann's, as implemented in PGP.  I have had a read of
67  * his comments and implemented my own version.
68  */
69 #include "bn_prime.h"
70
71 static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx,BN_CTX *ctx2,
72         BN_MONT_CTX *mont);
73 static int probable_prime(BIGNUM *rnd, int bits);
74 static int probable_prime_dh(BIGNUM *rnd, int bits,
75         BIGNUM *add, BIGNUM *rem, BN_CTX *ctx);
76 static int probable_prime_dh_safe(BIGNUM *rnd, int bits,
77         BIGNUM *add, BIGNUM *rem, BN_CTX *ctx);
78
79 BIGNUM *BN_generate_prime(BIGNUM *ret, int bits, int safe, BIGNUM *add,
80              BIGNUM *rem, void (*callback)(int,int,void *), void *cb_arg)
81         {
82         BIGNUM *rnd=NULL;
83         BIGNUM t;
84         int found=0;
85         int i,j,c1=0;
86         BN_CTX *ctx;
87         int checks = BN_prime_checks_for_size(bits);
88
89         ctx=BN_CTX_new();
90         if (ctx == NULL) goto err;
91         if (ret == NULL)
92                 {
93                 if ((rnd=BN_new()) == NULL) goto err;
94                 }
95         else
96                 rnd=ret;
97         BN_init(&t);
98 loop: 
99         /* make a random number and set the top and bottom bits */
100         if (add == NULL)
101                 {
102                 if (!probable_prime(rnd,bits)) goto err;
103                 }
104         else
105                 {
106                 if (safe)
107                         {
108                         if (!probable_prime_dh_safe(rnd,bits,add,rem,ctx))
109                                  goto err;
110                         }
111                 else
112                         {
113                         if (!probable_prime_dh(rnd,bits,add,rem,ctx))
114                                 goto err;
115                         }
116                 }
117         /* if (BN_mod_word(rnd,(BN_ULONG)3) == 1) goto loop; */
118         if (callback != NULL) callback(0,c1++,cb_arg);
119
120         if (!safe)
121                 {
122                 i=BN_is_prime(rnd,checks,callback,ctx,cb_arg);
123                 if (i == -1) goto err;
124                 if (i == 0) goto loop;
125                 }
126         else
127                 {
128                 /* for "safe prime" generation,
129                  * check that (p-1)/2 is prime.
130                  * Since a prime is odd, We just
131                  * need to divide by 2 */
132                 if (!BN_rshift1(&t,rnd)) goto err;
133
134                 for (i=0; i<checks; i++)
135                         {
136                         j=BN_is_prime(rnd,1,callback,ctx,cb_arg);
137                         if (j == -1) goto err;
138                         if (j == 0) goto loop;
139
140                         j=BN_is_prime(&t,1,callback,ctx,cb_arg);
141                         if (j == -1) goto err;
142                         if (j == 0) goto loop;
143
144                         if (callback != NULL) callback(2,c1-1,cb_arg);
145                         /* We have a safe prime test pass */
146                         }
147                 }
148         /* we have a prime :-) */
149         found = 1;
150 err:
151         if (!found && (ret == NULL) && (rnd != NULL)) BN_free(rnd);
152         BN_free(&t);
153         if (ctx != NULL) BN_CTX_free(ctx);
154         return(found ? rnd : NULL);
155         }
156
157 int BN_is_prime_fasttest(BIGNUM *a, int checks,
158                 void (*callback)(int,int,void *),
159                 BN_CTX *ctx_passed, BN_CTX *ctx2_passed, void *cb_arg,
160                 int do_trial_division)
161         {
162         int i,j,ret= -1;
163         BIGNUM *check;
164         BN_CTX *ctx=NULL,*ctx2=NULL;
165         BN_MONT_CTX *mont=NULL;
166
167         if (checks == BN_prime_checks)
168                 {
169                 int bits = BN_num_bits(a);
170                 checks = BN_prime_checks_for_size(bits);
171                 }
172
173         if (!BN_is_odd(a))
174                 return(0);
175         if (do_trial_division)
176                 for (i = 1; i < NUMPRIMES; i++)
177                         if (BN_mod_word(a, primes[i]) == 0) 
178                                 return 0;
179
180         if (ctx_passed != NULL)
181                 ctx=ctx_passed;
182         else
183                 if ((ctx=BN_CTX_new()) == NULL) goto err;
184         if (ctx2_passed != NULL)
185                 ctx2=ctx2_passed;
186         else
187                 if ((ctx2=BN_CTX_new()) == NULL) goto err;
188
189         if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
190
191         check= &(ctx->bn[ctx->tos++]);
192
193         /* Setup the montgomery structure */
194         if (!BN_MONT_CTX_set(mont,a,ctx2)) goto err;
195
196         for (i=0; i<checks; i++)
197                 {
198                 if (!BN_pseudo_rand(check,BN_num_bits(a),0,0)) goto err;
199                 if (BN_cmp(check, a) >= 0)
200                         BN_sub(check, check, a);
201                 j=witness(check,a,ctx,ctx2,mont);
202                 if (j == -1) goto err;
203                 if (j)
204                         {
205                         ret=0;
206                         goto err;
207                         }
208                 if (callback != NULL) callback(1,i,cb_arg);
209                 }
210         ret=1;
211 err:
212         ctx->tos--;
213         if ((ctx_passed == NULL) && (ctx != NULL))
214                 BN_CTX_free(ctx);
215         if ((ctx2_passed == NULL) && (ctx2 != NULL))
216                 BN_CTX_free(ctx2);
217         if (mont != NULL) BN_MONT_CTX_free(mont);
218                 
219         return(ret);
220         }
221
222 int BN_is_prime(BIGNUM *a, int checks, void (*callback)(int,int,void *),
223         BN_CTX *ctx_passed, void *cb_arg)
224         {
225         return BN_is_prime_fasttest(a, checks, callback, ctx_passed, NULL, cb_arg, 0);
226         }
227
228 static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx, BN_CTX *ctx2,
229              BN_MONT_CTX *mont)
230         {
231         int k,i,ret= -1,good;
232         BIGNUM *d,*dd,*tmp,*d1,*d2,*n1;
233         BIGNUM *mont_one,*mont_n1,*mont_a;
234
235         d1= &(ctx->bn[ctx->tos]);
236         d2= &(ctx->bn[ctx->tos+1]);
237         n1= &(ctx->bn[ctx->tos+2]);
238         ctx->tos+=3;
239
240         mont_one= &(ctx2->bn[ctx2->tos]);
241         mont_n1= &(ctx2->bn[ctx2->tos+1]);
242         mont_a= &(ctx2->bn[ctx2->tos+2]);
243         ctx2->tos+=3;
244
245         d=d1;
246         dd=d2;
247         if (!BN_one(d)) goto err;
248         if (!BN_sub(n1,n,d)) goto err; /* n1=n-1; */
249         k=BN_num_bits(n1);
250
251         if (!BN_to_montgomery(mont_one,BN_value_one(),mont,ctx2)) goto err;
252         if (!BN_to_montgomery(mont_n1,n1,mont,ctx2)) goto err;
253         if (!BN_to_montgomery(mont_a,a,mont,ctx2)) goto err;
254
255         BN_copy(d,mont_one);
256         for (i=k-1; i>=0; i--)
257                 {
258                 if (    (BN_cmp(d,mont_one) != 0) &&
259                         (BN_cmp(d,mont_n1) != 0))
260                         good=1;
261                 else
262                         good=0;
263
264                 BN_mod_mul_montgomery(dd,d,d,mont,ctx2);
265
266                 if (good && (BN_cmp(dd,mont_one) == 0))
267                         {
268                         ret=1;
269                         goto err;
270                         }
271                 if (BN_is_bit_set(n1,i))
272                         {
273                         BN_mod_mul_montgomery(d,dd,mont_a,mont,ctx2);
274                         }
275                 else
276                         {
277                         tmp=d;
278                         d=dd;
279                         dd=tmp;
280                         }
281                 }
282         if (BN_cmp(d,mont_one) == 0)
283                 i=0;
284         else    i=1;
285         ret=i;
286 err:
287         ctx->tos-=3;
288         ctx2->tos-=3;
289         return(ret);
290         }
291
292 static int probable_prime(BIGNUM *rnd, int bits)
293         {
294         int i;
295         BN_ULONG mods[NUMPRIMES];
296         BN_ULONG delta,d;
297
298 again:
299         if (!BN_rand(rnd,bits,1,1)) return(0);
300         /* we now have a random number 'rand' to test. */
301         for (i=1; i<NUMPRIMES; i++)
302                 mods[i]=BN_mod_word(rnd,(BN_ULONG)primes[i]);
303         delta=0;
304         loop: for (i=1; i<NUMPRIMES; i++)
305                 {
306                 /* check that rnd is not a prime and also
307                  * that gcd(rnd-1,primes) == 1 (except for 2) */
308                 if (((mods[i]+delta)%primes[i]) <= 1)
309                         {
310                         d=delta;
311                         delta+=2;
312                         /* perhaps need to check for overflow of
313                          * delta (but delta can be upto 2^32)
314                          * 21-May-98 eay - added overflow check */
315                         if (delta < d) goto again;
316                         goto loop;
317                         }
318                 }
319         if (!BN_add_word(rnd,delta)) return(0);
320         return(1);
321         }
322
323 static int probable_prime_dh(BIGNUM *rnd, int bits, BIGNUM *add, BIGNUM *rem,
324              BN_CTX *ctx)
325         {
326         int i,ret=0;
327         BIGNUM *t1;
328
329         t1= &(ctx->bn[ctx->tos++]);
330
331         if (!BN_rand(rnd,bits,0,1)) goto err;
332
333         /* we need ((rnd-rem) % add) == 0 */
334
335         if (!BN_mod(t1,rnd,add,ctx)) goto err;
336         if (!BN_sub(rnd,rnd,t1)) goto err;
337         if (rem == NULL)
338                 { if (!BN_add_word(rnd,1)) goto err; }
339         else
340                 { if (!BN_add(rnd,rnd,rem)) goto err; }
341
342         /* we now have a random number 'rand' to test. */
343
344         loop: for (i=1; i<NUMPRIMES; i++)
345                 {
346                 /* check that rnd is a prime */
347                 if (BN_mod_word(rnd,(BN_ULONG)primes[i]) <= 1)
348                         {
349                         if (!BN_add(rnd,rnd,add)) goto err;
350                         goto loop;
351                         }
352                 }
353         ret=1;
354 err:
355         ctx->tos--;
356         return(ret);
357         }
358
359 static int probable_prime_dh_safe(BIGNUM *p, int bits, BIGNUM *padd,
360              BIGNUM *rem, BN_CTX *ctx)
361         {
362         int i,ret=0;
363         BIGNUM *t1,*qadd=NULL,*q=NULL;
364
365         bits--;
366         t1= &(ctx->bn[ctx->tos++]);
367         q= &(ctx->bn[ctx->tos++]);
368         qadd= &(ctx->bn[ctx->tos++]);
369
370         if (!BN_rshift1(qadd,padd)) goto err;
371                 
372         if (!BN_rand(q,bits,0,1)) goto err;
373
374         /* we need ((rnd-rem) % add) == 0 */
375         if (!BN_mod(t1,q,qadd,ctx)) goto err;
376         if (!BN_sub(q,q,t1)) goto err;
377         if (rem == NULL)
378                 { if (!BN_add_word(q,1)) goto err; }
379         else
380                 {
381                 if (!BN_rshift1(t1,rem)) goto err;
382                 if (!BN_add(q,q,t1)) goto err;
383                 }
384
385         /* we now have a random number 'rand' to test. */
386         if (!BN_lshift1(p,q)) goto err;
387         if (!BN_add_word(p,1)) goto err;
388
389         loop: for (i=1; i<NUMPRIMES; i++)
390                 {
391                 /* check that p and q are prime */
392                 /* check that for p and q
393                  * gcd(p-1,primes) == 1 (except for 2) */
394                 if (    (BN_mod_word(p,(BN_ULONG)primes[i]) == 0) ||
395                         (BN_mod_word(q,(BN_ULONG)primes[i]) == 0))
396                         {
397                         if (!BN_add(p,p,padd)) goto err;
398                         if (!BN_add(q,q,qadd)) goto err;
399                         goto loop;
400                         }
401                 }
402         ret=1;
403 err:
404         ctx->tos-=3;
405         return(ret);
406         }
407
408 #if 0
409
410 #define RECP_MUL_MOD
411
412 static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx,
413                    BN_CTX *unused, BN_MONT_CTX *unused2)
414         {
415         int k,i,ret= -1;
416         BIGNUM *d,*dd,*tmp;
417         BIGNUM *d1,*d2,*x,*n1;
418         BN_RECP_CTX recp;
419
420         d1= &(ctx->bn[ctx->tos]);
421         d2= &(ctx->bn[ctx->tos+1]);
422         x=  &(ctx->bn[ctx->tos+2]);
423         n1= &(ctx->bn[ctx->tos+3]);
424         ctx->tos+=4;
425
426         d=d1;
427         dd=d2;
428         if (!BN_one(d)) goto err;
429         if (!BN_sub(n1,n,d)) goto err; /* n1=n-1; */
430         k=BN_num_bits(n1);
431
432         /* i=BN_num_bits(n); */
433 #ifdef RECP_MUL_MOD
434         BN_RECP_CTX_init(&recp);
435         if (BN_RECP_CTX_set(&recp,n,ctx) <= 0) goto err;
436 #endif
437
438         for (i=k-1; i>=0; i--)
439                 {
440                 if (BN_copy(x,d) == NULL) goto err;
441 #ifndef RECP_MUL_MOD
442                 if (!BN_mod_mul(dd,d,d,n,ctx)) goto err;
443 #else
444                 if (!BN_mod_mul_reciprocal(dd,d,d,&recp,ctx)) goto err;
445 #endif
446                 if (    BN_is_one(dd) &&
447                         !BN_is_one(x) &&
448                         (BN_cmp(x,n1) != 0))
449                         {
450                         ret=1;
451                         goto err;
452                         }
453                 if (BN_is_bit_set(n1,i))
454                         {
455 #ifndef RECP_MUL_MOD
456                         if (!BN_mod_mul(d,dd,a,n,ctx)) goto err;
457 #else
458                         if (!BN_mod_mul_reciprocal(d,dd,a,&recp,ctx)) goto err; 
459 #endif
460                         }
461                 else
462                         {
463                         tmp=d;
464                         d=dd;
465                         dd=tmp;
466                         }
467                 }
468         if (BN_is_one(d))
469                 i=0;
470         else    i=1;
471         ret=i;
472 err:
473         ctx->tos-=4;
474 #ifdef RECP_MUL_MOD
475         BN_RECP_CTX_free(&recp);
476 #endif
477         return(ret);
478         }
479 #endif