Subversion Repositories planix.SVN

Rev

Rev 33 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 - 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 
}