Bug fix!

diff --git a/CHANGES b/CHANGES
index c08fa854e78ff64c09973b7b368938cf94d4635c..401967431498d4810ab3be1a126631330c3cb4f5 100644 (file)
--- a/CHANGES
+++ b/CHANGES
@@ -4,6 +4,11 @@
 
  Changes between 0.9.4 and 0.9.5  [xx XXX 2000]
 
+  *) BN_mul bugfix: In bn_mul_part_recursion() only the a>a[n] && b>b[n]
+     case was implemented. This caused BN_div_recp() to fail occasionally
+     on 32 bit machines.
+     [Ulf Möller]
+
   *) Add an optional second argument to the set_label() in the perl
      assembly language builder. If this argument exists and is set
      to 1 it signals that the assembler should use a symbol whose 

diff --git a/crypto/bn/bn_mul.c b/crypto/bn/bn_mul.c
index ce7c548150e458212f783638717da1e784ff8a2d..eb007e19e9a9063700ca358ab9a61e6cd3bd850e 100644 (file)
--- a/crypto/bn/bn_mul.c
+++ b/crypto/bn/bn_mul.c
@@ -221,7 +221,7 @@ void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int tn,
             int n, BN_ULONG *t)
        {
        int i,j,n2=n*2;
-       unsigned int c1;
+       unsigned int c1,c2,neg,zero;
        BN_ULONG ln,lo,*p;
 
 # ifdef BN_COUNT
@@ -235,9 +235,43 @@ void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int tn,
                }
 
        /* r=(a[0]-a[1])*(b[1]-b[0]) */
-       bn_sub_words(t,      a,      &(a[n]),n); /* + */
-       bn_sub_words(&(t[n]),b,      &(b[n]),n); /* - */
-
+       c1=bn_cmp_words(a,&(a[n]),n);
+       c2=bn_cmp_words(&(b[n]),b,n);
+       zero=neg=0;
+       switch (c1*3+c2)
+               {
+       case -4:
+               bn_sub_words(t,      &(a[n]),a,      n); /* - */
+               bn_sub_words(&(t[n]),b,      &(b[n]),n); /* - */
+               break;
+       case -3:
+               zero=1;
+               /* break; */
+       case -2:
+               bn_sub_words(t,      &(a[n]),a,      n); /* - */
+               bn_sub_words(&(t[n]),&(b[n]),b,      n); /* + */
+               neg=1;
+               break;
+       case -1:
+       case 0:
+       case 1:
+               zero=1;
+               /* break; */
+       case 2:
+               bn_sub_words(t,      a,      &(a[n]),n); /* + */
+               bn_sub_words(&(t[n]),b,      &(b[n]),n); /* - */
+               neg=1;
+               break;
+       case 3:
+               zero=1;
+               /* break; */
+       case 4:
+               bn_sub_words(t,      a,      &(a[n]),n);
+               bn_sub_words(&(t[n]),&(b[n]),b,      n);
+               break;
+               }
+               /* The zero case isn't yet implemented here. The speedup
+                  would probably be negligible. */
 # if 0
        if (n == 4)
                {
@@ -313,7 +347,16 @@ void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int tn,
         */
 
        c1=(int)(bn_add_words(t,r,&(r[n2]),n2));
-       c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2));
+
+       if (neg) /* if t[32] is negative */
+               {
+               c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2));
+               }
+       else
+               {
+               /* Might have a carry */
+               c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),t,n2));
+               }
 
        /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
         * r[10] holds (a[0]*b[0])
@@ -674,7 +717,6 @@ int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
                        }
                }
 #endif /* BN_RECURSION */
-
        if (bn_wexpand(rr,top) == NULL) goto err;
        rr->top=top;
        bn_mul_normal(rr->d,a->d,al,b->d,bl);