OLD | NEW |
| (Empty) |
1 /* crypto/bn/bn_gcd.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 "cryptlib.h" | |
113 #include "bn_lcl.h" | |
114 | |
115 static BIGNUM *euclid(BIGNUM *a, BIGNUM *b); | |
116 | |
117 int BN_gcd(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx) | |
118 { | |
119 BIGNUM *a,*b,*t; | |
120 int ret=0; | |
121 | |
122 bn_check_top(in_a); | |
123 bn_check_top(in_b); | |
124 | |
125 BN_CTX_start(ctx); | |
126 a = BN_CTX_get(ctx); | |
127 b = BN_CTX_get(ctx); | |
128 if (a == NULL || b == NULL) goto err; | |
129 | |
130 if (BN_copy(a,in_a) == NULL) goto err; | |
131 if (BN_copy(b,in_b) == NULL) goto err; | |
132 a->neg = 0; | |
133 b->neg = 0; | |
134 | |
135 if (BN_cmp(a,b) < 0) { t=a; a=b; b=t; } | |
136 t=euclid(a,b); | |
137 if (t == NULL) goto err; | |
138 | |
139 if (BN_copy(r,t) == NULL) goto err; | |
140 ret=1; | |
141 err: | |
142 BN_CTX_end(ctx); | |
143 bn_check_top(r); | |
144 return(ret); | |
145 } | |
146 | |
147 static BIGNUM *euclid(BIGNUM *a, BIGNUM *b) | |
148 { | |
149 BIGNUM *t; | |
150 int shifts=0; | |
151 | |
152 bn_check_top(a); | |
153 bn_check_top(b); | |
154 | |
155 /* 0 <= b <= a */ | |
156 while (!BN_is_zero(b)) | |
157 { | |
158 /* 0 < b <= a */ | |
159 | |
160 if (BN_is_odd(a)) | |
161 { | |
162 if (BN_is_odd(b)) | |
163 { | |
164 if (!BN_sub(a,a,b)) goto err; | |
165 if (!BN_rshift1(a,a)) goto err; | |
166 if (BN_cmp(a,b) < 0) | |
167 { t=a; a=b; b=t; } | |
168 } | |
169 else /* a odd - b even */ | |
170 { | |
171 if (!BN_rshift1(b,b)) goto err; | |
172 if (BN_cmp(a,b) < 0) | |
173 { t=a; a=b; b=t; } | |
174 } | |
175 } | |
176 else /* a is even */ | |
177 { | |
178 if (BN_is_odd(b)) | |
179 { | |
180 if (!BN_rshift1(a,a)) goto err; | |
181 if (BN_cmp(a,b) < 0) | |
182 { t=a; a=b; b=t; } | |
183 } | |
184 else /* a even - b even */ | |
185 { | |
186 if (!BN_rshift1(a,a)) goto err; | |
187 if (!BN_rshift1(b,b)) goto err; | |
188 shifts++; | |
189 } | |
190 } | |
191 /* 0 <= b <= a */ | |
192 } | |
193 | |
194 if (shifts) | |
195 { | |
196 if (!BN_lshift(a,a,shifts)) goto err; | |
197 } | |
198 bn_check_top(a); | |
199 return(a); | |
200 err: | |
201 return(NULL); | |
202 } | |
203 | |
204 | |
205 /* solves ax == 1 (mod n) */ | |
206 static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, | |
207 const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx); | |
208 | |
209 BIGNUM *BN_mod_inverse(BIGNUM *in, | |
210 const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx) | |
211 { | |
212 BIGNUM *A,*B,*X,*Y,*M,*D,*T,*R=NULL; | |
213 BIGNUM *ret=NULL; | |
214 int sign; | |
215 | |
216 if ((BN_get_flags(a, BN_FLG_CONSTTIME) != 0) || (BN_get_flags(n, BN_FLG_
CONSTTIME) != 0)) | |
217 { | |
218 return BN_mod_inverse_no_branch(in, a, n, ctx); | |
219 } | |
220 | |
221 bn_check_top(a); | |
222 bn_check_top(n); | |
223 | |
224 BN_CTX_start(ctx); | |
225 A = BN_CTX_get(ctx); | |
226 B = BN_CTX_get(ctx); | |
227 X = BN_CTX_get(ctx); | |
228 D = BN_CTX_get(ctx); | |
229 M = BN_CTX_get(ctx); | |
230 Y = BN_CTX_get(ctx); | |
231 T = BN_CTX_get(ctx); | |
232 if (T == NULL) goto err; | |
233 | |
234 if (in == NULL) | |
235 R=BN_new(); | |
236 else | |
237 R=in; | |
238 if (R == NULL) goto err; | |
239 | |
240 BN_one(X); | |
241 BN_zero(Y); | |
242 if (BN_copy(B,a) == NULL) goto err; | |
243 if (BN_copy(A,n) == NULL) goto err; | |
244 A->neg = 0; | |
245 if (B->neg || (BN_ucmp(B, A) >= 0)) | |
246 { | |
247 if (!BN_nnmod(B, B, A, ctx)) goto err; | |
248 } | |
249 sign = -1; | |
250 /* From B = a mod |n|, A = |n| it follows that | |
251 * | |
252 * 0 <= B < A, | |
253 * -sign*X*a == B (mod |n|), | |
254 * sign*Y*a == A (mod |n|). | |
255 */ | |
256 | |
257 if (BN_is_odd(n) && (BN_num_bits(n) <= (BN_BITS <= 32 ? 450 : 2048))) | |
258 { | |
259 /* Binary inversion algorithm; requires odd modulus. | |
260 * This is faster than the general algorithm if the modulus | |
261 * is sufficiently small (about 400 .. 500 bits on 32-bit | |
262 * sytems, but much more on 64-bit systems) */ | |
263 int shift; | |
264 | |
265 while (!BN_is_zero(B)) | |
266 { | |
267 /* | |
268 * 0 < B < |n|, | |
269 * 0 < A <= |n|, | |
270 * (1) -sign*X*a == B (mod |n|), | |
271 * (2) sign*Y*a == A (mod |n|) | |
272 */ | |
273 | |
274 /* Now divide B by the maximum possible power of two i
n the integers, | |
275 * and divide X by the same value mod |n|. | |
276 * When we're done, (1) still holds. */ | |
277 shift = 0; | |
278 while (!BN_is_bit_set(B, shift)) /* note that 0 < B */ | |
279 { | |
280 shift++; | |
281 | |
282 if (BN_is_odd(X)) | |
283 { | |
284 if (!BN_uadd(X, X, n)) goto err; | |
285 } | |
286 /* now X is even, so we can easily divide it by
two */ | |
287 if (!BN_rshift1(X, X)) goto err; | |
288 } | |
289 if (shift > 0) | |
290 { | |
291 if (!BN_rshift(B, B, shift)) goto err; | |
292 } | |
293 | |
294 | |
295 /* Same for A and Y. Afterwards, (2) still holds. */ | |
296 shift = 0; | |
297 while (!BN_is_bit_set(A, shift)) /* note that 0 < A */ | |
298 { | |
299 shift++; | |
300 | |
301 if (BN_is_odd(Y)) | |
302 { | |
303 if (!BN_uadd(Y, Y, n)) goto err; | |
304 } | |
305 /* now Y is even */ | |
306 if (!BN_rshift1(Y, Y)) goto err; | |
307 } | |
308 if (shift > 0) | |
309 { | |
310 if (!BN_rshift(A, A, shift)) goto err; | |
311 } | |
312 | |
313 | |
314 /* We still have (1) and (2). | |
315 * Both A and B are odd. | |
316 * The following computations ensure that | |
317 * | |
318 * 0 <= B < |n|, | |
319 * 0 < A < |n|, | |
320 * (1) -sign*X*a == B (mod |n|), | |
321 * (2) sign*Y*a == A (mod |n|), | |
322 * | |
323 * and that either A or B is even in the next iterat
ion. | |
324 */ | |
325 if (BN_ucmp(B, A) >= 0) | |
326 { | |
327 /* -sign*(X + Y)*a == B - A (mod |n|) */ | |
328 if (!BN_uadd(X, X, Y)) goto err; | |
329 /* NB: we could use BN_mod_add_quick(X, X, Y, n)
, but that | |
330 * actually makes the algorithm slower */ | |
331 if (!BN_usub(B, B, A)) goto err; | |
332 } | |
333 else | |
334 { | |
335 /* sign*(X + Y)*a == A - B (mod |n|) */ | |
336 if (!BN_uadd(Y, Y, X)) goto err; | |
337 /* as above, BN_mod_add_quick(Y, Y, X, n) would
slow things down */ | |
338 if (!BN_usub(A, A, B)) goto err; | |
339 } | |
340 } | |
341 } | |
342 else | |
343 { | |
344 /* general inversion algorithm */ | |
345 | |
346 while (!BN_is_zero(B)) | |
347 { | |
348 BIGNUM *tmp; | |
349 | |
350 /* | |
351 * 0 < B < A, | |
352 * (*) -sign*X*a == B (mod |n|), | |
353 * sign*Y*a == A (mod |n|) | |
354 */ | |
355 | |
356 /* (D, M) := (A/B, A%B) ... */ | |
357 if (BN_num_bits(A) == BN_num_bits(B)) | |
358 { | |
359 if (!BN_one(D)) goto err; | |
360 if (!BN_sub(M,A,B)) goto err; | |
361 } | |
362 else if (BN_num_bits(A) == BN_num_bits(B) + 1) | |
363 { | |
364 /* A/B is 1, 2, or 3 */ | |
365 if (!BN_lshift1(T,B)) goto err; | |
366 if (BN_ucmp(A,T) < 0) | |
367 { | |
368 /* A < 2*B, so D=1 */ | |
369 if (!BN_one(D)) goto err; | |
370 if (!BN_sub(M,A,B)) goto err; | |
371 } | |
372 else | |
373 { | |
374 /* A >= 2*B, so D=2 or D=3 */ | |
375 if (!BN_sub(M,A,T)) goto err; | |
376 if (!BN_add(D,T,B)) goto err; /* use D (
:= 3*B) as temp */ | |
377 if (BN_ucmp(A,D) < 0) | |
378 { | |
379 /* A < 3*B, so D=2 */ | |
380 if (!BN_set_word(D,2)) goto err; | |
381 /* M (= A - 2*B) already has the
correct value */ | |
382 } | |
383 else | |
384 { | |
385 /* only D=3 remains */ | |
386 if (!BN_set_word(D,3)) goto err; | |
387 /* currently M = A - 2*B, but
we need M = A - 3*B */ | |
388 if (!BN_sub(M,M,B)) goto err; | |
389 } | |
390 } | |
391 } | |
392 else | |
393 { | |
394 if (!BN_div(D,M,A,B,ctx)) goto err; | |
395 } | |
396 | |
397 /* Now | |
398 * A = D*B + M; | |
399 * thus we have | |
400 * (**) sign*Y*a == D*B + M (mod |n|). | |
401 */ | |
402 | |
403 tmp=A; /* keep the BIGNUM object, the value does not mat
ter */ | |
404 | |
405 /* (A, B) := (B, A mod B) ... */ | |
406 A=B; | |
407 B=M; | |
408 /* ... so we have 0 <= B < A again */ | |
409 | |
410 /* Since the former M is now B and the former B is
now A, | |
411 * (**) translates into | |
412 * sign*Y*a == D*A + B (mod |n|), | |
413 * i.e. | |
414 * sign*Y*a - D*A == B (mod |n|). | |
415 * Similarly, (*) translates into | |
416 * -sign*X*a == A (mod |n|). | |
417 * | |
418 * Thus, | |
419 * sign*Y*a + D*sign*X*a == B (mod |n|), | |
420 * i.e. | |
421 * sign*(Y + D*X)*a == B (mod |n|). | |
422 * | |
423 * So if we set (X, Y, sign) := (Y + D*X, X, -sign), w
e arrive back at | |
424 * -sign*X*a == B (mod |n|), | |
425 * sign*Y*a == A (mod |n|). | |
426 * Note that X and Y stay non-negative all the time. | |
427 */ | |
428 | |
429 /* most of the time D is very small, so we can optimize
tmp := D*X+Y */ | |
430 if (BN_is_one(D)) | |
431 { | |
432 if (!BN_add(tmp,X,Y)) goto err; | |
433 } | |
434 else | |
435 { | |
436 if (BN_is_word(D,2)) | |
437 { | |
438 if (!BN_lshift1(tmp,X)) goto err; | |
439 } | |
440 else if (BN_is_word(D,4)) | |
441 { | |
442 if (!BN_lshift(tmp,X,2)) goto err; | |
443 } | |
444 else if (D->top == 1) | |
445 { | |
446 if (!BN_copy(tmp,X)) goto err; | |
447 if (!BN_mul_word(tmp,D->d[0])) goto err; | |
448 } | |
449 else | |
450 { | |
451 if (!BN_mul(tmp,D,X,ctx)) goto err; | |
452 } | |
453 if (!BN_add(tmp,tmp,Y)) goto err; | |
454 } | |
455 | |
456 M=Y; /* keep the BIGNUM object, the value does not matte
r */ | |
457 Y=X; | |
458 X=tmp; | |
459 sign = -sign; | |
460 } | |
461 } | |
462 | |
463 /* | |
464 * The while loop (Euclid's algorithm) ends when | |
465 * A == gcd(a,n); | |
466 * we have | |
467 * sign*Y*a == A (mod |n|), | |
468 * where Y is non-negative. | |
469 */ | |
470 | |
471 if (sign < 0) | |
472 { | |
473 if (!BN_sub(Y,n,Y)) goto err; | |
474 } | |
475 /* Now Y*a == A (mod |n|). */ | |
476 | |
477 | |
478 if (BN_is_one(A)) | |
479 { | |
480 /* Y*a == 1 (mod |n|) */ | |
481 if (!Y->neg && BN_ucmp(Y,n) < 0) | |
482 { | |
483 if (!BN_copy(R,Y)) goto err; | |
484 } | |
485 else | |
486 { | |
487 if (!BN_nnmod(R,Y,n,ctx)) goto err; | |
488 } | |
489 } | |
490 else | |
491 { | |
492 BNerr(BN_F_BN_MOD_INVERSE,BN_R_NO_INVERSE); | |
493 goto err; | |
494 } | |
495 ret=R; | |
496 err: | |
497 if ((ret == NULL) && (in == NULL)) BN_free(R); | |
498 BN_CTX_end(ctx); | |
499 bn_check_top(ret); | |
500 return(ret); | |
501 } | |
502 | |
503 | |
504 /* BN_mod_inverse_no_branch is a special version of BN_mod_inverse. | |
505 * It does not contain branches that may leak sensitive information. | |
506 */ | |
507 static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, | |
508 const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx) | |
509 { | |
510 BIGNUM *A,*B,*X,*Y,*M,*D,*T,*R=NULL; | |
511 BIGNUM local_A, local_B; | |
512 BIGNUM *pA, *pB; | |
513 BIGNUM *ret=NULL; | |
514 int sign; | |
515 | |
516 bn_check_top(a); | |
517 bn_check_top(n); | |
518 | |
519 BN_CTX_start(ctx); | |
520 A = BN_CTX_get(ctx); | |
521 B = BN_CTX_get(ctx); | |
522 X = BN_CTX_get(ctx); | |
523 D = BN_CTX_get(ctx); | |
524 M = BN_CTX_get(ctx); | |
525 Y = BN_CTX_get(ctx); | |
526 T = BN_CTX_get(ctx); | |
527 if (T == NULL) goto err; | |
528 | |
529 if (in == NULL) | |
530 R=BN_new(); | |
531 else | |
532 R=in; | |
533 if (R == NULL) goto err; | |
534 | |
535 BN_one(X); | |
536 BN_zero(Y); | |
537 if (BN_copy(B,a) == NULL) goto err; | |
538 if (BN_copy(A,n) == NULL) goto err; | |
539 A->neg = 0; | |
540 | |
541 if (B->neg || (BN_ucmp(B, A) >= 0)) | |
542 { | |
543 /* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked
, | |
544 * BN_div_no_branch will be called eventually. | |
545 */ | |
546 pB = &local_B; | |
547 BN_with_flags(pB, B, BN_FLG_CONSTTIME); | |
548 if (!BN_nnmod(B, pB, A, ctx)) goto err; | |
549 } | |
550 sign = -1; | |
551 /* From B = a mod |n|, A = |n| it follows that | |
552 * | |
553 * 0 <= B < A, | |
554 * -sign*X*a == B (mod |n|), | |
555 * sign*Y*a == A (mod |n|). | |
556 */ | |
557 | |
558 while (!BN_is_zero(B)) | |
559 { | |
560 BIGNUM *tmp; | |
561 | |
562 /* | |
563 * 0 < B < A, | |
564 * (*) -sign*X*a == B (mod |n|), | |
565 * sign*Y*a == A (mod |n|) | |
566 */ | |
567 | |
568 /* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked
, | |
569 * BN_div_no_branch will be called eventually. | |
570 */ | |
571 pA = &local_A; | |
572 BN_with_flags(pA, A, BN_FLG_CONSTTIME); | |
573 | |
574 /* (D, M) := (A/B, A%B) ... */ | |
575 if (!BN_div(D,M,pA,B,ctx)) goto err; | |
576 | |
577 /* Now | |
578 * A = D*B + M; | |
579 * thus we have | |
580 * (**) sign*Y*a == D*B + M (mod |n|). | |
581 */ | |
582 | |
583 tmp=A; /* keep the BIGNUM object, the value does not matter */ | |
584 | |
585 /* (A, B) := (B, A mod B) ... */ | |
586 A=B; | |
587 B=M; | |
588 /* ... so we have 0 <= B < A again */ | |
589 | |
590 /* Since the former M is now B and the former B is now A, | |
591 * (**) translates into | |
592 * sign*Y*a == D*A + B (mod |n|), | |
593 * i.e. | |
594 * sign*Y*a - D*A == B (mod |n|). | |
595 * Similarly, (*) translates into | |
596 * -sign*X*a == A (mod |n|). | |
597 * | |
598 * Thus, | |
599 * sign*Y*a + D*sign*X*a == B (mod |n|), | |
600 * i.e. | |
601 * sign*(Y + D*X)*a == B (mod |n|). | |
602 * | |
603 * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive
back at | |
604 * -sign*X*a == B (mod |n|), | |
605 * sign*Y*a == A (mod |n|). | |
606 * Note that X and Y stay non-negative all the time. | |
607 */ | |
608 | |
609 if (!BN_mul(tmp,D,X,ctx)) goto err; | |
610 if (!BN_add(tmp,tmp,Y)) goto err; | |
611 | |
612 M=Y; /* keep the BIGNUM object, the value does not matter */ | |
613 Y=X; | |
614 X=tmp; | |
615 sign = -sign; | |
616 } | |
617 | |
618 /* | |
619 * The while loop (Euclid's algorithm) ends when | |
620 * A == gcd(a,n); | |
621 * we have | |
622 * sign*Y*a == A (mod |n|), | |
623 * where Y is non-negative. | |
624 */ | |
625 | |
626 if (sign < 0) | |
627 { | |
628 if (!BN_sub(Y,n,Y)) goto err; | |
629 } | |
630 /* Now Y*a == A (mod |n|). */ | |
631 | |
632 if (BN_is_one(A)) | |
633 { | |
634 /* Y*a == 1 (mod |n|) */ | |
635 if (!Y->neg && BN_ucmp(Y,n) < 0) | |
636 { | |
637 if (!BN_copy(R,Y)) goto err; | |
638 } | |
639 else | |
640 { | |
641 if (!BN_nnmod(R,Y,n,ctx)) goto err; | |
642 } | |
643 } | |
644 else | |
645 { | |
646 BNerr(BN_F_BN_MOD_INVERSE_NO_BRANCH,BN_R_NO_INVERSE); | |
647 goto err; | |
648 } | |
649 ret=R; | |
650 err: | |
651 if ((ret == NULL) && (in == NULL)) BN_free(R); | |
652 BN_CTX_end(ctx); | |
653 bn_check_top(ret); | |
654 return(ret); | |
655 } | |
OLD | NEW |