From ab5a8760becf4711afa68221a5610e5572686f1f Mon Sep 17 00:00:00 2001 From: Rob Austein Date: Wed, 17 Jun 2015 15:13:27 -0400 Subject: RSA key generation and DER support. --- cryptech.h | 18 ++-- rsa.c | 249 ++++++++++++++++++++++++++++++++++++++++++++++++++++++- tests/test-rsa.c | 87 ++++++++++++++++++- 3 files changed, 344 insertions(+), 10 deletions(-) diff --git a/cryptech.h b/cryptech.h index 392a1b2..6af9ce8 100644 --- a/cryptech.h +++ b/cryptech.h @@ -444,7 +444,8 @@ DEFINE_HAL_ERROR(HAL_ERROR_KEYWRAP_BAD_PADDING, "Non-zero padding detected unwrapping key") \ DEFINE_HAL_ERROR(HAL_ERROR_IMPOSSIBLE, "\"Impossible\" error") \ DEFINE_HAL_ERROR(HAL_ERROR_ALLOCATION_FAILURE, "Memory allocation failed") \ - DEFINE_HAL_ERROR(HAL_ERROR_RESULT_TOO_LONG, "Result too long for buffer") \ + DEFINE_HAL_ERROR(HAL_ERROR_RESULT_TOO_LONG, "Result too long for buffer") \ + DEFINE_HAL_ERROR(HAL_ERROR_ASN1_PARSE_FAILED, "ASN.1 parse failed") \ END_OF_HAL_ERROR_LIST /* Marker to forestall silly line continuation errors */ @@ -631,12 +632,19 @@ extern hal_error_t hal_rsa_crt(hal_rsa_key_t key, const uint8_t * const m, const size_t m_len, uint8_t * result, const size_t result_len); -extern hal_error_t hal_rsa_gen(hal_rsa_key_t *key, - void *keybuf, const size_t keybuf_len, - const unsigned key_length, - const unsigned long public_exponent); +extern hal_error_t hal_rsa_key_gen(hal_rsa_key_t *key, + void *keybuf, const size_t keybuf_len, + const unsigned key_length, + const unsigned long public_exponent); +extern hal_error_t hal_rsa_key_to_der(hal_rsa_key_t key, + uint8_t *der, size_t *der_len, const size_t der_max); + +extern hal_error_t hal_rsa_key_from_der(hal_rsa_key_t *key, + void *keybuf, const size_t keybuf_len, + const uint8_t * const der, const size_t der_len); + #endif /* _CRYPTECH_H_ */ /* diff --git a/rsa.c b/rsa.c index 6c1e12e..ad5cb16 100644 --- a/rsa.c +++ b/rsa.c @@ -343,10 +343,10 @@ static hal_error_t find_prime(unsigned prime_length, fp_int *e, fp_int *result) return HAL_OK; } -hal_error_t hal_rsa_gen(hal_rsa_key_t *key_, - void *keybuf, const size_t keybuf_len, - const unsigned key_length, - const unsigned long public_exponent) +hal_error_t hal_rsa_key_gen(hal_rsa_key_t *key_, + void *keybuf, const size_t keybuf_len, + const unsigned key_length, + const unsigned long public_exponent) { struct rsa_key *key = keybuf; hal_error_t err = HAL_OK; @@ -409,6 +409,247 @@ hal_error_t hal_rsa_gen(hal_rsa_key_t *key_, return err; } +/* + * Minimal ASN.1 encoding and decoding for private keys. This is NOT + * a general-purpose ASN.1 implementation, just enough to read and + * write PKCS #1.5 RSAPrivateKey syntax (RFC 2313 section 7.2). + * + * If at some later date we need a full ASN.1 implementation we'll add + * it as (a) separate library module(s), but for now the goal is just + * to let us serialize private keys for internal use and debugging. + */ + +#define ASN1_INTEGER 0x02 +#define ASN1_SEQUENCE 0x30 + +static size_t count_length(size_t length) +{ + size_t result = 1; + + if (length >= 128) + for (; length > 0; length >>= 8) + result++; + + return result; +} + +static void encode_length(size_t length, size_t length_len, uint8_t *der) +{ + assert(der != NULL && length_len > 0 && length_len < 128); + + if (length < 128) { + assert(length_len == 1); + *der = (uint8_t) length; + } + + else { + *der = 0x80 | (uint8_t) --length_len; + while (length > 0 && length_len > 0) { + der[length_len--] = (uint8_t) (length & 0xFF); + length >>= 8; + } + assert(length == 0 && length_len == 0); + } +} + +static hal_error_t decode_header(const uint8_t tag, + const uint8_t * const der, size_t der_max, + size_t *hlen, size_t *vlen) +{ + assert(der != NULL && hlen != NULL && vlen != NULL); + + if (der_max < 2 || der[0] != tag) + return HAL_ERROR_ASN1_PARSE_FAILED; + + if ((der[1] & 0x80) == 0) { + *hlen = 2; + *vlen = der[1]; + } + + else { + *hlen = 2 + (der[1] & 0x7F); + *vlen = 0; + + if (*hlen > der_max) + return HAL_ERROR_ASN1_PARSE_FAILED; + + for (size_t i = 2; i < *hlen; i++) + *vlen = (*vlen << 8) + der[i]; + } + + if (*hlen + *vlen > der_max) + return HAL_ERROR_ASN1_PARSE_FAILED; + + return HAL_OK; +} + +static hal_error_t encode_integer(fp_int *bn, + uint8_t *der, size_t *der_len, const size_t der_max) +{ + if (bn == NULL || der_len == NULL) + return HAL_ERROR_BAD_ARGUMENTS; + + /* + * Calculate length. Need to pad data with a leading zero if most + * significant bit is set, to avoid flipping ASN.1 sign bit. If + * caller didn't supply a buffer, just return the total length. + */ + + const int cmp = fp_cmp_d(bn, 0); + + if (cmp != FP_EQ && cmp != FP_GT) + return HAL_ERROR_BAD_ARGUMENTS; + + const int leading_zero = (cmp == FP_EQ || (fp_count_bits(bn) & 7) == 0); + const size_t data_len = fp_unsigned_bin_size(bn) + leading_zero; + const size_t tag_len = 1; + const size_t length_len = count_length(data_len); + const size_t total_len = tag_len + length_len + data_len; + + *der_len = total_len; + + if (der == NULL) + return HAL_OK; + + if (total_len > der_max) + return HAL_ERROR_RESULT_TOO_LONG; + + /* + * Now encode. + */ + + *der++ = ASN1_INTEGER; + encode_length(data_len, length_len, der); + der += length_len; + if (leading_zero) + *der++ = 0x00; + fp_to_unsigned_bin(bn, der); + + return HAL_OK; +} + +static hal_error_t decode_integer(fp_int *bn, + const uint8_t * const der, size_t *der_len, const size_t der_max) +{ + if (bn == NULL || der == NULL) + return HAL_ERROR_BAD_ARGUMENTS; + + hal_error_t err; + size_t hlen, vlen; + + if ((err = decode_header(ASN1_INTEGER, der, der_max, &hlen, &vlen)) != HAL_OK) + return err; + + if (der_len != NULL) + *der_len = hlen + vlen; + + if (vlen < 1) + return HAL_ERROR_ASN1_PARSE_FAILED; + + fp_init(bn); + fp_read_unsigned_bin(bn, (uint8_t *) der + hlen, vlen); + return HAL_OK; +} + +/* + * RSAPrivateKey fields in the required order. + */ + +#define RSAPrivateKey_fields \ + _(&version); \ + _(&key->n); \ + _(&key->e); \ + _(&key->d); \ + _(&key->p); \ + _(&key->q); \ + _(&key->dP); \ + _(&key->dQ); \ + _(&key->u); + + +hal_error_t hal_rsa_key_to_der(hal_rsa_key_t key_, + uint8_t *der, size_t *der_len, const size_t der_max) +{ + struct rsa_key *key = key_.key; + hal_error_t err = HAL_OK; + + if (key == NULL || der_len == NULL || key->type != HAL_RSA_PRIVATE) + return HAL_ERROR_BAD_ARGUMENTS; + + fp_int version; + fp_zero(&version); + + /* + * Calculate length. + */ + + size_t data_len = 0; + +#define _(x) { size_t i; if ((err = encode_integer(x, NULL, &i, der_max - data_len)) != HAL_OK) return err; data_len += i; } + RSAPrivateKey_fields; +#undef _ + + const size_t tag_len = 1; + const size_t length_len = count_length(data_len); + const size_t total_len = tag_len + length_len + data_len; + + *der_len = total_len; + + if (der == NULL) + return HAL_OK; + + if (total_len > der_max) + return HAL_ERROR_RESULT_TOO_LONG; + + /* + * Now encode. + */ + + *der++ = ASN1_SEQUENCE; + encode_length(data_len, length_len, der); + der += length_len; + +#define _(x) { size_t i; if ((err = encode_integer(x, der, &i, data_len)) != HAL_OK) return err; der += i; data_len -= i; } + RSAPrivateKey_fields; +#undef _ + + return HAL_OK; +} + +hal_error_t hal_rsa_key_from_der(hal_rsa_key_t *key_, + void *keybuf, const size_t keybuf_len, + const uint8_t *der, const size_t der_len) +{ + if (key_ == NULL || keybuf == NULL || keybuf_len < sizeof(struct rsa_key) || der == NULL) + return HAL_ERROR_BAD_ARGUMENTS; + + memset(keybuf, 0, keybuf_len); + + struct rsa_key *key = keybuf; + + key->type = HAL_RSA_PRIVATE; + + hal_error_t err = HAL_OK; + size_t hlen, vlen; + + if ((err = decode_header(ASN1_SEQUENCE, der, der_len, &hlen, &vlen)) != HAL_OK) + return err; + + der += hlen; + + fp_int version; + fp_init(&version); + +#define _(x) { size_t i; if ((err = decode_integer(x, der, &i, vlen)) != HAL_OK) return err; der += i; vlen -= i; } + RSAPrivateKey_fields; +#undef _ + + if (fp_cmp_d(&version, 0) != FP_EQ) + return HAL_ERROR_ASN1_PARSE_FAILED; + + return HAL_OK; +} + /* * Local variables: * indent-tabs-mode: nil diff --git a/tests/test-rsa.c b/tests/test-rsa.c index 707cbe9..814541c 100644 --- a/tests/test-rsa.c +++ b/tests/test-rsa.c @@ -43,6 +43,7 @@ #include #include #include +#include #include @@ -118,6 +119,85 @@ static int test_crt(const char * const kind, const rsa_tc_t * const tc) return err == HAL_OK && !mismatch; } +/* + * Run one RSA key generation + CRT test. + */ + +static int test_gen(const char * const kind, const rsa_tc_t * const tc) +{ + printf("%s test for %lu-bit RSA key\n", kind, (unsigned long) tc->size); + + char fn[sizeof("test-rsa-key-xxxxxx.der")]; + uint8_t keybuf[hal_rsa_key_t_size]; + hal_error_t err = HAL_OK; + hal_rsa_key_t key; + FILE *f; + + if ((err = hal_rsa_key_gen(&key, keybuf, sizeof(keybuf), bitsToBytes(tc->size), 0x010001)) != HAL_OK) { + printf("RSA key generation failed: %s\n", hal_error_string(err)); + return 0; + } + + size_t der_len = 0; + + if ((err = hal_rsa_key_to_der(key, NULL, &der_len, 0)) != HAL_OK) { + printf("Getting DER length of RSA key failed: %s\n", hal_error_string(err)); + return 0; + } + + uint8_t der[der_len]; + + if ((err = hal_rsa_key_to_der(key, der, &der_len, sizeof(der))) != HAL_OK) { + printf("Converting RSA key to DER failed: %s\n", hal_error_string(err)); + return 0; + } + + snprintf(fn, sizeof(fn), "test-rsa-key-%04lu.der", (unsigned long) tc->size); + printf("Writing %s\n", fn); + + if ((f = fopen(fn, "wb")) == NULL) { + printf("Couldn't open %s: %s\n", fn, strerror(errno)); + return 0; + } + + if (fwrite(der, der_len, 1, f) != der_len) { + printf("Length mismatch writing %s\n", fn); + return 0; + } + + if (fclose(f) == EOF) { + printf("Couldn't close %s: %s\n", fn, strerror(errno)); + return 0; + } + + uint8_t result[tc->n.len]; + + if ((err = hal_rsa_crt(key, tc->m.val, tc->m.len, result, sizeof(result))) != HAL_OK) + printf("RSA CRT failed: %s\n", hal_error_string(err)); + + snprintf(fn, sizeof(fn), "test-rsa-sig-%04lu.der", (unsigned long) tc->size); + printf("Writing %s\n", fn); + + if ((f = fopen(fn, "wb")) == NULL) { + printf("Couldn't open %s: %s\n", fn, strerror(errno)); + return 0; + } + + if (fwrite(result, sizeof(result), 1, f) != sizeof(result)) { + printf("Length mismatch writing %s key\n", fn); + return 0; + } + + if (fclose(f) == EOF) { + printf("Couldn't close %s: %s\n", fn, strerror(errno)); + return 0; + } + + hal_rsa_key_clear(key); + + return err == HAL_OK; +} + /* * Time a test. */ @@ -148,7 +228,9 @@ static void _time_check(const struct timeval t0, const int ok) } while (0) /* - * Test signature and exponentiation for one RSA keypair. + * Test signature and exponentiation for one RSA keypair using + * precompiled test vectors, then generate a key of the same length + * and try generating a signature with that. */ static int test_rsa(const rsa_tc_t * const tc) @@ -164,6 +246,9 @@ static int test_rsa(const rsa_tc_t * const tc) /* RSA decyrption using CRT */ time_check(test_crt("Signature (CRT)", tc)); + /* Key generation and CRT -- not test vector, so writes key and sig to file */ + time_check(test_gen("Generation and CRT", tc)); + return ok; } -- cgit v1.2.3