01898d8e |
1 | /* -*-c-*- |
2 | * |
43429c4b |
3 | * $Id: rsa-decrypt.c,v 1.2 2000/06/17 11:57:56 mdw Exp $ |
01898d8e |
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 $ |
43429c4b |
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 | * |
01898d8e |
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 | |
43429c4b |
52 | /* --- @rsa_deccreate@ --- * |
01898d8e |
53 | * |
43429c4b |
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 |
01898d8e |
99 | * @mp *d@ = destination |
100 | * @mp *c@ = ciphertext message |
01898d8e |
101 | * |
43429c4b |
102 | * Returns: The recovered plaintext message. |
01898d8e |
103 | * |
43429c4b |
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. |
01898d8e |
109 | */ |
110 | |
43429c4b |
111 | mp *rsa_dec(rsa_decctx *rd, mp *d, mp *c) |
01898d8e |
112 | { |
113 | mp *ki = MP_NEW; |
43429c4b |
114 | rsa_param *rp = rd->rp; |
01898d8e |
115 | |
116 | /* --- If so desired, set up a blinding constant --- * |
117 | * |
118 | * Choose a constant %$k$% relatively prime to the modulus %$m$%. Compute |
43429c4b |
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. |
01898d8e |
121 | */ |
122 | |
123 | c = MP_COPY(c); |
43429c4b |
124 | if (rd->r) { |
125 | mp *k = MP_NEWSEC, *g = MP_NEW; |
01898d8e |
126 | |
127 | do { |
43429c4b |
128 | k = mprand_range(k, rp->n, rd->r, 0); |
01898d8e |
129 | mp_gcd(&g, 0, &ki, rp->n, k); |
130 | } while (MP_CMP(g, !=, MP_ONE)); |
43429c4b |
131 | k = mpmont_expr(&rd->nm, k, k, rp->e); |
132 | c = mpmont_mul(&rd->nm, c, c, k); |
01898d8e |
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 | { |
01898d8e |
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); |
43429c4b |
151 | cp = mpmont_exp(&rd->pm, cp, cp, rp->dp); |
01898d8e |
152 | |
153 | mp_div(0, &cq, c, rp->q); |
43429c4b |
154 | cq = mpmont_exp(&rd->qm, cq, cq, rp->dq); |
01898d8e |
155 | |
156 | /* --- Combine the halves using the result above --- */ |
157 | |
158 | d = mp_sub(d, cp, cq); |
01898d8e |
159 | mp_div(0, &d, d, rp->p); |
43429c4b |
160 | d = mpmont_mul(&rd->pm, d, d, rp->q_inv); |
161 | d = mpmont_mul(&rd->pm, d, d, rd->pm.r2); |
01898d8e |
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) { |
43429c4b |
177 | d = mpmont_mul(&rd->nm, d, d, ki); |
178 | d = mpmont_mul(&rd->nm, d, d, rd->nm.r2); |
01898d8e |
179 | mp_drop(ki); |
180 | } |
181 | |
182 | /* --- Done --- */ |
183 | |
184 | mp_drop(c); |
185 | return (d); |
186 | } |
187 | |
43429c4b |
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 | |
01898d8e |
209 | /*----- That's all, folks -------------------------------------------------*/ |