Put the first stage of my bignum debugging adventures into CVS. This code

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

diff --git a/crypto/bn/bn_exp.c b/crypto/bn/bn_exp.c
index 35ab56efc04d6b1ab90cb1fbdb5e0e910dfac7e4..462d4dbc4364c64fea091eabe3240fbd0dbe1e45 100644 (file)
--- a/crypto/bn/bn_exp.c
+++ b/crypto/bn/bn_exp.c
@@ -147,6 +147,7 @@ int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
 err:
        if (r != rr) BN_copy(r,rr);
        BN_CTX_end(ctx);
+       bn_check_top(r);
        return(ret);
        }
 
@@ -191,6 +192,7 @@ int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
         */
 
 #define MONT_MUL_MOD
+#define MONT_EXP_WORD
 #define RECP_MUL_MOD
 
 #ifdef MONT_MUL_MOD
@@ -202,12 +204,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
@@ -218,6 +222,7 @@ int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
                { ret=BN_mod_exp_simple(r,a,p,m,ctx); }
 #endif
 
+       bn_check_top(r);
        return(ret);
        }
 
@@ -235,20 +240,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)
@@ -329,6 +349,7 @@ err:
        for (i=0; i<ts; i++)
                BN_clear_free(&(val[i]));
        BN_RECP_CTX_free(&recp);
+       bn_check_top(r);
        return(ret);
        }
 
@@ -355,9 +376,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);
@@ -384,6 +406,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);
@@ -466,6 +493,7 @@ err:
        BN_CTX_end(ctx);
        for (i=0; i<ts; i++)
                BN_clear_free(&(val[i]));
+       bn_check_top(rr);
        return(ret);
        }
 
@@ -483,26 +511,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);
@@ -593,6 +634,7 @@ int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p,
 err:
        if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
        BN_CTX_end(ctx);
+       bn_check_top(rr);
        return(ret);
        }
 
@@ -611,8 +653,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);
@@ -621,6 +663,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)
@@ -700,6 +747,7 @@ err:
        BN_CTX_end(ctx);
        for (i=0; i<ts; i++)
                BN_clear_free(&(val[i]));
+       bn_check_top(r);
        return(ret);
        }