From 791af0ba537a9d4906653df76c122188df9b7f97 Mon Sep 17 00:00:00 2001
From: Mark Wooding <mdw@distorted.org.uk>
Date: Thu, 11 May 2017 10:42:15 +0100
Subject: [PATCH] pub/rsa-pub.c: Implement the optimal addition chains for e =
 3, e = 65537.

Also add tests for e = 3 (previously missing) and e = 17 (to exercise
the general modexp path).
---
 pub/rsa-pub.c | 27 ++++++++++++++++++++++++++-
 pub/t/rsa     | 24 ++++++++++++++++++++++++
 2 files changed, 50 insertions(+), 1 deletion(-)

diff --git a/pub/rsa-pub.c b/pub/rsa-pub.c
index 78793a92..5e13182d 100644
--- a/pub/rsa-pub.c
+++ b/pub/rsa-pub.c
@@ -48,7 +48,7 @@
 
 void rsa_pubcreate(rsa_pubctx *rd, rsa_pub *rp)
 {
-  rd->rp = rp;
+  rd->rp = rp; mp_shrink(rp->e);
   mpmont_create(&rd->mm, rp->n);
 }
 
@@ -79,6 +79,31 @@ void rsa_pubdestroy(rsa_pubctx *rd)
 
 mp *rsa_pubop(rsa_pubctx *rd, mp *d, mp *p)
 {
+  mp *e = rd->rp->e;
+  unsigned i;
+
+  if (MP_EQ(e, MP_THREE)) {
+    MP_COPY(p);
+    d = mpmont_mul(&rd->mm, d, p, rd->mm.r2);
+    d = mp_sqr(d, d); d = mpmont_reduce(&rd->mm, d, d);
+    d = mpmont_mul(&rd->mm, d, d, p);
+    MP_DROP(p);
+    return (d);
+  }
+#if MPW_BITS > 16
+  if (MP_LEN(e) == 1 && e->v[0] == 65537)
+#else
+  if (0 && MP_LEN(e) == 2 && e->v[0] == 1 && e->v[1] == (1 << (16 - MPW_BITS)))
+#endif
+  {
+    MP_COPY(p);
+    d = mpmont_mul(&rd->mm, d, p, rd->mm.r2);
+    for (i = 0; i < 16; i++)
+      { d = mp_sqr(d, d); d = mpmont_reduce(&rd->mm, d, d); }
+    d = mpmont_mul(&rd->mm, d, d, p);
+    MP_DROP(p);
+    return (d);
+  }
   return (mpmont_exp(&rd->mm, d, p, rd->rp->e));
 }
 
diff --git a/pub/t/rsa b/pub/t/rsa
index 2b2b27ae..deae87cc 100644
--- a/pub/t/rsa
+++ b/pub/t/rsa
@@ -18,6 +18,20 @@ p1sig-priv {
     0xc484642d0e4dc4a4424d22410456dbdd9275b5c157d6974a66bee9aa02501c26
     "cc22cc";
 
+  0xccbd3b508e1ac2ed16f0f85adfec8d17ad525018307e613e0ee3aa4652b7ceb3
+    17
+    0x786f50114488366d58c9fb80bff48f3a0cbd69a83e790ca4bc74e2a660f0b891
+    "616263" 0
+    0x26c39c4e2f0ddbeb3d17aa0403d2645d4c6ac65c226f7eaa74c467020762b247
+    "cc22cc";
+
+  0xac5d73713fff7f91fbe0908ff3062849a1c1becfcb8e40cd01b7323294d1fd41
+    3
+    0x72e8f7a0d554ffb6a7eb0b0aa2041adaa90b6d958c0365ac050b54b3708c113
+    "616263" 0
+    0x725d28894df5a54819fa55b4fac34653648d88a14cccefe83c2f6d6238b9abee
+    "cc22cc";
+
   0xb6dd0145ada7547bba5db3a35d34e612a8d73e93c33c720f4e4506428cacc6861b2143ed3a0683394fd94cfab8ab66a024161e9c9c1848d50627b3ac46de6d1b1d73ae7b5540b3df65c53aed9d4bdf1f86c8ddacfaf608823bb3d307d89d4c8bb11b5198f9851a519538787cd054ced98734daa2f7f2dc5b51c8c02ea8c362ff
     0x10001
     0xbee578ae84da6a17c0369191b97bbfb33b0f7904488c9185e8efa5d953820abd7515051461beeabea9dcefbfcd8921598c528b2272d1e7367b7676db222091443944672d439fe4cc75f4f9f0594a0b19a8c634fc7f88d0f16e08ec9a95f1f0c3c03ad467a2d7db37428c145cd26b8796264de2f2209a3c09f54fa51de689b81
@@ -55,6 +69,16 @@ p1vrf-pub {
     0xc484642d0e4dc4a4424d22410456dbdd9275b5c157d6974a66bee9aa02501c26
     "" 3 "616263" "cc22cc";
   0xccbd3b508e1ac2ed16f0f85adfec8d17ad525018307e613e0ee3aa4652b7ceb3
+    17
+    0x26c39c4e2f0ddbeb3d17aa0403d2645d4c6ac65c226f7eaa74c467020762b247
+    "" 3 "616263" "cc22cc";
+
+  0xac5d73713fff7f91fbe0908ff3062849a1c1becfcb8e40cd01b7323294d1fd41
+    3
+    0x725d28894df5a54819fa55b4fac34653648d88a14cccefe83c2f6d6238b9abee
+    "" 3 "616263" "cc22cc";
+
+  0xccbd3b508e1ac2ed16f0f85adfec8d17ad525018307e613e0ee3aa4652b7ceb3
     0x10001
     0xc484642d0e4dc4a4424d22410456dbdd9275b5c157d6974a66bee9aa02501c26
     "616263" 0 "" "cc22cc";
-- 
2.11.0