[u/mdw/putty] / sshrsa.c

/*
 * RSA implementation just sufficient for ssh client-side
 * initialisation step
 *
 * Rewritten for more speed by Joris van Rantwijk, Jun 1999.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "ssh.h"


int makekey(unsigned char *data, struct RSAKey *result,
	    unsigned char **keystr, int order) {
    unsigned char *p = data;
    int i;

    if (result) {
        result->bits = 0;
        for (i=0; i<4; i++)
            result->bits = (result->bits << 8) + *p++;
    } else
        p += 4;

    /*
     * order=0 means exponent then modulus (the keys sent by the
     * server). order=1 means modulus then exponent (the keys
     * stored in a keyfile).
     */

    if (order == 0)
        p += ssh1_read_bignum(p, result ? &result->exponent : NULL);
    if (result)
        result->bytes = (((p[0] << 8) + p[1]) + 7) / 8;
    if (keystr) *keystr = p+2;
    p += ssh1_read_bignum(p, result ? &result->modulus : NULL);
    if (order == 1)
        p += ssh1_read_bignum(p, result ? &result->exponent : NULL);

    return p - data;
}

int makeprivate(unsigned char *data, struct RSAKey *result) {
    return ssh1_read_bignum(data, &result->private_exponent);
}

void rsaencrypt(unsigned char *data, int length, struct RSAKey *key) {
    Bignum b1, b2;
    int i;
    unsigned char *p;

    memmove(data+key->bytes-length, data, length);
    data[0] = 0;
    data[1] = 2;

    for (i = 2; i < key->bytes-length-1; i++) {
	do {
	    data[i] = random_byte();
	} while (data[i] == 0);
    }
    data[key->bytes-length-1] = 0;

    b1 = bignum_from_bytes(data, key->bytes);

    b2 = modpow(b1, key->exponent, key->modulus);

    p = data;
    for (i=key->bytes; i-- ;) {
        *p++ = bignum_byte(b2, i);
    }

    freebn(b1);
    freebn(b2);
}

Bignum rsadecrypt(Bignum input, struct RSAKey *key) {
    Bignum ret;
    ret = modpow(input, key->private_exponent, key->modulus);
    return ret;
}

int rsastr_len(struct RSAKey *key) {
    Bignum md, ex;
    int mdlen, exlen;

    md = key->modulus;
    ex = key->exponent;
    mdlen = (ssh1_bignum_bitcount(md)+15) / 16;
    exlen = (ssh1_bignum_bitcount(ex)+15) / 16;
    return 4 * (mdlen+exlen) + 20;
}

void rsastr_fmt(char *str, struct RSAKey *key) {
    Bignum md, ex;
    int len = 0, i, nibbles;
    static const char hex[] = "0123456789abcdef";

    md = key->modulus;
    ex = key->exponent;

    len += sprintf(str+len, "0x");

    nibbles = (3 + ssh1_bignum_bitcount(ex))/4; if (nibbles<1) nibbles=1;
    for (i=nibbles; i-- ;)
        str[len++] = hex[(bignum_byte(ex, i/2) >> (4*(i%2))) & 0xF];

    len += sprintf(str+len, ",0x");

    nibbles = (3 + ssh1_bignum_bitcount(md))/4; if (nibbles<1) nibbles=1;
    for (i=nibbles; i-- ;)
        str[len++] = hex[(bignum_byte(md, i/2) >> (4*(i%2))) & 0xF];

    str[len] = '\0';
}

/*
 * Generate a fingerprint string for the key. Compatible with the
 * OpenSSH fingerprint code.
 */
void rsa_fingerprint(char *str, int len, struct RSAKey *key) {
    struct MD5Context md5c;
    unsigned char digest[16];
    char buffer[16*3+40];
    int numlen, slen, i;

    MD5Init(&md5c);
    numlen = ssh1_bignum_length(key->modulus) - 2;
    for (i = numlen; i-- ;) {
        unsigned char c = bignum_byte(key->modulus, i);
        MD5Update(&md5c, &c, 1);
    }
    numlen = ssh1_bignum_length(key->exponent) - 2;
    for (i = numlen; i-- ;) {
        unsigned char c = bignum_byte(key->exponent, i);
        MD5Update(&md5c, &c, 1);
    }
    MD5Final(digest, &md5c);

    sprintf(buffer, "%d ", ssh1_bignum_bitcount(key->modulus));
    for (i = 0; i < 16; i++)
        sprintf(buffer+strlen(buffer), "%s%02x", i?":":"", digest[i]);
    strncpy(str, buffer, len); str[len-1] = '\0';
    slen = strlen(str);
    if (key->comment && slen < len-1) {
        str[slen] = ' ';
        strncpy(str+slen+1, key->comment, len-slen-1);
        str[len-1] = '\0';
    }
}

/*
 * Verify that the public data in an RSA key matches the private
 * data.
 */
int rsa_verify(struct RSAKey *key) {
    Bignum n, ed, pm1, qm1, pm1qm1;
    int cmp;

    /* n must equal pq. */
    n = bigmul(key->p, key->q);
    cmp = bignum_cmp(n, key->modulus);
    freebn(n);
    if (cmp != 0)
	return 0;

    /* e * d must be congruent to 1, modulo (p-1)(q-1). */
    pm1 = copybn(key->p);
    decbn(pm1);
    qm1 = copybn(key->q);
    decbn(qm1);
    pm1qm1 = bigmul(pm1, qm1);
    freebn(pm1);
    freebn(qm1);
    ed = modmul(key->exponent, key->private_exponent, pm1qm1);
    sfree(pm1qm1);
    cmp = bignum_cmp(ed, One);
    sfree(ed);
    if (cmp != 0)
	return 0;

    return 1;
}

void freersakey(struct RSAKey *key) {
    if (key->modulus) freebn(key->modulus);
    if (key->exponent) freebn(key->exponent);
    if (key->private_exponent) freebn(key->private_exponent);
    if (key->comment) sfree(key->comment);
}

/* ----------------------------------------------------------------------
 * Implementation of the ssh-rsa signing key type. 
 */

#define GET_32BIT(cp) \
    (((unsigned long)(unsigned char)(cp)[0] << 24) | \
    ((unsigned long)(unsigned char)(cp)[1] << 16) | \
    ((unsigned long)(unsigned char)(cp)[2] << 8) | \
    ((unsigned long)(unsigned char)(cp)[3]))

#define PUT_32BIT(cp, value) { \
    (cp)[0] = (unsigned char)((value) >> 24); \
    (cp)[1] = (unsigned char)((value) >> 16); \
    (cp)[2] = (unsigned char)((value) >> 8); \
    (cp)[3] = (unsigned char)(value); }

static void getstring(char **data, int *datalen, char **p, int *length) {
    *p = NULL;
    if (*datalen < 4)
        return;
    *length = GET_32BIT(*data);
    *datalen -= 4; *data += 4;
    if (*datalen < *length)
        return;
    *p = *data;
    *data += *length; *datalen -= *length;
}
static Bignum getmp(char **data, int *datalen) {
    char *p;
    int length;
    Bignum b;

    getstring(data, datalen, &p, &length);
    if (!p)
        return NULL;
    b = bignum_from_bytes(p, length);
    return b;
}

static void *rsa2_newkey(char *data, int len) {
    char *p;
    int slen;
    struct RSAKey *rsa;

    rsa = smalloc(sizeof(struct RSAKey));
    if (!rsa) return NULL;
    getstring(&data, &len, &p, &slen);

    if (!p || slen != 7 || memcmp(p, "ssh-rsa", 7)) {
	sfree(rsa);
	return NULL;
    }
    rsa->exponent = getmp(&data, &len);
    rsa->modulus = getmp(&data, &len);
    rsa->private_exponent = NULL;
    rsa->comment = NULL;

    return rsa;
}

static void rsa2_freekey(void *key) {
    struct RSAKey *rsa = (struct RSAKey *)key;
    freersakey(rsa);
    sfree(rsa);
}

static char *rsa2_fmtkey(void *key) {
    struct RSAKey *rsa = (struct RSAKey *)key;
    char *p;
    int len;
    
    len = rsastr_len(rsa);
    p = smalloc(len);
     rsastr_fmt(p, rsa);
    return p;
}

static unsigned char *rsa2_public_blob(void *key, int *len) {
    struct RSAKey *rsa = (struct RSAKey *)key;
    int elen, mlen, bloblen;
    int i;
    unsigned char *blob, *p;

    elen = (ssh1_bignum_bitcount(rsa->exponent)+8)/8;
    mlen = (ssh1_bignum_bitcount(rsa->modulus)+8)/8;

    /*
     * string "ssh-rsa", mpint exp, mpint mod. Total 19+elen+mlen.
     * (three length fields, 12+7=19).
     */
    bloblen = 19+elen+mlen;
    blob = smalloc(bloblen);
    p = blob;
    PUT_32BIT(p, 7); p += 4;
    memcpy(p, "ssh-rsa", 7); p += 7;
    PUT_32BIT(p, elen); p += 4;
    for (i = elen; i-- ;) *p++ = bignum_byte(rsa->exponent, i);
    PUT_32BIT(p, mlen); p += 4;
    for (i = mlen; i-- ;) *p++ = bignum_byte(rsa->modulus, i);
    assert(p == blob + bloblen);
    *len = bloblen;
    return blob;
}

static unsigned char *rsa2_private_blob(void *key, int *len) {
    struct RSAKey *rsa = (struct RSAKey *)key;
    int dlen, plen, qlen, ulen, bloblen;
    int i;
    unsigned char *blob, *p;

    dlen = (ssh1_bignum_bitcount(rsa->private_exponent)+8)/8;
    plen = (ssh1_bignum_bitcount(rsa->p)+8)/8;
    qlen = (ssh1_bignum_bitcount(rsa->q)+8)/8;
    ulen = (ssh1_bignum_bitcount(rsa->iqmp)+8)/8;

    /*
     * mpint private_exp, mpint p, mpint q, mpint iqmp. Total 16 +
     * sum of lengths.
     */
    bloblen = 16+dlen+plen+qlen+ulen;
    blob = smalloc(bloblen);
    p = blob;
    PUT_32BIT(p, dlen); p += 4;
    for (i = dlen; i-- ;) *p++ = bignum_byte(rsa->private_exponent, i);
    PUT_32BIT(p, plen); p += 4;
    for (i = plen; i-- ;) *p++ = bignum_byte(rsa->p, i);
    PUT_32BIT(p, qlen); p += 4;
    for (i = qlen; i-- ;) *p++ = bignum_byte(rsa->q, i);
    PUT_32BIT(p, ulen); p += 4;
    for (i = ulen; i-- ;) *p++ = bignum_byte(rsa->iqmp, i);
    assert(p == blob + bloblen);
    *len = bloblen;
    return blob;
}

static void *rsa2_createkey(unsigned char *pub_blob, int pub_len,
			    unsigned char *priv_blob, int priv_len) {
    struct RSAKey *rsa;
    char *pb = (char *)priv_blob;
    
    rsa = rsa2_newkey((char *)pub_blob, pub_len);
    rsa->private_exponent = getmp(&pb, &priv_len);
    rsa->p = getmp(&pb, &priv_len);
    rsa->q = getmp(&pb, &priv_len);
    rsa->iqmp = getmp(&pb, &priv_len);

    if (!rsa_verify(rsa)) {
	rsa2_freekey(rsa);
	return NULL;
    }

    return rsa;
}

static void *rsa2_openssh_createkey(unsigned char **blob, int *len) {
    char **b = (char **)blob;
    struct RSAKey *rsa;

    rsa = smalloc(sizeof(struct RSAKey));
    if (!rsa) return NULL;
    rsa->comment = NULL;

    rsa->modulus = getmp(b, len);
    rsa->exponent = getmp(b, len);
    rsa->private_exponent = getmp(b, len);
    rsa->iqmp = getmp(b, len);
    rsa->p = getmp(b, len);
    rsa->q = getmp(b, len);

    if (!rsa->modulus || !rsa->exponent || !rsa->private_exponent ||
	!rsa->iqmp || !rsa->p || !rsa->q) {
	sfree(rsa->modulus);
	sfree(rsa->exponent);
	sfree(rsa->private_exponent);
	sfree(rsa->iqmp);
	sfree(rsa->p);
	sfree(rsa->q);
	sfree(rsa);
	return NULL;
    }

    return rsa;
}

static char *rsa2_fingerprint(void *key) {
    struct RSAKey *rsa = (struct RSAKey *)key;
    struct MD5Context md5c;
    unsigned char digest[16], lenbuf[4];
    char buffer[16*3+40];
    char *ret;
    int numlen, i;

    MD5Init(&md5c);
    MD5Update(&md5c, "\0\0\0\7ssh-rsa", 11);

#define ADD_BIGNUM(bignum) \
    numlen = (ssh1_bignum_bitcount(bignum)+8)/8; \
    PUT_32BIT(lenbuf, numlen); MD5Update(&md5c, lenbuf, 4); \
    for (i = numlen; i-- ;) { \
        unsigned char c = bignum_byte(bignum, i); \
        MD5Update(&md5c, &c, 1); \
    }
    ADD_BIGNUM(rsa->exponent);
    ADD_BIGNUM(rsa->modulus);
#undef ADD_BIGNUM

    MD5Final(digest, &md5c);

    sprintf(buffer, "ssh-rsa %d ", ssh1_bignum_bitcount(rsa->modulus));
    for (i = 0; i < 16; i++)
        sprintf(buffer+strlen(buffer), "%s%02x", i?":":"", digest[i]);
    ret = smalloc(strlen(buffer)+1);
    if (ret)
        strcpy(ret, buffer);
    return ret;
}

/*
 * This is the magic ASN.1/DER prefix that goes in the decoded
 * signature, between the string of FFs and the actual SHA hash
 * value. The meaning of it is:
 * 
 * 00 -- this marks the end of the FFs; not part of the ASN.1 bit itself
 * 
 * 30 21 -- a constructed SEQUENCE of length 0x21
 *    30 09 -- a constructed sub-SEQUENCE of length 9
 *       06 05 -- an object identifier, length 5
 *          2B 0E 03 02 1A -- object id { 1 3 14 3 2 26 }
 *                            (the 1,3 comes from 0x2B = 43 = 40*1+3)
 *       05 00 -- NULL
 *    04 14 -- a primitive OCTET STRING of length 0x14
 *       [0x14 bytes of hash data follows]
 * 
 * The object id in the middle there is listed as `id-sha1' in
 * ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-1/pkcs-1v2-1d2.asn (the
 * ASN module for PKCS #1) and its expanded form is as follows:
 * 
 * id-sha1                OBJECT IDENTIFIER ::= {
 *    iso(1) identified-organization(3) oiw(14) secsig(3)
 *    algorithms(2) 26 }
 */
static unsigned char asn1_weird_stuff[] = {
    0x00,0x30,0x21,0x30,0x09,0x06,0x05,0x2B,
    0x0E,0x03,0x02,0x1A,0x05,0x00,0x04,0x14,
};

#define ASN1_LEN ( (int) sizeof(asn1_weird_stuff) )

static int rsa2_verifysig(void *key, char *sig, int siglen,
			 char *data, int datalen) {
    struct RSAKey *rsa = (struct RSAKey *)key;
    Bignum in, out;
    char *p;
    int slen;
    int bytes, i, j, ret;
    unsigned char hash[20];

    getstring(&sig, &siglen, &p, &slen);
    if (!p || slen != 7 || memcmp(p, "ssh-rsa", 7)) {
        return 0;
    }
    in = getmp(&sig, &siglen);
    out = modpow(in, rsa->exponent, rsa->modulus);
    freebn(in);

    ret = 1;

    bytes = ssh1_bignum_bitcount(rsa->modulus) / 8;
    /* Top (partial) byte should be zero. */
    if (bignum_byte(out, bytes-1) != 0)
        ret = 0;
    /* First whole byte should be 1. */
    if (bignum_byte(out, bytes-2) != 1)
        ret = 0;
    /* Most of the rest should be FF. */
    for (i = bytes-3; i >= 20 + ASN1_LEN; i--) {
        if (bignum_byte(out, i) != 0xFF)
            ret = 0;
    }
    /* Then we expect to see the asn1_weird_stuff. */
    for (i = 20 + ASN1_LEN - 1, j=0; i >= 20; i--,j++) {
        if (bignum_byte(out, i) != asn1_weird_stuff[j])
            ret = 0;
    }
    /* Finally, we expect to see the SHA-1 hash of the signed data. */
    SHA_Simple(data, datalen, hash);
    for (i = 19, j=0; i >= 0; i--,j++) {
        if (bignum_byte(out, i) != hash[j])
            ret = 0;
    }

    return ret;
}

unsigned char *rsa2_sign(void *key, char *data, int datalen, int *siglen) {
    struct RSAKey *rsa = (struct RSAKey *)key;
    unsigned char *bytes;
    int nbytes;
    unsigned char hash[20];
    Bignum in, out;
    int i, j;

    SHA_Simple(data, datalen, hash);

    nbytes = (ssh1_bignum_bitcount(rsa->modulus)-1) / 8;
    bytes = smalloc(nbytes);

    bytes[0] = 1;
    for (i = 1; i < nbytes-20-ASN1_LEN; i++)
	bytes[i] = 0xFF;
    for (i = nbytes-20-ASN1_LEN, j=0; i < nbytes-20; i++,j++)
	bytes[i] = asn1_weird_stuff[j];
    for (i = nbytes-20, j=0; i < nbytes; i++,j++)
	bytes[i] = hash[j];

    in = bignum_from_bytes(bytes, nbytes);
    sfree(bytes);

    out = modpow(in, rsa->private_exponent, rsa->modulus);
    freebn(in);

    nbytes = (ssh1_bignum_bitcount(out)+7)/8;
    bytes = smalloc(4+7+4+nbytes);
    PUT_32BIT(bytes, 7);
    memcpy(bytes+4, "ssh-rsa", 7);
    PUT_32BIT(bytes+4+7, nbytes);
    for (i = 0; i < nbytes; i++)
	bytes[4+7+4+i] = bignum_byte(out, nbytes-1-i);
    freebn(out);

    *siglen = 4+7+4+nbytes;
    return bytes;
}

const struct ssh_signkey ssh_rsa = {
    rsa2_newkey,
    rsa2_freekey,
    rsa2_fmtkey,
    rsa2_public_blob,
    rsa2_private_blob,
    rsa2_createkey,
    rsa2_openssh_createkey,
    rsa2_fingerprint,
    rsa2_verifysig,
    rsa2_sign,
    "ssh-rsa",
    "rsa2"
};
Commit	Line	Data
374330e2	1	/*
	2	* RSA implementation just sufficient for ssh client-side
	3	* initialisation step
4644b0ce	4	*
4644b0ce	5	* Rewritten for more speed by Joris van Rantwijk, Jun 1999.
374330e2	6	*/
374330e2	7
374330e2	8	#include <stdio.h>
	9	#include <stdlib.h>
	10	#include <string.h>
65a22376	11	#include <assert.h>
374330e2	12
e5574168	13	#include "ssh.h"
374330e2	14
1c2a93c4	15
374330e2	16	int makekey(unsigned char data, struct RSAKey result,
7cca0d81	17	unsigned char **keystr, int order) {
374330e2	18	unsigned char *p = data;
7cca0d81	19	int i;
374330e2	20
a52f067e	21	if (result) {
	22	result->bits = 0;
	23	for (i=0; i<4; i++)
	24	result->bits = (result->bits << 8) + *p++;
	25	} else
	26	p += 4;
374330e2	27
7cca0d81	28	/*
	29	* order=0 means exponent then modulus (the keys sent by the
	30	* server). order=1 means modulus then exponent (the keys
	31	* stored in a keyfile).
	32	*/
374330e2	33
7cca0d81	34	if (order == 0)
a52f067e	35	p += ssh1_read_bignum(p, result ? &result->exponent : NULL);
	36	if (result)
	37	result->bytes = (((p[0] << 8) + p[1]) + 7) / 8;
7cca0d81	38	if (keystr) *keystr = p+2;
a52f067e	39	p += ssh1_read_bignum(p, result ? &result->modulus : NULL);
7cca0d81	40	if (order == 1)
a52f067e	41	p += ssh1_read_bignum(p, result ? &result->exponent : NULL);
374330e2	42
	43	return p - data;
	44	}
	45
7cca0d81	46	int makeprivate(unsigned char data, struct RSAKey result) {
	47	return ssh1_read_bignum(data, &result->private_exponent);
	48	}
	49
374330e2	50	void rsaencrypt(unsigned char data, int length, struct RSAKey key) {
374330e2	51	Bignum b1, b2;
3709bfe9	52	int i;
374330e2	53	unsigned char *p;
374330e2	54
374330e2	55	memmove(data+key->bytes-length, data, length);
	56	data[0] = 0;
	57	data[1] = 2;
	58
	59	for (i = 2; i < key->bytes-length-1; i++) {
	60	do {
	61	data[i] = random_byte();
	62	} while (data[i] == 0);
	63	}
	64	data[key->bytes-length-1] = 0;
	65
3709bfe9	66	b1 = bignum_from_bytes(data, key->bytes);
374330e2	67
59600f67	68	b2 = modpow(b1, key->exponent, key->modulus);
374330e2	69
374330e2	70	p = data;
d9373729	71	for (i=key->bytes; i-- ;) {
3709bfe9	72	*p++ = bignum_byte(b2, i);
374330e2	73	}
	74
	75	freebn(b1);
	76	freebn(b2);
	77	}
	78
7cca0d81	79	Bignum rsadecrypt(Bignum input, struct RSAKey *key) {
7cca0d81	80	Bignum ret;
59600f67	81	ret = modpow(input, key->private_exponent, key->modulus);
7cca0d81	82	return ret;
	83	}
	84
374330e2	85	int rsastr_len(struct RSAKey *key) {
374330e2	86	Bignum md, ex;
3709bfe9	87	int mdlen, exlen;
374330e2	88
	89	md = key->modulus;
	90	ex = key->exponent;
3709bfe9	91	mdlen = (ssh1_bignum_bitcount(md)+15) / 16;
	92	exlen = (ssh1_bignum_bitcount(ex)+15) / 16;
	93	return 4 * (mdlen+exlen) + 20;
374330e2	94	}
	95
	96	void rsastr_fmt(char str, struct RSAKey key) {
	97	Bignum md, ex;
d5859615	98	int len = 0, i, nibbles;
d5859615	99	static const char hex[] = "0123456789abcdef";
374330e2	100
	101	md = key->modulus;
	102	ex = key->exponent;
	103
d5859615	104	len += sprintf(str+len, "0x");
	105
	106	nibbles = (3 + ssh1_bignum_bitcount(ex))/4; if (nibbles<1) nibbles=1;
	107	for (i=nibbles; i-- ;)
	108	str[len++] = hex[(bignum_byte(ex, i/2) >> (4*(i%2))) & 0xF];
	109
	110	len += sprintf(str+len, ",0x");
	111
	112	nibbles = (3 + ssh1_bignum_bitcount(md))/4; if (nibbles<1) nibbles=1;
	113	for (i=nibbles; i-- ;)
	114	str[len++] = hex[(bignum_byte(md, i/2) >> (4*(i%2))) & 0xF];
	115
374330e2	116	str[len] = '\0';
	117	}
	118
1c2a93c4	119	/*
	120	* Generate a fingerprint string for the key. Compatible with the
	121	* OpenSSH fingerprint code.
	122	*/
	123	void rsa_fingerprint(char str, int len, struct RSAKey key) {
	124	struct MD5Context md5c;
	125	unsigned char digest[16];
	126	char buffer[16*3+40];
	127	int numlen, slen, i;
	128
	129	MD5Init(&md5c);
	130	numlen = ssh1_bignum_length(key->modulus) - 2;
	131	for (i = numlen; i-- ;) {
	132	unsigned char c = bignum_byte(key->modulus, i);
	133	MD5Update(&md5c, &c, 1);
	134	}
	135	numlen = ssh1_bignum_length(key->exponent) - 2;
	136	for (i = numlen; i-- ;) {
	137	unsigned char c = bignum_byte(key->exponent, i);
	138	MD5Update(&md5c, &c, 1);
	139	}
	140	MD5Final(digest, &md5c);
	141
	142	sprintf(buffer, "%d ", ssh1_bignum_bitcount(key->modulus));
	143	for (i = 0; i < 16; i++)
	144	sprintf(buffer+strlen(buffer), "%s%02x", i?":":"", digest[i]);
	145	strncpy(str, buffer, len); str[len-1] = '\0';
	146	slen = strlen(str);
	147	if (key->comment && slen < len-1) {
	148	str[slen] = ' ';
	149	strncpy(str+slen+1, key->comment, len-slen-1);
	150	str[len-1] = '\0';
	151	}
	152	}
	153
98f022f5	154	/*
	155	* Verify that the public data in an RSA key matches the private
	156	* data.
	157	*/
	158	int rsa_verify(struct RSAKey *key) {
	159	Bignum n, ed, pm1, qm1, pm1qm1;
	160	int cmp;
	161
	162	/* n must equal pq. */
	163	n = bigmul(key->p, key->q);
	164	cmp = bignum_cmp(n, key->modulus);
	165	freebn(n);
	166	if (cmp != 0)
	167	return 0;
	168
	169	/* e * d must be congruent to 1, modulo (p-1)(q-1). */
	170	pm1 = copybn(key->p);
	171	decbn(pm1);
	172	qm1 = copybn(key->q);
	173	decbn(qm1);
	174	pm1qm1 = bigmul(pm1, qm1);
	175	freebn(pm1);
	176	freebn(qm1);
	177	ed = modmul(key->exponent, key->private_exponent, pm1qm1);
	178	sfree(pm1qm1);
	179	cmp = bignum_cmp(ed, One);
	180	sfree(ed);
	181	if (cmp != 0)
	182	return 0;
014970c8	183
014970c8	184	return 1;
98f022f5	185	}
98f022f5	186
5c58ad2d	187	void freersakey(struct RSAKey *key) {
	188	if (key->modulus) freebn(key->modulus);
	189	if (key->exponent) freebn(key->exponent);
	190	if (key->private_exponent) freebn(key->private_exponent);
dcbde236	191	if (key->comment) sfree(key->comment);
5c58ad2d	192	}
85cc02bb	193
	194	/* ----------------------------------------------------------------------
	195	* Implementation of the ssh-rsa signing key type.
	196	*/
	197
	198	#define GET_32BIT(cp) \
	199	(((unsigned long)(unsigned char)(cp)[0] << 24) \| \
	200	((unsigned long)(unsigned char)(cp)[1] << 16) \| \
	201	((unsigned long)(unsigned char)(cp)[2] << 8) \| \
	202	((unsigned long)(unsigned char)(cp)[3]))
	203
	204	#define PUT_32BIT(cp, value) { \
	205	(cp)[0] = (unsigned char)((value) >> 24); \
	206	(cp)[1] = (unsigned char)((value) >> 16); \
	207	(cp)[2] = (unsigned char)((value) >> 8); \
	208	(cp)[3] = (unsigned char)(value); }
	209
	210	static void getstring(char *data, int datalen, char *p, int length) {
	211	*p = NULL;
	212	if (*datalen < 4)
	213	return;
	214	length = GET_32BIT(data);
	215	datalen -= 4; data += 4;
	216	if (datalen < length)
	217	return;
	218	p = data;
	219	data += length; datalen -= length;
	220	}
	221	static Bignum getmp(char *data, int datalen) {
	222	char *p;
	223	int length;
	224	Bignum b;
	225
	226	getstring(data, datalen, &p, &length);
	227	if (!p)
	228	return NULL;
	229	b = bignum_from_bytes(p, length);
	230	return b;
	231	}
	232
	233	static void rsa2_newkey(char data, int len) {
	234	char *p;
	235	int slen;
	236	struct RSAKey *rsa;
	237
	238	rsa = smalloc(sizeof(struct RSAKey));
	239	if (!rsa) return NULL;
	240	getstring(&data, &len, &p, &slen);
	241
45cebe79	242	if (!p \|\| slen != 7 \|\| memcmp(p, "ssh-rsa", 7)) {
85cc02bb	243	sfree(rsa);
	244	return NULL;
	245	}
	246	rsa->exponent = getmp(&data, &len);
	247	rsa->modulus = getmp(&data, &len);
	248	rsa->private_exponent = NULL;
	249	rsa->comment = NULL;
	250
	251	return rsa;
	252	}
	253
	254	static void rsa2_freekey(void *key) {
	255	struct RSAKey rsa = (struct RSAKey )key;
	256	freersakey(rsa);
	257	sfree(rsa);
	258	}
	259
	260	static char rsa2_fmtkey(void key) {
	261	struct RSAKey rsa = (struct RSAKey )key;
	262	char *p;
	263	int len;
	264
	265	len = rsastr_len(rsa);
	266	p = smalloc(len);
98f022f5	267	rsastr_fmt(p, rsa);
85cc02bb	268	return p;
	269	}
	270
65a22376	271	static unsigned char rsa2_public_blob(void key, int *len) {
	272	struct RSAKey rsa = (struct RSAKey )key;
	273	int elen, mlen, bloblen;
	274	int i;
	275	unsigned char blob, p;
	276
	277	elen = (ssh1_bignum_bitcount(rsa->exponent)+8)/8;
	278	mlen = (ssh1_bignum_bitcount(rsa->modulus)+8)/8;
	279
	280	/*
	281	* string "ssh-rsa", mpint exp, mpint mod. Total 19+elen+mlen.
	282	* (three length fields, 12+7=19).
	283	*/
	284	bloblen = 19+elen+mlen;
	285	blob = smalloc(bloblen);
	286	p = blob;
	287	PUT_32BIT(p, 7); p += 4;
	288	memcpy(p, "ssh-rsa", 7); p += 7;
	289	PUT_32BIT(p, elen); p += 4;
	290	for (i = elen; i-- ;) *p++ = bignum_byte(rsa->exponent, i);
	291	PUT_32BIT(p, mlen); p += 4;
	292	for (i = mlen; i-- ;) *p++ = bignum_byte(rsa->modulus, i);
	293	assert(p == blob + bloblen);
	294	*len = bloblen;
	295	return blob;
	296	}
	297
	298	static unsigned char rsa2_private_blob(void key, int *len) {
	299	struct RSAKey rsa = (struct RSAKey )key;
	300	int dlen, plen, qlen, ulen, bloblen;
	301	int i;
	302	unsigned char blob, p;
	303
	304	dlen = (ssh1_bignum_bitcount(rsa->private_exponent)+8)/8;
	305	plen = (ssh1_bignum_bitcount(rsa->p)+8)/8;
	306	qlen = (ssh1_bignum_bitcount(rsa->q)+8)/8;
	307	ulen = (ssh1_bignum_bitcount(rsa->iqmp)+8)/8;
	308
	309	/*
	310	* mpint private_exp, mpint p, mpint q, mpint iqmp. Total 16 +
	311	* sum of lengths.
	312	*/
	313	bloblen = 16+dlen+plen+qlen+ulen;
	314	blob = smalloc(bloblen);
	315	p = blob;
	316	PUT_32BIT(p, dlen); p += 4;
	317	for (i = dlen; i-- ;) *p++ = bignum_byte(rsa->private_exponent, i);
	318	PUT_32BIT(p, plen); p += 4;
	319	for (i = plen; i-- ;) *p++ = bignum_byte(rsa->p, i);
	320	PUT_32BIT(p, qlen); p += 4;
	321	for (i = qlen; i-- ;) *p++ = bignum_byte(rsa->q, i);
	322	PUT_32BIT(p, ulen); p += 4;
	323	for (i = ulen; i-- ;) *p++ = bignum_byte(rsa->iqmp, i);
	324	assert(p == blob + bloblen);
	325	*len = bloblen;
	326	return blob;
	327	}
	328
	329	static void rsa2_createkey(unsigned char pub_blob, int pub_len,
	330	unsigned char *priv_blob, int priv_len) {
	331	struct RSAKey *rsa;
	332	char pb = (char )priv_blob;
	333
	334	rsa = rsa2_newkey((char *)pub_blob, pub_len);
335	rsa->private_exponent = getmp(&pb, &priv_len);
336	rsa->p = getmp(&pb, &priv_len);
337	rsa->q = getmp(&pb, &priv_len);
338	rsa->iqmp = getmp(&pb, &priv_len);
339
98f022f5	340	if (!rsa_verify(rsa)) {
	341	rsa2_freekey(rsa);
	342	return NULL;
	343	}
	344
65a22376	345	return rsa;
	346	}
	347
45cebe79	348	static void rsa2_openssh_createkey(unsigned char blob, int len) {
	349	char b = (char )blob;
	350	struct RSAKey *rsa;
45cebe79	351
	352	rsa = smalloc(sizeof(struct RSAKey));
	353	if (!rsa) return NULL;
	354	rsa->comment = NULL;
	355
	356	rsa->modulus = getmp(b, len);
	357	rsa->exponent = getmp(b, len);
	358	rsa->private_exponent = getmp(b, len);
	359	rsa->iqmp = getmp(b, len);
	360	rsa->p = getmp(b, len);
	361	rsa->q = getmp(b, len);
	362
	363	if (!rsa->modulus \|\| !rsa->exponent \|\| !rsa->private_exponent \|\|
	364	!rsa->iqmp \|\| !rsa->p \|\| !rsa->q) {
	365	sfree(rsa->modulus);
	366	sfree(rsa->exponent);
	367	sfree(rsa->private_exponent);
	368	sfree(rsa->iqmp);
	369	sfree(rsa->p);
	370	sfree(rsa->q);
	371	sfree(rsa);
	372	return NULL;
	373	}
	374
	375	return rsa;
	376	}
	377
85cc02bb	378	static char rsa2_fingerprint(void key) {
	379	struct RSAKey rsa = (struct RSAKey )key;
	380	struct MD5Context md5c;
	381	unsigned char digest[16], lenbuf[4];
	382	char buffer[16*3+40];
	383	char *ret;
	384	int numlen, i;
	385
	386	MD5Init(&md5c);
	387	MD5Update(&md5c, "\0\0\0\7ssh-rsa", 11);
	388
	389	#define ADD_BIGNUM(bignum) \
	390	numlen = (ssh1_bignum_bitcount(bignum)+8)/8; \
	391	PUT_32BIT(lenbuf, numlen); MD5Update(&md5c, lenbuf, 4); \
	392	for (i = numlen; i-- ;) { \
	393	unsigned char c = bignum_byte(bignum, i); \
	394	MD5Update(&md5c, &c, 1); \
	395	}
	396	ADD_BIGNUM(rsa->exponent);
	397	ADD_BIGNUM(rsa->modulus);
	398	#undef ADD_BIGNUM
	399
	400	MD5Final(digest, &md5c);
	401
5d03233b	402	sprintf(buffer, "ssh-rsa %d ", ssh1_bignum_bitcount(rsa->modulus));
85cc02bb	403	for (i = 0; i < 16; i++)
	404	sprintf(buffer+strlen(buffer), "%s%02x", i?":":"", digest[i]);
	405	ret = smalloc(strlen(buffer)+1);
	406	if (ret)
	407	strcpy(ret, buffer);
	408	return ret;
	409	}
	410
	411	/*
	412	* This is the magic ASN.1/DER prefix that goes in the decoded
	413	* signature, between the string of FFs and the actual SHA hash
96a73db9	414	* value. The meaning of it is:
85cc02bb	415	*
	416	* 00 -- this marks the end of the FFs; not part of the ASN.1 bit itself
	417	*
	418	* 30 21 -- a constructed SEQUENCE of length 0x21
	419	* 30 09 -- a constructed sub-SEQUENCE of length 9
	420	* 06 05 -- an object identifier, length 5
96a73db9	421	* 2B 0E 03 02 1A -- object id { 1 3 14 3 2 26 }
96a73db9	422	* (the 1,3 comes from 0x2B = 43 = 40*1+3)
85cc02bb	423	* 05 00 -- NULL
	424	* 04 14 -- a primitive OCTET STRING of length 0x14
	425	* [0x14 bytes of hash data follows]
96a73db9	426	*
	427	* The object id in the middle there is listed as `id-sha1' in
	428	* ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-1/pkcs-1v2-1d2.asn (the
	429	* ASN module for PKCS #1) and its expanded form is as follows:
	430	*
	431	* id-sha1 OBJECT IDENTIFIER ::= {
	432	* iso(1) identified-organization(3) oiw(14) secsig(3)
	433	* algorithms(2) 26 }
85cc02bb	434	*/
	435	static unsigned char asn1_weird_stuff[] = {
	436	0x00,0x30,0x21,0x30,0x09,0x06,0x05,0x2B,
	437	0x0E,0x03,0x02,0x1A,0x05,0x00,0x04,0x14,
	438	};
	439
d8770b12	440	#define ASN1_LEN ( (int) sizeof(asn1_weird_stuff) )
d8770b12	441
85cc02bb	442	static int rsa2_verifysig(void key, char sig, int siglen,
	443	char *data, int datalen) {
	444	struct RSAKey rsa = (struct RSAKey )key;
	445	Bignum in, out;
	446	char *p;
	447	int slen;
	448	int bytes, i, j, ret;
	449	unsigned char hash[20];
	450
	451	getstring(&sig, &siglen, &p, &slen);
	452	if (!p \|\| slen != 7 \|\| memcmp(p, "ssh-rsa", 7)) {
	453	return 0;
	454	}
	455	in = getmp(&sig, &siglen);
	456	out = modpow(in, rsa->exponent, rsa->modulus);
	457	freebn(in);
	458
	459	ret = 1;
	460
	461	bytes = ssh1_bignum_bitcount(rsa->modulus) / 8;
	462	/* Top (partial) byte should be zero. */
	463	if (bignum_byte(out, bytes-1) != 0)
	464	ret = 0;
	465	/* First whole byte should be 1. */
	466	if (bignum_byte(out, bytes-2) != 1)
	467	ret = 0;
	468	/* Most of the rest should be FF. */
d8770b12	469	for (i = bytes-3; i >= 20 + ASN1_LEN; i--) {
85cc02bb	470	if (bignum_byte(out, i) != 0xFF)
	471	ret = 0;
	472	}
	473	/* Then we expect to see the asn1_weird_stuff. */
d8770b12	474	for (i = 20 + ASN1_LEN - 1, j=0; i >= 20; i--,j++) {
85cc02bb	475	if (bignum_byte(out, i) != asn1_weird_stuff[j])
	476	ret = 0;
	477	}
	478	/* Finally, we expect to see the SHA-1 hash of the signed data. */
	479	SHA_Simple(data, datalen, hash);
	480	for (i = 19, j=0; i >= 0; i--,j++) {
	481	if (bignum_byte(out, i) != hash[j])
	482	ret = 0;
	483	}
	484
	485	return ret;
	486	}
	487
65a22376	488	unsigned char rsa2_sign(void key, char data, int datalen, int siglen) {
	489	struct RSAKey rsa = (struct RSAKey )key;
	490	unsigned char *bytes;
	491	int nbytes;
	492	unsigned char hash[20];
	493	Bignum in, out;
	494	int i, j;
	495
	496	SHA_Simple(data, datalen, hash);
	497
	498	nbytes = (ssh1_bignum_bitcount(rsa->modulus)-1) / 8;
	499	bytes = smalloc(nbytes);
	500
	501	bytes[0] = 1;
d8770b12	502	for (i = 1; i < nbytes-20-ASN1_LEN; i++)
65a22376	503	bytes[i] = 0xFF;
d8770b12	504	for (i = nbytes-20-ASN1_LEN, j=0; i < nbytes-20; i++,j++)
65a22376	505	bytes[i] = asn1_weird_stuff[j];
	506	for (i = nbytes-20, j=0; i < nbytes; i++,j++)
	507	bytes[i] = hash[j];
	508
	509	in = bignum_from_bytes(bytes, nbytes);
	510	sfree(bytes);
	511
	512	out = modpow(in, rsa->private_exponent, rsa->modulus);
	513	freebn(in);
	514
	515	nbytes = (ssh1_bignum_bitcount(out)+7)/8;
	516	bytes = smalloc(4+7+4+nbytes);
	517	PUT_32BIT(bytes, 7);
	518	memcpy(bytes+4, "ssh-rsa", 7);
	519	PUT_32BIT(bytes+4+7, nbytes);
	520	for (i = 0; i < nbytes; i++)
	521	bytes[4+7+4+i] = bignum_byte(out, nbytes-1-i);
	522	freebn(out);
	523
	524	*siglen = 4+7+4+nbytes;
	525	return bytes;
85cc02bb	526	}
85cc02bb	527
65a22376	528	const struct ssh_signkey ssh_rsa = {
85cc02bb	529	rsa2_newkey,
	530	rsa2_freekey,
	531	rsa2_fmtkey,
65a22376	532	rsa2_public_blob,
	533	rsa2_private_blob,
	534	rsa2_createkey,
45cebe79	535	rsa2_openssh_createkey,
85cc02bb	536	rsa2_fingerprint,
	537	rsa2_verifysig,
	538	rsa2_sign,
	539	"ssh-rsa",
	540	"rsa2"
	541	};