Convert memset calls to OPENSSL_cleanse
[openssl.git] / crypto / bn / bn_gcd.c
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)
129         goto err;
130
131     if (BN_copy(a, in_a) == NULL)
132         goto err;
133     if (BN_copy(b, in_b) == NULL)
134         goto err;
135     a->neg = 0;
136     b->neg = 0;
137
138     if (BN_cmp(a, b) < 0) {
139         t = a;
140         a = b;
141         b = t;
142     }
143     t = euclid(a, b);
144     if (t == NULL)
145         goto err;
146
147     if (BN_copy(r, t) == NULL)
148         goto err;
149     ret = 1;
150  err:
151     BN_CTX_end(ctx);
152     bn_check_top(r);
153     return (ret);
154 }
155
156 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     while (!BN_is_zero(b)) {
166         /* 0 < b <= a */
167
168         if (BN_is_odd(a)) {
169             if (BN_is_odd(b)) {
170                 if (!BN_sub(a, a, b))
171                     goto err;
172                 if (!BN_rshift1(a, a))
173                     goto err;
174                 if (BN_cmp(a, b) < 0) {
175                     t = a;
176                     a = b;
177                     b = t;
178                 }
179             } else {            /* a odd - b even */
180
181                 if (!BN_rshift1(b, b))
182                     goto err;
183                 if (BN_cmp(a, b) < 0) {
184                     t = a;
185                     a = b;
186                     b = t;
187                 }
188             }
189         } else {                /* a is even */
190
191             if (BN_is_odd(b)) {
192                 if (!BN_rshift1(a, a))
193                     goto err;
194                 if (BN_cmp(a, b) < 0) {
195                     t = a;
196                     a = b;
197                     b = t;
198                 }
199             } else {            /* a even - b even */
200
201                 if (!BN_rshift1(a, a))
202                     goto err;
203                 if (!BN_rshift1(b, b))
204                     goto err;
205                 shifts++;
206             }
207         }
208         /* 0 <= b <= a */
209     }
210
211     if (shifts) {
212         if (!BN_lshift(a, a, shifts))
213             goto err;
214     }
215     bn_check_top(a);
216     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 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     if ((BN_get_flags(a, BN_FLG_CONSTTIME) != 0)
234         || (BN_get_flags(n, BN_FLG_CONSTTIME) != 0)) {
235         return BN_mod_inverse_no_branch(in, a, n, ctx);
236     }
237
238     bn_check_top(a);
239     bn_check_top(n);
240
241     BN_CTX_start(ctx);
242     A = BN_CTX_get(ctx);
243     B = BN_CTX_get(ctx);
244     X = BN_CTX_get(ctx);
245     D = BN_CTX_get(ctx);
246     M = BN_CTX_get(ctx);
247     Y = BN_CTX_get(ctx);
248     T = BN_CTX_get(ctx);
249     if (T == NULL)
250         goto err;
251
252     if (in == NULL)
253         R = BN_new();
254     else
255         R = in;
256     if (R == NULL)
257         goto err;
258
259     BN_one(X);
260     BN_zero(Y);
261     if (BN_copy(B, a) == NULL)
262         goto err;
263     if (BN_copy(A, n) == NULL)
264         goto err;
265     A->neg = 0;
266     if (B->neg || (BN_ucmp(B, A) >= 0)) {
267         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     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         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             while (!BN_is_bit_set(B, shift)) { /* note that 0 < B */
303                 shift++;
304
305                 if (BN_is_odd(X)) {
306                     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                 if (!BN_rshift1(X, X))
313                     goto err;
314             }
315             if (shift > 0) {
316                 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             while (!BN_is_bit_set(A, shift)) { /* note that 0 < A */
325                 shift++;
326
327                 if (BN_is_odd(Y)) {
328                     if (!BN_uadd(Y, Y, n))
329                         goto err;
330                 }
331                 /* now Y is even */
332                 if (!BN_rshift1(Y, Y))
333                     goto err;
334             }
335             if (shift > 0) {
336                 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             if (BN_ucmp(B, A) >= 0) {
353                 /* -sign*(X + Y)*a == B - A  (mod |n|) */
354                 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                 if (!BN_usub(B, B, A))
361                     goto err;
362             } else {
363                 /*  sign*(X + Y)*a == A - B  (mod |n|) */
364                 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                 if (!BN_usub(A, A, B))
371                     goto err;
372             }
373         }
374     } else {
375         /* general inversion algorithm */
376
377         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             if (BN_num_bits(A) == BN_num_bits(B)) {
388                 if (!BN_one(D))
389                     goto err;
390                 if (!BN_sub(M, A, B))
391                     goto err;
392             } else if (BN_num_bits(A) == BN_num_bits(B) + 1) {
393                 /* A/B is 1, 2, or 3 */
394                 if (!BN_lshift1(T, B))
395                     goto err;
396                 if (BN_ucmp(A, T) < 0) {
397                     /* A < 2*B, so D=1 */
398                     if (!BN_one(D))
399                         goto err;
400                     if (!BN_sub(M, A, B))
401                         goto err;
402                 } else {
403                     /* A >= 2*B, so D=2 or D=3 */
404                     if (!BN_sub(M, A, T))
405                         goto err;
406                     if (!BN_add(D, T, B))
407                         goto err; /* use D (:= 3*B) as temp */
408                     if (BN_ucmp(A, D) < 0) {
409                         /* A < 3*B, so D=2 */
410                         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                         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                         if (!BN_sub(M, M, B))
423                             goto err;
424                     }
425                 }
426             } else {
427                 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             if (BN_is_one(D)) {
471                 if (!BN_add(tmp, X, Y))
472                     goto err;
473             } else {
474                 if (BN_is_word(D, 2)) {
475                     if (!BN_lshift1(tmp, X))
476                         goto err;
477                 } else if (BN_is_word(D, 4)) {
478                     if (!BN_lshift(tmp, X, 2))
479                         goto err;
480                 } else if (D->top == 1) {
481                     if (!BN_copy(tmp, X))
482                         goto err;
483                     if (!BN_mul_word(tmp, D->d[0]))
484                         goto err;
485                 } else {
486                     if (!BN_mul(tmp, D, X, ctx))
487                         goto err;
488                 }
489                 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             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     if (sign < 0) {
510         if (!BN_sub(Y, n, Y))
511             goto err;
512     }
513     /* Now  Y*a  ==  A  (mod |n|).  */
514
515     if (BN_is_one(A)) {
516         /* Y*a == 1  (mod |n|) */
517         if (!Y->neg && BN_ucmp(Y, n) < 0) {
518             if (!BN_copy(R, Y))
519                 goto err;
520         } else {
521             if (!BN_nnmod(R, Y, n, ctx))
522                 goto err;
523         }
524     } else {
525         BNerr(BN_F_BN_MOD_INVERSE, BN_R_NO_INVERSE);
526         goto err;
527     }
528     ret = R;
529  err:
530     if ((ret == NULL) && (in == NULL))
531         BN_free(R);
532     BN_CTX_end(ctx);
533     bn_check_top(ret);
534     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 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     BN_CTX_start(ctx);
555     A = BN_CTX_get(ctx);
556     B = BN_CTX_get(ctx);
557     X = BN_CTX_get(ctx);
558     D = BN_CTX_get(ctx);
559     M = BN_CTX_get(ctx);
560     Y = BN_CTX_get(ctx);
561     T = BN_CTX_get(ctx);
562     if (T == NULL)
563         goto err;
564
565     if (in == NULL)
566         R = BN_new();
567     else
568         R = in;
569     if (R == NULL)
570         goto err;
571
572     BN_one(X);
573     BN_zero(Y);
574     if (BN_copy(B, a) == NULL)
575         goto err;
576     if (BN_copy(A, n) == NULL)
577         goto err;
578     A->neg = 0;
579
580     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         local_B.flags = 0;
587         BN_with_flags(pB, B, BN_FLG_CONSTTIME);
588         if (!BN_nnmod(B, pB, A, ctx))
589             goto err;
590     }
591     sign = -1;
592     /*-
593      * From  B = a mod |n|,  A = |n|  it follows that
594      *
595      *      0 <= B < A,
596      *     -sign*X*a  ==  B   (mod |n|),
597      *      sign*Y*a  ==  A   (mod |n|).
598      */
599
600     while (!BN_is_zero(B)) {
601         BIGNUM *tmp;
602
603         /*-
604          *      0 < B < A,
605          * (*) -sign*X*a  ==  B   (mod |n|),
606          *      sign*Y*a  ==  A   (mod |n|)
607          */
608
609         /*
610          * Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked,
611          * BN_div_no_branch will be called eventually.
612          */
613         pA = &local_A;
614         local_A.flags = 0;
615         BN_with_flags(pA, A, BN_FLG_CONSTTIME);
616
617         /* (D, M) := (A/B, A%B) ... */
618         if (!BN_div(D, M, pA, B, ctx))
619             goto err;
620
621         /*-
622          * Now
623          *      A = D*B + M;
624          * thus we have
625          * (**)  sign*Y*a  ==  D*B + M   (mod |n|).
626          */
627
628         tmp = A;                /* keep the BIGNUM object, the value does not
629                                  * matter */
630
631         /* (A, B) := (B, A mod B) ... */
632         A = B;
633         B = M;
634         /* ... so we have  0 <= B < A  again */
635
636         /*-
637          * Since the former  M  is now  B  and the former  B  is now  A,
638          * (**) translates into
639          *       sign*Y*a  ==  D*A + B    (mod |n|),
640          * i.e.
641          *       sign*Y*a - D*A  ==  B    (mod |n|).
642          * Similarly, (*) translates into
643          *      -sign*X*a  ==  A          (mod |n|).
644          *
645          * Thus,
646          *   sign*Y*a + D*sign*X*a  ==  B  (mod |n|),
647          * i.e.
648          *        sign*(Y + D*X)*a  ==  B  (mod |n|).
649          *
650          * So if we set  (X, Y, sign) := (Y + D*X, X, -sign),  we arrive back at
651          *      -sign*X*a  ==  B   (mod |n|),
652          *       sign*Y*a  ==  A   (mod |n|).
653          * Note that  X  and  Y  stay non-negative all the time.
654          */
655
656         if (!BN_mul(tmp, D, X, ctx))
657             goto err;
658         if (!BN_add(tmp, tmp, Y))
659             goto err;
660
661         M = Y;                  /* keep the BIGNUM object, the value does not
662                                  * matter */
663         Y = X;
664         X = tmp;
665         sign = -sign;
666     }
667
668     /*-
669      * The while loop (Euclid's algorithm) ends when
670      *      A == gcd(a,n);
671      * we have
672      *       sign*Y*a  ==  A  (mod |n|),
673      * where  Y  is non-negative.
674      */
675
676     if (sign < 0) {
677         if (!BN_sub(Y, n, Y))
678             goto err;
679     }
680     /* Now  Y*a  ==  A  (mod |n|).  */
681
682     if (BN_is_one(A)) {
683         /* Y*a == 1  (mod |n|) */
684         if (!Y->neg && BN_ucmp(Y, n) < 0) {
685             if (!BN_copy(R, Y))
686                 goto err;
687         } else {
688             if (!BN_nnmod(R, Y, n, ctx))
689                 goto err;
690         }
691     } else {
692         BNerr(BN_F_BN_MOD_INVERSE_NO_BRANCH, BN_R_NO_INVERSE);
693         goto err;
694     }
695     ret = R;
696  err:
697     if ((ret == NULL) && (in == NULL))
698         BN_free(R);
699     BN_CTX_end(ctx);
700     bn_check_top(ret);
701     return (ret);
702 }