git.distorted.org.uk Git - u/mdw/catacomb/blob - rsa-decrypt.c

   1 /* -*-c-*-
   2  *
   3  * $Id: rsa-decrypt.c,v 1.2 2000/06/17 11:57:56 mdw Exp $
   4  *
   5  * RSA decryption
   6  *
   7  * (c) 1999 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: rsa-decrypt.c,v $
  33  * Revision 1.2  2000/06/17 11:57:56  mdw
  34  * Improve bulk performance by making better use of Montgomery
  35  * multiplication and separating out initialization and finalization from
  36  * the main code.
  37  *
  38  * Revision 1.1  1999/12/22 15:50:45  mdw
  39  * Initial RSA support.
  40  *
  41  */
  42
  43 /*----- Header files ------------------------------------------------------*/
  44
  45 #include "mp.h"
  46 #include "mpmont.h"
  47 #include "mprand.h"
  48 #include "rsa.h"
  49
  50 /*----- Main code ---------------------------------------------------------*/
  51
  52 /* --- @rsa_deccreate@ --- *
  53  *
  54  * Arguments:   @rsa_decctx *rd@ = pointer to an RSA decryption context
  55  *              @rsa_priv *rp@ = pointer to RSA private key
  56  *              @grand *r@ = pointer to random number source for blinding
  57  *
  58  * Returns:     ---
  59  *
  60  * Use:         Initializes an RSA decryption context.  Keeping a context
  61  *              for several decryption or signing operations provides a minor
  62  *              performance benefit.
  63  *
  64  *              The random number source may be null if blinding is not
  65  *              desired.  This improves decryption speed, at the risk of
  66  *              permitting timing attacks.
  67  */
  68
  69 void rsa_deccreate(rsa_decctx *rd, rsa_param *rp, grand *r)
  70 {
  71   rd->rp = rp;
  72   rd->r = r;
  73   if (r)
  74     mpmont_create(&rd->nm, rp->n);
  75   mpmont_create(&rd->pm, rp->p);
  76   mpmont_create(&rd->qm, rp->q);
  77 }
  78
  79 /* --- @rsa_decdestroy@ --- *
  80  *
  81  * Arguments:   @rsa_decctx *rd@ = pointer to an RSA decryption context
  82  *
  83  * Returns:     ---
  84  *
  85  * Use:         Destroys an RSA decryption context.
  86  */
  87
  88 void rsa_decdestroy(rsa_decctx *rd)
  89 {
  90   if (rd->r)
  91     mpmont_destroy(&rd->nm);
  92   mpmont_destroy(&rd->pm);
  93   mpmont_destroy(&rd->qm);
  94 }
  95
  96 /* --- @rsa_dec@ --- *
  97  *
  98  * Arguments:   @rsa_decctx *rd@ = pointer to RSA decryption context
  99  *              @mp *d@ = destination
 100  *              @mp *c@ = ciphertext message
 101  *
 102  * Returns:     The recovered plaintext message.
 103  *
 104  * Use:         Performs RSA decryption.  This function takes advantage of
 105  *              knowledge of the key factors in order to speed up
 106  *              decryption.  It also blinds the ciphertext prior to
 107  *              decryption and unblinds it afterwards to thwart timing
 108  *              attacks.
 109  */
 110
 111 mp *rsa_dec(rsa_decctx *rd, mp *d, mp *c)
 112 {
 113   mp *ki = MP_NEW;
 114   rsa_param *rp = rd->rp;
 115
 116   /* --- If so desired, set up a blinding constant --- *
 117    *
 118    * Choose a constant %$k$% relatively prime to the modulus %$m$%.  Compute
 119    * %$c' = c k^e \bmod n$%, and %$k^{-1} \bmod n$%.  Don't bother with the
 120    * CRT stuff here because %$e$% is chosen to be small.
 121    */
 122
 123   c = MP_COPY(c);
 124   if (rd->r) {
 125     mp *k = MP_NEWSEC, *g = MP_NEW;
 126
 127     do {
 128       k = mprand_range(k, rp->n, rd->r, 0);
 129       mp_gcd(&g, 0, &ki, rp->n, k);
 130     } while (MP_CMP(g, !=, MP_ONE));
 131     k = mpmont_expr(&rd->nm, k, k, rp->e);
 132     c = mpmont_mul(&rd->nm, c, c, k);
 133     mp_drop(k);
 134     mp_drop(g);
 135   }
 136
 137   /* --- Do the actual modular exponentiation --- *
 138    *
 139    * Use a slightly hacked version of the Chinese Remainder Theorem stuff.
 140    *
 141    * Let %$q' = q^{-1} \bmod p$%.  Then note that
 142    * %$c^d \equiv q (q'(c_p^{d_p} - c_q^{d_q}) \bmod p) + c_q^{d_q} \pmod n$%
 143    */
 144
 145   {
 146     mp *cp = MP_NEW, *cq = MP_NEW;
 147
 148     /* --- Work out the two halves of the result --- */
 149
 150     mp_div(0, &cp, c, rp->p);
 151     cp = mpmont_exp(&rd->pm, cp, cp, rp->dp);
 152
 153     mp_div(0, &cq, c, rp->q);
 154     cq = mpmont_exp(&rd->qm, cq, cq, rp->dq);
 155
 156     /* --- Combine the halves using the result above --- */
 157
 158     d = mp_sub(d, cp, cq);
 159     mp_div(0, &d, d, rp->p);
 160     d = mpmont_mul(&rd->pm, d, d, rp->q_inv);
 161     d = mpmont_mul(&rd->pm, d, d, rd->pm.r2);
 162
 163     d = mp_mul(d, d, rp->q);
 164     d = mp_add(d, d, cq);
 165     if (MP_CMP(d, >=, rp->n))
 166       d = mp_sub(d, d, rp->n);
 167
 168     /* --- Tidy away temporary variables --- */
 169
 170     mp_drop(cp);
 171     mp_drop(cq);
 172   }
 173
 174   /* --- Finally, possibly remove the blinding factor --- */
 175
 176   if (ki) {
 177     d = mpmont_mul(&rd->nm, d, d, ki);
 178     d = mpmont_mul(&rd->nm, d, d, rd->nm.r2);
 179     mp_drop(ki);
 180   }
 181
 182   /* --- Done --- */
 183
 184   mp_drop(c);
 185   return (d);
 186 }
 187
 188 /* --- @rsa_decrypt@ --- *
 189  *
 190  * Arguments:   @rsa_param *rp@ = pointer to RSA parameters
 191  *              @mp *d@ = destination
 192  *              @mp *c@ = ciphertext message
 193  *              @grand *r@ = pointer to random number source for blinding
 194  *
 195  * Returns:     Correctly decrypted message.
 196  *
 197  * Use:         Performs RSA decryption, very carefully.
 198  */
 199
 200 mp *rsa_decrypt(rsa_param *rp, mp *d, mp *c, grand *r)
 201 {
 202   rsa_decctx rd;
 203   rsa_deccreate(&rd, rp, r);
 204   d = rsa_dec(&rd, d, c);
 205   rsa_decdestroy(&rd);
 206   return (d);
 207 }
 208
 209 /*----- That's all, folks -------------------------------------------------*/