aboutsummaryrefslogtreecommitdiff
path: root/rsa.c
diff options
context:
space:
mode:
Diffstat (limited to 'rsa.c')
-rw-r--r--rsa.c147
1 files changed, 102 insertions, 45 deletions
diff --git a/rsa.c b/rsa.c
index 01d8290..1b5de7d 100644
--- a/rsa.c
+++ b/rsa.c
@@ -12,7 +12,7 @@
* St Denis's libtomcrypt code.
*
* Authors: Rob Austein
- * Copyright (c) 2015, NORDUnet A/S
+ * Copyright (c) 2015-2018, NORDUnet A/S
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
@@ -102,6 +102,15 @@
#endif
/*
+ * How big to make the blinding factors cache.
+ * Zero disables the cache entirely.
+ */
+
+#ifndef HAL_RSA_BLINDING_CACHE_SIZE
+#define HAL_RSA_BLINDING_CACHE_SIZE 2
+#endif
+
+/*
* Whether we want debug output.
*/
@@ -123,6 +132,20 @@ void hal_rsa_set_blinding(const int onoff)
blinding = onoff;
}
+#if HAL_RSA_BLINDING_CACHE_SIZE > 0
+
+typedef struct {
+ unsigned lru;
+ fp_int n[1], bf[1], ubf[1];
+} bfc_slot_t;
+
+static struct {
+ unsigned lru;
+ bfc_slot_t slot[HAL_RSA_BLINDING_CACHE_SIZE];
+} bfc;
+
+#endif
+
/*
* RSA key implementation. This structure type is private to this
* module, anything else that needs to touch one of these just gets a
@@ -215,7 +238,7 @@ static hal_error_t modexp(hal_core_t *core,
const fp_int * const msg,
const fp_int * const exp,
const fp_int * const mod,
- fp_int *res,
+ fp_int * res,
uint8_t *coeff, const size_t coeff_len,
uint8_t *mont, const size_t mont_len)
{
@@ -225,29 +248,29 @@ static hal_error_t modexp(hal_core_t *core,
return HAL_ERROR_IMPOSSIBLE;
const size_t msg_len = (fp_unsigned_bin_size(unconst_fp_int(msg)) + 3) & ~3;
- const size_t exp_len = (fp_unsigned_bin_size(unconst_fp_int(exp)) + 3) & ~3;
- const size_t mod_len = (fp_unsigned_bin_size(unconst_fp_int(mod)) + 3) & ~3;
+ const size_t exp_len = (fp_unsigned_bin_size(unconst_fp_int(exp)) + 3) & ~3;
+ const size_t mod_len = (fp_unsigned_bin_size(unconst_fp_int(mod)) + 3) & ~3;
uint8_t msgbuf[msg_len];
uint8_t expbuf[exp_len];
uint8_t modbuf[mod_len];
uint8_t resbuf[mod_len];
- hal_modexp_arg_t args = {
- .core = core,
- .msg = msgbuf, .msg_len = sizeof(msgbuf),
- .exp = expbuf, .exp_len = sizeof(expbuf),
- .mod = modbuf, .mod_len = sizeof(modbuf),
- .result = resbuf, .result_len = sizeof(resbuf),
- .coeff = coeff, .coeff_len = coeff_len,
- .mont = mont, .mont_len = mont_len
- };
+ hal_modexp_arg_t args = {
+ .core = core,
+ .msg = msgbuf, .msg_len = sizeof(msgbuf),
+ .exp = expbuf, .exp_len = sizeof(expbuf),
+ .mod = modbuf, .mod_len = sizeof(modbuf),
+ .result = resbuf, .result_len = sizeof(resbuf),
+ .coeff = coeff, .coeff_len = coeff_len,
+ .mont = mont, .mont_len = mont_len
+ };
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 ||
(err = hal_modexp(precalc, &args)) != HAL_OK)
- goto fail;
+ goto fail;
fp_read_unsigned_bin(res, resbuf, sizeof(resbuf));
@@ -283,34 +306,34 @@ static hal_error_t modexp2(const int precalc,
return HAL_ERROR_IMPOSSIBLE;
const size_t msg_len = (fp_unsigned_bin_size(unconst_fp_int(msg)) + 3) & ~3;
- const size_t exp1_len = (fp_unsigned_bin_size(unconst_fp_int(exp1)) + 3) & ~3;
- const size_t mod1_len = (fp_unsigned_bin_size(unconst_fp_int(mod1)) + 3) & ~3;
- const size_t exp2_len = (fp_unsigned_bin_size(unconst_fp_int(exp2)) + 3) & ~3;
- const size_t mod2_len = (fp_unsigned_bin_size(unconst_fp_int(mod2)) + 3) & ~3;
+ const size_t exp1_len = (fp_unsigned_bin_size(unconst_fp_int(exp1)) + 3) & ~3;
+ const size_t mod1_len = (fp_unsigned_bin_size(unconst_fp_int(mod1)) + 3) & ~3;
+ const size_t exp2_len = (fp_unsigned_bin_size(unconst_fp_int(exp2)) + 3) & ~3;
+ const size_t mod2_len = (fp_unsigned_bin_size(unconst_fp_int(mod2)) + 3) & ~3;
uint8_t msgbuf[msg_len];
uint8_t expbuf1[exp1_len], modbuf1[mod1_len], resbuf1[mod1_len];
uint8_t expbuf2[exp2_len], modbuf2[mod2_len], resbuf2[mod2_len];
- hal_modexp_arg_t args1 = {
- .core = core1,
- .msg = msgbuf, .msg_len = sizeof(msgbuf),
- .exp = expbuf1, .exp_len = sizeof(expbuf1),
- .mod = modbuf1, .mod_len = sizeof(modbuf1),
- .result = resbuf1, .result_len = sizeof(resbuf1),
- .coeff = coeff1, .coeff_len = coeff1_len,
- .mont = mont1, .mont_len = mont1_len
- };
-
- hal_modexp_arg_t args2 = {
- .core = core2,
- .msg = msgbuf, .msg_len = sizeof(msgbuf),
- .exp = expbuf2, .exp_len = sizeof(expbuf2),
- .mod = modbuf2, .mod_len = sizeof(modbuf2),
- .result = resbuf2, .result_len = sizeof(resbuf2),
- .coeff = coeff2, .coeff_len = coeff2_len,
- .mont = mont2, .mont_len = mont2_len
- };
+ hal_modexp_arg_t args1 = {
+ .core = core1,
+ .msg = msgbuf, .msg_len = sizeof(msgbuf),
+ .exp = expbuf1, .exp_len = sizeof(expbuf1),
+ .mod = modbuf1, .mod_len = sizeof(modbuf1),
+ .result = resbuf1, .result_len = sizeof(resbuf1),
+ .coeff = coeff1, .coeff_len = coeff1_len,
+ .mont = mont1, .mont_len = mont1_len
+ };
+
+ hal_modexp_arg_t args2 = {
+ .core = core2,
+ .msg = msgbuf, .msg_len = sizeof(msgbuf),
+ .exp = expbuf2, .exp_len = sizeof(expbuf2),
+ .mod = modbuf2, .mod_len = sizeof(modbuf2),
+ .result = resbuf2, .result_len = sizeof(resbuf2),
+ .coeff = coeff2, .coeff_len = coeff2_len,
+ .mont = mont2, .mont_len = mont2_len
+ };
if ((err = unpack_fp(msg, msgbuf, sizeof(msgbuf))) != HAL_OK ||
(err = unpack_fp(exp1, expbuf1, sizeof(expbuf1))) != HAL_OK ||
@@ -318,7 +341,7 @@ static hal_error_t modexp2(const int precalc,
(err = unpack_fp(exp2, expbuf2, sizeof(expbuf2))) != HAL_OK ||
(err = unpack_fp(mod2, modbuf2, sizeof(modbuf2))) != HAL_OK ||
(err = hal_modexp2(precalc, &args1, &args2)) != HAL_OK)
- goto fail;
+ goto fail;
fp_read_unsigned_bin(res1, resbuf1, sizeof(resbuf1));
fp_read_unsigned_bin(res2, resbuf2, sizeof(resbuf2));
@@ -415,12 +438,10 @@ int fp_exptmod(fp_int *a, fp_int *b, fp_int *c, fp_int *d)
#endif /* HAL_RSA_SIGN_USE_MODEXP && HAL_RSA_KEYGEN_USE_MODEXP */
/*
- * Create blinding factors. There are various schemes for amortizing
- * the cost of this over multiple RSA operations, at present we don't
- * try. Come back to this if it looks like a bottleneck.
+ * Create blinding factors.
*/
-static hal_error_t create_blinding_factors(hal_core_t *core, hal_rsa_key_t *key, fp_int *bf, fp_int *ubf)
+static hal_error_t create_blinding_factors(hal_rsa_key_t *key, fp_int *bf, fp_int *ubf)
{
if (key == NULL || bf == NULL || ubf == NULL)
return HAL_ERROR_IMPOSSIBLE;
@@ -429,14 +450,39 @@ static hal_error_t create_blinding_factors(hal_core_t *core, hal_rsa_key_t *key,
uint8_t rnd[fp_unsigned_bin_size(unconst_fp_int(key->n))];
hal_error_t err = HAL_OK;
+ hal_rsa_bf_lock();
+
+#if HAL_RSA_BLINDING_CACHE_SIZE > 0
+ unsigned best_delta = 0;
+ int best_index = 0;
+
+ for (int i = 0; i < HAL_RSA_BLINDING_CACHE_SIZE; i++) {
+ bfc_slot_t *b = &bfc.slot[i];
+ const unsigned delta = bfc.lru - b->lru;
+ if (delta > best_delta) {
+ best_delta = delta;
+ best_index = i;
+ }
+ if (fp_cmp_mag(b->n, key->n) == FP_EQ) {
+ if (fp_sqrmod(b->bf, key->n, b->bf) != FP_OKAY ||
+ fp_sqrmod(b->ubf, key->n, b->ubf) != FP_OKAY)
+ continue; /* should never happen, but be safe */
+ fp_copy(b->bf, bf);
+ fp_copy(b->ubf, ubf);
+ err = HAL_OK;
+ goto fail;
+ }
+ }
+#endif
+
if ((err = hal_get_random(NULL, rnd, sizeof(rnd))) != HAL_OK)
goto fail;
fp_init(bf);
- fp_read_unsigned_bin(bf, rnd, sizeof(rnd));
+ fp_read_unsigned_bin(bf, rnd, sizeof(rnd));
fp_copy(bf, ubf);
- if ((err = modexp(core, precalc, bf, key->e, key->n, bf,
+ if ((err = modexp(NULL, precalc, bf, key->e, key->n, bf,
key->nC, sizeof(key->nC), key->nF, sizeof(key->nF))) != HAL_OK)
goto fail;
@@ -445,7 +491,18 @@ static hal_error_t create_blinding_factors(hal_core_t *core, hal_rsa_key_t *key,
FP_CHECK(fp_invmod(ubf, unconst_fp_int(key->n), ubf));
+#if HAL_RSA_BLINDING_CACHE_SIZE > 0
+ {
+ bfc_slot_t *b = &bfc.slot[best_index];
+ fp_copy(key->n, b->n);
+ fp_copy(bf, b->bf);
+ fp_copy(ubf, b->ubf);
+ b->lru = ++bfc.lru;
+ }
+#endif
+
fail:
+ hal_rsa_bf_unlock();
memset(rnd, 0, sizeof(rnd));
return err;
}
@@ -471,7 +528,7 @@ static hal_error_t rsa_crt(hal_core_t *core1, hal_core_t *core2, hal_rsa_key_t *
* Handle blinding if requested.
*/
if (blinding) {
- if ((err = create_blinding_factors(core1, key, bf, ubf)) != HAL_OK)
+ if ((err = create_blinding_factors(key, bf, ubf)) != HAL_OK)
goto fail;
FP_CHECK(fp_mulmod(msg, bf, unconst_fp_int(key->n), msg));
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-19 22:26:26 +0000