3 * $Id: rsa-priv.c,v 1.1 2000/07/01 11:23:20 mdw Exp $
5 * RSA private-key operations
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-priv.c,v $
33 * Revision 1.1 2000/07/01 11:23:20 mdw
34 * Renamed from `rsa-decrypt', since the name was no longer appropriate.
35 * Add functions for doing padded RSA decryption and signing.
37 * --- Previous lives as rsa-decrypt.c ---
39 * Revision 1.2 2000/06/17 11:57:56 mdw
40 * Improve bulk performance by making better use of Montgomery
41 * multiplication and separating out initialization and finalization from
44 * Revision 1.1 1999/12/22 15:50:45 mdw
45 * Initial RSA support.
49 /*----- Header files ------------------------------------------------------*/
51 #include <mLib/alloc.h>
52 #include <mLib/bits.h>
53 #include <mLib/dstr.h>
60 /*----- Public key operations ---------------------------------------------*/
62 /* --- @rsa_privcreate@ --- *
64 * Arguments: @rsa_privctx *rd@ = pointer to an RSA private key context
65 * @rsa_priv *rp@ = pointer to RSA private key
66 * @grand *r@ = pointer to random number source for blinding
70 * Use: Initializes an RSA private-key context. Keeping a context
71 * for several decryption or signing operations provides a minor
72 * performance benefit.
74 * The random number source may be null if blinding is not
75 * desired. This improves decryption speed, at the risk of
76 * permitting timing attacks.
79 void rsa_privcreate(rsa_privctx *rd, rsa_priv *rp, grand *r)
84 mpmont_create(&rd->nm, rp->n);
85 mpmont_create(&rd->pm, rp->p);
86 mpmont_create(&rd->qm, rp->q);
89 /* --- @rsa_privdestroy@ --- *
91 * Arguments: @rsa_privctx *rd@ = pointer to an RSA decryption context
95 * Use: Destroys an RSA decryption context.
98 void rsa_privdestroy(rsa_privctx *rd)
101 mpmont_destroy(&rd->nm);
102 mpmont_destroy(&rd->pm);
103 mpmont_destroy(&rd->qm);
106 /* --- @rsa_privop@ --- *
108 * Arguments: @rsa_privctx *rd@ = pointer to RSA private key context
109 * @mp *d@ = destination
110 * @mp *c@ = input message
112 * Returns: The transformed output message.
114 * Use: Performs an RSA private key operation. This function takes
115 * advantage of knowledge of the key factors in order to speed
116 * up decryption. It also blinds the ciphertext prior to
117 * decryption and unblinds it afterwards to thwart timing
121 mp *rsa_privop(rsa_privctx *rd, mp *d, mp *c)
124 rsa_priv *rp = rd->rp;
126 /* --- If so desired, set up a blinding constant --- *
128 * Choose a constant %$k$% relatively prime to the modulus %$m$%. Compute
129 * %$c' = c k^e \bmod n$%, and %$k^{-1} \bmod n$%. Don't bother with the
130 * CRT stuff here because %$e$% is chosen to be small.
135 mp *k = MP_NEWSEC, *g = MP_NEW;
138 k = mprand_range(k, rp->n, rd->r, 0);
139 mp_gcd(&g, 0, &ki, rp->n, k);
140 } while (MP_CMP(g, !=, MP_ONE));
141 k = mpmont_expr(&rd->nm, k, k, rp->e);
142 c = mpmont_mul(&rd->nm, c, c, k);
147 /* --- Do the actual modular exponentiation --- *
149 * Use a slightly hacked version of the Chinese Remainder Theorem stuff.
151 * Let %$q' = q^{-1} \bmod p$%. Then note that
152 * %$c^d \equiv q (q'(c_p^{d_p} - c_q^{d_q}) \bmod p) + c_q^{d_q} \pmod n$%
156 mp *cp = MP_NEW, *cq = MP_NEW;
158 /* --- Work out the two halves of the result --- */
160 mp_div(0, &cp, c, rp->p);
161 cp = mpmont_exp(&rd->pm, cp, cp, rp->dp);
163 mp_div(0, &cq, c, rp->q);
164 cq = mpmont_exp(&rd->qm, cq, cq, rp->dq);
166 /* --- Combine the halves using the result above --- */
168 d = mp_sub(d, cp, cq);
169 mp_div(0, &d, d, rp->p);
170 d = mpmont_mul(&rd->pm, d, d, rp->q_inv);
171 d = mpmont_mul(&rd->pm, d, d, rd->pm.r2);
173 d = mp_mul(d, d, rp->q);
174 d = mp_add(d, d, cq);
175 if (MP_CMP(d, >=, rp->n))
176 d = mp_sub(d, d, rp->n);
178 /* --- Tidy away temporary variables --- */
184 /* --- Finally, possibly remove the blinding factor --- */
187 d = mpmont_mul(&rd->nm, d, d, ki);
188 d = mpmont_mul(&rd->nm, d, d, rd->nm.r2);
198 /* --- @rsa_qprivop@ --- *
200 * Arguments: @rsa_priv *rp@ = pointer to RSA parameters
201 * @mp *d@ = destination
202 * @mp *c@ = input message
203 * @grand *r@ = pointer to random number source for blinding
205 * Returns: Correctly transformed output message
207 * Use: Performs an RSA private key operation, very carefully.
210 mp *rsa_qprivop(rsa_priv *rp, mp *d, mp *c, grand *r)
213 rsa_privcreate(&rd, rp, r);
214 d = rsa_privop(&rd, d, c);
215 rsa_privdestroy(&rd);
219 /*----- Operations with padding -------------------------------------------*/
221 /* --- @rsa_sign@ --- *
223 * Arguments: @rsa_privctx *rp@ = pointer to an RSA private key context
224 * @const void *m@ = pointer to input message
225 * @size_t sz@ = size of input message
226 * @dstr *d@ = pointer to output string
227 * @rsa_encodeproc e@ = encoding procedure
228 * @void *earg@ = argument pointer for encoding procedure
230 * Returns: The length of the output string if successful, negative on
233 * Use: Computes an RSA digital signature.
236 int rsa_sign(rsa_privctx *rp, const void *m, size_t sz,
237 dstr *d, rsa_encodeproc e, void *earg)
240 size_t n = mp_octets(rp->rp->n);
244 /* --- Sort out some space --- */
250 /* --- Do the packing --- */
252 if ((rc = e(m, sz, p, n, earg)) < 0)
255 /* --- Do the encryption --- */
257 x = mp_loadb(MP_NEWSEC, p, n);
258 x = rsa_privop(rp, x, x);
265 /* --- @rsa_decrypt@ --- *
267 * Arguments: @rsa_privctx *rp@ = pointer to an RSA private key context
268 * @const void *m@ = pointer to input message
269 * @size_t sz@ = size of input message
270 * @dstr *d@ = pointer to output string
271 * @rsa_decodeproc e@ = decoding procedure
272 * @void *earg@ = argument pointer for decoding procedure
274 * Returns: The length of the output string if successful, negative on
277 * Use: Does RSA signature verification.
280 int rsa_decrypt(rsa_privctx *rp, const void *m, size_t sz,
281 dstr *d, rsa_decodeproc e, void *earg)
284 size_t n = mp_octets(rp->rp->n);
288 /* --- Do the exponentiation --- */
290 p = x_alloc(d->a, n);
291 x = mp_loadb(MP_NEW, m, sz);
292 x = rsa_privop(rp, x, x);
296 /* --- Do the decoding --- */
298 rc = e(p, n, d, earg);
303 /*----- That's all, folks -------------------------------------------------*/