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 // chinese remainder theorem
6*8ccd4a63SDavid du Colombier //
7*8ccd4a63SDavid du Colombier // handbook of applied cryptography, menezes et al, 1997, pp 610 - 613
8*8ccd4a63SDavid du Colombier
9*8ccd4a63SDavid du Colombier struct CRTpre
10*8ccd4a63SDavid du Colombier {
11*8ccd4a63SDavid du Colombier int n; // number of moduli
12*8ccd4a63SDavid du Colombier mpint **m; // pointer to moduli
13*8ccd4a63SDavid du Colombier mpint **c; // precomputed coefficients
14*8ccd4a63SDavid du Colombier mpint **p; // precomputed products
15*8ccd4a63SDavid du Colombier mpint *a[1]; // local storage
16*8ccd4a63SDavid du Colombier };
17*8ccd4a63SDavid du Colombier
18*8ccd4a63SDavid du Colombier // setup crt info, returns a newly created structure
19*8ccd4a63SDavid du Colombier CRTpre*
crtpre(int n,mpint ** m)20*8ccd4a63SDavid du Colombier crtpre(int n, mpint **m)
21*8ccd4a63SDavid du Colombier {
22*8ccd4a63SDavid du Colombier CRTpre *crt;
23*8ccd4a63SDavid du Colombier int i, j;
24*8ccd4a63SDavid du Colombier mpint *u;
25*8ccd4a63SDavid du Colombier
26*8ccd4a63SDavid du Colombier crt = malloc(sizeof(CRTpre)+sizeof(mpint)*3*n);
27*8ccd4a63SDavid du Colombier if(crt == nil)
28*8ccd4a63SDavid du Colombier sysfatal("crtpre: %r");
29*8ccd4a63SDavid du Colombier crt->m = crt->a;
30*8ccd4a63SDavid du Colombier crt->c = crt->a+n;
31*8ccd4a63SDavid du Colombier crt->p = crt->c+n;
32*8ccd4a63SDavid du Colombier crt->n = n;
33*8ccd4a63SDavid du Colombier
34*8ccd4a63SDavid du Colombier // make a copy of the moduli
35*8ccd4a63SDavid du Colombier for(i = 0; i < n; i++)
36*8ccd4a63SDavid du Colombier crt->m[i] = mpcopy(m[i]);
37*8ccd4a63SDavid du Colombier
38*8ccd4a63SDavid du Colombier // precompute the products
39*8ccd4a63SDavid du Colombier u = mpcopy(mpone);
40*8ccd4a63SDavid du Colombier for(i = 0; i < n; i++){
41*8ccd4a63SDavid du Colombier mpmul(u, m[i], u);
42*8ccd4a63SDavid du Colombier crt->p[i] = mpcopy(u);
43*8ccd4a63SDavid du Colombier }
44*8ccd4a63SDavid du Colombier
45*8ccd4a63SDavid du Colombier // precompute the coefficients
46*8ccd4a63SDavid du Colombier for(i = 1; i < n; i++){
47*8ccd4a63SDavid du Colombier crt->c[i] = mpcopy(mpone);
48*8ccd4a63SDavid du Colombier for(j = 0; j < i; j++){
49*8ccd4a63SDavid du Colombier mpinvert(m[j], m[i], u);
50*8ccd4a63SDavid du Colombier mpmul(u, crt->c[i], u);
51*8ccd4a63SDavid du Colombier mpmod(u, m[i], crt->c[i]);
52*8ccd4a63SDavid du Colombier }
53*8ccd4a63SDavid du Colombier }
54*8ccd4a63SDavid du Colombier
55*8ccd4a63SDavid du Colombier mpfree(u);
56*8ccd4a63SDavid du Colombier
57*8ccd4a63SDavid du Colombier return crt;
58*8ccd4a63SDavid du Colombier }
59*8ccd4a63SDavid du Colombier
60*8ccd4a63SDavid du Colombier void
crtprefree(CRTpre * crt)61*8ccd4a63SDavid du Colombier crtprefree(CRTpre *crt)
62*8ccd4a63SDavid du Colombier {
63*8ccd4a63SDavid du Colombier int i;
64*8ccd4a63SDavid du Colombier
65*8ccd4a63SDavid du Colombier for(i = 0; i < crt->n; i++){
66*8ccd4a63SDavid du Colombier if(i != 0)
67*8ccd4a63SDavid du Colombier mpfree(crt->c[i]);
68*8ccd4a63SDavid du Colombier mpfree(crt->p[i]);
69*8ccd4a63SDavid du Colombier mpfree(crt->m[i]);
70*8ccd4a63SDavid du Colombier }
71*8ccd4a63SDavid du Colombier free(crt);
72*8ccd4a63SDavid du Colombier }
73*8ccd4a63SDavid du Colombier
74*8ccd4a63SDavid du Colombier // convert to residues, returns a newly created structure
75*8ccd4a63SDavid du Colombier CRTres*
crtin(CRTpre * crt,mpint * x)76*8ccd4a63SDavid du Colombier crtin(CRTpre *crt, mpint *x)
77*8ccd4a63SDavid du Colombier {
78*8ccd4a63SDavid du Colombier int i;
79*8ccd4a63SDavid du Colombier CRTres *res;
80*8ccd4a63SDavid du Colombier
81*8ccd4a63SDavid du Colombier res = malloc(sizeof(CRTres)+sizeof(mpint)*crt->n);
82*8ccd4a63SDavid du Colombier if(res == nil)
83*8ccd4a63SDavid du Colombier sysfatal("crtin: %r");
84*8ccd4a63SDavid du Colombier res->n = crt->n;
85*8ccd4a63SDavid du Colombier for(i = 0; i < res->n; i++){
86*8ccd4a63SDavid du Colombier res->r[i] = mpnew(0);
87*8ccd4a63SDavid du Colombier mpmod(x, crt->m[i], res->r[i]);
88*8ccd4a63SDavid du Colombier }
89*8ccd4a63SDavid du Colombier return res;
90*8ccd4a63SDavid du Colombier }
91*8ccd4a63SDavid du Colombier
92*8ccd4a63SDavid du Colombier // garners algorithm for converting residue form to linear
93*8ccd4a63SDavid du Colombier void
crtout(CRTpre * crt,CRTres * res,mpint * x)94*8ccd4a63SDavid du Colombier crtout(CRTpre *crt, CRTres *res, mpint *x)
95*8ccd4a63SDavid du Colombier {
96*8ccd4a63SDavid du Colombier mpint *u;
97*8ccd4a63SDavid du Colombier int i;
98*8ccd4a63SDavid du Colombier
99*8ccd4a63SDavid du Colombier u = mpnew(0);
100*8ccd4a63SDavid du Colombier mpassign(res->r[0], x);
101*8ccd4a63SDavid du Colombier
102*8ccd4a63SDavid du Colombier for(i = 1; i < crt->n; i++){
103*8ccd4a63SDavid du Colombier mpsub(res->r[i], x, u);
104*8ccd4a63SDavid du Colombier mpmul(u, crt->c[i], u);
105*8ccd4a63SDavid du Colombier mpmod(u, crt->m[i], u);
106*8ccd4a63SDavid du Colombier mpmul(u, crt->p[i-1], u);
107*8ccd4a63SDavid du Colombier mpadd(x, u, x);
108*8ccd4a63SDavid du Colombier }
109*8ccd4a63SDavid du Colombier
110*8ccd4a63SDavid du Colombier mpfree(u);
111*8ccd4a63SDavid du Colombier }
112*8ccd4a63SDavid du Colombier
113*8ccd4a63SDavid du Colombier // free the residue
114*8ccd4a63SDavid du Colombier void
crtresfree(CRTres * res)115*8ccd4a63SDavid du Colombier crtresfree(CRTres *res)
116*8ccd4a63SDavid du Colombier {
117*8ccd4a63SDavid du Colombier int i;
118*8ccd4a63SDavid du Colombier
119*8ccd4a63SDavid du Colombier for(i = 0; i < res->n; i++)
120*8ccd4a63SDavid du Colombier mpfree(res->r[i]);
121*8ccd4a63SDavid du Colombier free(res);
122*8ccd4a63SDavid du Colombier }
123