More options for bignum debugging
[u/mdw/putty] / sshrsa.c
CommitLineData
374330e2 1/*
2 * RSA implementation just sufficient for ssh client-side
3 * initialisation step
4644b0ce 4 *
5 * Rewritten for more speed by Joris van Rantwijk, Jun 1999.
374330e2 6 */
7
374330e2 8#include <stdio.h>
9#include <stdlib.h>
10#include <string.h>
11
e5574168 12#include "ssh.h"
374330e2 13
1c2a93c4 14
374330e2 15int makekey(unsigned char *data, struct RSAKey *result,
7cca0d81 16 unsigned char **keystr, int order) {
374330e2 17 unsigned char *p = data;
7cca0d81 18 int i;
374330e2 19
a52f067e 20 if (result) {
21 result->bits = 0;
22 for (i=0; i<4; i++)
23 result->bits = (result->bits << 8) + *p++;
24 } else
25 p += 4;
374330e2 26
7cca0d81 27 /*
28 * order=0 means exponent then modulus (the keys sent by the
29 * server). order=1 means modulus then exponent (the keys
30 * stored in a keyfile).
31 */
374330e2 32
7cca0d81 33 if (order == 0)
a52f067e 34 p += ssh1_read_bignum(p, result ? &result->exponent : NULL);
35 if (result)
36 result->bytes = (((p[0] << 8) + p[1]) + 7) / 8;
7cca0d81 37 if (keystr) *keystr = p+2;
a52f067e 38 p += ssh1_read_bignum(p, result ? &result->modulus : NULL);
7cca0d81 39 if (order == 1)
a52f067e 40 p += ssh1_read_bignum(p, result ? &result->exponent : NULL);
374330e2 41
42 return p - data;
43}
44
7cca0d81 45int makeprivate(unsigned char *data, struct RSAKey *result) {
46 return ssh1_read_bignum(data, &result->private_exponent);
47}
48
374330e2 49void rsaencrypt(unsigned char *data, int length, struct RSAKey *key) {
50 Bignum b1, b2;
3709bfe9 51 int i;
374330e2 52 unsigned char *p;
53
374330e2 54 memmove(data+key->bytes-length, data, length);
55 data[0] = 0;
56 data[1] = 2;
57
58 for (i = 2; i < key->bytes-length-1; i++) {
59 do {
60 data[i] = random_byte();
61 } while (data[i] == 0);
62 }
63 data[key->bytes-length-1] = 0;
64
3709bfe9 65 b1 = bignum_from_bytes(data, key->bytes);
374330e2 66
59600f67 67 b2 = modpow(b1, key->exponent, key->modulus);
374330e2 68
374330e2 69 p = data;
d9373729 70 for (i=key->bytes; i-- ;) {
3709bfe9 71 *p++ = bignum_byte(b2, i);
374330e2 72 }
73
74 freebn(b1);
75 freebn(b2);
76}
77
7cca0d81 78Bignum rsadecrypt(Bignum input, struct RSAKey *key) {
79 Bignum ret;
59600f67 80 ret = modpow(input, key->private_exponent, key->modulus);
7cca0d81 81 return ret;
82}
83
374330e2 84int rsastr_len(struct RSAKey *key) {
85 Bignum md, ex;
3709bfe9 86 int mdlen, exlen;
374330e2 87
88 md = key->modulus;
89 ex = key->exponent;
3709bfe9 90 mdlen = (ssh1_bignum_bitcount(md)+15) / 16;
91 exlen = (ssh1_bignum_bitcount(ex)+15) / 16;
92 return 4 * (mdlen+exlen) + 20;
374330e2 93}
94
95void rsastr_fmt(char *str, struct RSAKey *key) {
96 Bignum md, ex;
d5859615 97 int len = 0, i, nibbles;
98 static const char hex[] = "0123456789abcdef";
374330e2 99
100 md = key->modulus;
101 ex = key->exponent;
102
d5859615 103 len += sprintf(str+len, "0x");
104
105 nibbles = (3 + ssh1_bignum_bitcount(ex))/4; if (nibbles<1) nibbles=1;
106 for (i=nibbles; i-- ;)
107 str[len++] = hex[(bignum_byte(ex, i/2) >> (4*(i%2))) & 0xF];
108
109 len += sprintf(str+len, ",0x");
110
111 nibbles = (3 + ssh1_bignum_bitcount(md))/4; if (nibbles<1) nibbles=1;
112 for (i=nibbles; i-- ;)
113 str[len++] = hex[(bignum_byte(md, i/2) >> (4*(i%2))) & 0xF];
114
374330e2 115 str[len] = '\0';
116}
117
1c2a93c4 118/*
119 * Generate a fingerprint string for the key. Compatible with the
120 * OpenSSH fingerprint code.
121 */
122void rsa_fingerprint(char *str, int len, struct RSAKey *key) {
123 struct MD5Context md5c;
124 unsigned char digest[16];
125 char buffer[16*3+40];
126 int numlen, slen, i;
127
128 MD5Init(&md5c);
129 numlen = ssh1_bignum_length(key->modulus) - 2;
130 for (i = numlen; i-- ;) {
131 unsigned char c = bignum_byte(key->modulus, i);
132 MD5Update(&md5c, &c, 1);
133 }
134 numlen = ssh1_bignum_length(key->exponent) - 2;
135 for (i = numlen; i-- ;) {
136 unsigned char c = bignum_byte(key->exponent, i);
137 MD5Update(&md5c, &c, 1);
138 }
139 MD5Final(digest, &md5c);
140
141 sprintf(buffer, "%d ", ssh1_bignum_bitcount(key->modulus));
142 for (i = 0; i < 16; i++)
143 sprintf(buffer+strlen(buffer), "%s%02x", i?":":"", digest[i]);
144 strncpy(str, buffer, len); str[len-1] = '\0';
145 slen = strlen(str);
146 if (key->comment && slen < len-1) {
147 str[slen] = ' ';
148 strncpy(str+slen+1, key->comment, len-slen-1);
149 str[len-1] = '\0';
150 }
151}
152
5c58ad2d 153void freersakey(struct RSAKey *key) {
154 if (key->modulus) freebn(key->modulus);
155 if (key->exponent) freebn(key->exponent);
156 if (key->private_exponent) freebn(key->private_exponent);
dcbde236 157 if (key->comment) sfree(key->comment);
5c58ad2d 158}
85cc02bb 159
160/* ----------------------------------------------------------------------
161 * Implementation of the ssh-rsa signing key type.
162 */
163
164#define GET_32BIT(cp) \
165 (((unsigned long)(unsigned char)(cp)[0] << 24) | \
166 ((unsigned long)(unsigned char)(cp)[1] << 16) | \
167 ((unsigned long)(unsigned char)(cp)[2] << 8) | \
168 ((unsigned long)(unsigned char)(cp)[3]))
169
170#define PUT_32BIT(cp, value) { \
171 (cp)[0] = (unsigned char)((value) >> 24); \
172 (cp)[1] = (unsigned char)((value) >> 16); \
173 (cp)[2] = (unsigned char)((value) >> 8); \
174 (cp)[3] = (unsigned char)(value); }
175
176static void getstring(char **data, int *datalen, char **p, int *length) {
177 *p = NULL;
178 if (*datalen < 4)
179 return;
180 *length = GET_32BIT(*data);
181 *datalen -= 4; *data += 4;
182 if (*datalen < *length)
183 return;
184 *p = *data;
185 *data += *length; *datalen -= *length;
186}
187static Bignum getmp(char **data, int *datalen) {
188 char *p;
189 int length;
190 Bignum b;
191
192 getstring(data, datalen, &p, &length);
193 if (!p)
194 return NULL;
195 b = bignum_from_bytes(p, length);
196 return b;
197}
198
199static void *rsa2_newkey(char *data, int len) {
200 char *p;
201 int slen;
202 struct RSAKey *rsa;
203
204 rsa = smalloc(sizeof(struct RSAKey));
205 if (!rsa) return NULL;
206 getstring(&data, &len, &p, &slen);
207
208 if (!p || memcmp(p, "ssh-rsa", 7)) {
209 sfree(rsa);
210 return NULL;
211 }
212 rsa->exponent = getmp(&data, &len);
213 rsa->modulus = getmp(&data, &len);
214 rsa->private_exponent = NULL;
215 rsa->comment = NULL;
216
217 return rsa;
218}
219
220static void rsa2_freekey(void *key) {
221 struct RSAKey *rsa = (struct RSAKey *)key;
222 freersakey(rsa);
223 sfree(rsa);
224}
225
226static char *rsa2_fmtkey(void *key) {
227 struct RSAKey *rsa = (struct RSAKey *)key;
228 char *p;
229 int len;
230
231 len = rsastr_len(rsa);
232 p = smalloc(len);
233 rsastr_fmt(p, rsa);
234 return p;
235}
236
237static char *rsa2_fingerprint(void *key) {
238 struct RSAKey *rsa = (struct RSAKey *)key;
239 struct MD5Context md5c;
240 unsigned char digest[16], lenbuf[4];
241 char buffer[16*3+40];
242 char *ret;
243 int numlen, i;
244
245 MD5Init(&md5c);
246 MD5Update(&md5c, "\0\0\0\7ssh-rsa", 11);
247
248#define ADD_BIGNUM(bignum) \
249 numlen = (ssh1_bignum_bitcount(bignum)+8)/8; \
250 PUT_32BIT(lenbuf, numlen); MD5Update(&md5c, lenbuf, 4); \
251 for (i = numlen; i-- ;) { \
252 unsigned char c = bignum_byte(bignum, i); \
253 MD5Update(&md5c, &c, 1); \
254 }
255 ADD_BIGNUM(rsa->exponent);
256 ADD_BIGNUM(rsa->modulus);
257#undef ADD_BIGNUM
258
259 MD5Final(digest, &md5c);
260
5d03233b 261 sprintf(buffer, "ssh-rsa %d ", ssh1_bignum_bitcount(rsa->modulus));
85cc02bb 262 for (i = 0; i < 16; i++)
263 sprintf(buffer+strlen(buffer), "%s%02x", i?":":"", digest[i]);
264 ret = smalloc(strlen(buffer)+1);
265 if (ret)
266 strcpy(ret, buffer);
267 return ret;
268}
269
270/*
271 * This is the magic ASN.1/DER prefix that goes in the decoded
272 * signature, between the string of FFs and the actual SHA hash
273 * value. As closely as I can tell, the meaning of it is:
274 *
275 * 00 -- this marks the end of the FFs; not part of the ASN.1 bit itself
276 *
277 * 30 21 -- a constructed SEQUENCE of length 0x21
278 * 30 09 -- a constructed sub-SEQUENCE of length 9
279 * 06 05 -- an object identifier, length 5
280 * 2B 0E 03 02 1A --
281 * 05 00 -- NULL
282 * 04 14 -- a primitive OCTET STRING of length 0x14
283 * [0x14 bytes of hash data follows]
284 */
285static unsigned char asn1_weird_stuff[] = {
286 0x00,0x30,0x21,0x30,0x09,0x06,0x05,0x2B,
287 0x0E,0x03,0x02,0x1A,0x05,0x00,0x04,0x14,
288};
289
290static int rsa2_verifysig(void *key, char *sig, int siglen,
291 char *data, int datalen) {
292 struct RSAKey *rsa = (struct RSAKey *)key;
293 Bignum in, out;
294 char *p;
295 int slen;
296 int bytes, i, j, ret;
297 unsigned char hash[20];
298
299 getstring(&sig, &siglen, &p, &slen);
300 if (!p || slen != 7 || memcmp(p, "ssh-rsa", 7)) {
301 return 0;
302 }
303 in = getmp(&sig, &siglen);
304 out = modpow(in, rsa->exponent, rsa->modulus);
305 freebn(in);
306
307 ret = 1;
308
309 bytes = ssh1_bignum_bitcount(rsa->modulus) / 8;
310 /* Top (partial) byte should be zero. */
311 if (bignum_byte(out, bytes-1) != 0)
312 ret = 0;
313 /* First whole byte should be 1. */
314 if (bignum_byte(out, bytes-2) != 1)
315 ret = 0;
316 /* Most of the rest should be FF. */
317 for (i = bytes-3; i >= 20 + sizeof(asn1_weird_stuff); i--) {
318 if (bignum_byte(out, i) != 0xFF)
319 ret = 0;
320 }
321 /* Then we expect to see the asn1_weird_stuff. */
322 for (i = 20 + sizeof(asn1_weird_stuff) - 1, j=0; i >= 20; i--,j++) {
323 if (bignum_byte(out, i) != asn1_weird_stuff[j])
324 ret = 0;
325 }
326 /* Finally, we expect to see the SHA-1 hash of the signed data. */
327 SHA_Simple(data, datalen, hash);
328 for (i = 19, j=0; i >= 0; i--,j++) {
329 if (bignum_byte(out, i) != hash[j])
330 ret = 0;
331 }
332
333 return ret;
334}
335
336int rsa2_sign(void *key, char *sig, int siglen,
337 char *data, int datalen) {
338 return 0; /* FIXME */
339}
340
341struct ssh_signkey ssh_rsa = {
342 rsa2_newkey,
343 rsa2_freekey,
344 rsa2_fmtkey,
345 rsa2_fingerprint,
346 rsa2_verifysig,
347 rsa2_sign,
348 "ssh-rsa",
349 "rsa2"
350};