crt.c (2073B)
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 }