From: mdw <mdw>
Date: Sat, 17 Jun 2000 11:57:56 +0000 (+0000)
Subject: Improve bulk performance by making better use of Montgomery
X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/commitdiff_plain/43429c4bfc5c9036beb3e3a2dad88fa2e33aad46

Improve bulk performance by making better use of Montgomery
multiplication and separating out initialization and finalization from
the main code.
---

diff --git a/rsa-decrypt.c b/rsa-decrypt.c
index 808987c..cbeed03 100644
--- a/rsa-decrypt.c
+++ b/rsa-decrypt.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: rsa-decrypt.c,v 1.1 1999/12/22 15:50:45 mdw Exp $
+ * $Id: rsa-decrypt.c,v 1.2 2000/06/17 11:57:56 mdw Exp $
  *
  * RSA decryption
  *
@@ -30,6 +30,11 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: rsa-decrypt.c,v $
+ * Revision 1.2  2000/06/17 11:57:56  mdw
+ * Improve bulk performance by making better use of Montgomery
+ * multiplication and separating out initialization and finalization from
+ * the main code.
+ *
  * Revision 1.1  1999/12/22 15:50:45  mdw
  * Initial RSA support.
  *
@@ -44,40 +49,87 @@
 
 /*----- Main code ---------------------------------------------------------*/
 
-/* --- @rsa_decrypt@ --- *
+/* --- @rsa_deccreate@ --- *
  *
- * Arguments:	@rsa_param *rp@ = pointer to RSA parameters
+ * Arguments:	@rsa_decctx *rd@ = pointer to an RSA decryption context
+ *		@rsa_priv *rp@ = pointer to RSA private key
+ *		@grand *r@ = pointer to random number source for blinding
+ *
+ * Returns:	---
+ *
+ * Use:		Initializes an RSA decryption context.  Keeping a context
+ *		for several decryption or signing operations provides a minor
+ *		performance benefit.
+ *
+ *		The random number source may be null if blinding is not
+ *		desired.  This improves decryption speed, at the risk of
+ *		permitting timing attacks.
+ */
+
+void rsa_deccreate(rsa_decctx *rd, rsa_param *rp, grand *r)
+{
+  rd->rp = rp;
+  rd->r = r;
+  if (r)
+    mpmont_create(&rd->nm, rp->n);
+  mpmont_create(&rd->pm, rp->p);
+  mpmont_create(&rd->qm, rp->q);
+}
+
+/* --- @rsa_decdestroy@ --- *
+ *
+ * Arguments:	@rsa_decctx *rd@ = pointer to an RSA decryption context
+ *
+ * Returns:	---
+ *
+ * Use:		Destroys an RSA decryption context.
+ */
+
+void rsa_decdestroy(rsa_decctx *rd)
+{
+  if (rd->r)
+    mpmont_destroy(&rd->nm);
+  mpmont_destroy(&rd->pm);
+  mpmont_destroy(&rd->qm);
+}
+
+/* --- @rsa_dec@ --- *
+ *
+ * Arguments:	@rsa_decctx *rd@ = pointer to RSA decryption context
  *		@mp *d@ = destination
  *		@mp *c@ = ciphertext message
- *		@grand *r@ = pointer to random number source for blinding
  *
- * Returns:	Correctly decrypted message.
+ * Returns:	The recovered plaintext message.
  *
- * Use:		Performs RSA decryption, very carefully.
+ * Use:		Performs RSA decryption.  This function takes advantage of
+ *		knowledge of the key factors in order to speed up
+ *		decryption.  It also blinds the ciphertext prior to
+ *		decryption and unblinds it afterwards to thwart timing
+ *		attacks.
  */
 
-mp *rsa_decrypt(rsa_param *rp, mp *d, mp *c, grand *r)
+mp *rsa_dec(rsa_decctx *rd, mp *d, mp *c)
 {
   mp *ki = MP_NEW;
+  rsa_param *rp = rd->rp;
 
   /* --- If so desired, set up a blinding constant --- *
    *
    * Choose a constant %$k$% relatively prime to the modulus %$m$%.  Compute
-   * %$c' = c k^e \bmod n$%, and %$k^{-1} \bmod n$%.
+   * %$c' = c k^e \bmod n$%, and %$k^{-1} \bmod n$%.  Don't bother with the
+   * CRT stuff here because %$e$% is chosen to be small.
    */
 
   c = MP_COPY(c);
-  if (r) {
-    mp *k = MP_NEW, *g = MP_NEW;
-    mpmont mm;
+  if (rd->r) {
+    mp *k = MP_NEWSEC, *g = MP_NEW;
 
     do {
-      k = mprand_range(k, rp->n, r, 0);
+      k = mprand_range(k, rp->n, rd->r, 0);
       mp_gcd(&g, 0, &ki, rp->n, k);
     } while (MP_CMP(g, !=, MP_ONE));
-    mpmont_create(&mm, rp->n);
-    k = mpmont_expr(&mm, k, k, rp->e);
-    c = mpmont_mul(&mm, c, c, k);
+    k = mpmont_expr(&rd->nm, k, k, rp->e);
+    c = mpmont_mul(&rd->nm, c, c, k);
     mp_drop(k);
     mp_drop(g);
   }
@@ -91,28 +143,22 @@ mp *rsa_decrypt(rsa_param *rp, mp *d, mp *c, grand *r)
    */
 
   {
-    mpmont mm;
     mp *cp = MP_NEW, *cq = MP_NEW;
 
     /* --- Work out the two halves of the result --- */
 
     mp_div(0, &cp, c, rp->p);
-    mpmont_create(&mm, rp->p);
-    cp = mpmont_exp(&mm, cp, cp, rp->dp);
-    mpmont_destroy(&mm);
+    cp = mpmont_exp(&rd->pm, cp, cp, rp->dp);
 
     mp_div(0, &cq, c, rp->q);
-    mpmont_create(&mm, rp->q);
-    cq = mpmont_exp(&mm, cq, cq, rp->dq);
-    mpmont_destroy(&mm);
+    cq = mpmont_exp(&rd->qm, cq, cq, rp->dq);
 
     /* --- Combine the halves using the result above --- */
 
     d = mp_sub(d, cp, cq);
-    if (cp->f & MP_NEG)
-      d = mp_add(d, d, rp->p);
-    d = mp_mul(d, d, rp->q_inv);
     mp_div(0, &d, d, rp->p);
+    d = mpmont_mul(&rd->pm, d, d, rp->q_inv);
+    d = mpmont_mul(&rd->pm, d, d, rd->pm.r2);
 
     d = mp_mul(d, d, rp->q);
     d = mp_add(d, d, cq);
@@ -128,8 +174,8 @@ mp *rsa_decrypt(rsa_param *rp, mp *d, mp *c, grand *r)
   /* --- Finally, possibly remove the blinding factor --- */
 
   if (ki) {
-    d = mp_mul(d, d, ki);
-    mp_div(0, &d, d, rp->n);
+    d = mpmont_mul(&rd->nm, d, d, ki);
+    d = mpmont_mul(&rd->nm, d, d, rd->nm.r2);
     mp_drop(ki);
   }
 
@@ -139,4 +185,25 @@ mp *rsa_decrypt(rsa_param *rp, mp *d, mp *c, grand *r)
   return (d);
 }
 
+/* --- @rsa_decrypt@ --- *
+ *
+ * Arguments:	@rsa_param *rp@ = pointer to RSA parameters
+ *		@mp *d@ = destination
+ *		@mp *c@ = ciphertext message
+ *		@grand *r@ = pointer to random number source for blinding
+ *
+ * Returns:	Correctly decrypted message.
+ *
+ * Use:		Performs RSA decryption, very carefully.
+ */
+
+mp *rsa_decrypt(rsa_param *rp, mp *d, mp *c, grand *r)
+{
+  rsa_decctx rd;
+  rsa_deccreate(&rd, rp, r);
+  d = rsa_dec(&rd, d, c);
+  rsa_decdestroy(&rd);
+  return (d);
+}
+
 /*----- That's all, folks -------------------------------------------------*/