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>
  4 b3f61791 2004-03-21 devnull 
  5 b3f61791 2004-03-21 devnull // chinese remainder theorem
  6 b3f61791 2004-03-21 devnull //
  7 b3f61791 2004-03-21 devnull // handbook of applied cryptography, menezes et al, 1997, pp 610 - 613
  8 b3f61791 2004-03-21 devnull 
  9 b3f61791 2004-03-21 devnull struct CRTpre
 10 b3f61791 2004-03-21 devnull {
 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
 16 b3f61791 2004-03-21 devnull };
 17 b3f61791 2004-03-21 devnull 
 18 b3f61791 2004-03-21 devnull // setup crt info, returns a newly created structure
 19 b3f61791 2004-03-21 devnull CRTpre*
 20 b3f61791 2004-03-21 devnull crtpre(int n, mpint **m)
 21 b3f61791 2004-03-21 devnull {
 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;
 25 b3f61791 2004-03-21 devnull 
 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;
 33 b3f61791 2004-03-21 devnull 
 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]);
 37 b3f61791 2004-03-21 devnull 
 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);
 43 b3f61791 2004-03-21 devnull 	}
 44 b3f61791 2004-03-21 devnull 
 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]);
 52 b3f61791 2004-03-21 devnull 		}
 53 b3f61791 2004-03-21 devnull 	}
 54 b3f61791 2004-03-21 devnull 
 55 b3f61791 2004-03-21 devnull 	mpfree(u);
 56 b3f61791 2004-03-21 devnull 
 57 b3f61791 2004-03-21 devnull 	return crt;		
 58 b3f61791 2004-03-21 devnull }
 59 b3f61791 2004-03-21 devnull 
 60 b3f61791 2004-03-21 devnull void
 61 b3f61791 2004-03-21 devnull crtprefree(CRTpre *crt)
 62 b3f61791 2004-03-21 devnull {
 63 b3f61791 2004-03-21 devnull 	int i;
 64 b3f61791 2004-03-21 devnull 
 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]);
 70 b3f61791 2004-03-21 devnull 	}
 71 b3f61791 2004-03-21 devnull 	free(crt);
 72 b3f61791 2004-03-21 devnull }
 73 b3f61791 2004-03-21 devnull 
 74 b3f61791 2004-03-21 devnull // convert to residues, returns a newly created structure
 75 b3f61791 2004-03-21 devnull CRTres*
 76 b3f61791 2004-03-21 devnull crtin(CRTpre *crt, mpint *x)
 77 b3f61791 2004-03-21 devnull {
 78 b3f61791 2004-03-21 devnull 	int i;
 79 b3f61791 2004-03-21 devnull 	CRTres *res;
 80 b3f61791 2004-03-21 devnull 
 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]);
 88 b3f61791 2004-03-21 devnull 	}
 89 b3f61791 2004-03-21 devnull 	return res;
 90 b3f61791 2004-03-21 devnull }
 91 b3f61791 2004-03-21 devnull 
 92 b3f61791 2004-03-21 devnull // garners algorithm for converting residue form to linear
 93 b3f61791 2004-03-21 devnull void
 94 b3f61791 2004-03-21 devnull crtout(CRTpre *crt, CRTres *res, mpint *x)
 95 b3f61791 2004-03-21 devnull {
 96 b3f61791 2004-03-21 devnull 	mpint *u;
 97 b3f61791 2004-03-21 devnull 	int i;
 98 b3f61791 2004-03-21 devnull 
 99 b3f61791 2004-03-21 devnull 	u = mpnew(0);
100 b3f61791 2004-03-21 devnull 	mpassign(res->r[0], x);
101 b3f61791 2004-03-21 devnull 
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);
108 b3f61791 2004-03-21 devnull 	}
109 b3f61791 2004-03-21 devnull 
110 b3f61791 2004-03-21 devnull 	mpfree(u);
111 b3f61791 2004-03-21 devnull }
112 b3f61791 2004-03-21 devnull 
113 b3f61791 2004-03-21 devnull // free the residue
114 b3f61791 2004-03-21 devnull void
115 b3f61791 2004-03-21 devnull crtresfree(CRTres *res)
116 b3f61791 2004-03-21 devnull {
117 b3f61791 2004-03-21 devnull 	int i;
118 b3f61791 2004-03-21 devnull 
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);
122 b3f61791 2004-03-21 devnull }