X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=crypto%2Fbn%2Fbn_gcd.c;h=7649f63fd22ab2562d7cfe384fc39b5e379eeb2b;hb=c237de058f91072b5d54ad9c570049c14df6957e;hp=2c6fb2379a99328add8f52434e3c50efcd2d39d9;hpb=7d0d0996aa0e85734eaf5c8a3e6bd9e62604c166;p=oweals%2Fopenssl.git

diff --git a/crypto/bn/bn_gcd.c b/crypto/bn/bn_gcd.c
index 2c6fb2379a..7649f63fd2 100644
--- a/crypto/bn/bn_gcd.c
+++ b/crypto/bn/bn_gcd.c
@@ -244,17 +244,19 @@ BIGNUM *BN_mod_inverse(BIGNUM *in,
 	 *      sign*Y*a  ==  A   (mod |n|).
 	 */
 
-	if (BN_is_odd(n) && (BN_num_bits(n) <= 400))
+	if (BN_is_odd(n) && (BN_num_bits(n) <= (BN_BITS <= 32 ? 450 : 2048)))
 		{
 		/* Binary inversion algorithm; requires odd modulus.
 		 * This is faster than the general algorithm if the modulus
-		 * is sufficiently small. */
+		 * is sufficiently small (about 400 .. 500 bits on 32-bit
+		 * sytems, but much more on 64-bit systems) */
 		int shift;
 		
 		while (!BN_is_zero(B))
 			{
 			/*
-			 *      0 < B < A <= |n|,
+			 *      0 < B < |n|,
+			 *      0 < A <= |n|,
 			 * (1) -sign*X*a  ==  B   (mod |n|),
 			 * (2)  sign*Y*a  ==  A   (mod |n|)
 			 */
@@ -299,13 +301,16 @@ BIGNUM *BN_mod_inverse(BIGNUM *in,
 				}
 
 			
-			/* We still have (1) and (2), but  A  may no longer be larger than  B.
+			/* We still have (1) and (2).
 			 * Both  A  and  B  are odd.
 			 * The following computations ensure that
 			 *
-			 *      0 =< B < A = |n|,
+			 *     0 <= B < |n|,
+			 *      0 < A < |n|,
 			 * (1) -sign*X*a  ==  B   (mod |n|),
-			 * (2)  sign*Y*a  ==  A   (mod |n|)
+			 * (2)  sign*Y*a  ==  A   (mod |n|),
+			 *
+			 * and that either  A  or  B  is even in the next iteration.
 			 */
 			if (BN_ucmp(B, A) >= 0)
 				{
@@ -326,7 +331,7 @@ BIGNUM *BN_mod_inverse(BIGNUM *in,
 		}
 	else
 		{
-		/* general inversion algorithm (less efficient than binary inversion) */
+		/* general inversion algorithm */
 
 		while (!BN_is_zero(B))
 			{