+
+/*
+ * Compute (p * q) % 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.
+ */
+void modmul(Bignum p, Bignum q, Bignum mod, Bignum result)
+{
+ unsigned short *a, *n, *m, *o;
+ int mshift;
+ int pqlen, mlen, i, j;
+
+ /* Allocate m of size mlen, copy mod to m */
+ /* We use big endian internally */
+ mlen = mod[0];
+ m = malloc(mlen * sizeof(unsigned short));
+ for (j = 0; j < mlen; j++) m[j] = mod[mod[0] - j];
+
+ /* Shift m left to make msb bit set */
+ for (mshift = 0; mshift < 15; mshift++)
+ if ((m[0] << mshift) & 0x8000) break;
+ if (mshift) {
+ for (i = 0; i < mlen - 1; i++)
+ m[i] = (m[i] << mshift) | (m[i+1] >> (16-mshift));
+ m[mlen-1] = m[mlen-1] << mshift;
+ }
+
+ pqlen = (p[0] > q[0] ? p[0] : q[0]);
+
+ /* Allocate n of size pqlen, copy p to n */
+ n = malloc(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));
+ 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));
+
+ /* Main computation */
+ bigmul(n, o, a, pqlen);
+ bigmod(a, m, mlen, 2*pqlen);
+
+ /* Fixup result in case the modulus was shifted */
+ if (mshift) {
+ for (i = 2*pqlen - mlen - 1; i < 2*pqlen - 1; i++)
+ a[i] = (a[i] << mshift) | (a[i+1] >> (16-mshift));
+ a[2*pqlen-1] = a[2*pqlen-1] << mshift;
+ bigmod(a, m, mlen, pqlen*2);
+ for (i = 2*pqlen - 1; i >= 2*pqlen - mlen; i--)
+ a[i] = (a[i] >> mshift) | (a[i-1] << (16-mshift));
+ }
+
+ /* Copy result to buffer */
+ for (i = 0; i < mlen; i++)
+ result[result[0] - i] = a[i+2*pqlen-mlen];
+
+ /* 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);
+}
+
+/*
+ * Decrement a number.
+ */
+void decbn(Bignum bn) {
+ int i = 1;
+ while (i < bn[0] && bn[i] == 0)
+ bn[i++] = 0xFFFF;
+ bn[i]--;
+}
+
+/*
+ * Read an ssh1-format bignum from a data buffer. Return the number
+ * of bytes consumed.
+ */
+int ssh1_read_bignum(unsigned char *data, Bignum *result) {
+ unsigned char *p = data;
+ Bignum bn;
+ int i;
+ int w, b;
+
+ w = 0;
+ for (i=0; i<2; i++)
+ w = (w << 8) + *p++;
+
+ b = (w+7)/8; /* bits -> bytes */
+ w = (w+15)/16; /* bits -> words */
+
+ bn = newbn(w);
+
+ for (i=1; i<=w; i++)
+ bn[i] = 0;
+ for (i=b; i-- ;) {
+ unsigned char byte = *p++;
+ if (i & 1)
+ bn[1+i/2] |= byte<<8;
+ else
+ bn[1+i/2] |= byte;
+ }
+
+ *result = bn;
+
+ return p - data;
+}