X-Git-Url: https://git.distorted.org.uk/u/mdw/putty/blobdiff_plain/374330e25a6b51c40436fa869a381dd510790f6e..4017be6d5375063f59b63474490ac072e7f09b1a:/sshrsa.c

diff --git a/sshrsa.c b/sshrsa.c
index 70cf9bbe..bd92c7bd 100644
--- a/sshrsa.c
+++ b/sshrsa.c
@@ -1,23 +1,14 @@
 /*
  * 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>
 
-#include "ssh.h"
-
-typedef unsigned short *Bignum;
-
-static unsigned short Zero[1] = { 0 };
-
 #if defined TESTMODE || defined RSADEBUG
 #ifndef DLVL
 #define DLVL 10000
@@ -45,251 +36,38 @@ static void bndebug(char *name, Bignum b) {
 #define leave(x)
 #endif
 
-static Bignum newbn(int length) {
-    Bignum b = malloc((length+1)*sizeof(unsigned short));
-    if (!b)
-	abort();		       /* FIXME */
-    b[0] = length;
-    return b;
-}
-
-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;
-    }
-
-    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;
-    }
-
-    debug(result);
-    leave(("<sub\n"));
-}
-
-static int ge(Bignum r1, Bignum r2) {
-    int i;
-
-    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 */
-	}
-
-	i--;
-    }
-
-    dmsg(("equal\n"));
-    leave(("<ge\n"));
-    return 1;			       /* r1 = r2 */
-}
-
-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);
-	}
-
-	add(temp, temp, tmp2);
-	if (ge(tmp2, modulus))
-	    sub(tmp2, modulus, temp);
-	else
-	    add(tmp2, Zero, temp);
-    }
-
-    freebn(temp);
-    freebn(tmp2);
-
-    debug(result);
-    leave(("<modmult\n"));
-}
-
-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);
-	}
-
-	modmult(temp, temp, modulus, tmp2);
-	add(tmp2, Zero, temp);
-    }
-
-    freebn(temp);
-    freebn(tmp2);
-
-    debug(result);
-    leave(("<modpow\n"));
-}
+#include "ssh.h"
 
 int makekey(unsigned char *data, struct RSAKey *result,
-	    unsigned char **keystr) {
+	    unsigned char **keystr, int order) {
     unsigned char *p = data;
-    Bignum bn[2];
-    int i, j;
-    int w, b;
+    int i;
 
     result->bits = 0;
     for (i=0; i<4; i++)
 	result->bits = (result->bits << 8) + *p++;
 
-    for (j=0; j<2; j++) {
-
-	w = 0;
-	for (i=0; i<2; i++)
-	    w = (w << 8) + *p++;
-
-	result->bytes = b = (w+7)/8;   /* bits -> bytes */
-	w = (w+15)/16;		       /* bits -> words */
-
-	bn[j] = newbn(w);
-
-	if (keystr) *keystr = p;       /* point at key string, second time */
-
-	for (i=1; i<=w; i++)
-	    bn[j][i] = 0;
-	for (i=0; i<b; i++) {
-	    unsigned char byte = *p++;
-	    if ((b-i) & 1)
-		bn[j][w-i/2] |= byte;
-	    else
-		bn[j][w-i/2] |= byte<<8;
-	}
-
-	debug(bn[j]);
+    /*
+     * order=0 means exponent then modulus (the keys sent by the
+     * server). order=1 means modulus then exponent (the keys
+     * stored in a keyfile).
+     */
 
-    }
-
-    result->exponent = bn[0];
-    result->modulus = bn[1];
+    if (order == 0)
+        p += ssh1_read_bignum(p, &result->exponent);
+    result->bytes = (((p[0] << 8) + p[1]) + 7) / 8;
+    if (keystr) *keystr = p+2;
+    p += ssh1_read_bignum(p, &result->modulus);
+    if (order == 1)
+        p += ssh1_read_bignum(p, &result->exponent);
 
     return p - data;
 }
 
+int makeprivate(unsigned char *data, struct RSAKey *result) {
+    return ssh1_read_bignum(data, &result->private_exponent);
+}
+
 void rsaencrypt(unsigned char *data, int length, struct RSAKey *key) {
     Bignum b1, b2;
     int w, i;
@@ -316,12 +94,12 @@ void rsaencrypt(unsigned char *data, int length, struct RSAKey *key) {
     p = data;
     for (i=1; i<=w; i++)
 	b1[i] = 0;
-    for (i=0; i<key->bytes; i++) {
+    for (i=key->bytes; i-- ;) {
 	unsigned char byte = *p++;
-	if ((key->bytes-i) & 1)
-	    b1[w-i/2] |= byte;
+	if (i & 1)
+	    b1[1+i/2] |= byte<<8;
 	else
-	    b1[w-i/2] |= byte<<8;
+	    b1[1+i/2] |= byte;
     }
 
     debug(b1);
@@ -331,12 +109,12 @@ void rsaencrypt(unsigned char *data, int length, struct RSAKey *key) {
     debug(b2);
 
     p = data;
-    for (i=0; i<key->bytes; i++) {
+    for (i=key->bytes; i-- ;) {
 	unsigned char b;
 	if (i & 1)
-	    b = b2[w-i/2] & 0xFF;
+	    b = b2[1+i/2] >> 8;
 	else
-	    b = b2[w-i/2] >> 8;
+	    b = b2[1+i/2] & 0xFF;
 	*p++ = b;
     }
 
@@ -344,6 +122,13 @@ void rsaencrypt(unsigned char *data, int length, struct RSAKey *key) {
     freebn(b2);
 }
 
+Bignum rsadecrypt(Bignum input, struct RSAKey *key) {
+    Bignum ret;
+    ret = newbn(key->modulus[0]);
+    modpow(input, key->private_exponent, key->modulus, ret);
+    return ret;
+}
+
 int rsastr_len(struct RSAKey *key) {
     Bignum md, ex;