X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/putty/blobdiff_plain/32874aeac8dacbca26663777b39a79efc5d8dc4b..8dacc30e3a1bd57526c21b701383f69ef93a6703:/sshbn.c diff --git a/sshbn.c b/sshbn.c index 0d0fce34..d404ed06 100644 --- a/sshbn.c +++ b/sshbn.c @@ -6,13 +6,7 @@ #include #include -#if 0 // use PuTTY main debugging for diagbn() -#include -#include "putty.h" -#define debugprint debug -#else -#define debugprint(x) printf x -#endif +#include "misc.h" #define BIGNUM_INTERNAL typedef unsigned short *Bignum; @@ -40,7 +34,7 @@ Bignum Zero = bnZero, One = bnOne; static Bignum newbn(int length) { - Bignum b = smalloc((length + 1) * sizeof(unsigned short)); + Bignum b = snewn(length + 1, unsigned short); if (!b) abort(); /* FIXME */ memset(b, 0, (length + 1) * sizeof(*b)); @@ -56,7 +50,7 @@ void bn_restore_invariant(Bignum b) Bignum copybn(Bignum orig) { - Bignum b = smalloc((orig[0] + 1) * sizeof(unsigned short)); + Bignum b = snewn(orig[0] + 1, unsigned short); if (!b) abort(); /* FIXME */ memcpy(b, orig, (orig[0] + 1) * sizeof(*b)); @@ -222,7 +216,7 @@ Bignum modpow(Bignum base, Bignum exp, Bignum mod) /* Allocate m of size mlen, copy mod to m */ /* We use big endian internally */ mlen = mod[0]; - m = smalloc(mlen * sizeof(unsigned short)); + m = snewn(mlen, unsigned short); for (j = 0; j < mlen; j++) m[j] = mod[mod[0] - j]; @@ -237,7 +231,7 @@ Bignum modpow(Bignum base, Bignum exp, Bignum mod) } /* Allocate n of size mlen, copy base to n */ - n = smalloc(mlen * sizeof(unsigned short)); + n = snewn(mlen, unsigned short); i = mlen - base[0]; for (j = 0; j < i; j++) n[j] = 0; @@ -245,8 +239,8 @@ Bignum modpow(Bignum base, Bignum exp, Bignum mod) n[i + j] = base[base[0] - j]; /* Allocate a and b of size 2*mlen. Set a = 1 */ - a = smalloc(2 * mlen * sizeof(unsigned short)); - b = smalloc(2 * mlen * sizeof(unsigned short)); + a = snewn(2 * mlen, unsigned short); + b = snewn(2 * mlen, unsigned short); for (i = 0; i < 2 * mlen; i++) a[i] = 0; a[2 * mlen - 1] = 1; @@ -331,7 +325,7 @@ Bignum modmul(Bignum p, Bignum q, Bignum mod) /* Allocate m of size mlen, copy mod to m */ /* We use big endian internally */ mlen = mod[0]; - m = smalloc(mlen * sizeof(unsigned short)); + m = snewn(mlen, unsigned short); for (j = 0; j < mlen; j++) m[j] = mod[mod[0] - j]; @@ -348,7 +342,7 @@ Bignum modmul(Bignum p, Bignum q, Bignum mod) pqlen = (p[0] > q[0] ? p[0] : q[0]); /* Allocate n of size pqlen, copy p to n */ - n = smalloc(pqlen * sizeof(unsigned short)); + n = snewn(pqlen, unsigned short); i = pqlen - p[0]; for (j = 0; j < i; j++) n[j] = 0; @@ -356,7 +350,7 @@ Bignum modmul(Bignum p, Bignum q, Bignum mod) n[i + j] = p[p[0] - j]; /* Allocate o of size pqlen, copy q to o */ - o = smalloc(pqlen * sizeof(unsigned short)); + o = snewn(pqlen, unsigned short); i = pqlen - q[0]; for (j = 0; j < i; j++) o[j] = 0; @@ -364,7 +358,7 @@ Bignum modmul(Bignum p, Bignum q, Bignum mod) o[i + j] = q[q[0] - j]; /* Allocate a of size 2*pqlen for result */ - a = smalloc(2 * pqlen * sizeof(unsigned short)); + a = snewn(2 * pqlen, unsigned short); /* Main computation */ internal_mul(n, o, a, pqlen); @@ -409,9 +403,10 @@ Bignum modmul(Bignum p, Bignum q, Bignum mod) * Compute p % mod. * The most significant word of mod MUST be non-zero. * We assume that the result array is the same size as the mod array. - * We optionally write out a quotient. + * We optionally write out a quotient if `quotient' is non-NULL. + * We can avoid writing out the result if `result' is NULL. */ -void bigmod(Bignum p, Bignum mod, Bignum result, Bignum quotient) +static void bigdivmod(Bignum p, Bignum mod, Bignum result, Bignum quotient) { unsigned short *n, *m; int mshift; @@ -420,7 +415,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 = smalloc(mlen * sizeof(unsigned short)); + m = snewn(mlen, unsigned short); for (j = 0; j < mlen; j++) m[j] = mod[mod[0] - j]; @@ -440,7 +435,7 @@ void bigmod(Bignum p, Bignum mod, Bignum result, Bignum quotient) plen = mlen + 1; /* Allocate n of size plen, copy p to n */ - n = smalloc(plen * sizeof(unsigned short)); + n = snewn(plen, unsigned short); for (j = 0; j < plen; j++) n[j] = 0; for (j = 1; j <= p[0]; j++) @@ -460,9 +455,11 @@ void bigmod(Bignum p, Bignum mod, Bignum result, Bignum quotient) } /* Copy result to buffer */ - for (i = 1; i <= result[0]; i++) { - int j = plen - i; - result[i] = j >= 0 ? n[j] : 0; + if (result) { + for (i = 1; i <= result[0]; i++) { + int j = plen - i; + result[i] = j >= 0 ? n[j] : 0; + } } /* Free temporary arrays */ @@ -485,7 +482,7 @@ void decbn(Bignum bn) bn[i]--; } -Bignum bignum_from_bytes(unsigned char *data, int nbytes) +Bignum bignum_from_bytes(const unsigned char *data, int nbytes) { Bignum result; int w, i; @@ -512,9 +509,9 @@ Bignum bignum_from_bytes(unsigned char *data, int nbytes) * Read an ssh1-format bignum from a data buffer. Return the number * of bytes consumed. */ -int ssh1_read_bignum(unsigned char *data, Bignum * result) +int ssh1_read_bignum(const unsigned char *data, Bignum * result) { - unsigned char *p = data; + const unsigned char *p = data; int i; int w, b; @@ -676,7 +673,7 @@ Bignum bigmuladd(Bignum a, Bignum b, Bignum addend) Bignum ret; /* mlen space for a, mlen space for b, 2*mlen for result */ - workspace = smalloc(mlen * 4 * sizeof(unsigned short)); + workspace = snewn(mlen * 4, 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); @@ -749,16 +746,17 @@ Bignum bignum_bitmask(Bignum n) } /* - * Convert a (max 16-bit) short into a bignum. + * Convert a (max 32-bit) long into a bignum. */ -Bignum bignum_from_short(unsigned short n) +Bignum bignum_from_long(unsigned long n) { Bignum ret; - ret = newbn(2); - ret[1] = n & 0xFFFF; - ret[2] = (n >> 16) & 0xFFFF; - ret[0] = (ret[2] ? 2 : 1); + ret = newbn(3); + ret[1] = (unsigned short)(n & 0xFFFF); + ret[2] = (unsigned short)((n >> 16) & 0xFFFF); + ret[3] = 0; + ret[0] = (ret[2] ? 2 : 1); return ret; } @@ -799,26 +797,49 @@ unsigned short bignum_mod_short(Bignum number, unsigned short modulus) return (unsigned short) r; } +#if 0 void diagbn(char *prefix, Bignum md) { +#ifdef DEBUG int i, nibbles, morenibbles; static const char hex[] = "0123456789ABCDEF"; - debugprint(("%s0x", prefix ? prefix : "")); + debug(("%s0x", prefix ? prefix : "")); nibbles = (3 + bignum_bitcount(md)) / 4; if (nibbles < 1) nibbles = 1; morenibbles = 4 * md[0] - nibbles; for (i = 0; i < morenibbles; i++) - debugprint(("-")); + debug(("-")); for (i = nibbles; i--;) - debugprint( - ("%c", - hex[(bignum_byte(md, i / 2) >> (4 * (i % 2))) & 0xF])); + debug(("%c", + hex[(bignum_byte(md, i / 2) >> (4 * (i % 2))) & 0xF])); if (prefix) - debugprint(("\n")); + debug(("\n")); +#endif +} +#endif + +/* + * Simple division. + */ +Bignum bigdiv(Bignum a, Bignum b) +{ + Bignum q = newbn(a[0]); + bigdivmod(a, b, NULL, q); + return q; +} + +/* + * Simple remainder. + */ +Bignum bigmod(Bignum a, Bignum b) +{ + Bignum r = newbn(b[0]); + bigdivmod(a, b, r, NULL); + return r; } /* @@ -829,12 +850,9 @@ Bignum biggcd(Bignum av, Bignum bv) Bignum a = copybn(av); Bignum b = copybn(bv); - diagbn("a = ", a); - diagbn("b = ", b); while (bignum_cmp(b, Zero) != 0) { Bignum t = newbn(b[0]); - bigmod(a, b, t, NULL); - diagbn("t = ", t); + bigdivmod(a, b, t, NULL); while (t[0] > 1 && t[t[0]] == 0) t[0]--; freebn(a); @@ -860,7 +878,7 @@ Bignum modinv(Bignum number, Bignum modulus) while (bignum_cmp(b, One) != 0) { Bignum t = newbn(b[0]); Bignum q = newbn(a[0]); - bigmod(a, b, t, q); + bigdivmod(a, b, t, q); while (t[0] > 1 && t[t[0]] == 0) t[0]--; freebn(a); @@ -931,14 +949,14 @@ char *bignum_decimal(Bignum x) i = bignum_bitcount(x); ndigits = (28 * i + 92) / 93; /* multiply by 28/93 and round up */ ndigits++; /* allow for trailing \0 */ - ret = smalloc(ndigits); + ret = snewn(ndigits, char); /* * 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]); + workspace = snewn(x[0], unsigned short); for (i = 0; i < x[0]; i++) workspace[i] = x[x[0] - i];