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