1*8ccd4a63SDavid du Colombier #include "os.h"
2*8ccd4a63SDavid du Colombier #include <mp.h>
3*8ccd4a63SDavid du Colombier #include <libsec.h>
4*8ccd4a63SDavid du Colombier
5*8ccd4a63SDavid du Colombier // decrypt rsa using garner's algorithm for the chinese remainder theorem
6*8ccd4a63SDavid du Colombier // seminumerical algorithms, knuth, pp 253-254
7*8ccd4a63SDavid du Colombier // applied cryptography, menezes et al, pg 612
8*8ccd4a63SDavid du Colombier mpint*
rsadecrypt(RSApriv * rsa,mpint * in,mpint * out)9*8ccd4a63SDavid du Colombier rsadecrypt(RSApriv *rsa, mpint *in, mpint *out)
10*8ccd4a63SDavid du Colombier {
11*8ccd4a63SDavid du Colombier mpint *v1, *v2;
12*8ccd4a63SDavid du Colombier
13*8ccd4a63SDavid du Colombier if(out == nil)
14*8ccd4a63SDavid du Colombier out = mpnew(0);
15*8ccd4a63SDavid du Colombier
16*8ccd4a63SDavid du Colombier // convert in to modular representation
17*8ccd4a63SDavid du Colombier v1 = mpnew(0);
18*8ccd4a63SDavid du Colombier mpmod(in, rsa->p, v1);
19*8ccd4a63SDavid du Colombier v2 = mpnew(0);
20*8ccd4a63SDavid du Colombier mpmod(in, rsa->q, v2);
21*8ccd4a63SDavid du Colombier
22*8ccd4a63SDavid du Colombier // exponentiate the modular rep
23*8ccd4a63SDavid du Colombier mpexp(v1, rsa->kp, rsa->p, v1);
24*8ccd4a63SDavid du Colombier mpexp(v2, rsa->kq, rsa->q, v2);
25*8ccd4a63SDavid du Colombier
26*8ccd4a63SDavid du Colombier // out = v1 + p*((v2-v1)*c2 mod q)
27*8ccd4a63SDavid du Colombier mpsub(v2, v1, v2);
28*8ccd4a63SDavid du Colombier mpmul(v2, rsa->c2, v2);
29*8ccd4a63SDavid du Colombier mpmod(v2, rsa->q, v2);
30*8ccd4a63SDavid du Colombier mpmul(v2, rsa->p, out);
31*8ccd4a63SDavid du Colombier mpadd(v1, out, out);
32*8ccd4a63SDavid du Colombier
33*8ccd4a63SDavid du Colombier mpfree(v1);
34*8ccd4a63SDavid du Colombier mpfree(v2);
35*8ccd4a63SDavid du Colombier
36*8ccd4a63SDavid du Colombier return out;
37*8ccd4a63SDavid du Colombier }
38