3 * $Id: rsa-priv.c,v 1.4 2004/04/08 01:36:15 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 /*----- Header files ------------------------------------------------------*/
32 #include <mLib/alloc.h>
33 #include <mLib/bits.h>
34 #include <mLib/dstr.h>
41 /*----- Public key operations ---------------------------------------------*/
43 /* --- @rsa_privcreate@ --- *
45 * Arguments: @rsa_privctx *rd@ = pointer to an RSA private key context
46 * @rsa_priv *rp@ = pointer to RSA private key
47 * @grand *r@ = pointer to random number source for blinding
51 * Use: Initializes an RSA private-key context. Keeping a context
52 * for several decryption or signing operations provides a minor
53 * performance benefit.
55 * The random number source may be null if blinding is not
56 * desired. This improves decryption speed, at the risk of
57 * permitting timing attacks.
60 void rsa_privcreate(rsa_privctx
*rd
, rsa_priv
*rp
, grand
*r
)
65 mpmont_create(&rd
->nm
, rp
->n
);
66 mpmont_create(&rd
->pm
, rp
->p
);
67 mpmont_create(&rd
->qm
, rp
->q
);
70 /* --- @rsa_privdestroy@ --- *
72 * Arguments: @rsa_privctx *rd@ = pointer to an RSA decryption context
76 * Use: Destroys an RSA decryption context.
79 void rsa_privdestroy(rsa_privctx
*rd
)
82 mpmont_destroy(&rd
->nm
);
83 mpmont_destroy(&rd
->pm
);
84 mpmont_destroy(&rd
->qm
);
87 /* --- @rsa_privop@ --- *
89 * Arguments: @rsa_privctx *rd@ = pointer to RSA private key context
90 * @mp *d@ = destination
91 * @mp *c@ = input message
93 * Returns: The transformed output message.
95 * Use: Performs an RSA private key operation. This function takes
96 * advantage of knowledge of the key factors in order to speed
97 * up decryption. It also blinds the ciphertext prior to
98 * decryption and unblinds it afterwards to thwart timing
102 mp
*rsa_privop(rsa_privctx
*rd
, mp
*d
, mp
*c
)
105 rsa_priv
*rp
= rd
->rp
;
107 /* --- If so desired, set up a blinding constant --- *
109 * Choose a constant %$k$% relatively prime to the modulus %$m$%. Compute
110 * %$c' = c k^e \bmod n$%, and %$k^{-1} \bmod n$%. Don't bother with the
111 * CRT stuff here because %$e$% is chosen to be small.
116 mp
*k
= MP_NEWSEC
, *g
= MP_NEW
;
119 k
= mprand_range(k
, rp
->n
, rd
->r
, 0);
120 mp_gcd(&g
, 0, &ki
, rp
->n
, k
);
121 } while (!MP_EQ(g
, MP_ONE
));
122 k
= mpmont_mul(&rd
->nm
, k
, k
, rd
->nm
.r2
);
123 k
= mpmont_expr(&rd
->nm
, k
, k
, rp
->e
);
124 c
= mpmont_mul(&rd
->nm
, c
, c
, k
);
129 /* --- Do the actual modular exponentiation --- *
131 * Use a slightly hacked version of the Chinese Remainder Theorem stuff.
133 * Let %$q' = q^{-1} \bmod p$%. Then note that
134 * %$c^d \equiv q (q'(c_p^{d_p} - c_q^{d_q}) \bmod p) + c_q^{d_q} \pmod n$%
138 mp
*cp
= MP_NEW
, *cq
= MP_NEW
;
140 /* --- Work out the two halves of the result --- */
142 mp_div(0, &cp
, c
, rp
->p
);
143 cp
= mpmont_exp(&rd
->pm
, cp
, cp
, rp
->dp
);
145 mp_div(0, &cq
, c
, rp
->q
);
146 cq
= mpmont_exp(&rd
->qm
, cq
, cq
, rp
->dq
);
148 /* --- Combine the halves using the result above --- */
150 d
= mp_sub(d
, cp
, cq
);
151 mp_div(0, &d
, d
, rp
->p
);
152 d
= mpmont_mul(&rd
->pm
, d
, d
, rp
->q_inv
);
153 d
= mpmont_mul(&rd
->pm
, d
, d
, rd
->pm
.r2
);
155 d
= mp_mul(d
, d
, rp
->q
);
156 d
= mp_add(d
, d
, cq
);
157 if (MP_CMP(d
, >=, rp
->n
))
158 d
= mp_sub(d
, d
, rp
->n
);
160 /* --- Tidy away temporary variables --- */
166 /* --- Finally, possibly remove the blinding factor --- */
169 d
= mpmont_mul(&rd
->nm
, d
, d
, ki
);
170 d
= mpmont_mul(&rd
->nm
, d
, d
, rd
->nm
.r2
);
180 /* --- @rsa_qprivop@ --- *
182 * Arguments: @rsa_priv *rp@ = pointer to RSA parameters
183 * @mp *d@ = destination
184 * @mp *c@ = input message
185 * @grand *r@ = pointer to random number source for blinding
187 * Returns: Correctly transformed output message
189 * Use: Performs an RSA private key operation, very carefully.
192 mp
*rsa_qprivop(rsa_priv
*rp
, mp
*d
, mp
*c
, grand
*r
)
195 rsa_privcreate(&rd
, rp
, r
);
196 d
= rsa_privop(&rd
, d
, c
);
197 rsa_privdestroy(&rd
);
201 /*----- Operations with padding -------------------------------------------*/
203 /* --- @rsa_sign@ --- *
205 * Arguments: @rsa_privctx *rp@ = pointer to an RSA private key context
206 * @mp *d@ = where to put the result
207 * @const void *m@ = pointer to input message
208 * @size_t msz@ = size of input message
209 * @rsa_pad *e@ = encoding procedure
210 * @void *earg@ = argument pointer for encoding procedure
212 * Returns: The signature, as a multiprecision integer, or null on
215 * Use: Computes an RSA digital signature.
218 mp
*rsa_sign(rsa_privctx
*rp
, mp
*d
, const void *m
, size_t msz
,
219 rsa_pad
*e
, void *earg
)
222 unsigned long nb
= mp_bits(rp
->rp
->n
);
223 size_t n
= (nb
+ 7)/8;
224 arena
*a
= d
&& d
->a ? d
->a
->a
: arena_global
;
227 d
= e(d
, m
, msz
, p
, n
, nb
, earg
);
229 return (d ?
rsa_privop(rp
, d
, d
) : 0);
232 /* --- @rsa_decrypt@ --- *
234 * Arguments: @rsa_privctx *rp@ = pointer to an RSA private key context
235 * @mp *m@ = encrypted message, as a multiprecision integer
236 * @dstr *d@ = pointer to output string
237 * @rsa_decunpad *e@ = decoding procedure
238 * @void *earg@ = argument pointer for decoding procedure
240 * Returns: The length of the output string if successful, negative on
243 * Use: Does RSA decryption.
246 int rsa_decrypt(rsa_privctx
*rp
, mp
*m
, dstr
*d
,
247 rsa_decunpad
*e
, void *earg
)
249 mp
*p
= rsa_privop(rp
, MP_NEW
, m
);
250 unsigned long nb
= mp_bits(rp
->rp
->n
);
251 size_t n
= (nb
+ 7)/8;
255 rc
= e(p
, (octet
*)d
->buf
+ d
->len
, n
, nb
, earg
);
262 /*----- That's all, folks -------------------------------------------------*/