/* -*-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
*
/*----- 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.
*
/*----- 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);
}
*/
{
- 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);
/* --- 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);
}
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 -------------------------------------------------*/