2 * RSA implementation just sufficient for ssh client-side
5 * Rewritten for more speed by Joris van Rantwijk, Jun 1999.
15 int makekey(unsigned char *data, struct RSAKey *result,
16 unsigned char **keystr, int order) {
17 unsigned char *p = data;
23 result->bits = (result->bits << 8) + *p++;
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).
34 p += ssh1_read_bignum(p, result ? &result->exponent : NULL);
36 result->bytes = (((p[0] << 8) + p[1]) + 7) / 8;
37 if (keystr) *keystr = p+2;
38 p += ssh1_read_bignum(p, result ? &result->modulus : NULL);
40 p += ssh1_read_bignum(p, result ? &result->exponent : NULL);
45 int makeprivate(unsigned char *data, struct RSAKey *result) {
46 return ssh1_read_bignum(data, &result->private_exponent);
49 void rsaencrypt(unsigned char *data, int length, struct RSAKey *key) {
54 memmove(data+key->bytes-length, data, length);
58 for (i = 2; i < key->bytes-length-1; i++) {
60 data[i] = random_byte();
61 } while (data[i] == 0);
63 data[key->bytes-length-1] = 0;
65 b1 = bignum_from_bytes(data, key->bytes);
67 b2 = modpow(b1, key->exponent, key->modulus);
70 for (i=key->bytes; i-- ;) {
71 *p++ = bignum_byte(b2, i);
78 Bignum rsadecrypt(Bignum input, struct RSAKey *key) {
80 ret = modpow(input, key->private_exponent, key->modulus);
84 int rsastr_len(struct RSAKey *key) {
90 mdlen = (ssh1_bignum_bitcount(md)+15) / 16;
91 exlen = (ssh1_bignum_bitcount(ex)+15) / 16;
92 return 4 * (mdlen+exlen) + 20;
95 void rsastr_fmt(char *str, struct RSAKey *key) {
97 int len = 0, i, nibbles;
98 static const char hex[] = "0123456789abcdef";
103 len += sprintf(str+len, "0x");
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];
109 len += sprintf(str+len, ",0x");
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];
119 * Generate a fingerprint string for the key. Compatible with the
120 * OpenSSH fingerprint code.
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];
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);
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);
139 MD5Final(digest, &md5c);
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';
146 if (key->comment && slen < len-1) {
148 strncpy(str+slen+1, key->comment, len-slen-1);
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);
157 if (key->comment) sfree(key->comment);
160 /* ----------------------------------------------------------------------
161 * Implementation of the ssh-rsa signing key type.
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]))
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); }
176 static void getstring(char **data, int *datalen, char **p, int *length) {
180 *length = GET_32BIT(*data);
181 *datalen -= 4; *data += 4;
182 if (*datalen < *length)
185 *data += *length; *datalen -= *length;
187 static Bignum getmp(char **data, int *datalen) {
192 getstring(data, datalen, &p, &length);
195 b = bignum_from_bytes(p, length);
199 static void *rsa2_newkey(char *data, int len) {
204 rsa = smalloc(sizeof(struct RSAKey));
205 if (!rsa) return NULL;
206 getstring(&data, &len, &p, &slen);
208 if (!p || memcmp(p, "ssh-rsa", 7)) {
212 rsa->exponent = getmp(&data, &len);
213 rsa->modulus = getmp(&data, &len);
214 rsa->private_exponent = NULL;
220 static void rsa2_freekey(void *key) {
221 struct RSAKey *rsa = (struct RSAKey *)key;
226 static char *rsa2_fmtkey(void *key) {
227 struct RSAKey *rsa = (struct RSAKey *)key;
231 len = rsastr_len(rsa);
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];
246 MD5Update(&md5c, "\0\0\0\7ssh-rsa", 11);
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); \
255 ADD_BIGNUM(rsa->exponent);
256 ADD_BIGNUM(rsa->modulus);
259 MD5Final(digest, &md5c);
261 sprintf(buffer, "%d ", ssh1_bignum_bitcount(rsa->modulus));
262 for (i = 0; i < 16; i++)
263 sprintf(buffer+strlen(buffer), "%s%02x", i?":":"", digest[i]);
264 ret = smalloc(strlen(buffer)+1);
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:
275 * 00 -- this marks the end of the FFs; not part of the ASN.1 bit itself
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
282 * 04 14 -- a primitive OCTET STRING of length 0x14
283 * [0x14 bytes of hash data follows]
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,
290 static int rsa2_verifysig(void *key, char *sig, int siglen,
291 char *data, int datalen) {
292 struct RSAKey *rsa = (struct RSAKey *)key;
296 int bytes, i, j, ret;
297 unsigned char hash[20];
299 getstring(&sig, &siglen, &p, &slen);
300 if (!p || slen != 7 || memcmp(p, "ssh-rsa", 7)) {
303 in = getmp(&sig, &siglen);
304 out = modpow(in, rsa->exponent, rsa->modulus);
309 bytes = ssh1_bignum_bitcount(rsa->modulus) / 8;
310 /* Top (partial) byte should be zero. */
311 if (bignum_byte(out, bytes-1) != 0)
313 /* First whole byte should be 1. */
314 if (bignum_byte(out, bytes-2) != 1)
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)
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])
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])
336 int rsa2_sign(void *key, char *sig, int siglen,
337 char *data, int datalen) {
338 return 0; /* FIXME */
341 struct ssh_signkey ssh_rsa = {