X-Git-Url: https://git.distorted.org.uk/u/mdw/putty/blobdiff_plain/9400cf6f5d03ad3d258bfc6b373cbb0b52bf5863..0965bee0865fd8ea129b2de62a3c50e09c59a184:/sshbn.c

diff --git a/sshbn.c b/sshbn.c
index 51e59015..6615d41d 100644
--- a/sshbn.c
+++ b/sshbn.c
@@ -11,10 +11,24 @@
 unsigned short bnZero[1] = { 0 };
 unsigned short bnOne[2] = { 1, 1 };
 
+/*
+ * The Bignum format is an array of `unsigned short'. The first
+ * element of the array counts the remaining elements. The
+ * remaining elements express the actual number, base 2^16, _least_
+ * significant digit first. (So it's trivial to extract the bit
+ * with value 2^n for any n.)
+ *
+ * All Bignums in this module are positive. Negative numbers must
+ * be dealt with outside it.
+ *
+ * INVARIANT: the most significant word of any Bignum must be
+ * nonzero.
+ */
+
 Bignum Zero = bnZero, One = bnOne;
 
 Bignum newbn(int length) {
-    Bignum b = malloc((length+1)*sizeof(unsigned short));
+    Bignum b = smalloc((length+1)*sizeof(unsigned short));
     if (!b)
 	abort();		       /* FIXME */
     memset(b, 0, (length+1)*sizeof(*b));
@@ -23,7 +37,7 @@ Bignum newbn(int length) {
 }
 
 Bignum copybn(Bignum orig) {
-    Bignum b = malloc((orig[0]+1)*sizeof(unsigned short));
+    Bignum b = smalloc((orig[0]+1)*sizeof(unsigned short));
     if (!b)
 	abort();		       /* FIXME */
     memcpy(b, orig, (orig[0]+1)*sizeof(*b));
@@ -35,7 +49,7 @@ void freebn(Bignum b) {
      * Burn the evidence, just in case.
      */
     memset(b, 0, sizeof(b[0]) * (b[0] + 1));
-    free(b);
+    sfree(b);
 }
 
 /*
@@ -65,17 +79,17 @@ static void internal_mul(unsigned short *a, unsigned short *b,
     }
 }
 
-static int internal_add_shifted(unsigned short *number,
-                                unsigned short n, int shift) {
+static void internal_add_shifted(unsigned short *number,
+                                unsigned n, int shift) {
     int word = 1 + (shift / 16);
     int bshift = shift % 16;
-    unsigned long carry, addend;
+    unsigned long addend;
 
     addend = n << bshift;
 
     while (addend) {
         addend += number[word];
-        number[word] = addend & 0xFFFF;
+        number[word] = (unsigned short) addend & 0xFFFF;
         addend >>= 16;
         word++;
     }
@@ -170,16 +184,17 @@ static void internal_mod(unsigned short *a, int alen,
  * The most significant word of mod MUST be non-zero.
  * We assume that the result array is the same size as the mod array.
  */
-void modpow(Bignum base, Bignum exp, Bignum mod, Bignum result)
+Bignum modpow(Bignum base, Bignum exp, Bignum mod)
 {
     unsigned short *a, *b, *n, *m;
     int mshift;
     int mlen, i, j;
+    Bignum result;
 
     /* Allocate m of size mlen, copy mod to m */
     /* We use big endian internally */
     mlen = mod[0];
-    m = malloc(mlen * sizeof(unsigned short));
+    m = smalloc(mlen * sizeof(unsigned short));
     for (j = 0; j < mlen; j++) m[j] = mod[mod[0] - j];
 
     /* Shift m left to make msb bit set */
@@ -192,14 +207,14 @@ void modpow(Bignum base, Bignum exp, Bignum mod, Bignum result)
     }
 
     /* Allocate n of size mlen, copy base to n */
-    n = malloc(mlen * sizeof(unsigned short));
+    n = smalloc(mlen * sizeof(unsigned short));
     i = mlen - base[0];
     for (j = 0; j < i; j++) n[j] = 0;
     for (j = 0; j < base[0]; j++) n[i+j] = base[base[0] - j];
 
     /* Allocate a and b of size 2*mlen. Set a = 1 */
-    a = malloc(2 * mlen * sizeof(unsigned short));
-    b = malloc(2 * mlen * sizeof(unsigned short));
+    a = smalloc(2 * mlen * sizeof(unsigned short));
+    b = smalloc(2 * mlen * sizeof(unsigned short));
     for (i = 0; i < 2*mlen; i++) a[i] = 0;
     a[2*mlen-1] = 1;
 
@@ -238,14 +253,18 @@ void modpow(Bignum base, Bignum exp, Bignum mod, Bignum result)
     }
 
     /* Copy result to buffer */
+    result = newbn(mod[0]);
     for (i = 0; i < mlen; i++)
 	result[result[0] - i] = a[i+mlen];
+    while (result[0] > 1 && result[result[0]] == 0) result[0]--;
 
     /* Free temporary arrays */
-    for (i = 0; i < 2*mlen; i++) a[i] = 0; free(a);
-    for (i = 0; i < 2*mlen; i++) b[i] = 0; free(b);
-    for (i = 0; i < mlen; i++) m[i] = 0; free(m);
-    for (i = 0; i < mlen; i++) n[i] = 0; free(n);
+    for (i = 0; i < 2*mlen; i++) a[i] = 0; sfree(a);
+    for (i = 0; i < 2*mlen; i++) b[i] = 0; sfree(b);
+    for (i = 0; i < mlen; i++) m[i] = 0; sfree(m);
+    for (i = 0; i < mlen; i++) n[i] = 0; sfree(n);
+
+    return result;
 }
 
 /*
@@ -253,16 +272,17 @@ void modpow(Bignum base, Bignum exp, Bignum mod, Bignum result)
  * The most significant word of mod MUST be non-zero.
  * We assume that the result array is the same size as the mod array.
  */
-void modmul(Bignum p, Bignum q, Bignum mod, Bignum result)
+Bignum modmul(Bignum p, Bignum q, Bignum mod)
 {
     unsigned short *a, *n, *m, *o;
     int mshift;
     int pqlen, mlen, i, j;
+    Bignum result;
 
     /* Allocate m of size mlen, copy mod to m */
     /* We use big endian internally */
     mlen = mod[0];
-    m = malloc(mlen * sizeof(unsigned short));
+    m = smalloc(mlen * sizeof(unsigned short));
     for (j = 0; j < mlen; j++) m[j] = mod[mod[0] - j];
 
     /* Shift m left to make msb bit set */
@@ -277,19 +297,19 @@ void modmul(Bignum p, Bignum q, Bignum mod, Bignum result)
     pqlen = (p[0] > q[0] ? p[0] : q[0]);
 
     /* Allocate n of size pqlen, copy p to n */
-    n = malloc(pqlen * sizeof(unsigned short));
+    n = smalloc(pqlen * sizeof(unsigned short));
     i = pqlen - p[0];
     for (j = 0; j < i; j++) n[j] = 0;
     for (j = 0; j < p[0]; j++) n[i+j] = p[p[0] - j];
 
     /* Allocate o of size pqlen, copy q to o */
-    o = malloc(pqlen * sizeof(unsigned short));
+    o = smalloc(pqlen * sizeof(unsigned short));
     i = pqlen - q[0];
     for (j = 0; j < i; j++) o[j] = 0;
     for (j = 0; j < q[0]; j++) o[i+j] = q[q[0] - j];
 
     /* Allocate a of size 2*pqlen for result */
-    a = malloc(2 * pqlen * sizeof(unsigned short));
+    a = smalloc(2 * pqlen * sizeof(unsigned short));
 
     /* Main computation */
     internal_mul(n, o, a, pqlen);
@@ -306,14 +326,18 @@ void modmul(Bignum p, Bignum q, Bignum mod, Bignum result)
     }
 
     /* Copy result to buffer */
+    result = newbn(mod[0]);
     for (i = 0; i < mlen; i++)
 	result[result[0] - i] = a[i+2*pqlen-mlen];
+    while (result[0] > 1 && result[result[0]] == 0) result[0]--;
 
     /* Free temporary arrays */
-    for (i = 0; i < 2*pqlen; i++) a[i] = 0; free(a);
-    for (i = 0; i < mlen; i++) m[i] = 0; free(m);
-    for (i = 0; i < pqlen; i++) n[i] = 0; free(n);
-    for (i = 0; i < pqlen; i++) o[i] = 0; free(o);
+    for (i = 0; i < 2*pqlen; i++) a[i] = 0; sfree(a);
+    for (i = 0; i < mlen; i++) m[i] = 0; sfree(m);
+    for (i = 0; i < pqlen; i++) n[i] = 0; sfree(n);
+    for (i = 0; i < pqlen; i++) o[i] = 0; sfree(o);
+
+    return result;
 }
 
 /*
@@ -331,7 +355,7 @@ void bigmod(Bignum p, Bignum mod, Bignum result, Bignum quotient)
     /* Allocate m of size mlen, copy mod to m */
     /* We use big endian internally */
     mlen = mod[0];
-    m = malloc(mlen * sizeof(unsigned short));
+    m = smalloc(mlen * sizeof(unsigned short));
     for (j = 0; j < mlen; j++) m[j] = mod[mod[0] - j];
 
     /* Shift m left to make msb bit set */
@@ -348,7 +372,7 @@ void bigmod(Bignum p, Bignum mod, Bignum result, Bignum quotient)
     if (plen <= mlen) plen = mlen+1;
 
     /* Allocate n of size plen, copy p to n */
-    n = malloc(plen * sizeof(unsigned short));
+    n = smalloc(plen * sizeof(unsigned short));
     for (j = 0; j < plen; j++) n[j] = 0;
     for (j = 1; j <= p[0]; j++) n[plen-j] = p[j];
 
@@ -372,8 +396,8 @@ void bigmod(Bignum p, Bignum mod, Bignum result, Bignum quotient)
     }
 
     /* Free temporary arrays */
-    for (i = 0; i < mlen; i++) m[i] = 0; free(m);
-    for (i = 0; i < plen; i++) n[i] = 0; free(n);
+    for (i = 0; i < mlen; i++) m[i] = 0; sfree(m);
+    for (i = 0; i < plen; i++) n[i] = 0; sfree(n);
 }
 
 /*
@@ -550,7 +574,7 @@ Bignum bigmuladd(Bignum a, Bignum b, Bignum addend) {
     Bignum ret;
 
     /* mlen space for a, mlen space for b, 2*mlen for result */
-    workspace = malloc(mlen * 4 * sizeof(unsigned short));
+    workspace = smalloc(mlen * 4 * sizeof(unsigned short));
     for (i = 0; i < mlen; i++) {
         workspace[0*mlen + i] = (mlen-i <= a[0] ? a[mlen-i] : 0);
         workspace[1*mlen + i] = (mlen-i <= b[0] ? b[mlen-i] : 0);
@@ -577,7 +601,7 @@ Bignum bigmuladd(Bignum a, Bignum b, Bignum addend) {
         for (i = 1; i <= rlen; i++) {
             carry += (i <= ret[0] ? ret[i] : 0);
             carry += (i <= addend[0] ? addend[i] : 0);
-            ret[i] = carry & 0xFFFF;
+            ret[i] = (unsigned short) carry & 0xFFFF;
             carry >>= 16;
             if (ret[i] != 0 && i > maxspot)
                 maxspot = i;
@@ -620,7 +644,7 @@ Bignum bignum_add_long(Bignum number, unsigned long addend) {
         carry += addend & 0xFFFF;
         carry += (i <= number[0] ? number[i] : 0);
         addend >>= 16;
-        ret[i] = carry & 0xFFFF;
+        ret[i] = (unsigned short) carry & 0xFFFF;
         carry >>= 16;
         if (ret[i] != 0)
             maxspot = i;
@@ -633,7 +657,6 @@ Bignum bignum_add_long(Bignum number, unsigned long addend) {
  * Compute the residue of a bignum, modulo a (max 16-bit) short.
  */
 unsigned short bignum_mod_short(Bignum number, unsigned short modulus) {
-    Bignum ret;
     unsigned long mod, r;
     int i;
 
@@ -641,7 +664,7 @@ unsigned short bignum_mod_short(Bignum number, unsigned short modulus) {
     mod = modulus;
     for (i = number[0]; i > 0; i--)
         r = (r * 65536 + number[i]) % mod;
-    return r;
+    return (unsigned short) r;
 }
 
 static void diagbn(char *prefix, Bignum md) {
@@ -736,3 +759,74 @@ Bignum modinv(Bignum number, Bignum modulus) {
     /* and return. */
     return x;
 }
+
+/*
+ * Render a bignum into decimal. Return a malloced string holding
+ * the decimal representation.
+ */
+char *bignum_decimal(Bignum x) {
+    int ndigits, ndigit;
+    int i, iszero;
+    unsigned long carry;
+    char *ret;
+    unsigned short *workspace;
+
+    /*
+     * First, estimate the number of digits. Since log(10)/log(2)
+     * is just greater than 93/28 (the joys of continued fraction
+     * approximations...) we know that for every 93 bits, we need
+     * at most 28 digits. This will tell us how much to malloc.
+     *
+     * Formally: if x has i bits, that means x is strictly less
+     * than 2^i. Since 2 is less than 10^(28/93), this is less than
+     * 10^(28i/93). We need an integer power of ten, so we must
+     * round up (rounding down might make it less than x again).
+     * Therefore if we multiply the bit count by 28/93, rounding
+     * up, we will have enough digits.
+     */
+    i = ssh1_bignum_bitcount(x);
+    ndigits = (28*i + 92)/93;          /* multiply by 28/93 and round up */
+    ndigits++;                         /* allow for trailing \0 */
+    ret = smalloc(ndigits);
+
+    /*
+     * Now allocate some workspace to hold the binary form as we
+     * repeatedly divide it by ten. Initialise this to the
+     * big-endian form of the number.
+     */
+    workspace = smalloc(sizeof(unsigned short) * x[0]);
+    for (i = 0; i < x[0]; i++)
+        workspace[i] = x[x[0] - i];
+
+    /*
+     * Next, write the decimal number starting with the last digit.
+     * We use ordinary short division, dividing 10 into the
+     * workspace.
+     */
+    ndigit = ndigits-1;
+    ret[ndigit] = '\0';
+    do {
+        iszero = 1;
+        carry = 0;
+        for (i = 0; i < x[0]; i++) {
+            carry = (carry << 16) + workspace[i];
+            workspace[i] = (unsigned short) (carry / 10);
+            if (workspace[i])
+                iszero = 0;
+            carry %= 10;
+        }
+        ret[--ndigit] = (char)(carry + '0');
+    } while (!iszero);
+
+    /*
+     * There's a chance we've fallen short of the start of the
+     * string. Correct if so.
+     */
+    if (ndigit > 0)
+        memmove(ret, ret+ndigit, ndigits-ndigit);
+
+    /*
+     * Done.
+     */
+    return ret;
+}