RSA key generation and DER support.

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;
@@ -410,6 +410,247 @@ hal_error_t hal_rsa_gen(hal_rsa_key_t *key_,
 }
 
 /*
+ * 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
  * End:
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 <stdlib.h>
 #include <string.h>
 #include <assert.h>
+#include <errno.h>
 
 #include <sys/time.h>
 
@@ -119,6 +120,85 @@ static int test_crt(const char * const kind, const rsa_tc_t * const tc)
 }
 
 /*
+ * 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;
 }