X-Git-Url: https://asedeno.scripts.mit.edu/gitweb/?a=blobdiff_plain;f=sshrsa.c;h=3a017c2945a69bde69b7c561af586279e030527d;hb=fe500c4d01e0634014fd371156540cf1529cb24a;hp=70cf9bbeaec6edf187220adee459782c7e59e0aa;hpb=c74130d423fd83a65c51b7634e3c34aaf557ae68;p=PuTTY.git

diff --git a/sshrsa.c b/sshrsa.c
index 70cf9bbe..3a017c29 100644
--- a/sshrsa.c
+++ b/sshrsa.c
@@ -1,13 +1,10 @@
 /*
  * RSA implementation just sufficient for ssh client-side
  * initialisation step
+ *
+ * Rewritten for more speed by Joris van Rantwijk, Jun 1999.
  */
 
-/*#include <windows.h>
-#define RSADEBUG
-#define DLVL 2
-#include "stel.h"*/
-
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
@@ -57,193 +54,188 @@ static void freebn(Bignum b) {
     free(b);
 }
 
-static int msb(Bignum r) {
-    int i;
-    int j;
-    unsigned short n;
-
-    for (i=r[0]; i>0; i--)
-	if (r[i])
-	    break;
-
-    j = (i-1)*16;
-    n = r[i];
-    if (n & 0xFF00) j += 8, n >>= 8;
-    if (n & 0x00F0) j += 4, n >>= 4;
-    if (n & 0x000C) j += 2, n >>= 2;
-    if (n & 0x0002) j += 1, n >>= 1;
-
-    return j;
-}
-
-static void add(Bignum r1, Bignum r2, Bignum result) {
-    int i;
-    long stuff = 0;
-
-    enter((">add\n"));
-    debug(r1);
-    debug(r2);
-
-    for (i = 1 ;; i++) {
-	if (i <= r1[0])
-	    stuff += r1[i];
-	if (i <= r2[0])
-	    stuff += r2[i];
-	if (i <= result[0])
-	    result[i] = stuff & 0xFFFFU;
-	if (i > r1[0] && i > r2[0] && i >= result[0])
-	    break;
-	stuff >>= 16;
+/*
+ * Compute c = a * b.
+ * Input is in the first len words of a and b.
+ * Result is returned in the first 2*len words of c.
+ */
+static void bigmul(unsigned short *a, unsigned short *b, unsigned short *c,
+                   int len)
+{
+    int i, j;
+    unsigned long ai, t;
+
+    for (j = len - 1; j >= 0; j--)
+	c[j+len] = 0;
+
+    for (i = len - 1; i >= 0; i--) {
+	ai = a[i];
+	t = 0;
+	for (j = len - 1; j >= 0; j--) {
+	    t += ai * (unsigned long) b[j];
+	    t += (unsigned long) c[i+j+1];
+	    c[i+j+1] = (unsigned short)t;
+	    t = t >> 16;
+	}
+	c[i] = (unsigned short)t;
     }
-
-    debug(result);
-    leave(("<add\n"));
 }
 
-static void sub(Bignum r1, Bignum r2, Bignum result) {
-    int i;
-    long stuff = 0;
-
-    enter((">sub\n"));
-    debug(r1);
-    debug(r2);
-
-    for (i = 1 ;; i++) {
-	if (i <= r1[0])
-	    stuff += r1[i];
-	if (i <= r2[0])
-	    stuff -= r2[i];
-	if (i <= result[0])
-	    result[i] = stuff & 0xFFFFU;
-	if (i > r1[0] && i > r2[0] && i >= result[0])
-	    break;
-	stuff = stuff<0 ? -1 : 0;
+/*
+ * Compute a = a % m.
+ * Input in first 2*len words of a and first len words of m.
+ * Output in first 2*len words of a (of which first len words will be zero).
+ * The MSW of m MUST have its high bit set.
+ */
+static void bigmod(unsigned short *a, unsigned short *m, int len)
+{
+    unsigned short m0, m1;
+    unsigned int h;
+    int i, k;
+
+    /* Special case for len == 1 */
+    if (len == 1) {
+	a[1] = (((long) a[0] << 16) + a[1]) % m[0];
+	a[0] = 0;
+	return;
     }
 
-    debug(result);
-    leave(("<sub\n"));
-}
+    m0 = m[0];
+    m1 = m[1];
 
-static int ge(Bignum r1, Bignum r2) {
-    int i;
+    for (i = 0; i <= len; i++) {
+	unsigned long t;
+	unsigned int q, r, c;
 
-    enter((">ge\n"));
-    debug(r1);
-    debug(r2);
-
-    if (r1[0] < r2[0])
-	i = r2[0];
-    else
-	i = r1[0];
-
-    while (i > 0) {
-	unsigned short n1 = (i > r1[0] ? 0 : r1[i]);
-	unsigned short n2 = (i > r2[0] ? 0 : r2[i]);
-
-	if (n1 > n2) {
-	    dmsg(("greater\n"));
-	    leave(("<ge\n"));
-	    return 1;		       /* r1 > r2 */
-	} else if (n1 < n2) {
-	    dmsg(("less\n"));
-	    leave(("<ge\n"));
-	    return 0;		       /* r1 < r2 */
+	if (i == 0) {
+	    h = 0;
+	} else {
+	    h = a[i-1];
+	    a[i-1] = 0;
 	}
 
-	i--;
-    }
-
-    dmsg(("equal\n"));
-    leave(("<ge\n"));
-    return 1;			       /* r1 = r2 */
-}
+	/* Find q = h:a[i] / m0 */
+	t = ((unsigned long) h << 16) + a[i];
+	q = t / m0;
+	r = t % m0;
+
+	/* Refine our estimate of q by looking at
+	 h:a[i]:a[i+1] / m0:m1 */
+	t = (long) m1 * (long) q;
+	if (t > ((unsigned long) r << 16) + a[i+1]) {
+	    q--;
+	    t -= m1;
+	    r = (r + m0) & 0xffff; /* overflow? */
+	    if (r >= (unsigned long)m0 &&
+                t > ((unsigned long) r << 16) + a[i+1])
+		q--;
+	}
 
-static void modmult(Bignum r1, Bignum r2, Bignum modulus, Bignum result) {
-    Bignum temp = newbn(modulus[0]+1);
-    Bignum tmp2 = newbn(modulus[0]+1);
-    int i;
-    int bit, bits, digit, smallbit;
-
-    enter((">modmult\n"));
-    debug(r1);
-    debug(r2);
-    debug(modulus);
-
-    for (i=1; i<=result[0]; i++)
-	result[i] = 0;		       /* result := 0 */
-    for (i=1; i<=temp[0]; i++)
-	temp[i] = (i > r2[0] ? 0 : r2[i]);   /* temp := r2 */
-
-    bits = 1+msb(r1);
-
-    for (bit = 0; bit < bits; bit++) {
-	digit = 1 + bit / 16;
-	smallbit = bit % 16;
-
-	debug(temp);
-	if (digit <= r1[0] && (r1[digit] & (1<<smallbit))) {
-	    dmsg(("bit %d\n", bit));
-	    add(temp, result, tmp2);
-	    if (ge(tmp2, modulus))
-		sub(tmp2, modulus, result);
-	    else
-		add(tmp2, Zero, result);
-	    debug(result);
+	/* Substract q * m from a[i...] */
+	c = 0;
+	for (k = len - 1; k >= 0; k--) {
+	    t = (long) q * (long) m[k];
+	    t += c;
+	    c = t >> 16;
+	    if ((unsigned short) t > a[i+k]) c++;
+	    a[i+k] -= (unsigned short) t;
 	}
 
-	add(temp, temp, tmp2);
-	if (ge(tmp2, modulus))
-	    sub(tmp2, modulus, temp);
-	else
-	    add(tmp2, Zero, temp);
+	/* Add back m in case of borrow */
+	if (c != h) {
+	    t = 0;
+	    for (k = len - 1; k >= 0; k--) {
+		t += m[k];
+		t += a[i+k];
+		a[i+k] = (unsigned short)t;
+		t = t >> 16;
+	    }
+	}
     }
+}
 
-    freebn(temp);
-    freebn(tmp2);
+/*
+ * 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.
+ */
+static void modpow(Bignum base, Bignum exp, Bignum mod, Bignum result)
+{
+    unsigned short *a, *b, *n, *m;
+    int mshift;
+    int 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;
+    }
 
-    debug(result);
-    leave(("<modmult\n"));
-}
+    /* Allocate n of size mlen, copy base to n */
+    n = malloc(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));
+    for (i = 0; i < 2*mlen; i++) a[i] = 0;
+    a[2*mlen-1] = 1;
+
+    /* Skip leading zero bits of exp. */
+    i = 0; j = 15;
+    while (i < exp[0] && (exp[exp[0] - i] & (1 << j)) == 0) {
+	j--;
+	if (j < 0) { i++; j = 15; }
+    }
 
-static void modpow(Bignum r1, Bignum r2, Bignum modulus, Bignum result) {
-    Bignum temp = newbn(modulus[0]+1);
-    Bignum tmp2 = newbn(modulus[0]+1);
-    int i;
-    int bit, bits, digit, smallbit;
-
-    enter((">modpow\n"));
-    debug(r1);
-    debug(r2);
-    debug(modulus);
-
-    for (i=1; i<=result[0]; i++)
-	result[i] = (i==1);	       /* result := 1 */
-    for (i=1; i<=temp[0]; i++)
-	temp[i] = (i > r1[0] ? 0 : r1[i]);   /* temp := r1 */
-
-    bits = 1+msb(r2);
-
-    for (bit = 0; bit < bits; bit++) {
-	digit = 1 + bit / 16;
-	smallbit = bit % 16;
-
-	debug(temp);
-	if (digit <= r2[0] && (r2[digit] & (1<<smallbit))) {
-	    dmsg(("bit %d\n", bit));
-	    modmult(temp, result, modulus, tmp2);
-	    add(tmp2, Zero, result);
-	    debug(result);
+    /* Main computation */
+    while (i < exp[0]) {
+	while (j >= 0) {
+	    bigmul(a + mlen, a + mlen, b, mlen);
+	    bigmod(b, m, mlen);
+	    if ((exp[exp[0] - i] & (1 << j)) != 0) {
+		bigmul(b + mlen, n, a, mlen);
+		bigmod(a, m, mlen);
+	    } else {
+		unsigned short *t;
+		t = a;  a = b;  b = t;
+	    }
+	    j--;
 	}
+	i++; j = 15;
+    }
 
-	modmult(temp, temp, modulus, tmp2);
-	add(tmp2, Zero, temp);
+    /* Fixup result in case the modulus was shifted */
+    if (mshift) {
+	for (i = mlen - 1; i < 2*mlen - 1; i++)
+	    a[i] = (a[i] << mshift) | (a[i+1] >> (16-mshift));
+	a[2*mlen-1] = a[2*mlen-1] << mshift;
+	bigmod(a, m, mlen);
+	for (i = 2*mlen - 1; i >= mlen; i--)
+	    a[i] = (a[i] >> mshift) | (a[i-1] << (16-mshift));
     }
 
-    freebn(temp);
-    freebn(tmp2);
+    /* Copy result to buffer */
+    for (i = 0; i < mlen; i++)
+	result[result[0] - i] = a[i+mlen];
 
-    debug(result);
-    leave(("<modpow\n"));
+    /* 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);
 }
 
 int makekey(unsigned char *data, struct RSAKey *result,