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