Fix some things that look like bugs.

One problem that looked like a problem in bn_recp.c at first turned
out to be a BN_mul bug.  An example is given in bn_recp.c; finding
the bug responsible for this is left as an exercise.

diff --git a/CHANGES b/CHANGES
index 107c31bf564fc1c2800274bcebf9d468df252e0c..8c2380a6a998c54167476a76363ecd00603a23cd 100644 (file)
--- a/CHANGES
+++ b/CHANGES
@@ -3,6 +3,16 @@
 
  Changes between 0.9.6 and 0.9.7  [xx XXX 2000]
 
+  *) Change BN_mod_exp_recp so that negative moduli are tolerated
+     (the sign is ignored).  Similarly, ignore the sign in BN_MONT_CTX_set
+     so that BN_mod_exp_mont and BN_mod_exp_mont_word work
+     for negative moduli.
+     [Bodo Moeller]
+
+  *) Fix BN_uadd and BN_usub: Always return non-negative results instead
+     of not touching the result's sign bit.
+     [Bodo Moeller]
+
   *) BN_div bugfix: If the result is 0, the sign (res->neg) must not be
      set.
      [Bodo Moeller]

diff --git a/crypto/bn/bn_add.c b/crypto/bn/bn_add.c
index 5d2469123302d58750b9b5c1c250637d395a4b68..6cba07e9f670ad83e4061357ea0a90ab135ad15c 100644 (file)
--- a/crypto/bn/bn_add.c
+++ b/crypto/bn/bn_add.c
@@ -64,6 +64,7 @@
 int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
        {
        const BIGNUM *tmp;
+       int a_neg = a->neg;
 
        bn_check_top(a);
        bn_check_top(b);
@@ -73,10 +74,10 @@ int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
         * -a +  b      b-a
         * -a + -b      -(a+b)
         */
-       if (a->neg ^ b->neg)
+       if (a_neg ^ b->neg)
                {
                /* only one is negative */
-               if (a->neg)
+               if (a_neg)
                        { tmp=a; a=b; b=tmp; }
 
                /* we are now a - b */
@@ -94,12 +95,11 @@ int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
                return(1);
                }
 
-       if (a->neg) /* both are neg */
+       if (!BN_uadd(r,a,b)) return(0);
+       if (a_neg) /* both are neg */
                r->neg=1;
        else
                r->neg=0;
-
-       if (!BN_uadd(r,a,b)) return(0);
        return(1);
        }
 
@@ -160,6 +160,7 @@ int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
                        *(rp++)= *(ap++);
                }
        /* memcpy(rp,ap,sizeof(*ap)*(max-i));*/
+       r->neg = 0;
        return(1);
        }
 
@@ -251,6 +252,7 @@ int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
 #endif
 
        r->top=max;
+       r->neg=0;
        bn_fix_top(r);
        return(1);
        }

diff --git a/crypto/bn/bn_exp.c b/crypto/bn/bn_exp.c
index 1739be68645b4af678d6609ead457b0df05d1765..afdfd580fb43947dc380aa44dccd232d1cc5c5c8 100644 (file)
--- a/crypto/bn/bn_exp.c
+++ b/crypto/bn/bn_exp.c
@@ -246,7 +246,17 @@ int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
        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;
@@ -497,9 +507,13 @@ 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))
 

diff --git a/crypto/bn/bn_mont.c b/crypto/bn/bn_mont.c
index 7f8296c893200478bcffe73a95c6fbd552d86a4b..f1765c03ac88b40e4cfdc923594bba7679f38737 100644 (file)
--- a/crypto/bn/bn_mont.c
+++ b/crypto/bn/bn_mont.c
@@ -226,7 +226,7 @@ int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont,
 
        if (BN_ucmp(ret, &(mont->N)) >= 0)
                {
-               BN_usub(ret,ret,&(mont->N));
+               if (!BN_usub(ret,ret,&(mont->N))) goto err;
                }
        retn=1;
  err:
@@ -274,6 +274,7 @@ int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
        BN_init(&Ri);
        R= &(mont->RR);                                 /* grab RR as a temp */
        BN_copy(&(mont->N),mod);                        /* Set N */
+       mont->N.neg = 0;
 
 #ifdef MONT_WORD
                {
@@ -289,40 +290,45 @@ int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
                tmod.d=buf;
                tmod.top=1;
                tmod.dmax=2;
-               tmod.neg=mod->neg;
+               tmod.neg=0;
                                                        /* Ri = R^-1 mod N*/
                if ((BN_mod_inverse(&Ri,R,&tmod,ctx)) == NULL)
                        goto err;
-               BN_lshift(&Ri,&Ri,BN_BITS2);            /* R*Ri */
+               if (!BN_lshift(&Ri,&Ri,BN_BITS2)) goto err; /* R*Ri */
                if (!BN_is_zero(&Ri))
-                       BN_sub_word(&Ri,1);
+                       {
+                       if (!BN_sub_word(&Ri,1)) goto err;
+                       }
                else /* if N mod word size == 1 */
-                       BN_set_word(&Ri,BN_MASK2);  /* Ri-- (mod word size) */
-               BN_div(&Ri,NULL,&Ri,&tmod,ctx); /* Ni = (R*Ri-1)/N,
-                                                * keep only least significant word: */
-               mont->n0=Ri.d[0];
+                       {
+                       if (!BN_set_word(&Ri,BN_MASK2)) goto err;  /* Ri-- (mod word size) */
+                       }
+               if (!BN_div(&Ri,NULL,&Ri,&tmod,ctx)) goto err;
+               /* Ni = (R*Ri-1)/N,
+                * keep only least significant word: */
+               mont->n0 = (Ri.top > 0) ? Ri.d[0] : 0;
                BN_free(&Ri);
                }
 #else /* !MONT_WORD */
                { /* bignum version */
-               mont->ri=BN_num_bits(mod);
-               BN_zero(R);
-               BN_set_bit(R,mont->ri);                 /* R = 2^ri */
-                                                       /* Ri = R^-1 mod N*/
-               if ((BN_mod_inverse(&Ri,R,mod,ctx)) == NULL)
+               mont->ri=BN_num_bits(&mont->N);
+               if (!BN_zero(R)) goto err;
+               if (!BN_set_bit(R,mont->ri)) goto err;  /* R = 2^ri */
+                                                       /* Ri = R^-1 mod N*/
+               if ((BN_mod_inverse(&Ri,R,&mont->N,ctx)) == NULL)
                        goto err;
-               BN_lshift(&Ri,&Ri,mont->ri);            /* R*Ri */
-               BN_sub_word(&Ri,1);
+               if (!BN_lshift(&Ri,&Ri,mont->ri)) goto err; /* R*Ri */
+               if (!BN_sub_word(&Ri,1)) goto err;
                                                        /* Ni = (R*Ri-1) / N */
-               BN_div(&(mont->Ni),NULL,&Ri,mod,ctx);
+               if (!BN_div(&(mont->Ni),NULL,&Ri,&mont->N,ctx)) goto err;
                BN_free(&Ri);
                }
 #endif
 
        /* setup RR for conversions */
-       BN_zero(&(mont->RR));
-       BN_set_bit(&(mont->RR),mont->ri*2);
-       BN_mod(&(mont->RR),&(mont->RR),&(mont->N),ctx);
+       if (!BN_zero(&(mont->RR))) goto err;
+       if (!BN_set_bit(&(mont->RR),mont->ri*2)) goto err;
+       if (!BN_mod(&(mont->RR),&(mont->RR),&(mont->N),ctx)) goto err;
 
        return(1);
 err:

diff --git a/crypto/bn/bn_recp.c b/crypto/bn/bn_recp.c
index 0700a0f06375265589911333ae2935ab11a3a0eb..2c0998eacd3dcbc47e42cb0cb49c1b6ac4fe4ace 100644 (file)
--- a/crypto/bn/bn_recp.c
+++ b/crypto/bn/bn_recp.c
@@ -93,8 +93,8 @@ void BN_RECP_CTX_free(BN_RECP_CTX *recp)
 
 int BN_RECP_CTX_set(BN_RECP_CTX *recp, const BIGNUM *d, BN_CTX *ctx)
        {
-       BN_copy(&(recp->N),d);
-       BN_zero(&(recp->Nr));
+       if (!BN_copy(&(recp->N),d)) return 0;
+       if (!BN_zero(&(recp->Nr))) return 0;
        recp->num_bits=BN_num_bits(d);
        recp->shift=0;
        return(1);
@@ -120,8 +120,7 @@ int BN_mod_mul_reciprocal(BIGNUM *r, const BIGNUM *x, const BIGNUM *y,
        else
                ca=x; /* Just do the mod */
 
-       BN_div_recp(NULL,r,ca,recp,ctx);
-       ret=1;
+       ret = BN_div_recp(NULL,r,ca,recp,ctx);
 err:
        BN_CTX_end(ctx);
        return(ret);
@@ -148,8 +147,8 @@ int BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m,
 
        if (BN_ucmp(m,&(recp->N)) < 0)
                {
-               BN_zero(d);
-               BN_copy(r,m);
+               if (!BN_zero(d)) return 0;
+               if (!BN_copy(r,m)) return 0;
                BN_CTX_end(ctx);
                return(1);
                }
@@ -159,21 +158,28 @@ int BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m,
         * we need multiply ABCDEF by 3 digests of the reciprocal of ab
         *
         */
-       i=BN_num_bits(m);
 
+       /* i := max(BN_num_bits(m), 2*BN_num_bits(N)) */
+       i=BN_num_bits(m);
        j=recp->num_bits<<1;
        if (j>i) i=j;
-       j>>=1;
 
+       /* Nr := round(2^i / N) */
        if (i != recp->shift)
                recp->shift=BN_reciprocal(&(recp->Nr),&(recp->N),
                        i,ctx); /* BN_reciprocal returns i, or -1 for an error */
        if (recp->shift == -1) goto err;
 
-       if (!BN_rshift(a,m,j)) goto err;
+       /* d := |round(round(m / 2^BN_num_bits(N)) * recp->Nr / 2^(i - BN_num_bits(N)))|
+        *    = |round(round(m / 2^BN_num_bits(N)) * round(2^i / N) / 2^(i - BN_num_bits(N)))|
+        *   <= |(m / 2^BN_num_bits(N)) * (2^i / N) * (2^BN_num_bits(N) / 2^i)|
+        *    = |m/N|
+        */
+       if (!BN_rshift(a,m,recp->num_bits)) goto err;
        if (!BN_mul(b,a,&(recp->Nr),ctx)) goto err;
-       if (!BN_rshift(d,b,i-j)) goto err;
+       if (!BN_rshift(d,b,i-recp->num_bits)) goto err;
        d->neg=0;
+
        if (!BN_mul(b,&(recp->N),d,ctx)) goto err;
        if (!BN_usub(r,m,b)) goto err;
        r->neg=0;
@@ -212,13 +218,50 @@ int BN_reciprocal(BIGNUM *r, const BIGNUM *m, int len, BN_CTX *ctx)
 
        BN_init(&t);
 
-       BN_zero(&t);
+       if (!BN_zero(&t)) goto err;
        if (!BN_set_bit(&t,len)) goto err;
 
        if (!BN_div(r,NULL,&t,m,ctx)) goto err;
+
+#if 1
+       {
+       BIGNUM v;
+       
+       BN_init(&v);
+       BN_mul(&v,r,m,ctx);
+       if (BN_num_bits(&v) > BN_num_bits(r) + BN_num_bits(m))
+               {
+               fprintf(stderr,"bn_recp.c: BN_mul does not work\n");
+               fprintf(stderr,"r =");
+               BN_print_fp(stderr,r);
+               fprintf(stderr,"\nm =");
+               BN_print_fp(stderr,m);
+               fprintf(stderr,"\nr*m =");
+               BN_print_fp(stderr,&v);
+               fprintf(stderr,"\n");
+               abort();
+
+/* Example output (Linux x86):
+
+bn_recp.c: BN_mul does not work
+r =11F5575B94E4AA12CA5D2B7A3DDC5E1A68C77758A941F3C50749D2BB2C65F8D2424E23642AC2CEEFE520FE594626AF7440772AD8C2F3801925E13B11B4398A51A
+m =E415484B146C8AC93EE7B5CAA1C0B0182324E60263BE95C3E26542CD3ADF818D92DD52C073E2B38AEEA5F6C926D2D3D53D7190461D3DF62A20449B5BEAF4F74D
+r*m =1B96E67C0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001B96E67AB2626FFC8A5076B1BE234C8A69F72D9D73A71EDB1649209D42FA20ACA2FAE36B481D9C6F2FE021A437FD81ABB62B5F13E8DEB58366ACEE8493B4F610BCFDBED2
+
+The result should be
+r*m =FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFB2626FFC8A5076B1BE234C8A69F72D9D73A71EDB1649209D42FA20ACA2FAE36B481D9C6F2FE021A437FD81ABB62B5F13E8DEB58366ACEE8493B4F610BCFDBED2
+(according to GNU bc).
+
+*/
+
+
+               }
+       BN_free(&v);
+       }
+#endif 
+
        ret=len;
 err:
        BN_free(&t);
        return(ret);
        }
-

diff --git a/crypto/bn/bntest.c b/crypto/bn/bntest.c
index 9f308b75a9e6a3a53a73ac2ef1742ef22f03e086..b83d0ba30d420e96ac70adde2c2eedd157130ca1 100644 (file)
--- a/crypto/bn/bntest.c
+++ b/crypto/bn/bntest.c
@@ -921,11 +921,10 @@ int test_kron(BIO *bp, BN_CTX *ctx)
                if (!BN_sub_word(t, 1)) goto err;
                if (!BN_rshift1(t, t)) goto err;
                /* r := a^t mod b */
-               /* FIXME: Using BN_mod_exp (Montgomery variant) leads to
-                * incorrect results if  b  is negative ("Legendre symbol
-                * computation failed").
-                * We want computations to be carried out modulo |b|. */
-               if (!BN_mod_exp_simple(r, a, t, b, ctx)) goto err;
+               b->neg=0;
+               
+               if (!BN_mod_exp_recp(r, a, t, b, ctx)) goto err; /* XXX should be BN_mod_exp_recp, but ..._recp triggers a bug that must be fixed */
+               b->neg=1;
 
                if (BN_is_word(r, 1))
                        legendre = 1;
@@ -934,7 +933,7 @@ int test_kron(BIO *bp, BN_CTX *ctx)
                else
                        {
                        if (!BN_add_word(r, 1)) goto err;
-                       if (0 != BN_cmp(r, b))
+                       if (0 != BN_ucmp(r, b))
                                {
                                fprintf(stderr, "Legendre symbol computation failed\n");
                                goto err;
@@ -1220,7 +1219,7 @@ int test_rshift1(BIO *bp)
                        }
                BN_sub(c,a,b);
                BN_sub(c,c,b);
-               if(!BN_is_zero(c) && !BN_is_one(c))
+               if(!BN_is_zero(c) && !BN_abs_is_word(c, 1))
                    {
                    fprintf(stderr,"Right shift one test failed!\n");
                    return 0;