2 * RSA implementation just sufficient for ssh client-side
17 typedef unsigned short *Bignum;
19 static unsigned short Zero[1] = { 0 };
21 #if defined TESTMODE || defined RSADEBUG
25 #define debug(x) bndebug(#x,x)
27 static void bndebug(char *name, Bignum b) {
29 int w = 50-level-strlen(name)-5*b[0];
33 dprintf("%*s%s%*s", level, "", name, w, "");
34 for (i=b[0]; i>0; i--)
35 dprintf(" %04x", b[i]);
38 #define dmsg(x) do {if(level<DLVL){dprintf("%*s",level,"");printf x;}} while(0)
39 #define enter(x) do { dmsg(x); level += 4; } while(0)
40 #define leave(x) do { level -= 4; dmsg(x); } while(0)
48 static Bignum newbn(int length) {
49 Bignum b = malloc((length+1)*sizeof(unsigned short));
56 static void freebn(Bignum b) {
60 static int msb(Bignum r) {
65 for (i=r[0]; i>0; i--)
71 if (n & 0xFF00) j += 8, n >>= 8;
72 if (n & 0x00F0) j += 4, n >>= 4;
73 if (n & 0x000C) j += 2, n >>= 2;
74 if (n & 0x0002) j += 1, n >>= 1;
79 static void add(Bignum r1, Bignum r2, Bignum result) {
93 result[i] = stuff & 0xFFFFU;
94 if (i > r1[0] && i > r2[0] && i >= result[0])
103 static void sub(Bignum r1, Bignum r2, Bignum result) {
117 result[i] = stuff & 0xFFFFU;
118 if (i > r1[0] && i > r2[0] && i >= result[0])
120 stuff = stuff<0 ? -1 : 0;
127 static int ge(Bignum r1, Bignum r2) {
140 unsigned short n1 = (i > r1[0] ? 0 : r1[i]);
141 unsigned short n2 = (i > r2[0] ? 0 : r2[i]);
146 return 1; /* r1 > r2 */
147 } else if (n1 < n2) {
150 return 0; /* r1 < r2 */
158 return 1; /* r1 = r2 */
161 static void modmult(Bignum r1, Bignum r2, Bignum modulus, Bignum result) {
162 Bignum temp = newbn(modulus[0]+1);
163 Bignum tmp2 = newbn(modulus[0]+1);
165 int bit, bits, digit, smallbit;
167 enter((">modmult\n"));
172 for (i=1; i<=result[0]; i++)
173 result[i] = 0; /* result := 0 */
174 for (i=1; i<=temp[0]; i++)
175 temp[i] = (i > r2[0] ? 0 : r2[i]); /* temp := r2 */
179 for (bit = 0; bit < bits; bit++) {
180 digit = 1 + bit / 16;
184 if (digit <= r1[0] && (r1[digit] & (1<<smallbit))) {
185 dmsg(("bit %d\n", bit));
186 add(temp, result, tmp2);
187 if (ge(tmp2, modulus))
188 sub(tmp2, modulus, result);
190 add(tmp2, Zero, result);
194 add(temp, temp, tmp2);
195 if (ge(tmp2, modulus))
196 sub(tmp2, modulus, temp);
198 add(tmp2, Zero, temp);
205 leave(("<modmult\n"));
208 static void modpow(Bignum r1, Bignum r2, Bignum modulus, Bignum result) {
209 Bignum temp = newbn(modulus[0]+1);
210 Bignum tmp2 = newbn(modulus[0]+1);
212 int bit, bits, digit, smallbit;
214 enter((">modpow\n"));
219 for (i=1; i<=result[0]; i++)
220 result[i] = (i==1); /* result := 1 */
221 for (i=1; i<=temp[0]; i++)
222 temp[i] = (i > r1[0] ? 0 : r1[i]); /* temp := r1 */
226 for (bit = 0; bit < bits; bit++) {
227 digit = 1 + bit / 16;
231 if (digit <= r2[0] && (r2[digit] & (1<<smallbit))) {
232 dmsg(("bit %d\n", bit));
233 modmult(temp, result, modulus, tmp2);
234 add(tmp2, Zero, result);
238 modmult(temp, temp, modulus, tmp2);
239 add(tmp2, Zero, temp);
246 leave(("<modpow\n"));
249 int makekey(unsigned char *data, struct RSAKey *result,
250 unsigned char **keystr) {
251 unsigned char *p = data;
258 result->bits = (result->bits << 8) + *p++;
260 for (j=0; j<2; j++) {
266 result->bytes = b = (w+7)/8; /* bits -> bytes */
267 w = (w+15)/16; /* bits -> words */
271 if (keystr) *keystr = p; /* point at key string, second time */
275 for (i=0; i<b; i++) {
276 unsigned char byte = *p++;
278 bn[j][w-i/2] |= byte;
280 bn[j][w-i/2] |= byte<<8;
287 result->exponent = bn[0];
288 result->modulus = bn[1];
293 void rsaencrypt(unsigned char *data, int length, struct RSAKey *key) {
298 debug(key->exponent);
300 memmove(data+key->bytes-length, data, length);
304 for (i = 2; i < key->bytes-length-1; i++) {
306 data[i] = random_byte();
307 } while (data[i] == 0);
309 data[key->bytes-length-1] = 0;
311 w = (key->bytes+1)/2;
319 for (i=0; i<key->bytes; i++) {
320 unsigned char byte = *p++;
321 if ((key->bytes-i) & 1)
324 b1[w-i/2] |= byte<<8;
329 modpow(b1, key->exponent, key->modulus, b2);
334 for (i=0; i<key->bytes; i++) {
337 b = b2[w-i/2] & 0xFF;
347 int rsastr_len(struct RSAKey *key) {
352 return 4 * (ex[0]+md[0]) + 10;
355 void rsastr_fmt(char *str, struct RSAKey *key) {
362 for (i=1; i<=ex[0]; i++) {
363 sprintf(str+len, "%04x", ex[i]);
364 len += strlen(str+len);
367 for (i=1; i<=md[0]; i++) {
368 sprintf(str+len, "%04x", md[i]);
369 len += strlen(str+len);
386 unsigned short P1[2] = { 1, p1 };
387 unsigned short P2[2] = { 1, p2 };
388 unsigned short P3[2] = { 1, p3 };
389 unsigned short bigmod[5] = { 4, 0, 0, 0, 32768U };
390 unsigned short mod[5] = { 4, 0, 0, 0, 0 };
391 unsigned short a[5] = { 4, 0, 0, 0, 0 };
392 unsigned short b[5] = { 4, 0, 0, 0, 0 };
393 unsigned short c[5] = { 4, 0, 0, 0, 0 };
394 unsigned short One[2] = { 1, 1 };
395 unsigned short Two[2] = { 1, 2 };
398 modmult(P1, P2, bigmod, a); debug(a);
399 modmult(a, P3, bigmod, mod); debug(mod);
401 sub(P1, One, a); debug(a);
402 sub(P2, One, b); debug(b);
403 modmult(a, b, bigmod, c); debug(c);
404 sub(P3, One, a); debug(a);
405 modmult(a, c, bigmod, b); debug(b);
407 modpow(Two, b, mod, a); debug(a);