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