Subversion Repositories planix.SVN

Rev

Rev 2 | Go to most recent revision | 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 
#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 
}