Consistently use a single notation to refer to SSH protocol versions, as

[u/mdw/putty] / sshbn.c

diff --git a/sshbn.c b/sshbn.c
index 2d8359e..7792e4e 100644 (file)
--- a/sshbn.c
+++ b/sshbn.c
@@ -3,6 +3,7 @@
  */
 
 #include <stdio.h>
+#include <assert.h>
 #include <stdlib.h>
 #include <string.h>
 
@@ -133,7 +134,7 @@ static void internal_add_shifted(BignumInt *number,
     int bshift = shift % BIGNUM_INT_BITS;
     BignumDblInt addend;
 
-    addend = n << bshift;
+    addend = (BignumDblInt)n << bshift;
 
     while (addend) {
        addend += number[word];
@@ -184,17 +185,36 @@ static void internal_mod(BignumInt *a, int alen,
            ai1 = a[i + 1];
 
        /* Find q = h:a[i] / m0 */
-       DIVMOD_WORD(q, r, h, a[i], m0);
-
-       /* Refine our estimate of q by looking at
-          h:a[i]:a[i+1] / m0:m1 */
-       t = MUL_WORD(m1, q);
-       if (t > ((BignumDblInt) r << BIGNUM_INT_BITS) + ai1) {
-           q--;
-           t -= m1;
-           r = (r + m0) & BIGNUM_INT_MASK;     /* overflow? */
-           if (r >= (BignumDblInt) m0 &&
-               t > ((BignumDblInt) r << BIGNUM_INT_BITS) + ai1) q--;
+       if (h >= m0) {
+           /*
+            * Special case.
+            * 
+            * To illustrate it, suppose a BignumInt is 8 bits, and
+            * we are dividing (say) A1:23:45:67 by A1:B2:C3. Then
+            * our initial division will be 0xA123 / 0xA1, which
+            * will give a quotient of 0x100 and a divide overflow.
+            * However, the invariants in this division algorithm
+            * are not violated, since the full number A1:23:... is
+            * _less_ than the quotient prefix A1:B2:... and so the
+            * following correction loop would have sorted it out.
+            * 
+            * In this situation we set q to be the largest
+            * quotient we _can_ stomach (0xFF, of course).
+            */
+           q = BIGNUM_INT_MASK;
+       } else {
+           DIVMOD_WORD(q, r, h, a[i], m0);
+
+           /* Refine our estimate of q by looking at
+            h:a[i]:a[i+1] / m0:m1 */
+           t = MUL_WORD(m1, q);
+           if (t > ((BignumDblInt) r << BIGNUM_INT_BITS) + ai1) {
+               q--;
+               t -= m1;
+               r = (r + m0) & BIGNUM_INT_MASK;     /* overflow? */
+               if (r >= (BignumDblInt) m0 &&
+                   t > ((BignumDblInt) r << BIGNUM_INT_BITS) + ai1) q--;
+           }
        }
 
        /* Subtract q * m from a[i...] */
@@ -226,16 +246,25 @@ static void internal_mod(BignumInt *a, int alen,
 
 /*
  * Compute (base ^ exp) % mod.
- * The base MUST be smaller than the modulus.
- * The most significant word of mod MUST be non-zero.
- * We assume that the result array is the same size as the mod array.
  */
-Bignum modpow(Bignum base, Bignum exp, Bignum mod)
+Bignum modpow(Bignum base_in, Bignum exp, Bignum mod)
 {
     BignumInt *a, *b, *n, *m;
     int mshift;
     int mlen, i, j;
-    Bignum result;
+    Bignum base, result;
+
+    /*
+     * The most significant word of mod needs to be non-zero. It
+     * should already be, but let's make sure.
+     */
+    assert(mod[mod[0]] != 0);
+
+    /*
+     * Make sure the base is smaller than the modulus, by reducing
+     * it modulo the modulus if not.
+     */
+    base = bigmod(base_in, mod);
 
     /* Allocate m of size mlen, copy mod to m */
     /* We use big endian internally */
@@ -331,6 +360,8 @@ Bignum modpow(Bignum base, Bignum exp, Bignum mod)
        n[i] = 0;
     sfree(n);
 
+    freebn(base);
+
     return result;
 }
 
@@ -527,20 +558,26 @@ Bignum bignum_from_bytes(const unsigned char *data, int nbytes)
 }
 
 /*
- * Read an ssh1-format bignum from a data buffer. Return the number
- * of bytes consumed.
+ * Read an SSH-1-format bignum from a data buffer. Return the number
+ * of bytes consumed, or -1 if there wasn't enough data.
  */
-int ssh1_read_bignum(const unsigned char *data, Bignum * result)
+int ssh1_read_bignum(const unsigned char *data, int len, Bignum * result)
 {
     const unsigned char *p = data;
     int i;
     int w, b;
 
+    if (len < 2)
+       return -1;
+
     w = 0;
     for (i = 0; i < 2; i++)
        w = (w << 8) + *p++;
     b = (w + 7) / 8;                  /* bits -> bytes */
 
+    if (len < b+2)
+       return -1;
+
     if (!result)                      /* just return length */
        return b + 2;
 
@@ -550,7 +587,7 @@ int ssh1_read_bignum(const unsigned char *data, Bignum * result)
 }
 
 /*
- * Return the bit count of a bignum, for ssh1 encoding.
+ * Return the bit count of a bignum, for SSH-1 encoding.
  */
 int bignum_bitcount(Bignum bn)
 {
@@ -561,7 +598,7 @@ int bignum_bitcount(Bignum bn)
 }
 
 /*
- * Return the byte length of a bignum when ssh1 encoded.
+ * Return the byte length of a bignum when SSH-1 encoded.
  */
 int ssh1_bignum_length(Bignum bn)
 {
@@ -569,7 +606,7 @@ int ssh1_bignum_length(Bignum bn)
 }
 
 /*
- * Return the byte length of a bignum when ssh2 encoded.
+ * Return the byte length of a bignum when SSH-2 encoded.
  */
 int ssh2_bignum_length(Bignum bn)
 {
@@ -617,7 +654,7 @@ void bignum_set_bit(Bignum bn, int bitnum, int value)
 }
 
 /*
- * Write a ssh1-format bignum into a buffer. It is assumed the
+ * Write a SSH-1-format bignum into a buffer. It is assumed the
  * buffer is big enough. Returns the number of bytes used.
  */
 int ssh1_write_bignum(void *data, Bignum bn)
@@ -729,6 +766,7 @@ Bignum bigmuladd(Bignum a, Bignum b, Bignum addend)
     }
     ret[0] = maxspot;
 
+    sfree(workspace);
     return ret;
 }
 
@@ -908,6 +946,7 @@ Bignum modinv(Bignum number, Bignum modulus)
        x = bigmuladd(q, xp, t);
        sign = -sign;
        freebn(t);
+       freebn(q);
     }
 
     freebn(b);
@@ -1009,5 +1048,6 @@ char *bignum_decimal(Bignum x)
     /*
      * Done.
      */
+    sfree(workspace);
     return ret;
 }