]>
git.ipfire.org Git - thirdparty/openssl.git/blob - crypto/bn/bn_prime.c
1 /* crypto/bn/bn_prime.c */
2 /* Copyright (C) 1995-1997 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.]
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.
72 static int witness(BIGNUM
*a
, BIGNUM
*n
, BN_CTX
*ctx
);
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
);
80 static int probable_prime();
81 static int probable_prime_dh();
82 static int probable_prime_dh_strong();
85 BIGNUM
*BN_generate_prime(bits
,strong
,add
,rem
,callback
)
90 void (*callback
)(P_I_I
);
99 if (ctx
== NULL
) goto err
;
100 if ((rnd
=BN_new()) == NULL
) goto err
;
102 if ((t
=BN_new()) == NULL
) goto err
;
104 /* make a random number and set the top and bottom bits */
107 if (!probable_prime(rnd
,bits
)) goto err
;
113 if (!probable_prime_dh_strong(rnd
,bits
,add
,rem
,ctx
))
118 if (!probable_prime_dh(rnd
,bits
,add
,rem
,ctx
))
122 /* if (BN_mod_word(rnd,(BN_ULONG)3) == 1) goto loop; */
123 if (callback
!= NULL
) callback(0,c1
++);
127 i
=BN_is_prime(rnd
,BN_prime_checks
,callback
,ctx
);
128 if (i
== -1) goto err
;
129 if (i
== 0) goto loop
;
133 /* for a strong prime generation,
134 * check that (p-1)/2 is prime.
135 * Since a prime is odd, We just
136 * need to divide by 2 */
137 if (!BN_rshift1(t
,rnd
)) goto err
;
139 for (i
=0; i
<BN_prime_checks
; i
++)
141 j
=BN_is_prime(rnd
,1,callback
,ctx
);
142 if (j
== -1) goto err
;
143 if (j
== 0) goto loop
;
145 j
=BN_is_prime(t
,1,callback
,ctx
);
146 if (j
== -1) goto err
;
147 if (j
== 0) goto loop
;
149 if (callback
!= NULL
) callback(2,c1
-1);
150 /* We have a strong prime test pass */
153 /* we have a prime :-) */
156 if ((ret
== NULL
) && (rnd
!= NULL
)) BN_free(rnd
);
157 if (t
!= NULL
) BN_free(t
);
158 if (ctx
!= NULL
) BN_CTX_free(ctx
);
162 int BN_is_prime(a
,checks
,callback
,ctx_passed
)
165 void (*callback
)(P_I_I
);
168 int i
,j
,c2
=0,ret
= -1;
172 if (ctx_passed
!= NULL
)
175 if ((ctx
=BN_CTX_new()) == NULL
) goto err
;
177 check
=ctx
->bn
[ctx
->tos
++];
178 for (i
=0; i
<checks
; i
++)
180 if (!BN_rand(check
,BN_num_bits(a
)-1,0,0)) goto err
;
181 j
=witness(check
,a
,ctx
);
182 if (j
== -1) goto err
;
188 if (callback
!= NULL
) callback(1,c2
++);
193 if ((ctx_passed
== NULL
) && (ctx
!= NULL
))
201 static int witness(a
, n
,ctx
)
208 BIGNUM
*d1
,*d2
,*x
,*n1
,*inv
;
210 d1
=ctx
->bn
[ctx
->tos
];
211 d2
=ctx
->bn
[ctx
->tos
+1];
212 x
=ctx
->bn
[ctx
->tos
+2];
213 n1
=ctx
->bn
[ctx
->tos
+3];
214 inv
=ctx
->bn
[ctx
->tos
+4];
219 if (!BN_one(d
)) goto err
;
220 if (!BN_sub(n1
,n
,d
)) goto err
; /* n1=n-1; */
223 /* i=BN_num_bits(n); */
225 nb
=BN_reciprocal(inv
,n
,ctx
); /**/
226 if (nb
== -1) goto err
;
229 for (i
=k
-1; i
>=0; i
--)
231 if (BN_copy(x
,d
) == NULL
) goto err
;
233 if (!BN_mod_mul(dd
,d
,d
,n
,ctx
)) goto err
;
235 if (!BN_mod_mul_reciprocal(dd
,d
,d
,n
,inv
,nb
,ctx
)) goto err
;
237 if ( BN_is_one(dd
) &&
244 if (BN_is_bit_set(n1
,i
))
247 if (!BN_mod_mul(d
,dd
,a
,n
,ctx
)) goto err
;
249 if (!BN_mod_mul_reciprocal(d
,dd
,a
,n
,inv
,nb
,ctx
)) goto err
;
268 static int probable_prime(rnd
, bits
)
273 MS_STATIC BN_ULONG mods
[NUMPRIMES
];
276 if (!BN_rand(rnd
,bits
,1,1)) return(0);
277 /* we now have a random number 'rand' to test. */
278 for (i
=1; i
<NUMPRIMES
; i
++)
279 mods
[i
]=BN_mod_word(rnd
,(BN_ULONG
)primes
[i
]);
281 loop
: for (i
=1; i
<NUMPRIMES
; i
++)
283 /* check that rnd is not a prime and also
284 * that gcd(rnd-1,primes) == 1 (except for 2) */
285 if (((mods
[i
]+delta
)%primes
[i
]) <= 1)
288 /* perhaps need to check for overflow of
289 * delta (but delta can be upto 2^32) */
293 if (!BN_add_word(rnd
,delta
)) return(0);
297 static int probable_prime_dh(rnd
, bits
, add
, rem
,ctx
)
307 t1
=ctx
->bn
[ctx
->tos
++];
309 if (!BN_rand(rnd
,bits
,0,1)) goto err
;
311 /* we need ((rnd-rem) % add) == 0 */
313 if (!BN_mod(t1
,rnd
,add
,ctx
)) goto err
;
314 if (!BN_sub(rnd
,rnd
,t1
)) goto err
;
316 { if (!BN_add_word(rnd
,1)) goto err
; }
318 { if (!BN_add(rnd
,rnd
,rem
)) goto err
; }
320 /* we now have a random number 'rand' to test. */
322 loop
: for (i
=1; i
<NUMPRIMES
; i
++)
324 /* check that rnd is a prime */
325 if (BN_mod_word(rnd
,(BN_LONG
)primes
[i
]) <= 1)
327 if (!BN_add(rnd
,rnd
,add
)) goto err
;
337 static int probable_prime_dh_strong(p
, bits
, padd
, rem
,ctx
)
345 BIGNUM
*t1
,*qadd
=NULL
,*q
=NULL
;
348 t1
=ctx
->bn
[ctx
->tos
++];
349 q
=ctx
->bn
[ctx
->tos
++];
350 qadd
=ctx
->bn
[ctx
->tos
++];
352 if (!BN_rshift1(qadd
,padd
)) goto err
;
354 if (!BN_rand(q
,bits
,0,1)) goto err
;
356 /* we need ((rnd-rem) % add) == 0 */
357 if (!BN_mod(t1
,q
,qadd
,ctx
)) goto err
;
358 if (!BN_sub(q
,q
,t1
)) goto err
;
360 { if (!BN_add_word(q
,1)) goto err
; }
363 if (!BN_rshift1(t1
,rem
)) goto err
;
364 if (!BN_add(q
,q
,t1
)) goto err
;
367 /* we now have a random number 'rand' to test. */
368 if (!BN_lshift1(p
,q
)) goto err
;
369 if (!BN_add_word(p
,1)) goto err
;
371 loop
: for (i
=1; i
<NUMPRIMES
; i
++)
373 /* check that p and q are prime */
374 /* check that for p and q
375 * gcd(p-1,primes) == 1 (except for 2) */
376 if ( (BN_mod_word(p
,(BN_LONG
)primes
[i
]) == 0) ||
377 (BN_mod_word(q
,(BN_LONG
)primes
[i
]) == 0))
379 if (!BN_add(p
,p
,padd
)) goto err
;
380 if (!BN_add(q
,q
,qadd
)) goto err
;