c760149f |
1 | /* -*-c-*- |
c760149f |
2 | * |
3 | * RSA private-key operations |
4 | * |
5 | * (c) 1999 Straylight/Edgeware |
6 | */ |
7 | |
45c0fd36 |
8 | /*----- Licensing notice --------------------------------------------------* |
c760149f |
9 | * |
10 | * This file is part of Catacomb. |
11 | * |
12 | * Catacomb is free software; you can redistribute it and/or modify |
13 | * it under the terms of the GNU Library General Public License as |
14 | * published by the Free Software Foundation; either version 2 of the |
15 | * License, or (at your option) any later version. |
45c0fd36 |
16 | * |
c760149f |
17 | * Catacomb is distributed in the hope that it will be useful, |
18 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
19 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
20 | * GNU Library General Public License for more details. |
45c0fd36 |
21 | * |
c760149f |
22 | * You should have received a copy of the GNU Library General Public |
23 | * License along with Catacomb; if not, write to the Free |
24 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, |
25 | * MA 02111-1307, USA. |
26 | */ |
27 | |
c760149f |
28 | /*----- Header files ------------------------------------------------------*/ |
29 | |
30 | #include <mLib/alloc.h> |
31 | #include <mLib/bits.h> |
32 | #include <mLib/dstr.h> |
33 | |
34 | #include "mp.h" |
35 | #include "mpmont.h" |
36 | #include "mprand.h" |
37 | #include "rsa.h" |
38 | |
39 | /*----- Public key operations ---------------------------------------------*/ |
40 | |
41 | /* --- @rsa_privcreate@ --- * |
42 | * |
43 | * Arguments: @rsa_privctx *rd@ = pointer to an RSA private key context |
44 | * @rsa_priv *rp@ = pointer to RSA private key |
45 | * @grand *r@ = pointer to random number source for blinding |
46 | * |
47 | * Returns: --- |
48 | * |
49 | * Use: Initializes an RSA private-key context. Keeping a context |
50 | * for several decryption or signing operations provides a minor |
51 | * performance benefit. |
52 | * |
53 | * The random number source may be null if blinding is not |
54 | * desired. This improves decryption speed, at the risk of |
55 | * permitting timing attacks. |
56 | */ |
57 | |
58 | void rsa_privcreate(rsa_privctx *rd, rsa_priv *rp, grand *r) |
59 | { |
60 | rd->rp = rp; |
61 | rd->r = r; |
62 | if (r) |
63 | mpmont_create(&rd->nm, rp->n); |
64 | mpmont_create(&rd->pm, rp->p); |
65 | mpmont_create(&rd->qm, rp->q); |
66 | } |
67 | |
68 | /* --- @rsa_privdestroy@ --- * |
69 | * |
70 | * Arguments: @rsa_privctx *rd@ = pointer to an RSA decryption context |
71 | * |
72 | * Returns: --- |
73 | * |
74 | * Use: Destroys an RSA decryption context. |
75 | */ |
76 | |
77 | void rsa_privdestroy(rsa_privctx *rd) |
78 | { |
79 | if (rd->r) |
80 | mpmont_destroy(&rd->nm); |
81 | mpmont_destroy(&rd->pm); |
82 | mpmont_destroy(&rd->qm); |
83 | } |
84 | |
85 | /* --- @rsa_privop@ --- * |
86 | * |
87 | * Arguments: @rsa_privctx *rd@ = pointer to RSA private key context |
88 | * @mp *d@ = destination |
89 | * @mp *c@ = input message |
90 | * |
91 | * Returns: The transformed output message. |
92 | * |
93 | * Use: Performs an RSA private key operation. This function takes |
94 | * advantage of knowledge of the key factors in order to speed |
95 | * up decryption. It also blinds the ciphertext prior to |
96 | * decryption and unblinds it afterwards to thwart timing |
97 | * attacks. |
98 | */ |
99 | |
100 | mp *rsa_privop(rsa_privctx *rd, mp *d, mp *c) |
101 | { |
102 | mp *ki = MP_NEW; |
103 | rsa_priv *rp = rd->rp; |
104 | |
105 | /* --- If so desired, set up a blinding constant --- * |
106 | * |
107 | * Choose a constant %$k$% relatively prime to the modulus %$m$%. Compute |
108 | * %$c' = c k^e \bmod n$%, and %$k^{-1} \bmod n$%. Don't bother with the |
109 | * CRT stuff here because %$e$% is chosen to be small. |
110 | */ |
111 | |
112 | c = MP_COPY(c); |
113 | if (rd->r) { |
114 | mp *k = MP_NEWSEC, *g = MP_NEW; |
115 | |
116 | do { |
117 | k = mprand_range(k, rp->n, rd->r, 0); |
118 | mp_gcd(&g, 0, &ki, rp->n, k); |
22bab86c |
119 | } while (!MP_EQ(g, MP_ONE)); |
b0b682aa |
120 | k = mpmont_mul(&rd->nm, k, k, rd->nm.r2); |
c760149f |
121 | k = mpmont_expr(&rd->nm, k, k, rp->e); |
122 | c = mpmont_mul(&rd->nm, c, c, k); |
123 | mp_drop(k); |
124 | mp_drop(g); |
125 | } |
126 | |
127 | /* --- Do the actual modular exponentiation --- * |
128 | * |
129 | * Use a slightly hacked version of the Chinese Remainder Theorem stuff. |
130 | * |
131 | * Let %$q' = q^{-1} \bmod p$%. Then note that |
132 | * %$c^d \equiv q (q'(c_p^{d_p} - c_q^{d_q}) \bmod p) + c_q^{d_q} \pmod n$% |
133 | */ |
134 | |
135 | { |
136 | mp *cp = MP_NEW, *cq = MP_NEW; |
137 | |
138 | /* --- Work out the two halves of the result --- */ |
139 | |
140 | mp_div(0, &cp, c, rp->p); |
141 | cp = mpmont_exp(&rd->pm, cp, cp, rp->dp); |
142 | |
143 | mp_div(0, &cq, c, rp->q); |
144 | cq = mpmont_exp(&rd->qm, cq, cq, rp->dq); |
145 | |
146 | /* --- Combine the halves using the result above --- */ |
147 | |
148 | d = mp_sub(d, cp, cq); |
149 | mp_div(0, &d, d, rp->p); |
150 | d = mpmont_mul(&rd->pm, d, d, rp->q_inv); |
151 | d = mpmont_mul(&rd->pm, d, d, rd->pm.r2); |
152 | |
153 | d = mp_mul(d, d, rp->q); |
154 | d = mp_add(d, d, cq); |
155 | if (MP_CMP(d, >=, rp->n)) |
156 | d = mp_sub(d, d, rp->n); |
157 | |
158 | /* --- Tidy away temporary variables --- */ |
159 | |
160 | mp_drop(cp); |
161 | mp_drop(cq); |
162 | } |
163 | |
164 | /* --- Finally, possibly remove the blinding factor --- */ |
165 | |
166 | if (ki) { |
167 | d = mpmont_mul(&rd->nm, d, d, ki); |
168 | d = mpmont_mul(&rd->nm, d, d, rd->nm.r2); |
169 | mp_drop(ki); |
170 | } |
171 | |
172 | /* --- Done --- */ |
173 | |
174 | mp_drop(c); |
175 | return (d); |
176 | } |
177 | |
178 | /* --- @rsa_qprivop@ --- * |
179 | * |
180 | * Arguments: @rsa_priv *rp@ = pointer to RSA parameters |
181 | * @mp *d@ = destination |
182 | * @mp *c@ = input message |
183 | * @grand *r@ = pointer to random number source for blinding |
184 | * |
185 | * Returns: Correctly transformed output message |
186 | * |
187 | * Use: Performs an RSA private key operation, very carefully. |
188 | */ |
189 | |
190 | mp *rsa_qprivop(rsa_priv *rp, mp *d, mp *c, grand *r) |
191 | { |
192 | rsa_privctx rd; |
193 | rsa_privcreate(&rd, rp, r); |
194 | d = rsa_privop(&rd, d, c); |
195 | rsa_privdestroy(&rd); |
196 | return (d); |
197 | } |
198 | |
199 | /*----- Operations with padding -------------------------------------------*/ |
200 | |
201 | /* --- @rsa_sign@ --- * |
202 | * |
203 | * Arguments: @rsa_privctx *rp@ = pointer to an RSA private key context |
b817bfc6 |
204 | * @mp *d@ = where to put the result |
c760149f |
205 | * @const void *m@ = pointer to input message |
b817bfc6 |
206 | * @size_t msz@ = size of input message |
207 | * @rsa_pad *e@ = encoding procedure |
c760149f |
208 | * @void *earg@ = argument pointer for encoding procedure |
209 | * |
b817bfc6 |
210 | * Returns: The signature, as a multiprecision integer, or null on |
c760149f |
211 | * failure. |
212 | * |
213 | * Use: Computes an RSA digital signature. |
214 | */ |
215 | |
b817bfc6 |
216 | mp *rsa_sign(rsa_privctx *rp, mp *d, const void *m, size_t msz, |
217 | rsa_pad *e, void *earg) |
c760149f |
218 | { |
c760149f |
219 | octet *p; |
b817bfc6 |
220 | unsigned long nb = mp_bits(rp->rp->n); |
221 | size_t n = (nb + 7)/8; |
222 | arena *a = d && d->a ? d->a->a : arena_global; |
223 | |
224 | p = x_alloc(a, n); |
225 | d = e(d, m, msz, p, n, nb, earg); |
226 | x_free(a, p); |
227 | return (d ? rsa_privop(rp, d, d) : 0); |
c760149f |
228 | } |
229 | |
230 | /* --- @rsa_decrypt@ --- * |
231 | * |
232 | * Arguments: @rsa_privctx *rp@ = pointer to an RSA private key context |
b817bfc6 |
233 | * @mp *m@ = encrypted message, as a multiprecision integer |
c760149f |
234 | * @dstr *d@ = pointer to output string |
b817bfc6 |
235 | * @rsa_decunpad *e@ = decoding procedure |
c760149f |
236 | * @void *earg@ = argument pointer for decoding procedure |
237 | * |
238 | * Returns: The length of the output string if successful, negative on |
239 | * failure. |
240 | * |
b817bfc6 |
241 | * Use: Does RSA decryption. |
c760149f |
242 | */ |
243 | |
b817bfc6 |
244 | int rsa_decrypt(rsa_privctx *rp, mp *m, dstr *d, |
245 | rsa_decunpad *e, void *earg) |
c760149f |
246 | { |
b817bfc6 |
247 | mp *p = rsa_privop(rp, MP_NEW, m); |
248 | unsigned long nb = mp_bits(rp->rp->n); |
249 | size_t n = (nb + 7)/8; |
c760149f |
250 | int rc; |
251 | |
b817bfc6 |
252 | dstr_ensure(d, n); |
253 | rc = e(p, (octet *)d->buf + d->len, n, nb, earg); |
254 | if (rc >= 0) |
255 | d->len += rc; |
256 | mp_drop(p); |
c760149f |
257 | return (rc); |
258 | } |
259 | |
260 | /*----- That's all, folks -------------------------------------------------*/ |