modexp512-x86_64.pl: make it work with ml64.
[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  * Copyright (c) 1998-2001 The OpenSSL Project.  All rights reserved.
60  *
61  * Redistribution and use in source and binary forms, with or without
62  * modification, are permitted provided that the following conditions
63  * are met:
64  *
65  * 1. Redistributions of source code must retain the above copyright
66  *    notice, this list of conditions and the following disclaimer. 
67  *
68  * 2. Redistributions in binary form must reproduce the above copyright
69  *    notice, this list of conditions and the following disclaimer in
70  *    the documentation and/or other materials provided with the
71  *    distribution.
72  *
73  * 3. All advertising materials mentioning features or use of this
74  *    software must display the following acknowledgment:
75  *    "This product includes software developed by the OpenSSL Project
76  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
77  *
78  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
79  *    endorse or promote products derived from this software without
80  *    prior written permission. For written permission, please contact
81  *    openssl-core@openssl.org.
82  *
83  * 5. Products derived from this software may not be called "OpenSSL"
84  *    nor may "OpenSSL" appear in their names without prior written
85  *    permission of the OpenSSL Project.
86  *
87  * 6. Redistributions of any form whatsoever must retain the following
88  *    acknowledgment:
89  *    "This product includes software developed by the OpenSSL Project
90  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
91  *
92  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
93  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
94  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
95  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
96  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
97  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
98  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
99  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
100  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
101  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
102  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
103  * OF THE POSSIBILITY OF SUCH DAMAGE.
104  * ====================================================================
105  *
106  * This product includes cryptographic software written by Eric Young
107  * (eay@cryptsoft.com).  This product includes software written by Tim
108  * Hudson (tjh@cryptsoft.com).
109  *
110  */
111
112 #include <stdio.h>
113 #include <time.h>
114 #include "cryptlib.h"
115 #include "bn_lcl.h"
116 #include <openssl/rand.h>
117
118 /* NB: these functions have been "upgraded", the deprecated versions (which are
119  * compatibility wrappers using these functions) are in bn_depr.c.
120  * - Geoff
121  */
122
123 /* The quick sieve algorithm approach to weeding out primes is
124  * Philip Zimmermann's, as implemented in PGP.  I have had a read of
125  * his comments and implemented my own version.
126  */
127 #include "bn_prime.h"
128
129 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
130         const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont);
131 static int probable_prime(BIGNUM *rnd, int bits);
132 static int probable_prime_dh(BIGNUM *rnd, int bits,
133         const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx);
134 static int probable_prime_dh_safe(BIGNUM *rnd, int bits,
135         const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx);
136
137 int BN_GENCB_call(BN_GENCB *cb, int a, int b)
138         {
139         /* No callback means continue */
140         if(!cb) return 1;
141         switch(cb->ver)
142                 {
143         case 1:
144                 /* Deprecated-style callbacks */
145                 if(!cb->cb.cb_1)
146                         return 1;
147                 cb->cb.cb_1(a, b, cb->arg);
148                 return 1;
149         case 2:
150                 /* New-style callbacks */
151                 return cb->cb.cb_2(a, b, cb);
152         default:
153                 break;
154                 }
155         /* Unrecognised callback type */
156         return 0;
157         }
158
159 int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe,
160         const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb)
161         {
162         BIGNUM *t;
163         int found=0;
164         int i,j,c1=0;
165         BN_CTX *ctx;
166         int checks = BN_prime_checks_for_size(bits);
167
168         ctx=BN_CTX_new();
169         if (ctx == NULL) goto err;
170         BN_CTX_start(ctx);
171         t = BN_CTX_get(ctx);
172         if(!t) goto err;
173 loop: 
174         /* make a random number and set the top and bottom bits */
175         if (add == NULL)
176                 {
177                 if (!probable_prime(ret,bits)) goto err;
178                 }
179         else
180                 {
181                 if (safe)
182                         {
183                         if (!probable_prime_dh_safe(ret,bits,add,rem,ctx))
184                                  goto err;
185                         }
186                 else
187                         {
188                         if (!probable_prime_dh(ret,bits,add,rem,ctx))
189                                 goto err;
190                         }
191                 }
192         /* if (BN_mod_word(ret,(BN_ULONG)3) == 1) goto loop; */
193         if(!BN_GENCB_call(cb, 0, c1++))
194                 /* aborted */
195                 goto err;
196
197         if (!safe)
198                 {
199                 i=BN_is_prime_fasttest_ex(ret,checks,ctx,0,cb);
200                 if (i == -1) goto err;
201                 if (i == 0) goto loop;
202                 }
203         else
204                 {
205                 /* for "safe prime" generation,
206                  * check that (p-1)/2 is prime.
207                  * Since a prime is odd, We just
208                  * need to divide by 2 */
209                 if (!BN_rshift1(t,ret)) goto err;
210
211                 for (i=0; i<checks; i++)
212                         {
213                         j=BN_is_prime_fasttest_ex(ret,1,ctx,0,cb);
214                         if (j == -1) goto err;
215                         if (j == 0) goto loop;
216
217                         j=BN_is_prime_fasttest_ex(t,1,ctx,0,cb);
218                         if (j == -1) goto err;
219                         if (j == 0) goto loop;
220
221                         if(!BN_GENCB_call(cb, 2, c1-1))
222                                 goto err;
223                         /* We have a safe prime test pass */
224                         }
225                 }
226         /* we have a prime :-) */
227         found = 1;
228 err:
229         if (ctx != NULL)
230                 {
231                 BN_CTX_end(ctx);
232                 BN_CTX_free(ctx);
233                 }
234         bn_check_top(ret);
235         return found;
236         }
237
238 int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, BN_GENCB *cb)
239         {
240         return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb);
241         }
242
243 int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
244                 int do_trial_division, BN_GENCB *cb)
245         {
246         int i, j, ret = -1;
247         int k;
248         BN_CTX *ctx = NULL;
249         BIGNUM *A1, *A1_odd, *check; /* taken from ctx */
250         BN_MONT_CTX *mont = NULL;
251         const BIGNUM *A = NULL;
252
253         if (BN_cmp(a, BN_value_one()) <= 0)
254                 return 0;
255         
256         if (checks == BN_prime_checks)
257                 checks = BN_prime_checks_for_size(BN_num_bits(a));
258
259         /* first look for small factors */
260         if (!BN_is_odd(a))
261                 /* a is even => a is prime if and only if a == 2 */
262                 return BN_is_word(a, 2);
263         if (do_trial_division)
264                 {
265                 for (i = 1; i < NUMPRIMES; i++)
266                         if (BN_mod_word(a, primes[i]) == 0) 
267                                 return 0;
268                 if(!BN_GENCB_call(cb, 1, -1))
269                         goto err;
270                 }
271
272         if (ctx_passed != NULL)
273                 ctx = ctx_passed;
274         else
275                 if ((ctx=BN_CTX_new()) == NULL)
276                         goto err;
277         BN_CTX_start(ctx);
278
279         /* A := abs(a) */
280         if (a->neg)
281                 {
282                 BIGNUM *t;
283                 if ((t = BN_CTX_get(ctx)) == NULL) goto err;
284                 BN_copy(t, a);
285                 t->neg = 0;
286                 A = t;
287                 }
288         else
289                 A = a;
290         A1 = BN_CTX_get(ctx);
291         A1_odd = BN_CTX_get(ctx);
292         check = BN_CTX_get(ctx);
293         if (check == NULL) goto err;
294
295         /* compute A1 := A - 1 */
296         if (!BN_copy(A1, A))
297                 goto err;
298         if (!BN_sub_word(A1, 1))
299                 goto err;
300         if (BN_is_zero(A1))
301                 {
302                 ret = 0;
303                 goto err;
304                 }
305
306         /* write  A1  as  A1_odd * 2^k */
307         k = 1;
308         while (!BN_is_bit_set(A1, k))
309                 k++;
310         if (!BN_rshift(A1_odd, A1, k))
311                 goto err;
312
313         /* Montgomery setup for computations mod A */
314         mont = BN_MONT_CTX_new();
315         if (mont == NULL)
316                 goto err;
317         if (!BN_MONT_CTX_set(mont, A, ctx))
318                 goto err;
319         
320         for (i = 0; i < checks; i++)
321                 {
322                 if (!BN_pseudo_rand_range(check, A1))
323                         goto err;
324                 if (!BN_add_word(check, 1))
325                         goto err;
326                 /* now 1 <= check < A */
327
328                 j = witness(check, A, A1, A1_odd, k, ctx, mont);
329                 if (j == -1) goto err;
330                 if (j)
331                         {
332                         ret=0;
333                         goto err;
334                         }
335                 if(!BN_GENCB_call(cb, 1, i))
336                         goto err;
337                 }
338         ret=1;
339 err:
340         if (ctx != NULL)
341                 {
342                 BN_CTX_end(ctx);
343                 if (ctx_passed == NULL)
344                         BN_CTX_free(ctx);
345                 }
346         if (mont != NULL)
347                 BN_MONT_CTX_free(mont);
348
349         return(ret);
350         }
351
352 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
353         const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont)
354         {
355         if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */
356                 return -1;
357         if (BN_is_one(w))
358                 return 0; /* probably prime */
359         if (BN_cmp(w, a1) == 0)
360                 return 0; /* w == -1 (mod a),  'a' is probably prime */
361         while (--k)
362                 {
363                 if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */
364                         return -1;
365                 if (BN_is_one(w))
366                         return 1; /* 'a' is composite, otherwise a previous 'w' would
367                                    * have been == -1 (mod 'a') */
368                 if (BN_cmp(w, a1) == 0)
369                         return 0; /* w == -1 (mod a), 'a' is probably prime */
370                 }
371         /* If we get here, 'w' is the (a-1)/2-th power of the original 'w',
372          * and it is neither -1 nor +1 -- so 'a' cannot be prime */
373         bn_check_top(w);
374         return 1;
375         }
376
377 static int probable_prime(BIGNUM *rnd, int bits)
378         {
379         int i;
380         prime_t mods[NUMPRIMES];
381         BN_ULONG delta,maxdelta;
382
383 again:
384         if (!BN_rand(rnd,bits,1,1)) return(0);
385         /* we now have a random number 'rand' to test. */
386         for (i=1; i<NUMPRIMES; i++)
387                 mods[i]=(prime_t)BN_mod_word(rnd,(BN_ULONG)primes[i]);
388         maxdelta=BN_MASK2 - primes[NUMPRIMES-1];
389         delta=0;
390         loop: for (i=1; i<NUMPRIMES; i++)
391                 {
392                 /* check that rnd is not a prime and also
393                  * that gcd(rnd-1,primes) == 1 (except for 2) */
394                 if (((mods[i]+delta)%primes[i]) <= 1)
395                         {
396                         delta+=2;
397                         if (delta > maxdelta) goto again;
398                         goto loop;
399                         }
400                 }
401         if (!BN_add_word(rnd,delta)) return(0);
402         bn_check_top(rnd);
403         return(1);
404         }
405
406 static int probable_prime_dh(BIGNUM *rnd, int bits,
407         const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx)
408         {
409         int i,ret=0;
410         BIGNUM *t1;
411
412         BN_CTX_start(ctx);
413         if ((t1 = BN_CTX_get(ctx)) == NULL) goto err;
414
415         if (!BN_rand(rnd,bits,0,1)) goto err;
416
417         /* we need ((rnd-rem) % add) == 0 */
418
419         if (!BN_mod(t1,rnd,add,ctx)) goto err;
420         if (!BN_sub(rnd,rnd,t1)) goto err;
421         if (rem == NULL)
422                 { if (!BN_add_word(rnd,1)) goto err; }
423         else
424                 { if (!BN_add(rnd,rnd,rem)) goto err; }
425
426         /* we now have a random number 'rand' to test. */
427
428         loop: for (i=1; i<NUMPRIMES; i++)
429                 {
430                 /* check that rnd is a prime */
431                 if (BN_mod_word(rnd,(BN_ULONG)primes[i]) <= 1)
432                         {
433                         if (!BN_add(rnd,rnd,add)) goto err;
434                         goto loop;
435                         }
436                 }
437         ret=1;
438 err:
439         BN_CTX_end(ctx);
440         bn_check_top(rnd);
441         return(ret);
442         }
443
444 static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
445         const BIGNUM *rem, BN_CTX *ctx)
446         {
447         int i,ret=0;
448         BIGNUM *t1,*qadd,*q;
449
450         bits--;
451         BN_CTX_start(ctx);
452         t1 = BN_CTX_get(ctx);
453         q = BN_CTX_get(ctx);
454         qadd = BN_CTX_get(ctx);
455         if (qadd == NULL) goto err;
456
457         if (!BN_rshift1(qadd,padd)) goto err;
458                 
459         if (!BN_rand(q,bits,0,1)) goto err;
460
461         /* we need ((rnd-rem) % add) == 0 */
462         if (!BN_mod(t1,q,qadd,ctx)) goto err;
463         if (!BN_sub(q,q,t1)) goto err;
464         if (rem == NULL)
465                 { if (!BN_add_word(q,1)) goto err; }
466         else
467                 {
468                 if (!BN_rshift1(t1,rem)) goto err;
469                 if (!BN_add(q,q,t1)) goto err;
470                 }
471
472         /* we now have a random number 'rand' to test. */
473         if (!BN_lshift1(p,q)) goto err;
474         if (!BN_add_word(p,1)) goto err;
475
476         loop: for (i=1; i<NUMPRIMES; i++)
477                 {
478                 /* check that p and q are prime */
479                 /* check that for p and q
480                  * gcd(p-1,primes) == 1 (except for 2) */
481                 if (    (BN_mod_word(p,(BN_ULONG)primes[i]) == 0) ||
482                         (BN_mod_word(q,(BN_ULONG)primes[i]) == 0))
483                         {
484                         if (!BN_add(p,p,padd)) goto err;
485                         if (!BN_add(q,q,qadd)) goto err;
486                         goto loop;
487                         }
488                 }
489         ret=1;
490 err:
491         BN_CTX_end(ctx);
492         bn_check_top(p);
493         return(ret);
494         }