diff options
author | Nicolas Boichat <drinkcat@google.com> | 2016-11-07 15:17:53 +0800 |
---|---|---|
committer | chrome-bot <chrome-bot@chromium.org> | 2016-11-10 21:28:28 -0800 |
commit | ef0f355e476b02dc74d99c25881d77488798e9bc (patch) | |
tree | 06ea1a205e6e2de3d05b35ab75ade26d892f4460 | |
parent | 5edf3f5a8cdd72f5f4c60aaf6acfcb92a9f09053 (diff) | |
download | chrome-ec-ef0f355e476b02dc74d99c25881d77488798e9bc.tar.gz |
common/rsa: Add support for exponent 3 RSA keys
These keys are much quicker to verify (259ms to 51ms on a -M0 at
48 Mhz), so they can be used when timing is critical and
verification needs to be performed on the board.
BRANCH=none
BUG=chromium:663631
TEST=make buildall -j && make run-rsa
TEST=make run-rsa3 (next commit)
Change-Id: I0da4b3e21543bb6f7b18e8b6ddc5e153046a61b8
Reviewed-on: https://chromium-review.googlesource.com/408006
Commit-Ready: Nicolas Boichat <drinkcat@chromium.org>
Tested-by: Nicolas Boichat <drinkcat@chromium.org>
Reviewed-by: Randall Spangler <rspangler@chromium.org>
Reviewed-by: Vincent Palatin <vpalatin@chromium.org>
-rw-r--r-- | common/rsa.c | 49 | ||||
-rw-r--r-- | include/config.h | 3 |
2 files changed, 50 insertions, 2 deletions
diff --git a/common/rsa.c b/common/rsa.c index 5a411cccef..e4e85c3374 100644 --- a/common/rsa.c +++ b/common/rsa.c @@ -69,6 +69,42 @@ static void mont_mul_add(const struct rsa_public_key *key, sub_mod(key, c); } +#ifdef CONFIG_RSA_EXPONENT_3 +/** + * Montgomery c[] += 0 * b[] / R % mod + */ +static void mont_mul_add_0(const struct rsa_public_key *key, + uint32_t *c, + const uint32_t *b) +{ + uint32_t d0 = c[0] * key->n0inv; + uint64_t B = (uint64_t)d0 * key->n[0] + c[0]; + uint32_t i; + + for (i = 1; i < RSANUMWORDS; ++i) { + B = (B >> 32) + (uint64_t)d0 * key->n[i] + c[i]; + c[i - 1] = (uint32_t)B; + } + + c[i - 1] = B >> 32; +} + +/* Montgomery c[] = a[] * 1 / R % key. */ +static void mont_mul_1(const struct rsa_public_key *key, + uint32_t *c, + const uint32_t *a) +{ + int i; + + for (i = 0; i < RSANUMWORDS; ++i) + c[i] = 0; + + mont_mul_add(key, c, 1, a); + for (i = 1; i < RSANUMWORDS; ++i) + mont_mul_add_0(key, c, a); +} +#endif + /** * Montgomery c[] = a[] * b[] / R % mod */ @@ -87,13 +123,14 @@ static void mont_mul(const struct rsa_public_key *key, /** * In-place public exponentiation. + * Exponent depends on the configuration (65537 (default), or 3). * * @param key Key to use in signing * @param inout Input and output big-endian byte array * @param workbuf32 Work buffer; caller must verify this is * 3 x RSANUMWORDS elements long. */ -static void mod_pow_F4(const struct rsa_public_key *key, uint8_t *inout, +static void mod_pow(const struct rsa_public_key *key, uint8_t *inout, uint32_t *workbuf32) { uint32_t *a = workbuf32; @@ -112,12 +149,20 @@ static void mod_pow_F4(const struct rsa_public_key *key, uint8_t *inout, a[i] = tmp; } + /* TODO(drinkcat): This operation could be precomputed to save time. */ mont_mul(key, a_r, a, key->rr); /* a_r = a * RR / R mod M */ +#ifdef CONFIG_RSA_EXPONENT_3 + mont_mul(key, aa_r, a_r, a_r); + mont_mul(key, a, aa_r, a_r); + mont_mul_1(key, aaa, a); +#else + /* Exponent 65537 */ for (i = 0; i < 16; i += 2) { mont_mul(key, aa_r, a_r, a_r); /* aa_r = a_r * a_r / R mod M */ mont_mul(key, a_r, aa_r, aa_r);/* a_r = aa_r * aa_r / R mod M */ } mont_mul(key, aaa, a_r, a); /* aaa = a_r * a / R mod M */ +#endif /* Make sure aaa < mod; aaa is at most 1x mod too large. */ if (ge_mod(key, aaa)) @@ -200,7 +245,7 @@ int rsa_verify(const struct rsa_public_key *key, const uint8_t *signature, /* Copy input to local workspace. */ memcpy(buf, signature, RSANUMBYTES); - mod_pow_F4(key, buf, workbuf32); /* In-place exponentiation. */ + mod_pow(key, buf, workbuf32); /* In-place exponentiation. */ /* Check the PKCS#1 padding */ if (check_padding(buf) != 0) diff --git a/include/config.h b/include/config.h index 3f8637e3f8..aaf575fe7f 100644 --- a/include/config.h +++ b/include/config.h @@ -1664,6 +1664,9 @@ /* Define the RSA key size. */ #undef CONFIG_RSA_KEY_SIZE +/* Use RSA exponent 3 instead of F4 (65537) */ +#undef CONFIG_RSA_EXPONENT_3 + /* * Verify the RW firmware using the RSA signature. * (for accessories without software sync) |