]>
git.ipfire.org Git - thirdparty/openssl.git/blob - crypto/bn/bn_prime.c
1 /* crypto/bn/bn_prime.c */
2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
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.
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).
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.
23 * Redistribution and use in source and binary forms, with or without
24 * modification, are permitted provided that the following conditions
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)"
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
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.]
63 #include <openssl/rand.h>
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.
71 /* number of Miller-Rabin iterations for an error rate of less than 2^-80
72 * for random 'b'-bit input, b >= 100 (taken from table 4.4 in the Handbook
73 * of Applied Cryptography [Menezes, van Oorschot, Vanstone; CRC Press 1996];
74 * original paper: Damgaard, Landrock, Pomerance: Average case error estimates
75 * for the strong probable prime test. -- Math. Comp. 61 (1993) 177-194) */
76 #define BN_prime_checks_size(b) ((b) >= 1300 ? 2 : \
89 static int witness(BIGNUM
*a
, BIGNUM
*n
, BN_CTX
*ctx
,BN_CTX
*ctx2
,
91 static int probable_prime(BIGNUM
*rnd
, int bits
);
92 static int probable_prime_dh(BIGNUM
*rnd
, int bits
,
93 BIGNUM
*add
, BIGNUM
*rem
, BN_CTX
*ctx
);
94 static int probable_prime_dh_safe(BIGNUM
*rnd
, int bits
,
95 BIGNUM
*add
, BIGNUM
*rem
, BN_CTX
*ctx
);
97 BIGNUM
*BN_generate_prime(BIGNUM
*ret
, int bits
, int safe
, BIGNUM
*add
,
98 BIGNUM
*rem
, void (*callback
)(int,int,void *), void *cb_arg
)
105 int checks
= BN_prime_checks_size(bits
);
108 if (ctx
== NULL
) goto err
;
111 if ((rnd
=BN_new()) == NULL
) goto err
;
117 /* make a random number and set the top and bottom bits */
120 if (!probable_prime(rnd
,bits
)) goto err
;
126 if (!probable_prime_dh_safe(rnd
,bits
,add
,rem
,ctx
))
131 if (!probable_prime_dh(rnd
,bits
,add
,rem
,ctx
))
135 /* if (BN_mod_word(rnd,(BN_ULONG)3) == 1) goto loop; */
136 if (callback
!= NULL
) callback(0,c1
++,cb_arg
);
140 i
=BN_is_prime(rnd
,checks
,callback
,ctx
,cb_arg
);
141 if (i
== -1) goto err
;
142 if (i
== 0) goto loop
;
146 /* for "safe prime" generation,
147 * check that (p-1)/2 is prime.
148 * Since a prime is odd, We just
149 * need to divide by 2 */
150 if (!BN_rshift1(&t
,rnd
)) goto err
;
152 for (i
=0; i
<checks
; i
++)
154 j
=BN_is_prime(rnd
,1,callback
,ctx
,cb_arg
);
155 if (j
== -1) goto err
;
156 if (j
== 0) goto loop
;
158 j
=BN_is_prime(&t
,1,callback
,ctx
,cb_arg
);
159 if (j
== -1) goto err
;
160 if (j
== 0) goto loop
;
162 if (callback
!= NULL
) callback(2,c1
-1,cb_arg
);
163 /* We have a safe prime test pass */
166 /* we have a prime :-) */
169 if (!found
&& (ret
== NULL
) && (rnd
!= NULL
)) BN_free(rnd
);
171 if (ctx
!= NULL
) BN_CTX_free(ctx
);
172 return(found
? rnd
: NULL
);
175 int BN_is_prime(BIGNUM
*a
, int checks
, void (*callback
)(int,int,void *),
176 BN_CTX
*ctx_passed
, void *cb_arg
)
178 int i
,j
,c2
=0,ret
= -1;
180 BN_CTX
*ctx
=NULL
,*ctx2
=NULL
;
181 BN_MONT_CTX
*mont
=NULL
;
183 if (checks
== BN_prime_checks
)
185 int bits
= BN_num_bits(a
);
186 checks
= BN_prime_checks_size(bits
);
191 if (ctx_passed
!= NULL
)
194 if ((ctx
=BN_CTX_new()) == NULL
) goto err
;
196 if ((ctx2
=BN_CTX_new()) == NULL
) goto err
;
197 if ((mont
=BN_MONT_CTX_new()) == NULL
) goto err
;
199 check
= &(ctx
->bn
[ctx
->tos
++]);
201 /* Setup the montgomery structure */
202 if (!BN_MONT_CTX_set(mont
,a
,ctx2
)) goto err
;
204 for (i
=0; i
<checks
; i
++)
206 if (!BN_rand(check
,BN_num_bits(a
)-1,0,0)) goto err
;
207 j
=witness(check
,a
,ctx
,ctx2
,mont
);
208 if (j
== -1) goto err
;
214 if (callback
!= NULL
) callback(1,c2
++,cb_arg
);
219 if ((ctx_passed
== NULL
) && (ctx
!= NULL
))
223 if (mont
!= NULL
) BN_MONT_CTX_free(mont
);
228 static int witness(BIGNUM
*a
, BIGNUM
*n
, BN_CTX
*ctx
, BN_CTX
*ctx2
,
231 int k
,i
,ret
= -1,good
;
232 BIGNUM
*d
,*dd
,*tmp
,*d1
,*d2
,*n1
;
233 BIGNUM
*mont_one
,*mont_n1
,*mont_a
;
235 d1
= &(ctx
->bn
[ctx
->tos
]);
236 d2
= &(ctx
->bn
[ctx
->tos
+1]);
237 n1
= &(ctx
->bn
[ctx
->tos
+2]);
240 mont_one
= &(ctx2
->bn
[ctx2
->tos
]);
241 mont_n1
= &(ctx2
->bn
[ctx2
->tos
+1]);
242 mont_a
= &(ctx2
->bn
[ctx2
->tos
+2]);
247 if (!BN_one(d
)) goto err
;
248 if (!BN_sub(n1
,n
,d
)) goto err
; /* n1=n-1; */
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
;
256 for (i
=k
-1; i
>=0; i
--)
258 if ( (BN_cmp(d
,mont_one
) != 0) &&
259 (BN_cmp(d
,mont_n1
) != 0))
264 BN_mod_mul_montgomery(dd
,d
,d
,mont
,ctx2
);
266 if (good
&& (BN_cmp(dd
,mont_one
) == 0))
271 if (BN_is_bit_set(n1
,i
))
273 BN_mod_mul_montgomery(d
,dd
,mont_a
,mont
,ctx2
);
282 if (BN_cmp(d
,mont_one
) == 0)
292 static int probable_prime(BIGNUM
*rnd
, int bits
)
295 MS_STATIC BN_ULONG mods
[NUMPRIMES
];
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
]);
304 loop
: for (i
=1; i
<NUMPRIMES
; i
++)
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)
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
;
319 if (!BN_add_word(rnd
,delta
)) return(0);
323 static int probable_prime_dh(BIGNUM
*rnd
, int bits
, BIGNUM
*add
, BIGNUM
*rem
,
329 t1
= &(ctx
->bn
[ctx
->tos
++]);
331 if (!BN_rand(rnd
,bits
,0,1)) goto err
;
333 /* we need ((rnd-rem) % add) == 0 */
335 if (!BN_mod(t1
,rnd
,add
,ctx
)) goto err
;
336 if (!BN_sub(rnd
,rnd
,t1
)) goto err
;
338 { if (!BN_add_word(rnd
,1)) goto err
; }
340 { if (!BN_add(rnd
,rnd
,rem
)) goto err
; }
342 /* we now have a random number 'rand' to test. */
344 loop
: for (i
=1; i
<NUMPRIMES
; i
++)
346 /* check that rnd is a prime */
347 if (BN_mod_word(rnd
,(BN_ULONG
)primes
[i
]) <= 1)
349 if (!BN_add(rnd
,rnd
,add
)) goto err
;
359 static int probable_prime_dh_safe(BIGNUM
*p
, int bits
, BIGNUM
*padd
,
360 BIGNUM
*rem
, BN_CTX
*ctx
)
363 BIGNUM
*t1
,*qadd
=NULL
,*q
=NULL
;
366 t1
= &(ctx
->bn
[ctx
->tos
++]);
367 q
= &(ctx
->bn
[ctx
->tos
++]);
368 qadd
= &(ctx
->bn
[ctx
->tos
++]);
370 if (!BN_rshift1(qadd
,padd
)) goto err
;
372 if (!BN_rand(q
,bits
,0,1)) goto err
;
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
;
378 { if (!BN_add_word(q
,1)) goto err
; }
381 if (!BN_rshift1(t1
,rem
)) goto err
;
382 if (!BN_add(q
,q
,t1
)) goto err
;
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
;
389 loop
: for (i
=1; i
<NUMPRIMES
; i
++)
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))
397 if (!BN_add(p
,p
,padd
)) goto err
;
398 if (!BN_add(q
,q
,qadd
)) goto err
;
412 static int witness(BIGNUM
*a
, BIGNUM
*n
, BN_CTX
*ctx
,
413 BN_CTX
*unused
, BN_MONT_CTX
*unused2
)
417 BIGNUM
*d1
,*d2
,*x
,*n1
;
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]);
428 if (!BN_one(d
)) goto err
;
429 if (!BN_sub(n1
,n
,d
)) goto err
; /* n1=n-1; */
432 /* i=BN_num_bits(n); */
434 BN_RECP_CTX_init(&recp
);
435 if (BN_RECP_CTX_set(&recp
,n
,ctx
) <= 0) goto err
;
438 for (i
=k
-1; i
>=0; i
--)
440 if (BN_copy(x
,d
) == NULL
) goto err
;
442 if (!BN_mod_mul(dd
,d
,d
,n
,ctx
)) goto err
;
444 if (!BN_mod_mul_reciprocal(dd
,d
,d
,&recp
,ctx
)) goto err
;
446 if ( BN_is_one(dd
) &&
453 if (BN_is_bit_set(n1
,i
))
456 if (!BN_mod_mul(d
,dd
,a
,n
,ctx
)) goto err
;
458 if (!BN_mod_mul_reciprocal(d
,dd
,a
,&recp
,ctx
)) goto err
;
475 BN_RECP_CTX_free(&recp
);