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 |
15 | int 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 |
45 | int makeprivate(unsigned char *data, struct RSAKey *result) { |
46 | return ssh1_read_bignum(data, &result->private_exponent); |
47 | } |
48 | |
374330e2 |
49 | void 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 |
78 | Bignum 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 |
84 | int 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 | |
95 | void 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 | */ |
122 | void 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 |
153 | void 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 | |
176 | static 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 | } |
187 | static 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 | |
199 | static 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 | |
220 | static void rsa2_freekey(void *key) { |
221 | struct RSAKey *rsa = (struct RSAKey *)key; |
222 | freersakey(rsa); |
223 | sfree(rsa); |
224 | } |
225 | |
226 | static 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 | |
237 | static 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 | */ |
285 | static 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 | |
290 | static 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 | |
336 | int rsa2_sign(void *key, char *sig, int siglen, |
337 | char *data, int datalen) { |
338 | return 0; /* FIXME */ |
339 | } |
340 | |
341 | struct 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 | }; |