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