/*
* 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
#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++) {
+ /*
+ * order=0 means exponent then modulus (the keys sent by the
+ * server). order=1 means modulus then exponent (the keys
+ * stored in a keyfile).
+ */
- 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]);
-
- }
-
- 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;
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);
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;
}
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;
str[len] = '\0';
}
+void freersakey(struct RSAKey *key) {
+ if (key->modulus) freebn(key->modulus);
+ if (key->exponent) freebn(key->exponent);
+ if (key->private_exponent) freebn(key->private_exponent);
+ if (key->comment) free(key->comment);
+}
+
#ifdef TESTMODE
#ifndef NODDY
projects / u / mdw / putty / blobdiff