summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn/bn_prime.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libcrypto/bn/bn_prime.c')
-rw-r--r--src/lib/libcrypto/bn/bn_prime.c447
1 files changed, 0 insertions, 447 deletions
diff --git a/src/lib/libcrypto/bn/bn_prime.c b/src/lib/libcrypto/bn/bn_prime.c
deleted file mode 100644
index 6fa0f9be1e..0000000000
--- a/src/lib/libcrypto/bn/bn_prime.c
+++ /dev/null
@@ -1,447 +0,0 @@
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
71static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx,BN_CTX *ctx2,
72 BN_MONT_CTX *mont);
73static int probable_prime(BIGNUM *rnd, int bits);
74static int probable_prime_dh(BIGNUM *rnd, int bits,
75 BIGNUM *add, BIGNUM *rem, BN_CTX *ctx);
76static int probable_prime_dh_strong(BIGNUM *rnd, int bits,
77 BIGNUM *add, BIGNUM *rem, BN_CTX *ctx);
78BIGNUM *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);
95loop:
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;
147err:
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
154int 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;
190err:
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
203static 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;
261err:
262 ctx->tos-=3;
263 ctx2->tos-=3;
264 return(ret);
265 }
266
267static int probable_prime(BIGNUM *rnd, int bits)
268 {
269 int i;
270 MS_STATIC BN_ULONG mods[NUMPRIMES];
271 BN_ULONG delta,d;
272
273again:
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
298static 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;
329err:
330 ctx->tos--;
331 return(ret);
332 }
333
334static 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;
378err:
379 ctx->tos-=3;
380 return(ret);
381 }
382
383#if 0
384static 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;
443err:
444 ctx->tos-=5;
445 return(ret);
446 }
447#endif
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-22 17:17:38 +0000