X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/putty/blobdiff_plain/5a502a193f88c484cff9872bdbf0e2143d96294b..8d90b8b27bf086da6245030459ab3e5977313eb0:/sshbn.c

diff --git a/sshbn.c b/sshbn.c
index 6cab8962..ecdb90e8 100644
--- a/sshbn.c
+++ b/sshbn.c
@@ -148,7 +148,7 @@ void freebn(Bignum b)
     /*
      * Burn the evidence, just in case.
      */
-    memset(b, 0, sizeof(b[0]) * (b[0] + 1));
+    smemclr(b, sizeof(b[0]) * (b[0] + 1));
     sfree(b);
 }
 
@@ -221,10 +221,8 @@ static int mul_compute_scratch(int len)
 static void internal_mul(const BignumInt *a, const BignumInt *b,
 			 BignumInt *c, int len, BignumInt *scratch)
 {
-    int i, j;
-    BignumDblInt t;
-
     if (len > KARATSUBA_THRESHOLD) {
+        int i;
 
         /*
          * Karatsuba divide-and-conquer algorithm. Cut each input in
@@ -311,9 +309,9 @@ static void internal_mul(const BignumInt *a, const BignumInt *b,
          * copied over. */
         scratch[0] = scratch[1] = scratch[midlen] = scratch[midlen+1] = 0;
 
-        for (j = 0; j < toplen; j++) {
-            scratch[midlen - toplen + j] = a[j]; /* a_1 */
-            scratch[2*midlen - toplen + j] = b[j]; /* b_1 */
+        for (i = 0; i < toplen; i++) {
+            scratch[midlen - toplen + i] = a[i]; /* a_1 */
+            scratch[2*midlen - toplen + i] = b[i]; /* b_1 */
         }
 
         /* compute a_1 + a_0 */
@@ -355,8 +353,8 @@ static void internal_mul(const BignumInt *a, const BignumInt *b,
          * product to obtain the middle one.
          */
         scratch[0] = scratch[1] = scratch[2] = scratch[3] = 0;
-        for (j = 0; j < 2*toplen; j++)
-            scratch[2*midlen - 2*toplen + j] = c[j];
+        for (i = 0; i < 2*toplen; i++)
+            scratch[2*midlen - 2*toplen + i] = c[i];
         scratch[1] = internal_add(scratch+2, c + 2*toplen,
                                   scratch+2, 2*botlen);
 #ifdef KARA_DEBUG
@@ -386,13 +384,13 @@ static void internal_mul(const BignumInt *a, const BignumInt *b,
         carry = internal_add(c + 2*len - botlen - 2*midlen,
                              scratch + 2*midlen,
                              c + 2*len - botlen - 2*midlen, 2*midlen);
-        j = 2*len - botlen - 2*midlen - 1;
+        i = 2*len - botlen - 2*midlen - 1;
         while (carry) {
-            assert(j >= 0);
-            carry += c[j];
-            c[j] = (BignumInt)carry;
+            assert(i >= 0);
+            carry += c[i];
+            c[i] = (BignumInt)carry;
             carry >>= BIGNUM_INT_BITS;
-            j--;
+            i--;
         }
 #ifdef KARA_DEBUG
         printf("ab = 0x");
@@ -403,23 +401,27 @@ static void internal_mul(const BignumInt *a, const BignumInt *b,
 #endif
 
     } else {
+        int i;
+        BignumInt carry;
+        BignumDblInt t;
+        const BignumInt *ap, *bp;
+        BignumInt *cp, *cps;
 
         /*
          * Multiply in the ordinary O(N^2) way.
          */
 
-        for (j = 0; j < 2 * len; j++)
-            c[j] = 0;
+        for (i = 0; i < 2 * len; i++)
+            c[i] = 0;
 
-        for (i = len - 1; i >= 0; i--) {
-            t = 0;
-            for (j = len - 1; j >= 0; j--) {
-                t += MUL_WORD(a[i], (BignumDblInt) b[j]);
-                t += (BignumDblInt) c[i + j + 1];
-                c[i + j + 1] = (BignumInt) t;
-                t = t >> BIGNUM_INT_BITS;
+        for (cps = c + 2*len, ap = a + len; ap-- > a; cps--) {
+            carry = 0;
+            for (cp = cps, bp = b + len; cp--, bp-- > b ;) {
+                t = (MUL_WORD(*ap, *bp) + carry) + *cp;
+                *cp = (BignumInt) t;
+                carry = (BignumInt)(t >> BIGNUM_INT_BITS);
             }
-            c[i] = (BignumInt) t;
+            *cp = carry;
         }
     }
 }
@@ -432,10 +434,8 @@ static void internal_mul(const BignumInt *a, const BignumInt *b,
 static void internal_mul_low(const BignumInt *a, const BignumInt *b,
                              BignumInt *c, int len, BignumInt *scratch)
 {
-    int i, j;
-    BignumDblInt t;
-
     if (len > KARATSUBA_THRESHOLD) {
+        int i;
 
         /*
          * Karatsuba-aware version of internal_mul_low. As before, we
@@ -492,8 +492,8 @@ static void internal_mul_low(const BignumInt *a, const BignumInt *b,
                          scratch + 2*len);
 
         /* Copy the bottom half of the big coefficient into place */
-        for (j = 0; j < botlen; j++)
-            c[toplen + j] = scratch[2*toplen + botlen + j];
+        for (i = 0; i < botlen; i++)
+            c[toplen + i] = scratch[2*toplen + botlen + i];
 
         /* Add the two small coefficients, throwing away the returned carry */
         internal_add(scratch, scratch + toplen, scratch, toplen);
@@ -503,20 +503,27 @@ static void internal_mul_low(const BignumInt *a, const BignumInt *b,
                      c, toplen);
 
     } else {
+        int i;
+        BignumInt carry;
+        BignumDblInt t;
+        const BignumInt *ap, *bp;
+        BignumInt *cp, *cps;
 
-        for (j = 0; j < len; j++)
-            c[j] = 0;
+        /*
+         * Multiply in the ordinary O(N^2) way.
+         */
 
-        for (i = len - 1; i >= 0; i--) {
-            t = 0;
-            for (j = len - 1; j >= len - i - 1; j--) {
-                t += MUL_WORD(a[i], (BignumDblInt) b[j]);
-                t += (BignumDblInt) c[i + j + 1 - len];
-                c[i + j + 1 - len] = (BignumInt) t;
-                t = t >> BIGNUM_INT_BITS;
+        for (i = 0; i < len; i++)
+            c[i] = 0;
+
+        for (cps = c + len, ap = a + len; ap-- > a; cps--) {
+            carry = 0;
+            for (cp = cps, bp = b + len; bp--, cp-- > c ;) {
+                t = (MUL_WORD(*ap, *bp) + carry) + *cp;
+                *cp = (BignumInt) t;
+                carry = (BignumInt)(t >> BIGNUM_INT_BITS);
             }
         }
-
     }
 }
 
@@ -808,20 +815,15 @@ Bignum modpow_simple(Bignum base_in, Bignum exp, Bignum mod)
 	result[0]--;
 
     /* Free temporary arrays */
-    for (i = 0; i < 2 * mlen; i++)
-	a[i] = 0;
+    smemclr(a, 2 * mlen * sizeof(*a));
     sfree(a);
-    for (i = 0; i < scratchlen; i++)
-	scratch[i] = 0;
+    smemclr(scratch, scratchlen * sizeof(*scratch));
     sfree(scratch);
-    for (i = 0; i < 2 * mlen; i++)
-	b[i] = 0;
+    smemclr(b, 2 * mlen * sizeof(*b));
     sfree(b);
-    for (i = 0; i < mlen; i++)
-	m[i] = 0;
+    smemclr(m, mlen * sizeof(*m));
     sfree(m);
-    for (i = 0; i < mlen; i++)
-	n[i] = 0;
+    smemclr(n, mlen * sizeof(*n));
     sfree(n);
 
     freebn(base);
@@ -890,7 +892,7 @@ Bignum modpow(Bignum base_in, Bignum exp, Bignum mod)
 
     mninv = snewn(len, BignumInt);
     for (j = 0; j < len; j++)
-	mninv[len - 1 - j] = (j < inv[0] ? inv[j + 1] : 0);
+	mninv[len - 1 - j] = (j < (int)inv[0] ? inv[j + 1] : 0);
     freebn(inv);         /* we don't need this copy of it any more */
     /* Now negate mninv mod r, so it's the inverse of -n rather than +n. */
     x = snewn(len, BignumInt);
@@ -900,13 +902,13 @@ Bignum modpow(Bignum base_in, Bignum exp, Bignum mod)
 
     /* x = snewn(len, BignumInt); */ /* already done above */
     for (j = 0; j < len; j++)
-	x[len - 1 - j] = (j < base[0] ? base[j + 1] : 0);
+	x[len - 1 - j] = (j < (int)base[0] ? base[j + 1] : 0);
     freebn(base);        /* we don't need this copy of it any more */
 
     a = snewn(2*len, BignumInt);
     b = snewn(2*len, BignumInt);
     for (j = 0; j < len; j++)
-	a[2*len - 1 - j] = (j < rn[0] ? rn[j + 1] : 0);
+	a[2*len - 1 - j] = (j < (int)rn[0] ? rn[j + 1] : 0);
     freebn(rn);
 
     /* Scratch space for multiplies */
@@ -958,23 +960,17 @@ Bignum modpow(Bignum base_in, Bignum exp, Bignum mod)
 	result[0]--;
 
     /* Free temporary arrays */
-    for (i = 0; i < scratchlen; i++)
-	scratch[i] = 0;
+    smemclr(scratch, scratchlen * sizeof(*scratch));
     sfree(scratch);
-    for (i = 0; i < 2 * len; i++)
-	a[i] = 0;
+    smemclr(a, 2 * len * sizeof(*a));
     sfree(a);
-    for (i = 0; i < 2 * len; i++)
-	b[i] = 0;
+    smemclr(b, 2 * len * sizeof(*b));
     sfree(b);
-    for (i = 0; i < len; i++)
-	mninv[i] = 0;
+    smemclr(mninv, len * sizeof(*mninv));
     sfree(mninv);
-    for (i = 0; i < len; i++)
-	n[i] = 0;
+    smemclr(n, len * sizeof(*n));
     sfree(n);
-    for (i = 0; i < len; i++)
-	x[i] = 0;
+    smemclr(x, len * sizeof(*x));
     sfree(x);
 
     return result;
@@ -1011,6 +1007,13 @@ Bignum modmul(Bignum p, Bignum q, Bignum mod)
 
     pqlen = (p[0] > q[0] ? p[0] : q[0]);
 
+    /*
+     * Make sure that we're allowing enough space. The shifting below
+     * will underflow the vectors we allocate if pqlen is too small.
+     */
+    if (2*pqlen <= mlen)
+        pqlen = mlen/2 + 1;
+
     /* Allocate n of size pqlen, copy p to n */
     n = snewn(pqlen, BignumInt);
     i = pqlen - p[0];
@@ -1057,20 +1060,15 @@ Bignum modmul(Bignum p, Bignum q, Bignum mod)
 	result[0]--;
 
     /* Free temporary arrays */
-    for (i = 0; i < scratchlen; i++)
-	scratch[i] = 0;
+    smemclr(scratch, scratchlen * sizeof(*scratch));
     sfree(scratch);
-    for (i = 0; i < 2 * pqlen; i++)
-	a[i] = 0;
+    smemclr(a, 2 * pqlen * sizeof(*a));
     sfree(a);
-    for (i = 0; i < mlen; i++)
-	m[i] = 0;
+    smemclr(m, mlen * sizeof(*m));
     sfree(m);
-    for (i = 0; i < pqlen; i++)
-	n[i] = 0;
+    smemclr(n, pqlen * sizeof(*n));
     sfree(n);
-    for (i = 0; i < pqlen; i++)
-	o[i] = 0;
+    smemclr(o, pqlen * sizeof(*o));
     sfree(o);
 
     return result;
@@ -1140,11 +1138,9 @@ static void bigdivmod(Bignum p, Bignum mod, Bignum result, Bignum quotient)
     }
 
     /* Free temporary arrays */
-    for (i = 0; i < mlen; i++)
-	m[i] = 0;
+    smemclr(m, mlen * sizeof(*m));
     sfree(m);
-    for (i = 0; i < plen; i++)
-	n[i] = 0;
+    smemclr(n, plen * sizeof(*n));
     sfree(n);
 }
 
@@ -1391,8 +1387,7 @@ Bignum bigmuladd(Bignum a, Bignum b, Bignum addend)
     }
     ret[0] = maxspot;
 
-    for (i = 0; i < wslen; i++)
-        workspace[i] = 0;
+    smemclr(workspace, wslen * sizeof(*workspace));
     sfree(workspace);
     return ret;
 }
@@ -1743,6 +1738,7 @@ char *bignum_decimal(Bignum x)
     /*
      * Done.
      */
+    smemclr(workspace, x[0] * sizeof(*workspace));
     sfree(workspace);
     return ret;
 }
@@ -1754,7 +1750,7 @@ char *bignum_decimal(Bignum x)
 #include <ctype.h>
 
 /*
- * gcc -g -O0 -DTESTBN -o testbn sshbn.c misc.c -I unix -I charset
+ * gcc -Wall -g -O0 -DTESTBN -o testbn sshbn.c misc.c conf.c tree234.c unix/uxmisc.c -I. -I unix -I charset
  *
  * Then feed to this program's standard input the output of
  * testdata/bignum.py .
@@ -1828,7 +1824,7 @@ int main(int argc, char **argv)
             Bignum a, b, c, p;
 
             if (ptrnum != 3) {
-                printf("%d: mul with %d parameters, expected 3\n", line);
+                printf("%d: mul with %d parameters, expected 3\n", line, ptrnum);
                 exit(1);
             }
             a = bignum_from_bytes(ptrs[0], ptrs[1]-ptrs[0]);
@@ -1857,11 +1853,49 @@ int main(int argc, char **argv)
             freebn(b);
             freebn(c);
             freebn(p);
+        } else if (!strcmp(buf, "modmul")) {
+            Bignum a, b, m, c, p;
+
+            if (ptrnum != 4) {
+                printf("%d: modmul with %d parameters, expected 4\n",
+                       line, ptrnum);
+                exit(1);
+            }
+            a = bignum_from_bytes(ptrs[0], ptrs[1]-ptrs[0]);
+            b = bignum_from_bytes(ptrs[1], ptrs[2]-ptrs[1]);
+            m = bignum_from_bytes(ptrs[2], ptrs[3]-ptrs[2]);
+            c = bignum_from_bytes(ptrs[3], ptrs[4]-ptrs[3]);
+            p = modmul(a, b, m);
+
+            if (bignum_cmp(c, p) == 0) {
+                passes++;
+            } else {
+                char *as = bignum_decimal(a);
+                char *bs = bignum_decimal(b);
+                char *ms = bignum_decimal(m);
+                char *cs = bignum_decimal(c);
+                char *ps = bignum_decimal(p);
+                
+                printf("%d: fail: %s * %s mod %s gave %s expected %s\n",
+                       line, as, bs, ms, ps, cs);
+                fails++;
+
+                sfree(as);
+                sfree(bs);
+                sfree(ms);
+                sfree(cs);
+                sfree(ps);
+            }
+            freebn(a);
+            freebn(b);
+            freebn(m);
+            freebn(c);
+            freebn(p);
         } else if (!strcmp(buf, "pow")) {
             Bignum base, expt, modulus, expected, answer;
 
             if (ptrnum != 4) {
-                printf("%d: mul with %d parameters, expected 3\n", line);
+                printf("%d: mul with %d parameters, expected 4\n", line, ptrnum);
                 exit(1);
             }