3 * $Id: rsa-priv.c,v 1.3 2001/06/16 12:56:38 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.3 2001/06/16 12:56:38 mdw
34 * Fixes for interface change to @mpmont_expr@ and @mpmont_mexpr@.
36 * Revision 1.2 2000/10/08 12:11:22 mdw
37 * Use @MP_EQ@ instead of @MP_CMP@.
39 * Revision 1.1 2000/07/01 11:23:20 mdw
40 * Renamed from `rsa-decrypt', since the name was no longer appropriate.
41 * Add functions for doing padded RSA decryption and signing.
43 * --- Previous lives as rsa-decrypt.c ---
45 * Revision 1.2 2000/06/17 11:57:56 mdw
46 * Improve bulk performance by making better use of Montgomery
47 * multiplication and separating out initialization and finalization from
50 * Revision 1.1 1999/12/22 15:50:45 mdw
51 * Initial RSA support.
55 /*----- Header files ------------------------------------------------------*/
57 #include <mLib/alloc.h>
58 #include <mLib/bits.h>
59 #include <mLib/dstr.h>
66 /*----- Public key operations ---------------------------------------------*/
68 /* --- @rsa_privcreate@ --- *
70 * Arguments: @rsa_privctx *rd@ = pointer to an RSA private key context
71 * @rsa_priv *rp@ = pointer to RSA private key
72 * @grand *r@ = pointer to random number source for blinding
76 * Use: Initializes an RSA private-key context. Keeping a context
77 * for several decryption or signing operations provides a minor
78 * performance benefit.
80 * The random number source may be null if blinding is not
81 * desired. This improves decryption speed, at the risk of
82 * permitting timing attacks.
85 void rsa_privcreate(rsa_privctx
*rd
, rsa_priv
*rp
, grand
*r
)
90 mpmont_create(&rd
->nm
, rp
->n
);
91 mpmont_create(&rd
->pm
, rp
->p
);
92 mpmont_create(&rd
->qm
, rp
->q
);
95 /* --- @rsa_privdestroy@ --- *
97 * Arguments: @rsa_privctx *rd@ = pointer to an RSA decryption context
101 * Use: Destroys an RSA decryption context.
104 void rsa_privdestroy(rsa_privctx
*rd
)
107 mpmont_destroy(&rd
->nm
);
108 mpmont_destroy(&rd
->pm
);
109 mpmont_destroy(&rd
->qm
);
112 /* --- @rsa_privop@ --- *
114 * Arguments: @rsa_privctx *rd@ = pointer to RSA private key context
115 * @mp *d@ = destination
116 * @mp *c@ = input message
118 * Returns: The transformed output message.
120 * Use: Performs an RSA private key operation. This function takes
121 * advantage of knowledge of the key factors in order to speed
122 * up decryption. It also blinds the ciphertext prior to
123 * decryption and unblinds it afterwards to thwart timing
127 mp
*rsa_privop(rsa_privctx
*rd
, mp
*d
, mp
*c
)
130 rsa_priv
*rp
= rd
->rp
;
132 /* --- If so desired, set up a blinding constant --- *
134 * Choose a constant %$k$% relatively prime to the modulus %$m$%. Compute
135 * %$c' = c k^e \bmod n$%, and %$k^{-1} \bmod n$%. Don't bother with the
136 * CRT stuff here because %$e$% is chosen to be small.
141 mp
*k
= MP_NEWSEC
, *g
= MP_NEW
;
144 k
= mprand_range(k
, rp
->n
, rd
->r
, 0);
145 mp_gcd(&g
, 0, &ki
, rp
->n
, k
);
146 } while (!MP_EQ(g
, MP_ONE
));
147 k
= mpmont_mul(&rd
->nm
, k
, k
, rd
->nm
.r2
);
148 k
= mpmont_expr(&rd
->nm
, k
, k
, rp
->e
);
149 c
= mpmont_mul(&rd
->nm
, c
, c
, k
);
154 /* --- Do the actual modular exponentiation --- *
156 * Use a slightly hacked version of the Chinese Remainder Theorem stuff.
158 * Let %$q' = q^{-1} \bmod p$%. Then note that
159 * %$c^d \equiv q (q'(c_p^{d_p} - c_q^{d_q}) \bmod p) + c_q^{d_q} \pmod n$%
163 mp
*cp
= MP_NEW
, *cq
= MP_NEW
;
165 /* --- Work out the two halves of the result --- */
167 mp_div(0, &cp
, c
, rp
->p
);
168 cp
= mpmont_exp(&rd
->pm
, cp
, cp
, rp
->dp
);
170 mp_div(0, &cq
, c
, rp
->q
);
171 cq
= mpmont_exp(&rd
->qm
, cq
, cq
, rp
->dq
);
173 /* --- Combine the halves using the result above --- */
175 d
= mp_sub(d
, cp
, cq
);
176 mp_div(0, &d
, d
, rp
->p
);
177 d
= mpmont_mul(&rd
->pm
, d
, d
, rp
->q_inv
);
178 d
= mpmont_mul(&rd
->pm
, d
, d
, rd
->pm
.r2
);
180 d
= mp_mul(d
, d
, rp
->q
);
181 d
= mp_add(d
, d
, cq
);
182 if (MP_CMP(d
, >=, rp
->n
))
183 d
= mp_sub(d
, d
, rp
->n
);
185 /* --- Tidy away temporary variables --- */
191 /* --- Finally, possibly remove the blinding factor --- */
194 d
= mpmont_mul(&rd
->nm
, d
, d
, ki
);
195 d
= mpmont_mul(&rd
->nm
, d
, d
, rd
->nm
.r2
);
205 /* --- @rsa_qprivop@ --- *
207 * Arguments: @rsa_priv *rp@ = pointer to RSA parameters
208 * @mp *d@ = destination
209 * @mp *c@ = input message
210 * @grand *r@ = pointer to random number source for blinding
212 * Returns: Correctly transformed output message
214 * Use: Performs an RSA private key operation, very carefully.
217 mp
*rsa_qprivop(rsa_priv
*rp
, mp
*d
, mp
*c
, grand
*r
)
220 rsa_privcreate(&rd
, rp
, r
);
221 d
= rsa_privop(&rd
, d
, c
);
222 rsa_privdestroy(&rd
);
226 /*----- Operations with padding -------------------------------------------*/
228 /* --- @rsa_sign@ --- *
230 * Arguments: @rsa_privctx *rp@ = pointer to an RSA private key context
231 * @const void *m@ = pointer to input message
232 * @size_t sz@ = size of input message
233 * @dstr *d@ = pointer to output string
234 * @rsa_encodeproc e@ = encoding procedure
235 * @void *earg@ = argument pointer for encoding procedure
237 * Returns: The length of the output string if successful, negative on
240 * Use: Computes an RSA digital signature.
243 int rsa_sign(rsa_privctx
*rp
, const void *m
, size_t sz
,
244 dstr
*d
, rsa_encodeproc e
, void *earg
)
247 size_t n
= mp_octets(rp
->rp
->n
);
251 /* --- Sort out some space --- */
254 p
= (octet
*)d
->buf
+ d
->len
;
257 /* --- Do the packing --- */
259 if ((rc
= e(m
, sz
, p
, n
, earg
)) < 0)
262 /* --- Do the encryption --- */
264 x
= mp_loadb(MP_NEWSEC
, p
, n
);
265 x
= rsa_privop(rp
, x
, x
);
272 /* --- @rsa_decrypt@ --- *
274 * Arguments: @rsa_privctx *rp@ = pointer to an RSA private key context
275 * @const void *m@ = pointer to input message
276 * @size_t sz@ = size of input message
277 * @dstr *d@ = pointer to output string
278 * @rsa_decodeproc e@ = decoding procedure
279 * @void *earg@ = argument pointer for decoding procedure
281 * Returns: The length of the output string if successful, negative on
284 * Use: Does RSA signature verification.
287 int rsa_decrypt(rsa_privctx
*rp
, const void *m
, size_t sz
,
288 dstr
*d
, rsa_decodeproc e
, void *earg
)
291 size_t n
= mp_octets(rp
->rp
->n
);
295 /* --- Do the exponentiation --- */
297 p
= x_alloc(d
->a
, n
);
298 x
= mp_loadb(MP_NEW
, m
, sz
);
299 x
= rsa_privop(rp
, x
, x
);
303 /* --- Do the decoding --- */
305 rc
= e(p
, n
, d
, earg
);
310 /*----- That's all, folks -------------------------------------------------*/