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*
crtpre(int n,mpint ** m)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
crtprefree(CRTpre * crt)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*
crtin(CRTpre * crt,mpint * x)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
crtout(CRTpre * crt,CRTres * res,mpint * x)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
crtresfree(CRTres * res)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 }
123