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