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 EXPORT_C 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) goto err;

   129 

   130 	if (BN_copy(a,in_a) == NULL) goto err;

   131 	if (BN_copy(b,in_b) == NULL) goto err;

   132 	a->neg = 0;

   133 	b->neg = 0;

   134 

   135 	if (BN_cmp(a,b) < 0) { t=a; a=b; b=t; }

   136 	t=euclid(a,b);

   137 	if (t == NULL) goto err;

   138 

   139 	if (BN_copy(r,t) == NULL) goto err;

   140 	ret=1;

   141 err:

   142 	BN_CTX_end(ctx);

   143 	bn_check_top(r);

   144 	return(ret);

   145 	}

   146 

   147 static BIGNUM *euclid(BIGNUM *a, BIGNUM *b)

   148 	{

   149 	BIGNUM *t;

   150 	int shifts=0;

   151 

   152 	bn_check_top(a);

   153 	bn_check_top(b);

   154 

   155 	/* 0 <= b <= a */

   156 	while (!BN_is_zero(b))

   157 		{

   158 		/* 0 < b <= a */

   159 

   160 		if (BN_is_odd(a))

   161 			{

   162 			if (BN_is_odd(b))

   163 				{

   164 				if (!BN_sub(a,a,b)) goto err;

   165 				if (!BN_rshift1(a,a)) goto err;

   166 				if (BN_cmp(a,b) < 0)

   167 					{ t=a; a=b; b=t; }

   168 				}

   169 			else		/* a odd - b even */

   170 				{

   171 				if (!BN_rshift1(b,b)) goto err;

   172 				if (BN_cmp(a,b) < 0)

   173 					{ t=a; a=b; b=t; }

   174 				}

   175 			}

   176 		else			/* a is even */

   177 			{

   178 			if (BN_is_odd(b))

   179 				{

   180 				if (!BN_rshift1(a,a)) goto err;

   181 				if (BN_cmp(a,b) < 0)

   182 					{ t=a; a=b; b=t; }

   183 				}

   184 			else		/* a even - b even */

   185 				{

   186 				if (!BN_rshift1(a,a)) goto err;

   187 				if (!BN_rshift1(b,b)) goto err;

   188 				shifts++;

   189 				}

   190 			}

   191 		/* 0 <= b <= a */

   192 		}

   193 

   194 	if (shifts)

   195 		{

   196 		if (!BN_lshift(a,a,shifts)) goto err;

   197 		}

   198 	bn_check_top(a);

   199 	return(a);

   200 err:

   201 	return(NULL);

   202 	}

   203 

   204 

   205 /* solves ax == 1 (mod n) */

   206 static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in,

   207         const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx);

   208 EXPORT_C BIGNUM *BN_mod_inverse(BIGNUM *in,

   209 	const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx)

   210 	{

   211 	BIGNUM *A,*B,*X,*Y,*M,*D,*T,*R=NULL;

   212 	BIGNUM *ret=NULL;

   213 	int sign;

   214 	if ((BN_get_flags(a, BN_FLG_CONSTTIME) != 0) || (BN_get_flags(n, BN_FLG_CONSTTIME) != 0))

   215 		{

   216 		return BN_mod_inverse_no_branch(in, a, n, ctx);

   217 		}

   218 

   219 	bn_check_top(a);

   220 	bn_check_top(n);

   221 

   222 	BN_CTX_start(ctx);

   223 	A = BN_CTX_get(ctx);

   224 	B = BN_CTX_get(ctx);

   225 	X = BN_CTX_get(ctx);

   226 	D = BN_CTX_get(ctx);

   227 	M = BN_CTX_get(ctx);

   228 	Y = BN_CTX_get(ctx);

   229 	T = BN_CTX_get(ctx);

   230 	if (T == NULL) goto err;

   231 

   232 	if (in == NULL)

   233 		R=BN_new();

   234 	else

   235 		R=in;

   236 	if (R == NULL) goto err;

   237 

   238 	BN_one(X);

   239 	BN_zero(Y);

   240 	if (BN_copy(B,a) == NULL) goto err;

   241 	if (BN_copy(A,n) == NULL) goto err;

   242 	A->neg = 0;

   243 	if (B->neg || (BN_ucmp(B, A) >= 0))

   244 		{

   245 		if (!BN_nnmod(B, B, A, ctx)) goto err;

   246 		}

   247 	sign = -1;

   248 	/* From  B = a mod |n|,  A = |n|  it follows that

   249 	 *

   250 	 *      0 <= B < A,

   251 	 *     -sign*X*a  ==  B   (mod |n|),

   252 	 *      sign*Y*a  ==  A   (mod |n|).

   253 	 */

   254 

   255 	if (BN_is_odd(n) && (BN_num_bits(n) <= (BN_BITS <= 32 ? 450 : 2048)))

   256 		{

   257 		/* Binary inversion algorithm; requires odd modulus.

   258 		 * This is faster than the general algorithm if the modulus

   259 		 * is sufficiently small (about 400 .. 500 bits on 32-bit

   260 		 * sytems, but much more on 64-bit systems) */

   261 		int shift;

   262 		

   263 		while (!BN_is_zero(B))

   264 			{

   265 			/*

   266 			 *      0 < B < |n|,

   267 			 *      0 < A <= |n|,

   268 			 * (1) -sign*X*a  ==  B   (mod |n|),

   269 			 * (2)  sign*Y*a  ==  A   (mod |n|)

   270 			 */

   271 

   272 			/* Now divide  B  by the maximum possible power of two in the integers,

   273 			 * and divide  X  by the same value mod |n|.

   274 			 * When we're done, (1) still holds. */

   275 			shift = 0;

   276 			while (!BN_is_bit_set(B, shift)) /* note that 0 < B */

   277 				{

   278 				shift++;

   279 				

   280 				if (BN_is_odd(X))

   281 					{

   282 					if (!BN_uadd(X, X, n)) goto err;

   283 					}

   284 				/* now X is even, so we can easily divide it by two */

   285 				if (!BN_rshift1(X, X)) goto err;

   286 				}

   287 			if (shift > 0)

   288 				{

   289 				if (!BN_rshift(B, B, shift)) goto err;

   290 				}

   291 

   292 

   293 			/* Same for  A  and  Y.  Afterwards, (2) still holds. */

   294 			shift = 0;

   295 			while (!BN_is_bit_set(A, shift)) /* note that 0 < A */

   296 				{

   297 				shift++;

   298 				

   299 				if (BN_is_odd(Y))

   300 					{

   301 					if (!BN_uadd(Y, Y, n)) goto err;

   302 					}

   303 				/* now Y is even */

   304 				if (!BN_rshift1(Y, Y)) goto err;

   305 				}

   306 			if (shift > 0)

   307 				{

   308 				if (!BN_rshift(A, A, shift)) goto err;

   309 				}

   310 

   311 			

   312 			/* We still have (1) and (2).

   313 			 * Both  A  and  B  are odd.

   314 			 * The following computations ensure that

   315 			 *

   316 			 *     0 <= B < |n|,

   317 			 *      0 < A < |n|,

   318 			 * (1) -sign*X*a  ==  B   (mod |n|),

   319 			 * (2)  sign*Y*a  ==  A   (mod |n|),

   320 			 *

   321 			 * and that either  A  or  B  is even in the next iteration.

   322 			 */

   323 			if (BN_ucmp(B, A) >= 0)

   324 				{

   325 				/* -sign*(X + Y)*a == B - A  (mod |n|) */

   326 				if (!BN_uadd(X, X, Y)) goto err;

   327 				/* NB: we could use BN_mod_add_quick(X, X, Y, n), but that

   328 				 * actually makes the algorithm slower */

   329 				if (!BN_usub(B, B, A)) goto err;

   330 				}

   331 			else

   332 				{

   333 				/*  sign*(X + Y)*a == A - B  (mod |n|) */

   334 				if (!BN_uadd(Y, Y, X)) goto err;

   335 				/* as above, BN_mod_add_quick(Y, Y, X, n) would slow things down */

   336 				if (!BN_usub(A, A, B)) goto err;

   337 				}

   338 			}

   339 		}

   340 	else

   341 		{

   342 		/* general inversion algorithm */

   343 

   344 		while (!BN_is_zero(B))

   345 			{

   346 			BIGNUM *tmp;

   347 			

   348 			/*

   349 			 *      0 < B < A,

   350 			 * (*) -sign*X*a  ==  B   (mod |n|),

   351 			 *      sign*Y*a  ==  A   (mod |n|)

   352 			 */

   353 			

   354 			/* (D, M) := (A/B, A%B) ... */

   355 			if (BN_num_bits(A) == BN_num_bits(B))

   356 				{

   357 				if (!BN_one(D)) goto err;

   358 				if (!BN_sub(M,A,B)) goto err;

   359 				}

   360 			else if (BN_num_bits(A) == BN_num_bits(B) + 1)

   361 				{

   362 				/* A/B is 1, 2, or 3 */

   363 				if (!BN_lshift1(T,B)) goto err;

   364 				if (BN_ucmp(A,T) < 0)

   365 					{

   366 					/* A < 2*B, so D=1 */

   367 					if (!BN_one(D)) goto err;

   368 					if (!BN_sub(M,A,B)) goto err;

   369 					}

   370 				else

   371 					{

   372 					/* A >= 2*B, so D=2 or D=3 */

   373 					if (!BN_sub(M,A,T)) goto err;

   374 					if (!BN_add(D,T,B)) goto err; /* use D (:= 3*B) as temp */

   375 					if (BN_ucmp(A,D) < 0)

   376 						{

   377 						/* A < 3*B, so D=2 */

   378 						if (!BN_set_word(D,2)) goto err;

   379 						/* M (= A - 2*B) already has the correct value */

   380 						}

   381 					else

   382 						{

   383 						/* only D=3 remains */

   384 						if (!BN_set_word(D,3)) goto err;

   385 						/* currently  M = A - 2*B,  but we need  M = A - 3*B */

   386 						if (!BN_sub(M,M,B)) goto err;

   387 						}

   388 					}

   389 				}

   390 			else

   391 				{

   392 				if (!BN_div(D,M,A,B,ctx)) goto err;

   393 				}

   394 			

   395 			/* Now

   396 			 *      A = D*B + M;

   397 			 * thus we have

   398 			 * (**)  sign*Y*a  ==  D*B + M   (mod |n|).

   399 			 */

   400 			

   401 			tmp=A; /* keep the BIGNUM object, the value does not matter */

   402 			

   403 			/* (A, B) := (B, A mod B) ... */

   404 			A=B;

   405 			B=M;

   406 			/* ... so we have  0 <= B < A  again */

   407 			

   408 			/* Since the former  M  is now  B  and the former  B  is now  A,

   409 			 * (**) translates into

   410 			 *       sign*Y*a  ==  D*A + B    (mod |n|),

   411 			 * i.e.

   412 			 *       sign*Y*a - D*A  ==  B    (mod |n|).

   413 			 * Similarly, (*) translates into

   414 			 *      -sign*X*a  ==  A          (mod |n|).

   415 			 *

   416 			 * Thus,

   417 			 *   sign*Y*a + D*sign*X*a  ==  B  (mod |n|),

   418 			 * i.e.

   419 			 *        sign*(Y + D*X)*a  ==  B  (mod |n|).

   420 			 *

   421 			 * So if we set  (X, Y, sign) := (Y + D*X, X, -sign),  we arrive back at

   422 			 *      -sign*X*a  ==  B   (mod |n|),

   423 			 *       sign*Y*a  ==  A   (mod |n|).

   424 			 * Note that  X  and  Y  stay non-negative all the time.

   425 			 */

   426 			

   427 			/* most of the time D is very small, so we can optimize tmp := D*X+Y */

   428 			if (BN_is_one(D))

   429 				{

   430 				if (!BN_add(tmp,X,Y)) goto err;

   431 				}

   432 			else

   433 				{

   434 				if (BN_is_word(D,2))

   435 					{

   436 					if (!BN_lshift1(tmp,X)) goto err;

   437 					}

   438 				else if (BN_is_word(D,4))

   439 					{

   440 					if (!BN_lshift(tmp,X,2)) goto err;

   441 					}

   442 				else if (D->top == 1)

   443 					{

   444 					if (!BN_copy(tmp,X)) goto err;

   445 					if (!BN_mul_word(tmp,D->d[0])) goto err;

   446 					}

   447 				else

   448 					{

   449 					if (!BN_mul(tmp,D,X,ctx)) goto err;

   450 					}

   451 				if (!BN_add(tmp,tmp,Y)) goto err;

   452 				}

   453 			

   454 			M=Y; /* keep the BIGNUM object, the value does not matter */

   455 			Y=X;

   456 			X=tmp;

   457 			sign = -sign;

   458 			}

   459 		}

   460 		

   461 	/*

   462 	 * The while loop (Euclid's algorithm) ends when

   463 	 *      A == gcd(a,n);

   464 	 * we have

   465 	 *       sign*Y*a  ==  A  (mod |n|),

   466 	 * where  Y  is non-negative.

   467 	 */

   468 

   469 	if (sign < 0)

   470 		{

   471 		if (!BN_sub(Y,n,Y)) goto err;

   472 		}

   473 	/* Now  Y*a  ==  A  (mod |n|).  */

   474 	

   475 

   476 	if (BN_is_one(A))

   477 		{

   478 		/* Y*a == 1  (mod |n|) */

   479 		if (!Y->neg && BN_ucmp(Y,n) < 0)

   480 			{

   481 			if (!BN_copy(R,Y)) goto err;

   482 			}

   483 		else

   484 			{

   485 			if (!BN_nnmod(R,Y,n,ctx)) goto err;

   486 			}

   487 		}

   488 	else

   489 		{

   490 		BNerr(BN_F_BN_MOD_INVERSE,BN_R_NO_INVERSE);

   491 		goto err;

   492 		}

   493 	ret=R;

   494 err:

   495 	if ((ret == NULL) && (in == NULL)) BN_free(R);

   496 	BN_CTX_end(ctx);

   497 	bn_check_top(ret);

   498 	return(ret);

   499 	}

   500 

   501 

   502 /* BN_mod_inverse_no_branch is a special version of BN_mod_inverse. 

   503  * It does not contain branches that may leak sensitive information.

   504  */

   505 static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in,

   506 	const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx)

   507 	{

   508 	BIGNUM *A,*B,*X,*Y,*M,*D,*T,*R=NULL;

   509 	BIGNUM local_A, local_B;

   510 	BIGNUM *pA, *pB;

   511 	BIGNUM *ret=NULL;

   512 	int sign;

   513 

   514 	bn_check_top(a);

   515 	bn_check_top(n);

   516 

   517 	BN_CTX_start(ctx);

   518 	A = BN_CTX_get(ctx);

   519 	B = BN_CTX_get(ctx);

   520 	X = BN_CTX_get(ctx);

   521 	D = BN_CTX_get(ctx);

   522 	M = BN_CTX_get(ctx);

   523 	Y = BN_CTX_get(ctx);

   524 	T = BN_CTX_get(ctx);

   525 	if (T == NULL) goto err;

   526 

   527 	if (in == NULL)

   528 		R=BN_new();

   529 	else

   530 		R=in;

   531 	if (R == NULL) goto err;

   532 

   533 	BN_one(X);

   534 	BN_zero(Y);

   535 	if (BN_copy(B,a) == NULL) goto err;

   536 	if (BN_copy(A,n) == NULL) goto err;

   537 	A->neg = 0;

   538 

   539 	if (B->neg || (BN_ucmp(B, A) >= 0))

   540 		{

   541 		/* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked,

   542 	 	 * BN_div_no_branch will be called eventually.

   543 	 	 */

   544 		pB = &local_B;

   545 		BN_with_flags(pB, B, BN_FLG_CONSTTIME);	

   546 		if (!BN_nnmod(B, pB, A, ctx)) goto err;

   547 		}

   548 	sign = -1;

   549 	/* From  B = a mod |n|,  A = |n|  it follows that

   550 	 *

   551 	 *      0 <= B < A,

   552 	 *     -sign*X*a  ==  B   (mod |n|),

   553 	 *      sign*Y*a  ==  A   (mod |n|).

   554 	 */

   555 

   556 	while (!BN_is_zero(B))

   557 		{

   558 		BIGNUM *tmp;

   559 		

   560 		/*

   561 		 *      0 < B < A,

   562 		 * (*) -sign*X*a  ==  B   (mod |n|),

   563 		 *      sign*Y*a  ==  A   (mod |n|)

   564 		 */

   565 

   566 		/* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked,

   567 	 	 * BN_div_no_branch will be called eventually.

   568 	 	 */

   569 		pA = &local_A;

   570 		BN_with_flags(pA, A, BN_FLG_CONSTTIME);	

   571 		

   572 		/* (D, M) := (A/B, A%B) ... */		

   573 		if (!BN_div(D,M,pA,B,ctx)) goto err;

   574 		

   575 		/* Now

   576 		 *      A = D*B + M;

   577 		 * thus we have

   578 		 * (**)  sign*Y*a  ==  D*B + M   (mod |n|).

   579 		 */

   580 		

   581 		tmp=A; /* keep the BIGNUM object, the value does not matter */

   582 		

   583 		/* (A, B) := (B, A mod B) ... */

   584 		A=B;

   585 		B=M;

   586 		/* ... so we have  0 <= B < A  again */

   587 		

   588 		/* Since the former  M  is now  B  and the former  B  is now  A,

   589 		 * (**) translates into

   590 		 *       sign*Y*a  ==  D*A + B    (mod |n|),

   591 		 * i.e.

   592 		 *       sign*Y*a - D*A  ==  B    (mod |n|).

   593 		 * Similarly, (*) translates into

   594 		 *      -sign*X*a  ==  A          (mod |n|).

   595 		 *

   596 		 * Thus,

   597 		 *   sign*Y*a + D*sign*X*a  ==  B  (mod |n|),

   598 		 * i.e.

   599 		 *        sign*(Y + D*X)*a  ==  B  (mod |n|).

   600 		 *

   601 		 * So if we set  (X, Y, sign) := (Y + D*X, X, -sign),  we arrive back at

   602 		 *      -sign*X*a  ==  B   (mod |n|),

   603 		 *       sign*Y*a  ==  A   (mod |n|).

   604 		 * Note that  X  and  Y  stay non-negative all the time.

   605 		 */

   606 			

   607 		if (!BN_mul(tmp,D,X,ctx)) goto err;

   608 		if (!BN_add(tmp,tmp,Y)) goto err;

   609 

   610 		M=Y; /* keep the BIGNUM object, the value does not matter */

   611 		Y=X;

   612 		X=tmp;

   613 		sign = -sign;

   614 		}

   615 		

   616 	/*

   617 	 * The while loop (Euclid's algorithm) ends when

   618 	 *      A == gcd(a,n);

   619 	 * we have

   620 	 *       sign*Y*a  ==  A  (mod |n|),

   621 	 * where  Y  is non-negative.

   622 	 */

   623 

   624 	if (sign < 0)

   625 		{

   626 		if (!BN_sub(Y,n,Y)) goto err;

   627 		}

   628 	/* Now  Y*a  ==  A  (mod |n|).  */

   629 

   630 	if (BN_is_one(A))

   631 		{

   632 		/* Y*a == 1  (mod |n|) */

   633 		if (!Y->neg && BN_ucmp(Y,n) < 0)

   634 			{

   635 			if (!BN_copy(R,Y)) goto err;

   636 			}

   637 		else

   638 			{

   639 			if (!BN_nnmod(R,Y,n,ctx)) goto err;

   640 			}

   641 		}

   642 	else

   643 		{

   644 		BNerr(BN_F_BN_MOD_INVERSE_NO_BRANCH,BN_R_NO_INVERSE);

   645 		goto err;

   646 		}

   647 	ret=R;

   648 err:

   649 	if ((ret == NULL) && (in == NULL)) BN_free(R);

   650 	BN_CTX_end(ctx);

   651 	bn_check_top(ret);

   652 	return(ret);

   653 	}