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