summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorjsing <>2023-01-21 09:21:11 +0000
committerjsing <>2023-01-21 09:21:11 +0000
commit71fbf41bd2b9e40f88e44c107ffcde8405fa4f14 (patch)
treebb49a1d930f380fac250032d18cf02d631ca4c4c /src
parent33b8a0e11319f8cfbe896e89be1e758ff0815afa (diff)
downloadopenbsd-71fbf41bd2b9e40f88e44c107ffcde8405fa4f14.tar.gz
openbsd-71fbf41bd2b9e40f88e44c107ffcde8405fa4f14.tar.bz2
openbsd-71fbf41bd2b9e40f88e44c107ffcde8405fa4f14.zip
Reorder functions and drop unnessary static prototypes.
No functional change.
Diffstat (limited to 'src')
-rw-r--r--src/lib/libcrypto/bn/bn_gcd.c735
1 files changed, 363 insertions, 372 deletions
diff --git a/src/lib/libcrypto/bn/bn_gcd.c b/src/lib/libcrypto/bn/bn_gcd.c
index 0d8bdf07eb..84c3d85850 100644
--- a/src/lib/libcrypto/bn/bn_gcd.c
+++ b/src/lib/libcrypto/bn/bn_gcd.c
@@ -1,4 +1,4 @@
1/* $OpenBSD: bn_gcd.c,v 1.20 2022/12/26 07:18:51 jmc Exp $ */ 1/* $OpenBSD: bn_gcd.c,v 1.21 2023/01/21 09:21:11 jsing Exp $ */
2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 * All rights reserved. 3 * All rights reserved.
4 * 4 *
@@ -113,63 +113,6 @@
113 113
114#include "bn_local.h" 114#include "bn_local.h"
115 115
116static BIGNUM *euclid(BIGNUM *a, BIGNUM *b);
117static BIGNUM *BN_gcd_no_branch(BIGNUM *in, const BIGNUM *a, const BIGNUM *n,
118 BN_CTX *ctx);
119
120int
121BN_gcd(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx)
122{
123 BIGNUM *a, *b, *t;
124 int ret = 0;
125
126
127 BN_CTX_start(ctx);
128 if ((a = BN_CTX_get(ctx)) == NULL)
129 goto err;
130 if ((b = BN_CTX_get(ctx)) == NULL)
131 goto err;
132
133 if (BN_copy(a, in_a) == NULL)
134 goto err;
135 if (BN_copy(b, in_b) == NULL)
136 goto err;
137 a->neg = 0;
138 b->neg = 0;
139
140 if (BN_cmp(a, b) < 0) {
141 t = a;
142 a = b;
143 b = t;
144 }
145 t = euclid(a, b);
146 if (t == NULL)
147 goto err;
148
149 if (BN_copy(r, t) == NULL)
150 goto err;
151 ret = 1;
152
153err:
154 BN_CTX_end(ctx);
155 return (ret);
156}
157
158int
159BN_gcd_ct(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx)
160{
161 if (BN_gcd_no_branch(r, in_a, in_b, ctx) == NULL)
162 return 0;
163 return 1;
164}
165
166int
167BN_gcd_nonct(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx)
168{
169 return BN_gcd(r, in_a, in_b, ctx);
170}
171
172
173static BIGNUM * 116static BIGNUM *
174euclid(BIGNUM *a, BIGNUM *b) 117euclid(BIGNUM *a, BIGNUM *b)
175{ 118{
@@ -237,11 +180,370 @@ err:
237 return (NULL); 180 return (NULL);
238} 181}
239 182
183/*
184 * BN_gcd_no_branch is a special version of BN_mod_inverse_no_branch.
185 * that returns the GCD.
186 */
187static BIGNUM *
188BN_gcd_no_branch(BIGNUM *in, const BIGNUM *a, const BIGNUM *n,
189 BN_CTX *ctx)
190{
191 BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL;
192 BIGNUM local_A, local_B;
193 BIGNUM *pA, *pB;
194 BIGNUM *ret = NULL;
195 int sign;
240 196
241/* solves ax == 1 (mod n) */ 197 if (in == NULL)
242static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, const BIGNUM *a, 198 goto err;
243 const BIGNUM *n, BN_CTX *ctx); 199 R = in;
200
201 BN_init(&local_A);
202 BN_init(&local_B);
203
204
205 BN_CTX_start(ctx);
206 if ((A = BN_CTX_get(ctx)) == NULL)
207 goto err;
208 if ((B = BN_CTX_get(ctx)) == NULL)
209 goto err;
210 if ((X = BN_CTX_get(ctx)) == NULL)
211 goto err;
212 if ((D = BN_CTX_get(ctx)) == NULL)
213 goto err;
214 if ((M = BN_CTX_get(ctx)) == NULL)
215 goto err;
216 if ((Y = BN_CTX_get(ctx)) == NULL)
217 goto err;
218 if ((T = BN_CTX_get(ctx)) == NULL)
219 goto err;
220
221 if (!BN_one(X))
222 goto err;
223 BN_zero(Y);
224 if (BN_copy(B, a) == NULL)
225 goto err;
226 if (BN_copy(A, n) == NULL)
227 goto err;
228 A->neg = 0;
229
230 if (B->neg || (BN_ucmp(B, A) >= 0)) {
231 /*
232 * Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked,
233 * BN_div_no_branch will be called eventually.
234 */
235 pB = &local_B;
236 /* BN_init() done at the top of the function. */
237 BN_with_flags(pB, B, BN_FLG_CONSTTIME);
238 if (!BN_nnmod(B, pB, A, ctx))
239 goto err;
240 }
241 sign = -1;
242 /* From B = a mod |n|, A = |n| it follows that
243 *
244 * 0 <= B < A,
245 * -sign*X*a == B (mod |n|),
246 * sign*Y*a == A (mod |n|).
247 */
248
249 while (!BN_is_zero(B)) {
250 BIGNUM *tmp;
251
252 /*
253 * 0 < B < A,
254 * (*) -sign*X*a == B (mod |n|),
255 * sign*Y*a == A (mod |n|)
256 */
257
258 /*
259 * Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked,
260 * BN_div_no_branch will be called eventually.
261 */
262 pA = &local_A;
263 /* BN_init() done at the top of the function. */
264 BN_with_flags(pA, A, BN_FLG_CONSTTIME);
265
266 /* (D, M) := (A/B, A%B) ... */
267 if (!BN_div_ct(D, M, pA, B, ctx))
268 goto err;
269
270 /* Now
271 * A = D*B + M;
272 * thus we have
273 * (**) sign*Y*a == D*B + M (mod |n|).
274 */
275 tmp = A; /* keep the BIGNUM object, the value does not matter */
276
277 /* (A, B) := (B, A mod B) ... */
278 A = B;
279 B = M;
280 /* ... so we have 0 <= B < A again */
281
282 /* Since the former M is now B and the former B is now A,
283 * (**) translates into
284 * sign*Y*a == D*A + B (mod |n|),
285 * i.e.
286 * sign*Y*a - D*A == B (mod |n|).
287 * Similarly, (*) translates into
288 * -sign*X*a == A (mod |n|).
289 *
290 * Thus,
291 * sign*Y*a + D*sign*X*a == B (mod |n|),
292 * i.e.
293 * sign*(Y + D*X)*a == B (mod |n|).
294 *
295 * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at
296 * -sign*X*a == B (mod |n|),
297 * sign*Y*a == A (mod |n|).
298 * Note that X and Y stay non-negative all the time.
299 */
300
301 if (!BN_mul(tmp, D, X, ctx))
302 goto err;
303 if (!BN_add(tmp, tmp, Y))
304 goto err;
305
306 M = Y; /* keep the BIGNUM object, the value does not matter */
307 Y = X;
308 X = tmp;
309 sign = -sign;
310 }
311
312 /*
313 * The while loop (Euclid's algorithm) ends when
314 * A == gcd(a,n);
315 */
316
317 if (!BN_copy(R, A))
318 goto err;
319 ret = R;
320err:
321 if ((ret == NULL) && (in == NULL))
322 BN_free(R);
323 BN_CTX_end(ctx);
324 return (ret);
325}
326
327int
328BN_gcd(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx)
329{
330 BIGNUM *a, *b, *t;
331 int ret = 0;
332
333
334 BN_CTX_start(ctx);
335 if ((a = BN_CTX_get(ctx)) == NULL)
336 goto err;
337 if ((b = BN_CTX_get(ctx)) == NULL)
338 goto err;
339
340 if (BN_copy(a, in_a) == NULL)
341 goto err;
342 if (BN_copy(b, in_b) == NULL)
343 goto err;
344 a->neg = 0;
345 b->neg = 0;
346
347 if (BN_cmp(a, b) < 0) {
348 t = a;
349 a = b;
350 b = t;
351 }
352 t = euclid(a, b);
353 if (t == NULL)
354 goto err;
355
356 if (BN_copy(r, t) == NULL)
357 goto err;
358 ret = 1;
359
360err:
361 BN_CTX_end(ctx);
362 return (ret);
363}
364
365int
366BN_gcd_ct(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx)
367{
368 if (BN_gcd_no_branch(r, in_a, in_b, ctx) == NULL)
369 return 0;
370 return 1;
371}
372
373int
374BN_gcd_nonct(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx)
375{
376 return BN_gcd(r, in_a, in_b, ctx);
377}
378
379/* BN_mod_inverse_no_branch is a special version of BN_mod_inverse.
380 * It does not contain branches that may leak sensitive information.
381 */
382static BIGNUM *
383BN_mod_inverse_no_branch(BIGNUM *in, const BIGNUM *a, const BIGNUM *n,
384 BN_CTX *ctx)
385{
386 BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL;
387 BIGNUM local_A, local_B;
388 BIGNUM *pA, *pB;
389 BIGNUM *ret = NULL;
390 int sign;
391
392
393 BN_init(&local_A);
394 BN_init(&local_B);
395
396 BN_CTX_start(ctx);
397 if ((A = BN_CTX_get(ctx)) == NULL)
398 goto err;
399 if ((B = BN_CTX_get(ctx)) == NULL)
400 goto err;
401 if ((X = BN_CTX_get(ctx)) == NULL)
402 goto err;
403 if ((D = BN_CTX_get(ctx)) == NULL)
404 goto err;
405 if ((M = BN_CTX_get(ctx)) == NULL)
406 goto err;
407 if ((Y = BN_CTX_get(ctx)) == NULL)
408 goto err;
409 if ((T = BN_CTX_get(ctx)) == NULL)
410 goto err;
411
412 if (in == NULL)
413 R = BN_new();
414 else
415 R = in;
416 if (R == NULL)
417 goto err;
418
419 if (!BN_one(X))
420 goto err;
421 BN_zero(Y);
422 if (BN_copy(B, a) == NULL)
423 goto err;
424 if (BN_copy(A, n) == NULL)
425 goto err;
426 A->neg = 0;
427
428 if (B->neg || (BN_ucmp(B, A) >= 0)) {
429 /*
430 * Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked,
431 * BN_div_no_branch will be called eventually.
432 */
433 pB = &local_B;
434 /* BN_init() done at the top of the function. */
435 BN_with_flags(pB, B, BN_FLG_CONSTTIME);
436 if (!BN_nnmod(B, pB, A, ctx))
437 goto err;
438 }
439 sign = -1;
440 /* From B = a mod |n|, A = |n| it follows that
441 *
442 * 0 <= B < A,
443 * -sign*X*a == B (mod |n|),
444 * sign*Y*a == A (mod |n|).
445 */
446
447 while (!BN_is_zero(B)) {
448 BIGNUM *tmp;
449
450 /*
451 * 0 < B < A,
452 * (*) -sign*X*a == B (mod |n|),
453 * sign*Y*a == A (mod |n|)
454 */
455
456 /*
457 * Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked,
458 * BN_div_no_branch will be called eventually.
459 */
460 pA = &local_A;
461 /* BN_init() done at the top of the function. */
462 BN_with_flags(pA, A, BN_FLG_CONSTTIME);
463
464 /* (D, M) := (A/B, A%B) ... */
465 if (!BN_div_ct(D, M, pA, B, ctx))
466 goto err;
467
468 /* Now
469 * A = D*B + M;
470 * thus we have
471 * (**) sign*Y*a == D*B + M (mod |n|).
472 */
473 tmp = A; /* keep the BIGNUM object, the value does not matter */
474
475 /* (A, B) := (B, A mod B) ... */
476 A = B;
477 B = M;
478 /* ... so we have 0 <= B < A again */
479
480 /* Since the former M is now B and the former B is now A,
481 * (**) translates into
482 * sign*Y*a == D*A + B (mod |n|),
483 * i.e.
484 * sign*Y*a - D*A == B (mod |n|).
485 * Similarly, (*) translates into
486 * -sign*X*a == A (mod |n|).
487 *
488 * Thus,
489 * sign*Y*a + D*sign*X*a == B (mod |n|),
490 * i.e.
491 * sign*(Y + D*X)*a == B (mod |n|).
492 *
493 * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at
494 * -sign*X*a == B (mod |n|),
495 * sign*Y*a == A (mod |n|).
496 * Note that X and Y stay non-negative all the time.
497 */
498
499 if (!BN_mul(tmp, D, X, ctx))
500 goto err;
501 if (!BN_add(tmp, tmp, Y))
502 goto err;
503
504 M = Y; /* keep the BIGNUM object, the value does not matter */
505 Y = X;
506 X = tmp;
507 sign = -sign;
508 }
509
510 /*
511 * The while loop (Euclid's algorithm) ends when
512 * A == gcd(a,n);
513 * we have
514 * sign*Y*a == A (mod |n|),
515 * where Y is non-negative.
516 */
517
518 if (sign < 0) {
519 if (!BN_sub(Y, n, Y))
520 goto err;
521 }
522 /* Now Y*a == A (mod |n|). */
244 523
524 if (BN_is_one(A)) {
525 /* Y*a == 1 (mod |n|) */
526 if (!Y->neg && BN_ucmp(Y, n) < 0) {
527 if (!BN_copy(R, Y))
528 goto err;
529 } else {
530 if (!BN_nnmod(R, Y, n, ctx))
531 goto err;
532 }
533 } else {
534 BNerror(BN_R_NO_INVERSE);
535 goto err;
536 }
537 ret = R;
538
539err:
540 if ((ret == NULL) && (in == NULL))
541 BN_free(R);
542 BN_CTX_end(ctx);
543 return (ret);
544}
545
546/* solves ax == 1 (mod n) */
245static BIGNUM * 547static BIGNUM *
246BN_mod_inverse_internal(BIGNUM *in, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx, 548BN_mod_inverse_internal(BIGNUM *in, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx,
247 int ct) 549 int ct)
@@ -551,314 +853,3 @@ BN_mod_inverse_ct(BIGNUM *in, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx)
551{ 853{
552 return BN_mod_inverse_internal(in, a, n, ctx, 1); 854 return BN_mod_inverse_internal(in, a, n, ctx, 1);
553} 855}
554
555/* BN_mod_inverse_no_branch is a special version of BN_mod_inverse.
556 * It does not contain branches that may leak sensitive information.
557 */
558static BIGNUM *
559BN_mod_inverse_no_branch(BIGNUM *in, const BIGNUM *a, const BIGNUM *n,
560 BN_CTX *ctx)
561{
562 BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL;
563 BIGNUM local_A, local_B;
564 BIGNUM *pA, *pB;
565 BIGNUM *ret = NULL;
566 int sign;
567
568
569 BN_init(&local_A);
570 BN_init(&local_B);
571
572 BN_CTX_start(ctx);
573 if ((A = BN_CTX_get(ctx)) == NULL)
574 goto err;
575 if ((B = BN_CTX_get(ctx)) == NULL)
576 goto err;
577 if ((X = BN_CTX_get(ctx)) == NULL)
578 goto err;
579 if ((D = BN_CTX_get(ctx)) == NULL)
580 goto err;
581 if ((M = BN_CTX_get(ctx)) == NULL)
582 goto err;
583 if ((Y = BN_CTX_get(ctx)) == NULL)
584 goto err;
585 if ((T = BN_CTX_get(ctx)) == NULL)
586 goto err;
587
588 if (in == NULL)
589 R = BN_new();
590 else
591 R = in;
592 if (R == NULL)
593 goto err;
594
595 if (!BN_one(X))
596 goto err;
597 BN_zero(Y);
598 if (BN_copy(B, a) == NULL)
599 goto err;
600 if (BN_copy(A, n) == NULL)
601 goto err;
602 A->neg = 0;
603
604 if (B->neg || (BN_ucmp(B, A) >= 0)) {
605 /*
606 * Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked,
607 * BN_div_no_branch will be called eventually.
608 */
609 pB = &local_B;
610 /* BN_init() done at the top of the function. */
611 BN_with_flags(pB, B, BN_FLG_CONSTTIME);
612 if (!BN_nnmod(B, pB, A, ctx))
613 goto err;
614 }
615 sign = -1;
616 /* From B = a mod |n|, A = |n| it follows that
617 *
618 * 0 <= B < A,
619 * -sign*X*a == B (mod |n|),
620 * sign*Y*a == A (mod |n|).
621 */
622
623 while (!BN_is_zero(B)) {
624 BIGNUM *tmp;
625
626 /*
627 * 0 < B < A,
628 * (*) -sign*X*a == B (mod |n|),
629 * sign*Y*a == A (mod |n|)
630 */
631
632 /*
633 * Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked,
634 * BN_div_no_branch will be called eventually.
635 */
636 pA = &local_A;
637 /* BN_init() done at the top of the function. */
638 BN_with_flags(pA, A, BN_FLG_CONSTTIME);
639
640 /* (D, M) := (A/B, A%B) ... */
641 if (!BN_div_ct(D, M, pA, B, ctx))
642 goto err;
643
644 /* Now
645 * A = D*B + M;
646 * thus we have
647 * (**) sign*Y*a == D*B + M (mod |n|).
648 */
649 tmp = A; /* keep the BIGNUM object, the value does not matter */
650
651 /* (A, B) := (B, A mod B) ... */
652 A = B;
653 B = M;
654 /* ... so we have 0 <= B < A again */
655
656 /* Since the former M is now B and the former B is now A,
657 * (**) translates into
658 * sign*Y*a == D*A + B (mod |n|),
659 * i.e.
660 * sign*Y*a - D*A == B (mod |n|).
661 * Similarly, (*) translates into
662 * -sign*X*a == A (mod |n|).
663 *
664 * Thus,
665 * sign*Y*a + D*sign*X*a == B (mod |n|),
666 * i.e.
667 * sign*(Y + D*X)*a == B (mod |n|).
668 *
669 * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at
670 * -sign*X*a == B (mod |n|),
671 * sign*Y*a == A (mod |n|).
672 * Note that X and Y stay non-negative all the time.
673 */
674
675 if (!BN_mul(tmp, D, X, ctx))
676 goto err;
677 if (!BN_add(tmp, tmp, Y))
678 goto err;
679
680 M = Y; /* keep the BIGNUM object, the value does not matter */
681 Y = X;
682 X = tmp;
683 sign = -sign;
684 }
685
686 /*
687 * The while loop (Euclid's algorithm) ends when
688 * A == gcd(a,n);
689 * we have
690 * sign*Y*a == A (mod |n|),
691 * where Y is non-negative.
692 */
693
694 if (sign < 0) {
695 if (!BN_sub(Y, n, Y))
696 goto err;
697 }
698 /* Now Y*a == A (mod |n|). */
699
700 if (BN_is_one(A)) {
701 /* Y*a == 1 (mod |n|) */
702 if (!Y->neg && BN_ucmp(Y, n) < 0) {
703 if (!BN_copy(R, Y))
704 goto err;
705 } else {
706 if (!BN_nnmod(R, Y, n, ctx))
707 goto err;
708 }
709 } else {
710 BNerror(BN_R_NO_INVERSE);
711 goto err;
712 }
713 ret = R;
714
715err:
716 if ((ret == NULL) && (in == NULL))
717 BN_free(R);
718 BN_CTX_end(ctx);
719 return (ret);
720}
721
722/*
723 * BN_gcd_no_branch is a special version of BN_mod_inverse_no_branch.
724 * that returns the GCD.
725 */
726static BIGNUM *
727BN_gcd_no_branch(BIGNUM *in, const BIGNUM *a, const BIGNUM *n,
728 BN_CTX *ctx)
729{
730 BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL;
731 BIGNUM local_A, local_B;
732 BIGNUM *pA, *pB;
733 BIGNUM *ret = NULL;
734 int sign;
735
736 if (in == NULL)
737 goto err;
738 R = in;
739
740 BN_init(&local_A);
741 BN_init(&local_B);
742
743
744 BN_CTX_start(ctx);
745 if ((A = BN_CTX_get(ctx)) == NULL)
746 goto err;
747 if ((B = BN_CTX_get(ctx)) == NULL)
748 goto err;
749 if ((X = BN_CTX_get(ctx)) == NULL)
750 goto err;
751 if ((D = BN_CTX_get(ctx)) == NULL)
752 goto err;
753 if ((M = BN_CTX_get(ctx)) == NULL)
754 goto err;
755 if ((Y = BN_CTX_get(ctx)) == NULL)
756 goto err;
757 if ((T = BN_CTX_get(ctx)) == NULL)
758 goto err;
759
760 if (!BN_one(X))
761 goto err;
762 BN_zero(Y);
763 if (BN_copy(B, a) == NULL)
764 goto err;
765 if (BN_copy(A, n) == NULL)
766 goto err;
767 A->neg = 0;
768
769 if (B->neg || (BN_ucmp(B, A) >= 0)) {
770 /*
771 * Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked,
772 * BN_div_no_branch will be called eventually.
773 */
774 pB = &local_B;
775 /* BN_init() done at the top of the function. */
776 BN_with_flags(pB, B, BN_FLG_CONSTTIME);
777 if (!BN_nnmod(B, pB, A, ctx))
778 goto err;
779 }
780 sign = -1;
781 /* From B = a mod |n|, A = |n| it follows that
782 *
783 * 0 <= B < A,
784 * -sign*X*a == B (mod |n|),
785 * sign*Y*a == A (mod |n|).
786 */
787
788 while (!BN_is_zero(B)) {
789 BIGNUM *tmp;
790
791 /*
792 * 0 < B < A,
793 * (*) -sign*X*a == B (mod |n|),
794 * sign*Y*a == A (mod |n|)
795 */
796
797 /*
798 * Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked,
799 * BN_div_no_branch will be called eventually.
800 */
801 pA = &local_A;
802 /* BN_init() done at the top of the function. */
803 BN_with_flags(pA, A, BN_FLG_CONSTTIME);
804
805 /* (D, M) := (A/B, A%B) ... */
806 if (!BN_div_ct(D, M, pA, B, ctx))
807 goto err;
808
809 /* Now
810 * A = D*B + M;
811 * thus we have
812 * (**) sign*Y*a == D*B + M (mod |n|).
813 */
814 tmp = A; /* keep the BIGNUM object, the value does not matter */
815
816 /* (A, B) := (B, A mod B) ... */
817 A = B;
818 B = M;
819 /* ... so we have 0 <= B < A again */
820
821 /* Since the former M is now B and the former B is now A,
822 * (**) translates into
823 * sign*Y*a == D*A + B (mod |n|),
824 * i.e.
825 * sign*Y*a - D*A == B (mod |n|).
826 * Similarly, (*) translates into
827 * -sign*X*a == A (mod |n|).
828 *
829 * Thus,
830 * sign*Y*a + D*sign*X*a == B (mod |n|),
831 * i.e.
832 * sign*(Y + D*X)*a == B (mod |n|).
833 *
834 * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at
835 * -sign*X*a == B (mod |n|),
836 * sign*Y*a == A (mod |n|).
837 * Note that X and Y stay non-negative all the time.
838 */
839
840 if (!BN_mul(tmp, D, X, ctx))
841 goto err;
842 if (!BN_add(tmp, tmp, Y))
843 goto err;
844
845 M = Y; /* keep the BIGNUM object, the value does not matter */
846 Y = X;
847 X = tmp;
848 sign = -sign;
849 }
850
851 /*
852 * The while loop (Euclid's algorithm) ends when
853 * A == gcd(a,n);
854 */
855
856 if (!BN_copy(R, A))
857 goto err;
858 ret = R;
859err:
860 if ((ret == NULL) && (in == NULL))
861 BN_free(R);
862 BN_CTX_end(ctx);
863 return (ret);
864}
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-22 20:15:12 +0000