1 b3f61791 2004-03-21 devnull #include "os.h"
2 b3f61791 2004-03-21 devnull #include <mp.h>
3 b3f61791 2004-03-21 devnull #include <libsec.h>
5 b3f61791 2004-03-21 devnull // chinese remainder theorem
7 b3f61791 2004-03-21 devnull // handbook of applied cryptography, menezes et al, 1997, pp 610 - 613
9 b3f61791 2004-03-21 devnull struct CRTpre
11 b3f61791 2004-03-21 devnull int n; // number of moduli
12 b3f61791 2004-03-21 devnull mpint **m; // pointer to moduli
13 b3f61791 2004-03-21 devnull mpint **c; // precomputed coefficients
14 b3f61791 2004-03-21 devnull mpint **p; // precomputed products
15 b3f61791 2004-03-21 devnull mpint *a[1]; // local storage
18 b3f61791 2004-03-21 devnull // setup crt info, returns a newly created structure
20 b3f61791 2004-03-21 devnull crtpre(int n, mpint **m)
22 b3f61791 2004-03-21 devnull CRTpre *crt;
23 b3f61791 2004-03-21 devnull int i, j;
24 b3f61791 2004-03-21 devnull mpint *u;
26 b3f61791 2004-03-21 devnull crt = malloc(sizeof(CRTpre)+sizeof(mpint)*3*n);
27 b3f61791 2004-03-21 devnull if(crt == nil)
28 b3f61791 2004-03-21 devnull sysfatal("crtpre: %r");
29 b3f61791 2004-03-21 devnull crt->m = crt->a;
30 b3f61791 2004-03-21 devnull crt->c = crt->a+n;
31 b3f61791 2004-03-21 devnull crt->p = crt->c+n;
32 b3f61791 2004-03-21 devnull crt->n = n;
34 b3f61791 2004-03-21 devnull // make a copy of the moduli
35 b3f61791 2004-03-21 devnull for(i = 0; i < n; i++)
36 b3f61791 2004-03-21 devnull crt->m[i] = mpcopy(m[i]);
38 b3f61791 2004-03-21 devnull // precompute the products
39 b3f61791 2004-03-21 devnull u = mpcopy(mpone);
40 b3f61791 2004-03-21 devnull for(i = 0; i < n; i++){
41 b3f61791 2004-03-21 devnull mpmul(u, m[i], u);
42 b3f61791 2004-03-21 devnull crt->p[i] = mpcopy(u);
45 b3f61791 2004-03-21 devnull // precompute the coefficients
46 b3f61791 2004-03-21 devnull for(i = 1; i < n; i++){
47 b3f61791 2004-03-21 devnull crt->c[i] = mpcopy(mpone);
48 b3f61791 2004-03-21 devnull for(j = 0; j < i; j++){
49 b3f61791 2004-03-21 devnull mpinvert(m[j], m[i], u);
50 b3f61791 2004-03-21 devnull mpmul(u, crt->c[i], u);
51 b3f61791 2004-03-21 devnull mpmod(u, m[i], crt->c[i]);
55 b3f61791 2004-03-21 devnull mpfree(u);
57 b3f61791 2004-03-21 devnull return crt;
61 b3f61791 2004-03-21 devnull crtprefree(CRTpre *crt)
65 b3f61791 2004-03-21 devnull for(i = 0; i < crt->n; i++){
66 b3f61791 2004-03-21 devnull if(i != 0)
67 b3f61791 2004-03-21 devnull mpfree(crt->c[i]);
68 b3f61791 2004-03-21 devnull mpfree(crt->p[i]);
69 b3f61791 2004-03-21 devnull mpfree(crt->m[i]);
71 b3f61791 2004-03-21 devnull free(crt);
74 b3f61791 2004-03-21 devnull // convert to residues, returns a newly created structure
76 b3f61791 2004-03-21 devnull crtin(CRTpre *crt, mpint *x)
79 b3f61791 2004-03-21 devnull CRTres *res;
81 b3f61791 2004-03-21 devnull res = malloc(sizeof(CRTres)+sizeof(mpint)*crt->n);
82 b3f61791 2004-03-21 devnull if(res == nil)
83 b3f61791 2004-03-21 devnull sysfatal("crtin: %r");
84 b3f61791 2004-03-21 devnull res->n = crt->n;
85 b3f61791 2004-03-21 devnull for(i = 0; i < res->n; i++){
86 b3f61791 2004-03-21 devnull res->r[i] = mpnew(0);
87 b3f61791 2004-03-21 devnull mpmod(x, crt->m[i], res->r[i]);
89 b3f61791 2004-03-21 devnull return res;
92 b3f61791 2004-03-21 devnull // garners algorithm for converting residue form to linear
94 b3f61791 2004-03-21 devnull crtout(CRTpre *crt, CRTres *res, mpint *x)
96 b3f61791 2004-03-21 devnull mpint *u;
99 b3f61791 2004-03-21 devnull u = mpnew(0);
100 b3f61791 2004-03-21 devnull mpassign(res->r[0], x);
102 b3f61791 2004-03-21 devnull for(i = 1; i < crt->n; i++){
103 b3f61791 2004-03-21 devnull mpsub(res->r[i], x, u);
104 b3f61791 2004-03-21 devnull mpmul(u, crt->c[i], u);
105 b3f61791 2004-03-21 devnull mpmod(u, crt->m[i], u);
106 b3f61791 2004-03-21 devnull mpmul(u, crt->p[i-1], u);
107 b3f61791 2004-03-21 devnull mpadd(x, u, x);
110 b3f61791 2004-03-21 devnull mpfree(u);
113 b3f61791 2004-03-21 devnull // free the residue
115 b3f61791 2004-03-21 devnull crtresfree(CRTres *res)
119 b3f61791 2004-03-21 devnull for(i = 0; i < res->n; i++)
120 b3f61791 2004-03-21 devnull mpfree(res->r[i]);
121 b3f61791 2004-03-21 devnull free(res);