X-Git-Url: https://git.distorted.org.uk/u/mdw/putty/blobdiff_plain/0016d70b76e2706064b54c9dd24d45a45646b0de..985b644054f5e0d777184c48bfd8a97e824705fd:/sshbn.c

diff --git a/sshbn.c b/sshbn.c
index d32eb1bb..7792e4ec 100644
--- a/sshbn.c
+++ b/sshbn.c
@@ -185,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...] */
@@ -539,7 +558,7 @@ Bignum bignum_from_bytes(const unsigned char *data, int nbytes)
 }
 
 /*
- * Read an ssh1-format bignum from a data buffer. Return the number
+ * 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, int len, Bignum * result)
@@ -568,7 +587,7 @@ int ssh1_read_bignum(const unsigned char *data, int len, 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)
 {
@@ -579,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)
 {
@@ -587,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)
 {
@@ -635,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)