First cut at RSA decryption/signature using the Chinese Remainder

Theorem.  Not yet tested, and given the number of moving parts I would
be astonished if this version actually worked, but it does compile.
Added some timing code to tests/test-rsa.c so we can see whether this
is doing anything useful once it does work.

7 files changed, 409 insertions, 16 deletions

diff --git a/Makefile.in b/Makefile.in
index 2e86815..b28cec8 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -29,7 +29,8 @@
 
 INC		= cryptech.h
 LIB		= libcryptech.a
-OBJ		= ${IO_OBJ} csprng.o hash.o aes_keywrap.o pbkdf2.o modexp.o errorstrings.o
+OBJ		= ${IO_OBJ} csprng.o hash.o aes_keywrap.o pbkdf2.o \
+		  modexp.o rsa.o errorstrings.o
 
 IO_OBJ		= ${IO_OBJ_@FPGA_BUS@}
 IO_OBJ_EIM	= hal_io_eim.o novena-eim.o
@@ -38,11 +39,13 @@ IO_OBJ_I2C 	= hal_io_i2c.o
 CC		= @CC@
 CFLAGS		= @CFLAGS@
 LDFLAGS		= @LDFLAGS@
+TFMDIR		= @TFMDIR@
 
 prefix		= @prefix@
 exec_prefix	= @exec_prefix@
 includedir	= @includedir@
 libdir		= @libdir@
+abs_top_builddir= @abs_top_builddir@
 
 all: ${LIB}
 	cd tests; ${MAKE} $@
diff --git a/configure b/configure
index de3ba04..f03cbe3 100755
--- a/configure
+++ b/configure
@@ -583,6 +583,7 @@ PACKAGE_URL=''
 
 ac_subst_vars='LTLIBOBJS
 LIBOBJS
+TFMDIR
 LDFLAGS
 CFLAGS
 CC
@@ -635,7 +636,8 @@ target_alias
 FPGA_BUS
 CC
 CFLAGS
-LDFLAGS'
+LDFLAGS
+TFMDIR'
 
 
 # Initialize some variables set by options.
@@ -1246,6 +1248,7 @@ Some influential environment variables:
   CC          C compiler command
   CFLAGS      C compiler flags
   LDFLAGS     Linker flags
+  TFMDIR      Directory containing libtfm.a and tfm.h
 
 Use these variables to override the choices made by `configure' or to help
 it to find libraries and programs with nonstandard names/locations.
@@ -1684,6 +1687,7 @@ ac_compiler_gnu=$ac_cv_c_compiler_gnu
 
 
 
+
 case $FPGA_BUS in #(
   "") :
     FPGA_BUS=EIM ;; #(
@@ -1695,19 +1699,25 @@ esac
 
 case $CC in #(
   "") :
-    CC="cc" ;; #(
+    CC='cc' ;; #(
   *) :
      ;;
 esac
 case $CFLAGS in #(
   "") :
-    CFLAGS="-g -Wall -fPIC" ;; #(
+    CFLAGS='-g3 -Wall -fPIC -std=c99 -I${TFMDIR}' ;; #(
   *) :
      ;;
 esac
 case $LDFLAGS in #(
   "") :
-    LDFLAGS="-g" ;; #(
+    LDFLAGS='-g3 -L${TFMDIR} -ltfm' ;; #(
+  *) :
+     ;;
+esac
+case $TFMDIR in #(
+  "") :
+    TFMDIR='${abs_top_builddir}/../libtfm' ;; #(
   *) :
      ;;
 esac
@@ -1720,6 +1730,8 @@ $as_echo "$as_me: C compiler: $CC" >&6;}
 $as_echo "$as_me: C compiler flags: $CFLAGS" >&6;}
 { $as_echo "$as_me:${as_lineno-$LINENO}: Linker flags: $LDFLAGS" >&5
 $as_echo "$as_me: Linker flags: $LDFLAGS" >&6;}
+{ $as_echo "$as_me:${as_lineno-$LINENO}: libtfm directory: $TFMDIR" >&5
+$as_echo "$as_me: libtfm directory: $TFMDIR" >&6;}
 
 ac_config_files="$ac_config_files Makefile tests/Makefile"
 
diff --git a/configure.ac b/configure.ac
index d62d460..aecdcc0 100644
--- a/configure.ac
+++ b/configure.ac
@@ -39,22 +39,25 @@
 
 AC_INIT([libcryptech], [0.1])
 
-AC_ARG_VAR([FPGA_BUS],	[Bus architecture to use (currently must be "EIM" or "I2C")])
-AC_ARG_VAR([CC],	[C compiler command])
-AC_ARG_VAR([CFLAGS],	[C compiler flags])
-AC_ARG_VAR([LDFLAGS],	[Linker flags])
+AC_ARG_VAR([FPGA_BUS],  [Bus architecture to use (currently must be "EIM" or "I2C")])
+AC_ARG_VAR([CC],        [C compiler command])
+AC_ARG_VAR([CFLAGS],    [C compiler flags])
+AC_ARG_VAR([LDFLAGS],   [Linker flags])
+AC_ARG_VAR([TFMDIR],    [Directory containing libtfm.a and tfm.h])
 
 AS_CASE($FPGA_BUS, [""],[FPGA_BUS=EIM], [EIM|I2C],[],
-	[AC_MSG_ERROR([Invalid setting of FPGA_BUS, must be "EIM" or "I2C"])])
-	
-AS_CASE($CC,      [""],[CC="cc"],		  [])
-AS_CASE($CFLAGS,  [""],[CFLAGS="-g -Wall -fPIC"], [])
-AS_CASE($LDFLAGS, [""],[LDFLAGS="-g"],		  [])
+        [AC_MSG_ERROR([Invalid setting of FPGA_BUS, must be "EIM" or "I2C"])])
+        
+AS_CASE($CC,      [""],[CC='cc'],                                       [])
+AS_CASE($CFLAGS,  [""],[CFLAGS='-g3 -Wall -fPIC -std=c99 -I${TFMDIR}'], [])
+AS_CASE($LDFLAGS, [""],[LDFLAGS='-g3 -L${TFMDIR} -ltfm'],               [])
+AS_CASE($TFMDIR,  [""],[TFMDIR='${abs_top_builddir}/../libtfm'],        [])
 
 AC_MSG_NOTICE([FPGA bus: $FPGA_BUS])
 AC_MSG_NOTICE([C compiler: $CC])
 AC_MSG_NOTICE([C compiler flags: $CFLAGS])
 AC_MSG_NOTICE([Linker flags: $LDFLAGS])
+AC_MSG_NOTICE([libtfm directory: $TFMDIR])
 
 AC_CONFIG_FILES([Makefile tests/Makefile])
 AC_OUTPUT
diff --git a/cryptech.h b/cryptech.h
index 1ca6a89..6f7d439 100644
--- a/cryptech.h
+++ b/cryptech.h
@@ -442,6 +442,10 @@
   DEFINE_HAL_ERROR(HAL_ERROR_KEYWRAP_BAD_MAGIC,         "Bad magic number while unwrapping key")        \
   DEFINE_HAL_ERROR(HAL_ERROR_KEYWRAP_BAD_LENGTH,        "Length out of range while unwrapping key")     \
   DEFINE_HAL_ERROR(HAL_ERROR_KEYWRAP_BAD_PADDING,       "Non-zero padding detected unwrapping key")     \
+  DEFINE_HAL_ERROR(HAL_ERROR_CRT_FAILED,                "CRT calculation failed")                       \
+  DEFINE_HAL_ERROR(HAL_ERROR_ALLOCATION_FAILURE,        "Memory allocation failed")                     \
+  DEFINE_HAL_ERROR(HAL_ERROR_UNKNOWN_TFM_FAILURE,       "Unknown libtfm failure")                       \
+  DEFINE_HAL_ERROR(HAL_ERROR_RESULT_TOO_LONG,		"Result too long for buffer")			\
   END_OF_HAL_ERROR_LIST
 
 /* Marker to forestall silly line continuation errors */
@@ -595,6 +599,22 @@ extern hal_error_t hal_modexp(const uint8_t * const msg, const size_t msg_len, /
                               uint8_t * result, const size_t result_len);
 
 
+/*
+ * RSA.  This is not the real API (yet), just test functions for debugging.
+ */
+
+extern void hal_rsa_set_debug(const int onoff);
+
+extern hal_error_t hal_rsa_crt(const uint8_t * const m, const size_t m_len,
+                               const uint8_t * const n, const size_t n_len,
+                               const uint8_t * const e, const size_t e_len,
+                               const uint8_t * const d, const size_t d_len,
+                               const uint8_t * const p, const size_t p_len,
+                               const uint8_t * const q, const size_t q_len,
+                               const uint8_t * const u, const size_t u_len,
+                               uint8_t * result, const size_t result_len);
+
+
 
 
 #endif /* _CRYPTECH_H_ */
diff --git a/rsa.c b/rsa.c
new file mode 100644
index 0000000..b61feb4
--- /dev/null
+++ b/rsa.c
@@ -0,0 +1,286 @@
+/*
+ * rsa.c
+ * -----
+ * Basic RSA functions based on Cryptech ModExp core.
+ *
+ * The mix of what we're doing in software vs what we're doing on the
+ * FPGA is a moving target.  Goal for now is to have the bits we need
+ * to do in C be straightforward to review and as simple as possible
+ * (but no simpler).
+ *
+ * Much of the code in this module is based, at least loosely, on Tom
+ * St Denis's libtomcrypt code.  
+ *
+ * Authors: Rob Austein
+ * Copyright (c) 2015, SUNET
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+
+#include "cryptech.h"
+
+/*
+ * Use "Tom's Fast Math" library for our bignum implementation.  This
+ * particular implementation has a couple of nice features:
+ *
+ * - The code is relatively readable, thus reviewable.
+ *
+ * - The bignum representation doesn't use dynamic memory, which
+ *   simplifies things for us.
+ *
+ * The price tag for not using dynamic memory is that libtfm has to be
+ * configured to know about the largest bignum one wants it to be able
+ * to support at compile time.  This should not be a serious problem.
+ */
+
+#include "tfm.h"
+
+/*
+ * Whether we want debug output.
+ */
+
+static int debug = 0;
+
+void hal_rsa_set_debug(const int onoff)
+{
+  debug = onoff;
+}
+
+/*
+ * Check a result, report on failure if debugging, pass failures up
+ * the chain.
+ */
+
+#define check(_expr_)                                                   \
+  do {                                                                  \
+    hal_error_t _err = (_expr_);                                        \
+    if (_err != HAL_OK && debug)                                        \
+      printf("%s failed: %s\n", #_expr_, hal_error_string(_err));       \
+    if (_err != HAL_OK)                                                 \
+      return _err;                                                      \
+  } while (0)
+
+/*
+ * RSA key implementation.  This structure type is private to this
+ * module, anything else that needs to touch one of these just gets a
+ * typed opaque pointer.  We do, however, export the size, so that we
+ * can make memory allocation the caller's problem (well, maybe).
+ */
+
+typedef enum { RSA_PRIVATE, RSA_PUBLIC } rsa_key_type_t;
+
+typedef struct {
+  rsa_key_type_t type;          /* What kind of key this is */
+  fp_int n;                     /* The modulus */
+  fp_int e;                     /* Public exponent */
+  fp_int d;                     /* Private exponent */
+  fp_int p;                     /* 1st prime factor */
+  fp_int q;                     /* 2nd prime factor */
+  fp_int u;                     /* 1/q mod p */
+  fp_int dP;                    /* d mod (p - 1) */
+  fp_int dQ;                    /* d mod (q - 1) */
+} rsa_key_t;
+
+const size_t hal_rsa_key_t_size = sizeof(rsa_key_t);
+
+/*
+ * In the long run we want a full RSA implementation, or enough of one
+ * to cover what we need in PKCS #11.  For the moment, though, the
+ * most urgent thing is to see whether this approach to performing the
+ * CRT calculation works (and is any faster), followed by whether we
+ * can use this approach for key generation.
+ *
+ * So don't worry about whether the following functions are what we
+ * want in the long run, they'll probably evolve as we go.
+ */
+
+#warning Should do RSA blinding, skipping for now
+
+#define lose(_code_)                                    \
+  do { err = _code_; goto fail; } while (0)
+
+#define FP_CHECK(_expr_)                                \
+  do {                                                  \
+    switch (_expr_) {                                   \
+    case FP_OKAY: break;                                \
+    case FP_VAL:  lose(HAL_ERROR_BAD_ARGUMENTS);        \
+    case FP_MEM:  lose(HAL_ERROR_ALLOCATION_FAILURE);   \
+    default:      lose(HAL_ERROR_UNKNOWN_TFM_FAILURE);  \
+    }                                                   \
+  } while (0)
+
+
+/*
+ * Unpack a bignum into a byte array, with length check.
+ */
+
+static hal_error_t unpack_fp(fp_int *bn, uint8_t *buffer, const size_t length)
+{
+  hal_error_t err = HAL_OK;
+
+  assert(bn != NULL && buffer != NULL);
+
+  const size_t bytes = fp_unsigned_bin_size(bn);
+
+  if (bytes > length)
+    lose(HAL_ERROR_RESULT_TOO_LONG);
+
+  memset(buffer, 0, length);
+  fp_to_unsigned_bin(bn, buffer + length - bytes);
+
+ fail:
+  return err;
+}
+
+/*
+ * modexp_fp() is a function I haven't written yet which takes
+ * fp_int values, unwraps them, feeds the numbers into hal_modexp(),
+ * and wraps the result back up as a fp_int.
+ */
+
+/* modexp_fp(&tmp.msg, &key.dP, &key.p, &tmp.m1) */
+
+static hal_error_t modexp_fp(fp_int *msg, fp_int *exp, fp_int *mod, fp_int *res)
+{
+  hal_error_t err = HAL_OK;
+
+  assert(msg != NULL && exp != NULL && mod != NULL && res != NULL);
+
+  uint8_t msgbuf[(fp_unsigned_bin_size(msg) + 3) & ~3];
+  uint8_t expbuf[(fp_unsigned_bin_size(exp) + 3) & ~3];
+  uint8_t modbuf[(fp_unsigned_bin_size(mod) + 3) & ~3];
+
+  if ((err = unpack_fp(msg, msgbuf, sizeof(msgbuf))) != HAL_OK ||
+      (err = unpack_fp(exp, expbuf, sizeof(expbuf))) != HAL_OK ||
+      (err = unpack_fp(mod, modbuf, sizeof(modbuf))) != HAL_OK)
+    goto fail;
+
+  uint8_t resbuf[FP_MAX_SIZE/8];
+
+  if ((err = hal_modexp(msgbuf, sizeof(msgbuf),
+                        expbuf, sizeof(expbuf),
+                        modbuf, sizeof(modbuf),
+                        resbuf, sizeof(resbuf))) != HAL_OK)
+    goto fail;
+
+  fp_read_unsigned_bin(res, resbuf, sizeof(resbuf));
+
+ fail:
+  memset(msgbuf, 0, sizeof(msgbuf));
+  memset(expbuf, 0, sizeof(expbuf));
+  memset(modbuf, 0, sizeof(modbuf));
+  return err;
+}
+
+/*
+ * CRT with the components we have.  PyCrypto doesn't give us dP or
+ * dQ, probably because they're so easy to calculate that it's
+ * (almost) not worth the bother.
+ */
+
+hal_error_t hal_rsa_crt(const uint8_t * const m, const size_t m_len,
+                        const uint8_t * const n, const size_t n_len,
+                        const uint8_t * const e, const size_t e_len,
+                        const uint8_t * const d, const size_t d_len,
+                        const uint8_t * const p, const size_t p_len,
+                        const uint8_t * const q, const size_t q_len,
+                        const uint8_t * const u, const size_t u_len,
+                        uint8_t * result, const size_t result_len)
+{
+  hal_error_t err = HAL_OK;
+  rsa_key_t key;
+  struct { fp_int t, msg, m1, m2; } tmp;
+
+  key.type = RSA_PRIVATE;
+
+#define _(x) do { fp_init(&key.x); fp_read_unsigned_bin(&key.x, (uint8_t *) x, x##_len); } while (0)
+  _(n); _(e); _(d); _(p); _(q); _(u);
+#undef _
+
+  fp_init(&tmp.t);
+  fp_init(&tmp.msg);
+  fp_init(&tmp.m1);
+  fp_init(&tmp.m2);
+
+  /* Calculate dP = d % (p-1) and dQ = d % (q-1) */
+
+  fp_sub_d(&key.p, 1, &tmp.t);
+  FP_CHECK(fp_mod(&key.d, &tmp.t, &key.dP));
+
+  fp_sub_d(&key.q, 1, &tmp.t);
+  FP_CHECK(fp_mod(&key.d, &tmp.t, &key.dQ));
+
+  /* Read message to be signed/decrypted into a bignum */
+
+  fp_read_unsigned_bin(&tmp.msg, (uint8_t *) m, m_len);
+
+  /* OK, try to perform the CRT */
+
+  /* m1 = msg ** dP mod p, m2 = msg ** dQ mod q */
+  if ((err = modexp_fp(&tmp.msg, &key.dP, &key.p, &tmp.m1)) != HAL_OK ||
+      (err = modexp_fp(&tmp.msg, &key.dQ, &key.q, &tmp.m2)) != HAL_OK)
+    goto fail;
+
+  /* t = m1 - m2 */
+  fp_sub(&tmp.m1, &tmp.m2, &tmp.t);
+
+  /* Add zero (mod p) if necessary to get positive result */
+  if (fp_cmp_d(&tmp.t, 0) == FP_LT)
+    fp_add(&tmp.t, &key.p, &tmp.t);
+  if (fp_cmp_d(&tmp.t, 0) == FP_LT)
+    fp_add(&tmp.t, &key.p, &tmp.t);
+  if (fp_cmp_d(&tmp.t, 0) == FP_LT)
+    lose(HAL_ERROR_CRT_FAILED);
+
+  /* t = (t * u mod p) * q + m2 */
+  FP_CHECK(fp_mulmod(&tmp.t, &key.u, &key.p, &tmp.t));
+  fp_mul(&tmp.t, &key.q, &tmp.t);
+  fp_add(&tmp.t, &tmp.m2, &tmp.t);
+
+  /* Have result, write it back to caller */
+  if ((err = unpack_fp(&tmp.t, result, result_len)) != HAL_OK)
+    goto fail;
+
+  /* Done, fall through into cleanup code */
+
+ fail:
+  memset(&key, 0, sizeof(key));
+  memset(&tmp, 0, sizeof(tmp));
+
+  return err;
+}
+
+/*
+ * Local variables:
+ * indent-tabs-mode: nil
+ * End:
+ */
diff --git a/tests/Makefile.in b/tests/Makefile.in
index 757624a..46a3aba 100644
--- a/tests/Makefile.in
+++ b/tests/Makefile.in
@@ -34,6 +34,13 @@ BIN		= test-aes-key-wrap test-hash test-pbkdf2 test-rsa
 CC		= @CC@
 CFLAGS		= @CFLAGS@ -I..
 LDFLAGS		= @LDFLAGS@ ${LIB}
+TFMDIR		= @TFMDIR@
+
+prefix		= @prefix@
+exec_prefix	= @exec_prefix@
+includedir	= @includedir@
+libdir		= @libdir@
+abs_top_builddir= @abs_top_builddir@
 
 all: ${BIN}
 
diff --git a/tests/test-rsa.c b/tests/test-rsa.c
index 150c6eb..51e1009 100644
--- a/tests/test-rsa.c
+++ b/tests/test-rsa.c
@@ -44,6 +44,8 @@
 #include <string.h>
 #include <assert.h>
 
+#include <sys/time.h>
+
 #include "cryptech.h"
 #include "test-rsa.h"
 
@@ -77,13 +79,73 @@ static int test_modexp(const char * const kind,
 }
 
 /*
+ * Run one RSA CRT test.
+ */
+
+static int test_crt(const char * const kind, const rsa_tc_t * const tc)
+{
+  uint8_t result[tc->n.len];
+
+  printf("%s test for %lu-bit RSA key\n", kind, (unsigned long) tc->size);
+
+  if (hal_rsa_crt(tc->m.val, tc->m.len,
+                  tc->n.val, tc->n.len,
+                  tc->e.val, tc->e.len,
+                  tc->d.val, tc->d.len,
+                  tc->p.val, tc->p.len,
+                  tc->q.val, tc->q.len,
+                  tc->u.val, tc->u.len,
+                  result, sizeof(result)) != HAL_OK) {
+    printf("RSA CRT failed\n");
+    return 0;
+  }
+
+  if (memcmp(result, tc->s.val, tc->s.len)) {
+    printf("MISMATCH\n");
+    return 0;
+  }
+
+  printf("OK\n");
+  return 1;
+}
+
+
+#define time_check(_expr_)                      \
+  do {                                          \
+    struct timeval _t1, _t2, _td;               \
+    gettimeofday(&_t1, NULL);                   \
+    int _ok = (_expr_);                         \
+    gettimeofday(&_t2, NULL);                   \
+    _td.tv_sec = _t2.tv_sec - _t1.tv_sec;       \
+    _td.tv_usec = _t2.tv_usec - _t1.tv_usec;    \
+    if (_td.tv_usec < 0) {                      \
+      _td.tv_usec += 1000000;                   \
+      _td.tv_sec  -= 1;                         \
+    }                                           \
+    printf("%lu.%06lu %s\n",                    \
+           (unsigned long) _td.tv_sec,          \
+           (unsigned long) _td.tv_usec,         \
+           _ok ? "OK" : "FAILED");              \
+    if (!_ok)                                   \
+      return 0;                                 \
+  } while (0)
+
+/*
  * Test signature and exponentiation for one RSA keypair.
  */
 
 static int test_rsa(const rsa_tc_t * const tc)
 {
-  return (test_modexp("Signature",    tc, &tc->m, &tc->d, &tc->s) && /* RSA decryption */
-          test_modexp("Verification", tc, &tc->s, &tc->e, &tc->m));  /* RSA encryption */
+  /* RSA encryption */
+  time_check(test_modexp("Verification", tc, &tc->s, &tc->e, &tc->m));
+
+  /* Brute force RSA decryption */
+  time_check(test_modexp("Signature (ModExp)", tc, &tc->m, &tc->d, &tc->s));
+
+  /* RSA decyrption using CRT */
+  time_check(test_crt("Signature (CRT)", tc));
+
+  return 1;
 }
 
 int main(int argc, char *argv[])