6fa0f9be1ee32b4767e8ed154832b88923601119
[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 seive 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_strong(BIGNUM *rnd, int bits,
77         BIGNUM *add, BIGNUM *rem, BN_CTX *ctx);
78 BIGNUM *BN_generate_prime(BIGNUM *ret, int bits, int strong, BIGNUM *add,
79              BIGNUM *rem, void (*callback)(int,int,void *), void *cb_arg)
80         {
81         BIGNUM *rnd=NULL;
82         BIGNUM t;
83         int i,j,c1=0;
84         BN_CTX *ctx;
85
86         ctx=BN_CTX_new();
87         if (ctx == NULL) goto err;
88         if (ret == NULL)
89                 {
90                 if ((rnd=BN_new()) == NULL) goto err;
91                 }
92         else
93                 rnd=ret;
94         BN_init(&t);
95 loop: 
96         /* make a random number and set the top and bottom bits */
97         if (add == NULL)
98                 {
99                 if (!probable_prime(rnd,bits)) goto err;
100                 }
101         else
102                 {
103                 if (strong)
104                         {
105                         if (!probable_prime_dh_strong(rnd,bits,add,rem,ctx))
106                                  goto err;
107                         }
108                 else
109                         {
110                         if (!probable_prime_dh(rnd,bits,add,rem,ctx))
111                                 goto err;
112                         }
113                 }
114         /* if (BN_mod_word(rnd,(BN_ULONG)3) == 1) goto loop; */
115         if (callback != NULL) callback(0,c1++,cb_arg);
116
117         if (!strong)
118                 {
119                 i=BN_is_prime(rnd,BN_prime_checks,callback,ctx,cb_arg);
120                 if (i == -1) goto err;
121                 if (i == 0) goto loop;
122                 }
123         else
124                 {
125                 /* for a strong prime generation,
126                  * check that (p-1)/2 is prime.
127                  * Since a prime is odd, We just
128                  * need to divide by 2 */
129                 if (!BN_rshift1(&t,rnd)) goto err;
130
131                 for (i=0; i<BN_prime_checks; i++)
132                         {
133                         j=BN_is_prime(rnd,1,callback,ctx,cb_arg);
134                         if (j == -1) goto err;
135                         if (j == 0) goto loop;
136
137                         j=BN_is_prime(&t,1,callback,ctx,cb_arg);
138                         if (j == -1) goto err;
139                         if (j == 0) goto loop;
140
141                         if (callback != NULL) callback(2,c1-1,cb_arg);
142                         /* We have a strong prime test pass */
143                         }
144                 }
145         /* we have a prime :-) */
146         ret=rnd;
147 err:
148         if ((ret == NULL) && (rnd != NULL)) BN_free(rnd);
149         BN_free(&t);
150         if (ctx != NULL) BN_CTX_free(ctx);
151         return(ret);
152         }
153
154 int BN_is_prime(BIGNUM *a, int checks, void (*callback)(int,int,void *),
155              BN_CTX *ctx_passed, void *cb_arg)
156         {
157         int i,j,c2=0,ret= -1;
158         BIGNUM *check;
159         BN_CTX *ctx=NULL,*ctx2=NULL;
160         BN_MONT_CTX *mont=NULL;
161
162         if (!BN_is_odd(a))
163                 return(0);
164         if (ctx_passed != NULL)
165                 ctx=ctx_passed;
166         else
167                 if ((ctx=BN_CTX_new()) == NULL) goto err;
168
169         if ((ctx2=BN_CTX_new()) == NULL) goto err;
170         if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
171
172         check= &(ctx->bn[ctx->tos++]);
173
174         /* Setup the montgomery structure */
175         if (!BN_MONT_CTX_set(mont,a,ctx2)) goto err;
176
177         for (i=0; i<checks; i++)
178                 {
179                 if (!BN_rand(check,BN_num_bits(a)-1,0,0)) goto err;
180                 j=witness(check,a,ctx,ctx2,mont);
181                 if (j == -1) goto err;
182                 if (j)
183                         {
184                         ret=0;
185                         goto err;
186                         }
187                 if (callback != NULL) callback(1,c2++,cb_arg);
188                 }
189         ret=1;
190 err:
191         ctx->tos--;
192         if ((ctx_passed == NULL) && (ctx != NULL))
193                 BN_CTX_free(ctx);
194         if (ctx2 != NULL)
195                 BN_CTX_free(ctx2);
196         if (mont != NULL) BN_MONT_CTX_free(mont);
197                 
198         return(ret);
199         }
200
201 #define RECP_MUL_MOD
202
203 static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx, BN_CTX *ctx2,
204              BN_MONT_CTX *mont)
205         {
206         int k,i,ret= -1,good;
207         BIGNUM *d,*dd,*tmp,*d1,*d2,*n1;
208         BIGNUM *mont_one,*mont_n1,*mont_a;
209
210         d1= &(ctx->bn[ctx->tos]);
211         d2= &(ctx->bn[ctx->tos+1]);
212         n1= &(ctx->bn[ctx->tos+2]);
213         ctx->tos+=3;
214
215         mont_one= &(ctx2->bn[ctx2->tos]);
216         mont_n1= &(ctx2->bn[ctx2->tos+1]);
217         mont_a= &(ctx2->bn[ctx2->tos+2]);
218         ctx2->tos+=3;
219
220         d=d1;
221         dd=d2;
222         if (!BN_one(d)) goto err;
223         if (!BN_sub(n1,n,d)) goto err; /* n1=n-1; */
224         k=BN_num_bits(n1);
225
226         if (!BN_to_montgomery(mont_one,BN_value_one(),mont,ctx2)) goto err;
227         if (!BN_to_montgomery(mont_n1,n1,mont,ctx2)) goto err;
228         if (!BN_to_montgomery(mont_a,a,mont,ctx2)) goto err;
229
230         BN_copy(d,mont_one);
231         for (i=k-1; i>=0; i--)
232                 {
233                 if (    (BN_cmp(d,mont_one) != 0) &&
234                         (BN_cmp(d,mont_n1) != 0))
235                         good=1;
236                 else
237                         good=0;
238
239                 BN_mod_mul_montgomery(dd,d,d,mont,ctx2);
240
241                 if (good && (BN_cmp(dd,mont_one) == 0))
242                         {
243                         ret=1;
244                         goto err;
245                         }
246                 if (BN_is_bit_set(n1,i))
247                         {
248                         BN_mod_mul_montgomery(d,dd,mont_a,mont,ctx2);
249                         }
250                 else
251                         {
252                         tmp=d;
253                         d=dd;
254                         dd=tmp;
255                         }
256                 }
257         if (BN_cmp(d,mont_one) == 0)
258                 i=0;
259         else    i=1;
260         ret=i;
261 err:
262         ctx->tos-=3;
263         ctx2->tos-=3;
264         return(ret);
265         }
266
267 static int probable_prime(BIGNUM *rnd, int bits)
268         {
269         int i;
270         MS_STATIC BN_ULONG mods[NUMPRIMES];
271         BN_ULONG delta,d;
272
273 again:
274         if (!BN_rand(rnd,bits,1,1)) return(0);
275         /* we now have a random number 'rand' to test. */
276         for (i=1; i<NUMPRIMES; i++)
277                 mods[i]=BN_mod_word(rnd,(BN_ULONG)primes[i]);
278         delta=0;
279         loop: for (i=1; i<NUMPRIMES; i++)
280                 {
281                 /* check that rnd is not a prime and also
282                  * that gcd(rnd-1,primes) == 1 (except for 2) */
283                 if (((mods[i]+delta)%primes[i]) <= 1)
284                         {
285                         d=delta;
286                         delta+=2;
287                         /* perhaps need to check for overflow of
288                          * delta (but delta can be upto 2^32)
289                          * 21-May-98 eay - added overflow check */
290                         if (delta < d) goto again;
291                         goto loop;
292                         }
293                 }
294         if (!BN_add_word(rnd,delta)) return(0);
295         return(1);
296         }
297
298 static int probable_prime_dh(BIGNUM *rnd, int bits, BIGNUM *add, BIGNUM *rem,
299              BN_CTX *ctx)
300         {
301         int i,ret=0;
302         BIGNUM *t1;
303
304         t1= &(ctx->bn[ctx->tos++]);
305
306         if (!BN_rand(rnd,bits,0,1)) goto err;
307
308         /* we need ((rnd-rem) % add) == 0 */
309
310         if (!BN_mod(t1,rnd,add,ctx)) goto err;
311         if (!BN_sub(rnd,rnd,t1)) goto err;
312         if (rem == NULL)
313                 { if (!BN_add_word(rnd,1)) goto err; }
314         else
315                 { if (!BN_add(rnd,rnd,rem)) goto err; }
316
317         /* we now have a random number 'rand' to test. */
318
319         loop: for (i=1; i<NUMPRIMES; i++)
320                 {
321                 /* check that rnd is a prime */
322                 if (BN_mod_word(rnd,(BN_ULONG)primes[i]) <= 1)
323                         {
324                         if (!BN_add(rnd,rnd,add)) goto err;
325                         goto loop;
326                         }
327                 }
328         ret=1;
329 err:
330         ctx->tos--;
331         return(ret);
332         }
333
334 static int probable_prime_dh_strong(BIGNUM *p, int bits, BIGNUM *padd,
335              BIGNUM *rem, BN_CTX *ctx)
336         {
337         int i,ret=0;
338         BIGNUM *t1,*qadd=NULL,*q=NULL;
339
340         bits--;
341         t1= &(ctx->bn[ctx->tos++]);
342         q= &(ctx->bn[ctx->tos++]);
343         qadd= &(ctx->bn[ctx->tos++]);
344
345         if (!BN_rshift1(qadd,padd)) goto err;
346                 
347         if (!BN_rand(q,bits,0,1)) goto err;
348
349         /* we need ((rnd-rem) % add) == 0 */
350         if (!BN_mod(t1,q,qadd,ctx)) goto err;
351         if (!BN_sub(q,q,t1)) goto err;
352         if (rem == NULL)
353                 { if (!BN_add_word(q,1)) goto err; }
354         else
355                 {
356                 if (!BN_rshift1(t1,rem)) goto err;
357                 if (!BN_add(q,q,t1)) goto err;
358                 }
359
360         /* we now have a random number 'rand' to test. */
361         if (!BN_lshift1(p,q)) goto err;
362         if (!BN_add_word(p,1)) goto err;
363
364         loop: for (i=1; i<NUMPRIMES; i++)
365                 {
366                 /* check that p and q are prime */
367                 /* check that for p and q
368                  * gcd(p-1,primes) == 1 (except for 2) */
369                 if (    (BN_mod_word(p,(BN_ULONG)primes[i]) == 0) ||
370                         (BN_mod_word(q,(BN_ULONG)primes[i]) == 0))
371                         {
372                         if (!BN_add(p,p,padd)) goto err;
373                         if (!BN_add(q,q,qadd)) goto err;
374                         goto loop;
375                         }
376                 }
377         ret=1;
378 err:
379         ctx->tos-=3;
380         return(ret);
381         }
382
383 #if 0
384 static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx)
385         {
386         int k,i,nb,ret= -1;
387         BIGNUM *d,*dd,*tmp;
388         BIGNUM *d1,*d2,*x,*n1,*inv;
389
390         d1= &(ctx->bn[ctx->tos]);
391         d2= &(ctx->bn[ctx->tos+1]);
392         x=  &(ctx->bn[ctx->tos+2]);
393         n1= &(ctx->bn[ctx->tos+3]);
394         inv=&(ctx->bn[ctx->tos+4]);
395         ctx->tos+=5;
396
397         d=d1;
398         dd=d2;
399         if (!BN_one(d)) goto err;
400         if (!BN_sub(n1,n,d)) goto err; /* n1=n-1; */
401         k=BN_num_bits(n1);
402
403         /* i=BN_num_bits(n); */
404 #ifdef RECP_MUL_MOD
405         nb=BN_reciprocal(inv,n,ctx); /**/
406         if (nb == -1) goto err;
407 #endif
408
409         for (i=k-1; i>=0; i--)
410                 {
411                 if (BN_copy(x,d) == NULL) goto err;
412 #ifndef RECP_MUL_MOD
413                 if (!BN_mod_mul(dd,d,d,n,ctx)) goto err;
414 #else
415                 if (!BN_mod_mul_reciprocal(dd,d,d,n,inv,nb,ctx)) goto err;
416 #endif
417                 if (    BN_is_one(dd) &&
418                         !BN_is_one(x) &&
419                         (BN_cmp(x,n1) != 0))
420                         {
421                         ret=1;
422                         goto err;
423                         }
424                 if (BN_is_bit_set(n1,i))
425                         {
426 #ifndef RECP_MUL_MOD
427                         if (!BN_mod_mul(d,dd,a,n,ctx)) goto err;
428 #else
429                         if (!BN_mod_mul_reciprocal(d,dd,a,n,inv,nb,ctx)) goto err; 
430 #endif
431                         }
432                 else
433                         {
434                         tmp=d;
435                         d=dd;
436                         dd=tmp;
437                         }
438                 }
439         if (BN_is_one(d))
440                 i=0;
441         else    i=1;
442         ret=i;
443 err:
444         ctx->tos-=5;
445         return(ret);
446         }
447 #endif