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 } 123