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