X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=crypto%2Fbn%2Fbn_exp.c;h=afdfd580fb43947dc380aa44dccd232d1cc5c5c8;hb=710e5d5639c8f943d73f49733382c1b787d1abb6;hp=e6b3a5f5f97ad45f9576a1b268cc4c60b819f687;hpb=78a0c1f18d5a1f0e51b7467ef7b153b8c29fbb03;p=oweals%2Fopenssl.git

diff --git a/crypto/bn/bn_exp.c b/crypto/bn/bn_exp.c
index e6b3a5f5f9..afdfd580fb 100644
--- a/crypto/bn/bn_exp.c
+++ b/crypto/bn/bn_exp.c
@@ -169,15 +169,29 @@ int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
 	 * exponentiation using the reciprocal-based quick remaindering
 	 * algorithm is used.
 	 *
-	 * (For computations  a^p mod m  where  a, p, m  are of the same
-	 * length, BN_mod_exp_recp takes roughly 50 .. 70 % the time
-	 * required by the standard algorithm, and BN_mod_exp takes
-	 * about 33 .. 40 % of it.
-	 * [Timings obtained with expspeed.c on a AMD K6-2 platform under Linux,
-	 * with various OpenSSL debugging macros defined.  YMMV.])
+	 * (Timing obtained with expspeed.c [computations  a^p mod m
+	 * where  a, p, m  are of the same length: 256, 512, 1024, 2048,
+	 * 4096, 8192 bits], compared to the running time of the
+	 * standard algorithm:
+	 *
+	 *   BN_mod_exp_mont   33 .. 40 %  [AMD K6-2, Linux, debug configuration]
+         *                     55 .. 77 %  [UltraSparc processor, but
+	 *                                  debug-solaris-sparcv8-gcc conf.]
+	 * 
+	 *   BN_mod_exp_recp   50 .. 70 %  [AMD K6-2, Linux, debug configuration]
+	 *                     62 .. 118 % [UltraSparc, debug-solaris-sparcv8-gcc]
+	 *
+	 * On the Sparc, BN_mod_exp_recp was faster than BN_mod_exp_mont
+	 * at 2048 and more bits, but at 512 and 1024 bits, it was
+	 * slower even than the standard algorithm!
+	 *
+	 * "Real" timings [linux-elf, solaris-sparcv9-gcc configurations]
+	 * should be obtained when the new Montgomery reduction code
+	 * has been integrated into OpenSSL.)
 	 */
 
 #define MONT_MUL_MOD
+#define MONT_EXP_WORD
 #define RECP_MUL_MOD
 
 #ifdef MONT_MUL_MOD
@@ -189,12 +203,14 @@ int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
 
 	if (BN_is_odd(m))
 		{
+#  ifdef MONT_EXP_WORD
 		if (a->top == 1 && !a->neg)
 			{
 			BN_ULONG A = a->d[0];
 			ret=BN_mod_exp_mont_word(r,A,p,m,ctx,NULL);
 			}
 		else
+#  endif
 			ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL);
 		}
 	else
@@ -222,20 +238,35 @@ int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
 
 	if (bits == 0)
 		{
-		BN_one(r);
-		return(1);
+		ret = BN_one(r);
+		return ret;
 		}
 
 	BN_CTX_start(ctx);
 	if ((aa = BN_CTX_get(ctx)) == NULL) goto err;
 
 	BN_RECP_CTX_init(&recp);
-	if (BN_RECP_CTX_set(&recp,m,ctx) <= 0) goto err;
+	if (m->neg)
+		{
+		/* ignore sign of 'm' */
+		if (!BN_copy(aa, m)) goto err;
+		aa->neg = 0;
+		if (BN_RECP_CTX_set(&recp,aa,ctx) <= 0) goto err;
+		}
+	else
+		{
+		if (BN_RECP_CTX_set(&recp,m,ctx) <= 0) goto err;
+		}
 
 	BN_init(&(val[0]));
 	ts=1;
 
 	if (!BN_nnmod(&(val[0]),a,m,ctx)) goto err;		/* 1 */
+	if (BN_is_zero(&(val[0])))
+		{
+		ret = BN_zero(r);
+		goto err;
+		}
 
 	window = BN_window_bits_for_exponent_size(bits);
 	if (window > 1)
@@ -342,9 +373,10 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
 	bits=BN_num_bits(p);
 	if (bits == 0)
 		{
-		BN_one(rr);
-		return(1);
+		ret = BN_one(rr);
+		return ret;
 		}
+
 	BN_CTX_start(ctx);
 	d = BN_CTX_get(ctx);
 	r = BN_CTX_get(ctx);
@@ -363,7 +395,7 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
 
 	BN_init(&val[0]);
 	ts=1;
-	if (!a->neg && BN_ucmp(a,m) >= 0)
+	if (a->neg || BN_ucmp(a,m) >= 0)
 		{
 		if (!BN_nnmod(&(val[0]),a,m,ctx))
 			goto err;
@@ -371,6 +403,11 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
 		}
 	else
 		aa=a;
+	if (BN_is_zero(aa))
+		{
+		ret = BN_zero(rr);
+		goto err;
+		}
 	if (!BN_to_montgomery(&(val[0]),aa,mont,ctx)) goto err; /* 1 */
 
 	window = BN_window_bits_for_exponent_size(bits);
@@ -470,26 +507,39 @@ int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p,
 		(/* BN_ucmp(r, (m)) < 0 ? 1 :*/  \
 			(BN_mod(t, r, m, ctx) && (swap_tmp = r, r = t, t = swap_tmp, 1))))
 		/* BN_MOD_MUL_WORD is only used with 'w' large,
-		  * so the BN_ucmp test is probably more overhead
-		  * than always using BN_mod (which uses BN_copy if
-		  * a similar test returns true). */
+		 * so the BN_ucmp test is probably more overhead
+		 * than always using BN_mod (which uses BN_copy if
+		 * a similar test returns true). */
+		/* We can use BN_mod and do not need BN_nnmod because our
+		 * accumulator is never negative (the result of BN_mod does
+		 * not depend on the sign of the modulus).
+		 */
 #define BN_TO_MONTGOMERY_WORD(r, w, mont) \
 		(BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont), ctx))
 
 	bn_check_top(p);
 	bn_check_top(m);
 
-	if (!(m->d[0] & 1))
+	if (m->top == 0 || !(m->d[0] & 1))
 		{
 		BNerr(BN_F_BN_MOD_EXP_MONT_WORD,BN_R_CALLED_WITH_EVEN_MODULUS);
 		return(0);
 		}
+	if (m->top == 1)
+		a %= m->d[0]; /* make sure that 'a' is reduced */
+
 	bits = BN_num_bits(p);
 	if (bits == 0)
 		{
-		BN_one(rr);
-		return(1);
+		ret = BN_one(rr);
+		return ret;
 		}
+	if (a == 0)
+		{
+		ret = BN_zero(rr);
+		return ret;
+		}
+
 	BN_CTX_start(ctx);
 	d = BN_CTX_get(ctx);
 	r = BN_CTX_get(ctx);
@@ -598,8 +648,8 @@ int BN_mod_exp_simple(BIGNUM *r,
 
 	if (bits == 0)
 		{
-		BN_one(r);
-		return(1);
+		ret = BN_one(r);
+		return ret;
 		}
 
 	BN_CTX_start(ctx);
@@ -608,6 +658,11 @@ int BN_mod_exp_simple(BIGNUM *r,
 	BN_init(&(val[0]));
 	ts=1;
 	if (!BN_nnmod(&(val[0]),a,m,ctx)) goto err;		/* 1 */
+	if (BN_is_zero(&(val[0])))
+		{
+		ret = BN_zero(r);
+		goto err;
+		}
 
 	window = BN_window_bits_for_exponent_size(bits);
 	if (window > 1)