3 * RSA private-key operations
5 * (c) 1999 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Catacomb.
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.
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.
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,
28 /*----- Header files ------------------------------------------------------*/
30 #include <mLib/alloc.h>
31 #include <mLib/bits.h>
32 #include <mLib/dstr.h>
39 /*----- Public key operations ---------------------------------------------*/
41 /* --- @rsa_privcreate@ --- *
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
49 * Use: Initializes an RSA private-key context. Keeping a context
50 * for several decryption or signing operations provides a minor
51 * performance benefit.
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.
58 void rsa_privcreate(rsa_privctx
*rd
, rsa_priv
*rp
, grand
*r
)
63 mpmont_create(&rd
->nm
, rp
->n
);
64 mpmont_create(&rd
->pm
, rp
->p
);
65 mpmont_create(&rd
->qm
, rp
->q
);
68 /* --- @rsa_privdestroy@ --- *
70 * Arguments: @rsa_privctx *rd@ = pointer to an RSA decryption context
74 * Use: Destroys an RSA decryption context.
77 void rsa_privdestroy(rsa_privctx
*rd
)
80 mpmont_destroy(&rd
->nm
);
81 mpmont_destroy(&rd
->pm
);
82 mpmont_destroy(&rd
->qm
);
85 /* --- @rsa_privop@ --- *
87 * Arguments: @rsa_privctx *rd@ = pointer to RSA private key context
88 * @mp *d@ = destination
89 * @mp *c@ = input message
91 * Returns: The transformed output message.
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
100 mp
*rsa_privop(rsa_privctx
*rd
, mp
*d
, mp
*c
)
103 rsa_priv
*rp
= rd
->rp
;
105 /* --- If so desired, set up a blinding constant --- *
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.
114 mp
*k
= MP_NEWSEC
, *g
= MP_NEW
;
117 k
= mprand_range(k
, rp
->n
, rd
->r
, 0);
118 mp_gcd(&g
, 0, &ki
, rp
->n
, k
);
119 } while (!MP_EQ(g
, MP_ONE
));
120 k
= mpmont_mul(&rd
->nm
, k
, k
, rd
->nm
.r2
);
121 k
= mpmont_expr(&rd
->nm
, k
, k
, rp
->e
);
122 c
= mpmont_mul(&rd
->nm
, c
, c
, k
);
127 /* --- Do the actual modular exponentiation --- *
129 * Use a slightly hacked version of the Chinese Remainder Theorem stuff.
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$%
136 mp
*cp
= MP_NEW
, *cq
= MP_NEW
;
138 /* --- Work out the two halves of the result --- */
140 mp_div(0, &cp
, c
, rp
->p
);
141 cp
= mpmont_exp(&rd
->pm
, cp
, cp
, rp
->dp
);
143 mp_div(0, &cq
, c
, rp
->q
);
144 cq
= mpmont_exp(&rd
->qm
, cq
, cq
, rp
->dq
);
146 /* --- Combine the halves using the result above --- */
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
);
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
);
158 /* --- Tidy away temporary variables --- */
164 /* --- Finally, possibly remove the blinding factor --- */
167 d
= mpmont_mul(&rd
->nm
, d
, d
, ki
);
168 d
= mpmont_mul(&rd
->nm
, d
, d
, rd
->nm
.r2
);
178 /* --- @rsa_qprivop@ --- *
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
185 * Returns: Correctly transformed output message
187 * Use: Performs an RSA private key operation, very carefully.
190 mp
*rsa_qprivop(rsa_priv
*rp
, mp
*d
, mp
*c
, grand
*r
)
193 rsa_privcreate(&rd
, rp
, r
);
194 d
= rsa_privop(&rd
, d
, c
);
195 rsa_privdestroy(&rd
);
199 /*----- Operations with padding -------------------------------------------*/
201 /* --- @rsa_sign@ --- *
203 * Arguments: @rsa_privctx *rp@ = pointer to an RSA private key context
204 * @mp *d@ = where to put the result
205 * @const void *m@ = pointer to input message
206 * @size_t msz@ = size of input message
207 * @rsa_pad *e@ = encoding procedure
208 * @void *earg@ = argument pointer for encoding procedure
210 * Returns: The signature, as a multiprecision integer, or null on
213 * Use: Computes an RSA digital signature.
216 mp
*rsa_sign(rsa_privctx
*rp
, mp
*d
, const void *m
, size_t msz
,
217 rsa_pad
*e
, void *earg
)
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
;
225 d
= e(d
, m
, msz
, p
, n
, nb
, earg
);
227 return (d ?
rsa_privop(rp
, d
, d
) : 0);
230 /* --- @rsa_decrypt@ --- *
232 * Arguments: @rsa_privctx *rp@ = pointer to an RSA private key context
233 * @mp *m@ = encrypted message, as a multiprecision integer
234 * @dstr *d@ = pointer to output string
235 * @rsa_decunpad *e@ = decoding procedure
236 * @void *earg@ = argument pointer for decoding procedure
238 * Returns: The length of the output string if successful, negative on
241 * Use: Does RSA decryption.
244 int rsa_decrypt(rsa_privctx
*rp
, mp
*m
, dstr
*d
,
245 rsa_decunpad
*e
, void *earg
)
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;
253 rc
= e(p
, (octet
*)d
->buf
+ d
->len
, n
, nb
, earg
);
260 /*----- That's all, folks -------------------------------------------------*/