3 * $Id: rsa-decrypt.c,v 1.2 2000/06/17 11:57:56 mdw Exp $
7 * (c) 1999 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
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.
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.
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,
30 /*----- Revision history --------------------------------------------------*
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
38 * Revision 1.1 1999/12/22 15:50:45 mdw
39 * Initial RSA support.
43 /*----- Header files ------------------------------------------------------*/
50 /*----- Main code ---------------------------------------------------------*/
52 /* --- @rsa_deccreate@ --- *
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
60 * Use: Initializes an RSA decryption context. Keeping a context
61 * for several decryption or signing operations provides a minor
62 * performance benefit.
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.
69 void rsa_deccreate(rsa_decctx
*rd
, rsa_param
*rp
, grand
*r
)
74 mpmont_create(&rd
->nm
, rp
->n
);
75 mpmont_create(&rd
->pm
, rp
->p
);
76 mpmont_create(&rd
->qm
, rp
->q
);
79 /* --- @rsa_decdestroy@ --- *
81 * Arguments: @rsa_decctx *rd@ = pointer to an RSA decryption context
85 * Use: Destroys an RSA decryption context.
88 void rsa_decdestroy(rsa_decctx
*rd
)
91 mpmont_destroy(&rd
->nm
);
92 mpmont_destroy(&rd
->pm
);
93 mpmont_destroy(&rd
->qm
);
96 /* --- @rsa_dec@ --- *
98 * Arguments: @rsa_decctx *rd@ = pointer to RSA decryption context
99 * @mp *d@ = destination
100 * @mp *c@ = ciphertext message
102 * Returns: The recovered plaintext message.
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
111 mp
*rsa_dec(rsa_decctx
*rd
, mp
*d
, mp
*c
)
114 rsa_param
*rp
= rd
->rp
;
116 /* --- If so desired, set up a blinding constant --- *
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.
125 mp
*k
= MP_NEWSEC
, *g
= MP_NEW
;
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
);
137 /* --- Do the actual modular exponentiation --- *
139 * Use a slightly hacked version of the Chinese Remainder Theorem stuff.
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$%
146 mp
*cp
= MP_NEW
, *cq
= MP_NEW
;
148 /* --- Work out the two halves of the result --- */
150 mp_div(0, &cp
, c
, rp
->p
);
151 cp
= mpmont_exp(&rd
->pm
, cp
, cp
, rp
->dp
);
153 mp_div(0, &cq
, c
, rp
->q
);
154 cq
= mpmont_exp(&rd
->qm
, cq
, cq
, rp
->dq
);
156 /* --- Combine the halves using the result above --- */
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
);
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
);
168 /* --- Tidy away temporary variables --- */
174 /* --- Finally, possibly remove the blinding factor --- */
177 d
= mpmont_mul(&rd
->nm
, d
, d
, ki
);
178 d
= mpmont_mul(&rd
->nm
, d
, d
, rd
->nm
.r2
);
188 /* --- @rsa_decrypt@ --- *
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
195 * Returns: Correctly decrypted message.
197 * Use: Performs RSA decryption, very carefully.
200 mp
*rsa_decrypt(rsa_param
*rp
, mp
*d
, mp
*c
, grand
*r
)
203 rsa_deccreate(&rd
, rp
, r
);
204 d
= rsa_dec(&rd
, d
, c
);
209 /*----- That's all, folks -------------------------------------------------*/