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>

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)