Fix a ** 0 mod 1 = 0 for real this time.

[openssl.git] / crypto / bn / bn_exp.c

diff --git a/crypto/bn/bn_exp.c b/crypto/bn/bn_exp.c
index eebcb96b55ebb7261a510cbd469d7e125545b733..98db765f3829af0a5c1bb7fd4dfaaecd7b1fc66f 100644 (file)
--- a/crypto/bn/bn_exp.c
+++ b/crypto/bn/bn_exp.c
@@ -126,13 +126,7 @@
 # include <alloca.h>
 #endif
 
-#undef RSAZ_ENABLED
-#if defined(OPENSSL_BN_ASM_MONT) && \
-        (defined(__x86_64) || defined(__x86_64__) || \
-         defined(_M_AMD64) || defined(_M_X64))
-# include "rsaz_exp.h"
-# define RSAZ_ENABLED
-#endif
+#include "rsaz_exp.h"
 
 #undef SPARC_T4_MONT
 #if defined(OPENSSL_BN_ASM_MONT) && (defined(__sparc__) || defined(__sparc))
@@ -185,10 +179,10 @@ int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
                 goto err;
         }
     }
-    ret = 1;
- err:
     if (r != rr)
         BN_copy(r, rr);
+    ret = 1;
+ err:
     BN_CTX_end(ctx);
     bn_check_top(r);
     return (ret);
@@ -203,36 +197,36 @@ int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
     bn_check_top(p);
     bn_check_top(m);
 
-        /*-
-         * For even modulus  m = 2^k*m_odd,  it might make sense to compute
-         * a^p mod m_odd  and  a^p mod 2^k  separately (with Montgomery
-         * exponentiation for the odd part), using appropriate exponent
-         * reductions, and combine the results using the CRT.
-         *
-         * For now, we use Montgomery only if the modulus is odd; otherwise,
-         * exponentiation using the reciprocal-based quick remaindering
-         * algorithm is used.
-         *
-         * (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.)
-         */
+    /*-
+     * For even modulus  m = 2^k*m_odd,  it might make sense to compute
+     * a^p mod m_odd  and  a^p mod 2^k  separately (with Montgomery
+     * exponentiation for the odd part), using appropriate exponent
+     * reductions, and combine the results using the CRT.
+     *
+     * For now, we use Montgomery only if the modulus is odd; otherwise,
+     * exponentiation using the reciprocal-based quick remaindering
+     * algorithm is used.
+     *
+     * (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
@@ -288,9 +282,14 @@ int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
     }
 
     bits = BN_num_bits(p);
-
     if (bits == 0) {
-        ret = BN_one(r);
+        /* x**0 mod 1 is still zero. */
+        if (BN_is_one(m)) {
+            ret = 1;
+            BN_zero(r);
+        } else {
+            ret = BN_one(r);
+        }
         return ret;
     }
 
@@ -424,7 +423,13 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
     }
     bits = BN_num_bits(p);
     if (bits == 0) {
-        ret = BN_one(rr);
+        /* x**0 mod 1 is still zero. */
+        if (BN_is_one(m)) {
+            ret = 1;
+            BN_zero(rr);
+        } else {
+            ret = BN_one(rr);
+        }
         return ret;
     }
 
@@ -668,15 +673,22 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
     bn_check_top(p);
     bn_check_top(m);
 
-    top = m->top;
-
-    if (!(m->d[0] & 1)) {
+    if (!BN_is_odd(m)) {
         BNerr(BN_F_BN_MOD_EXP_MONT_CONSTTIME, BN_R_CALLED_WITH_EVEN_MODULUS);
         return (0);
     }
+
+    top = m->top;
+
     bits = BN_num_bits(p);
     if (bits == 0) {
-        ret = BN_one(rr);
+        /* x**0 mod 1 is still zero. */
+        if (BN_is_one(m)) {
+            ret = 1;
+            BN_zero(rr);
+        } else {
+            ret = BN_one(rr);
+        }
         return ret;
     }
 
@@ -1187,8 +1199,9 @@ int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p,
         if (BN_is_one(m)) {
             ret = 1;
             BN_zero(rr);
-        } else
+        } else {
             ret = BN_one(rr);
+        }
         return ret;
     }
     if (a == 0) {
@@ -1302,9 +1315,14 @@ int BN_mod_exp_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
     }
 
     bits = BN_num_bits(p);
-
-    if (bits == 0) {
-        ret = BN_one(r);
+   if (bits == 0) {
+        /* x**0 mod 1 is still zero. */
+        if (BN_is_one(m)) {
+            ret = 1;
+            BN_zero(r);
+        } else {
+            ret = BN_one(r);
+        }
         return ret;
     }