aboutsummaryrefslogtreecommitdiff
path: root/rsa.c
diff options
context:
space:
mode:
Diffstat (limited to 'rsa.c')
-rw-r--r--rsa.c286
1 files changed, 286 insertions, 0 deletions
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:
+ */