2 * RSA implementation just sufficient for ssh client-side
4 * Modified by Joris, Jun 1999.
20 typedef unsigned short *Bignum
;
22 static unsigned short Zero
[1] = { 0 };
24 #if defined TESTMODE || defined RSADEBUG
28 #define debug(x) bndebug(#x,x)
30 static void bndebug(char *name
, Bignum b
) {
32 int w
= 50-level
-strlen(name
)-5*b
[0];
36 dprintf("%*s%s%*s", level
, "", name
, w
, "");
37 for (i
=b
[0]; i
>0; i
--)
38 dprintf(" %04x", b
[i
]);
41 #define dmsg(x) do {if(level<DLVL){dprintf("%*s",level,"");printf x;}} while(0)
42 #define enter(x) do { dmsg(x); level += 4; } while(0)
43 #define leave(x) do { level -= 4; dmsg(x); } while(0)
51 static Bignum
newbn(int length
) {
52 Bignum b
= malloc((length
+1)*sizeof(unsigned short));
59 static void freebn(Bignum b
) {
67 * Input is in the first len words of a and b.
68 * Result is returned in the first 2*len words of c.
70 static void bigmul(unsigned short *a
, unsigned short *b
, unsigned short *c
,
76 for (j
= len
- 1; j
>= 0; j
--)
79 for (i
= len
- 1; i
>= 0; i
--) {
82 for (j
= len
- 1; j
>= 0; j
--) {
83 t
+= ai
* (unsigned long) b
[j
];
84 t
+= (unsigned long) c
[i
+j
+1];
95 * Input in first 2*len words of a and first len words of m.
96 * Output in first 2*len words of a (of which first len words will be zero).
97 * The MSW of m MUST have its high bit set.
99 static void bigmod(unsigned short *a
, unsigned short *m
, int len
)
101 unsigned short m0
, m1
;
105 /* Special case for len == 1 */
107 a
[1] = (((long) a
[0] << 16) + a
[1]) % m
[0];
115 for (i
= 0; i
<= len
; i
++) {
117 unsigned int q
, r
, c
;
126 /* Find q = h:a[i] / m0 */
127 t
= ((unsigned long) h
<< 16) + a
[i
];
131 /* Refine our estimate of q by looking at
132 h:a[i]:a[i+1] / m0:m1 */
133 t
= (long) m1
* (long) q
;
134 if (t
> ((unsigned long) r
<< 16) + a
[i
+1]) {
137 r
= (r
+ m0
) & 0xffff; /* overflow? */
138 if (r
>= m0
&& t
> ((unsigned long) r
<< 16) + a
[i
+1])
142 /* Substract q * m from a[i...] */
144 for (k
= len
- 1; k
>= 0; k
--) {
145 t
= (long) q
* (long) m
[k
];
148 if ((unsigned short) t
> a
[i
+k
]) c
++;
149 a
[i
+k
] -= (unsigned short) t
;
152 /* Add back m in case of borrow */
155 for (k
= len
- 1; k
>= 0; k
--) {
167 * Compute (base ^ exp) % mod.
168 * The base MUST be smaller than the modulus.
169 * The most significant word of mod MUST be non-zero.
170 * We assume that the result array is the same size as the mod array.
172 static void modpow(Bignum base
, Bignum exp
, Bignum mod
, Bignum result
)
174 unsigned short *a
, *b
, *n
, *m
;
178 /* Allocate m of size mlen, copy mod to m */
179 /* We use big endian internally */
181 m
= malloc(mlen
* sizeof(unsigned short));
182 for (j
= 0; j
< mlen
; j
++) m
[j
] = mod
[mod
[0] - j
];
184 /* Shift m left to make msb bit set */
185 for (mshift
= 0; mshift
< 15; mshift
++)
186 if ((m
[0] << mshift
) & 0x8000) break;
188 for (i
= 0; i
< mlen
- 1; i
++)
189 m
[i
] = (m
[i
] << mshift
) | (m
[i
+1] >> (16-mshift
));
190 m
[mlen
-1] = m
[mlen
-1] << mshift
;
193 /* Allocate n of size mlen, copy base to n */
194 n
= malloc(mlen
* sizeof(unsigned short));
196 for (j
= 0; j
< i
; j
++) n
[j
] = 0;
197 for (j
= 0; j
< base
[0]; j
++) n
[i
+j
] = base
[base
[0] - j
];
199 /* Allocate a and b of size 2*mlen. Set a = 1 */
200 a
= malloc(2 * mlen
* sizeof(unsigned short));
201 b
= malloc(2 * mlen
* sizeof(unsigned short));
202 for (i
= 0; i
< 2*mlen
; i
++) a
[i
] = 0;
205 /* Skip leading zero bits of exp. */
207 while (i
< exp
[0] && (exp
[exp
[0] - i
] & (1 << j
)) == 0) {
209 if (j
< 0) { i
++; j
= 15; }
212 /* Main computation */
215 bigmul(a
+ mlen
, a
+ mlen
, b
, mlen
);
217 if ((exp
[exp
[0] - i
] & (1 << j
)) != 0) {
218 bigmul(b
+ mlen
, n
, a
, mlen
);
229 /* Fixup result in case the modulus was shifted */
231 for (i
= mlen
- 1; i
< 2*mlen
- 1; i
++)
232 a
[i
] = (a
[i
] << mshift
) | (a
[i
+1] >> (16-mshift
));
233 a
[2*mlen
-1] = a
[2*mlen
-1] << mshift
;
235 for (i
= 2*mlen
- 1; i
>= mlen
; i
--)
236 a
[i
] = (a
[i
] >> mshift
) | (a
[i
-1] << (16-mshift
));
239 /* Copy result to buffer */
240 for (i
= 0; i
< mlen
; i
++)
241 result
[result
[0] - i
] = a
[i
+mlen
];
243 /* Free temporary arrays */
244 for (i
= 0; i
< 2*mlen
; i
++) a
[i
] = 0; free(a
);
245 for (i
= 0; i
< 2*mlen
; i
++) b
[i
] = 0; free(b
);
246 for (i
= 0; i
< mlen
; i
++) m
[i
] = 0; free(m
);
247 for (i
= 0; i
< mlen
; i
++) n
[i
] = 0; free(n
);
252 static int msb(Bignum r
) {
257 for (i
=r
[0]; i
>0; i
--)
263 if (n
& 0xFF00) j
+= 8, n
>>= 8;
264 if (n
& 0x00F0) j
+= 4, n
>>= 4;
265 if (n
& 0x000C) j
+= 2, n
>>= 2;
266 if (n
& 0x0002) j
+= 1, n
>>= 1;
271 static void add(Bignum r1
, Bignum r2
, Bignum result
) {
285 result
[i
] = stuff
& 0xFFFFU
;
286 if (i
> r1
[0] && i
> r2
[0] && i
>= result
[0])
295 static void sub(Bignum r1
, Bignum r2
, Bignum result
) {
309 result
[i
] = stuff
& 0xFFFFU
;
310 if (i
> r1
[0] && i
> r2
[0] && i
>= result
[0])
312 stuff
= stuff
<0 ?
-1 : 0;
319 static int ge(Bignum r1
, Bignum r2
) {
332 unsigned short n1
= (i
> r1
[0] ?
0 : r1
[i
]);
333 unsigned short n2
= (i
> r2
[0] ?
0 : r2
[i
]);
338 return 1; /* r1 > r2 */
339 } else if (n1
< n2
) {
342 return 0; /* r1 < r2 */
350 return 1; /* r1 = r2 */
353 static void modmult(Bignum r1
, Bignum r2
, Bignum modulus
, Bignum result
) {
354 Bignum temp
= newbn(modulus
[0]+1);
355 Bignum tmp2
= newbn(modulus
[0]+1);
357 int bit
, bits
, digit
, smallbit
;
359 enter((">modmult\n"));
364 for (i
=1; i
<=result
[0]; i
++)
365 result
[i
] = 0; /* result := 0 */
366 for (i
=1; i
<=temp
[0]; i
++)
367 temp
[i
] = (i
> r2
[0] ?
0 : r2
[i
]); /* temp := r2 */
371 for (bit
= 0; bit
< bits
; bit
++) {
372 digit
= 1 + bit
/ 16;
376 if (digit
<= r1
[0] && (r1
[digit
] & (1<<smallbit
))) {
377 dmsg(("bit %d\n", bit
));
378 add(temp
, result
, tmp2
);
379 if (ge(tmp2
, modulus
))
380 sub(tmp2
, modulus
, result
);
382 add(tmp2
, Zero
, result
);
386 add(temp
, temp
, tmp2
);
387 if (ge(tmp2
, modulus
))
388 sub(tmp2
, modulus
, temp
);
390 add(tmp2
, Zero
, temp
);
397 leave(("<modmult\n"));
400 static void modpow(Bignum r1
, Bignum r2
, Bignum modulus
, Bignum result
) {
401 Bignum temp
= newbn(modulus
[0]+1);
402 Bignum tmp2
= newbn(modulus
[0]+1);
404 int bit
, bits
, digit
, smallbit
;
406 enter((">modpow\n"));
411 for (i
=1; i
<=result
[0]; i
++)
412 result
[i
] = (i
==1); /* result := 1 */
413 for (i
=1; i
<=temp
[0]; i
++)
414 temp
[i
] = (i
> r1
[0] ?
0 : r1
[i
]); /* temp := r1 */
418 for (bit
= 0; bit
< bits
; bit
++) {
419 digit
= 1 + bit
/ 16;
423 if (digit
<= r2
[0] && (r2
[digit
] & (1<<smallbit
))) {
424 dmsg(("bit %d\n", bit
));
425 modmult(temp
, result
, modulus
, tmp2
);
426 add(tmp2
, Zero
, result
);
430 modmult(temp
, temp
, modulus
, tmp2
);
431 add(tmp2
, Zero
, temp
);
438 leave(("<modpow\n"));
443 int makekey(unsigned char *data
, struct RSAKey
*result
,
444 unsigned char **keystr
) {
445 unsigned char *p
= data
;
452 result
->bits
= (result
->bits
<< 8) + *p
++;
454 for (j
=0; j
<2; j
++) {
460 result
->bytes
= b
= (w
+7)/8; /* bits -> bytes */
461 w
= (w
+15)/16; /* bits -> words */
465 if (keystr
) *keystr
= p
; /* point at key string, second time */
469 for (i
=0; i
<b
; i
++) {
470 unsigned char byte
= *p
++;
472 bn
[j
][w
-i
/2] |= byte
;
474 bn
[j
][w
-i
/2] |= byte
<<8;
481 result
->exponent
= bn
[0];
482 result
->modulus
= bn
[1];
487 void rsaencrypt(unsigned char *data
, int length
, struct RSAKey
*key
) {
492 debug(key
->exponent
);
494 memmove(data
+key
->bytes
-length
, data
, length
);
498 for (i
= 2; i
< key
->bytes
-length
-1; i
++) {
500 data
[i
] = random_byte();
501 } while (data
[i
] == 0);
503 data
[key
->bytes
-length
-1] = 0;
505 w
= (key
->bytes
+1)/2;
513 for (i
=0; i
<key
->bytes
; i
++) {
514 unsigned char byte
= *p
++;
515 if ((key
->bytes
-i
) & 1)
518 b1
[w
-i
/2] |= byte
<<8;
523 modpow(b1
, key
->exponent
, key
->modulus
, b2
);
528 for (i
=0; i
<key
->bytes
; i
++) {
531 b
= b2
[w
-i
/2] & 0xFF;
541 int rsastr_len(struct RSAKey
*key
) {
546 return 4 * (ex
[0]+md
[0]) + 10;
549 void rsastr_fmt(char *str
, struct RSAKey
*key
) {
556 for (i
=1; i
<=ex
[0]; i
++) {
557 sprintf(str
+len
, "%04x", ex
[i
]);
558 len
+= strlen(str
+len
);
561 for (i
=1; i
<=md
[0]; i
++) {
562 sprintf(str
+len
, "%04x", md
[i
]);
563 len
+= strlen(str
+len
);
580 unsigned short P1
[2] = { 1, p1
};
581 unsigned short P2
[2] = { 1, p2
};
582 unsigned short P3
[2] = { 1, p3
};
583 unsigned short bigmod
[5] = { 4, 0, 0, 0, 32768U };
584 unsigned short mod
[5] = { 4, 0, 0, 0, 0 };
585 unsigned short a
[5] = { 4, 0, 0, 0, 0 };
586 unsigned short b
[5] = { 4, 0, 0, 0, 0 };
587 unsigned short c
[5] = { 4, 0, 0, 0, 0 };
588 unsigned short One
[2] = { 1, 1 };
589 unsigned short Two
[2] = { 1, 2 };
592 modmult(P1
, P2
, bigmod
, a
); debug(a
);
593 modmult(a
, P3
, bigmod
, mod
); debug(mod
);
595 sub(P1
, One
, a
); debug(a
);
596 sub(P2
, One
, b
); debug(b
);
597 modmult(a
, b
, bigmod
, c
); debug(c
);
598 sub(P3
, One
, a
); debug(a
);
599 modmult(a
, c
, bigmod
, b
); debug(b
);
601 modpow(Two
, b
, mod
, a
); debug(a
);