1 b3f61791 2004-03-21 devnull #include "os.h"
  2 b3f61791 2004-03-21 devnull #include <mp.h>
  3 b3f61791 2004-03-21 devnull 
  4 cbeb0b26 2006-04-01 devnull /* chinese remainder theorem */
  5 cbeb0b26 2006-04-01 devnull /* */
  6 cbeb0b26 2006-04-01 devnull /* handbook of applied cryptography, menezes et al, 1997, pp 610 - 613 */
  7 b3f61791 2004-03-21 devnull 
  8 b3f61791 2004-03-21 devnull struct CRTpre
  9 b3f61791 2004-03-21 devnull {
 10 cbeb0b26 2006-04-01 devnull 	int	n;		/* number of moduli */
 11 cbeb0b26 2006-04-01 devnull 	mpint	**m;		/* pointer to moduli */
 12 cbeb0b26 2006-04-01 devnull 	mpint	**c;		/* precomputed coefficients */
 13 cbeb0b26 2006-04-01 devnull 	mpint	**p;		/* precomputed products */
 14 cbeb0b26 2006-04-01 devnull 	mpint	*a[1];		/* local storage */
 15 b3f61791 2004-03-21 devnull };
 16 b3f61791 2004-03-21 devnull 
 17 cbeb0b26 2006-04-01 devnull /* setup crt info, returns a newly created structure */
 18 b3f61791 2004-03-21 devnull CRTpre*
 19 b3f61791 2004-03-21 devnull crtpre(int n, mpint **m)
 20 b3f61791 2004-03-21 devnull {
 21 b3f61791 2004-03-21 devnull 	CRTpre *crt;
 22 b3f61791 2004-03-21 devnull 	int i, j;
 23 b3f61791 2004-03-21 devnull 	mpint *u;
 24 b3f61791 2004-03-21 devnull 
 25 b3f61791 2004-03-21 devnull 	crt = malloc(sizeof(CRTpre)+sizeof(mpint)*3*n);
 26 b3f61791 2004-03-21 devnull 	if(crt == nil)
 27 b3f61791 2004-03-21 devnull 		sysfatal("crtpre: %r");
 28 b3f61791 2004-03-21 devnull 	crt->m = crt->a;
 29 b3f61791 2004-03-21 devnull 	crt->c = crt->a+n;
 30 b3f61791 2004-03-21 devnull 	crt->p = crt->c+n;
 31 b3f61791 2004-03-21 devnull 	crt->n = n;
 32 b3f61791 2004-03-21 devnull 
 33 cbeb0b26 2006-04-01 devnull 	/* make a copy of the moduli */
 34 b3f61791 2004-03-21 devnull 	for(i = 0; i < n; i++)
 35 b3f61791 2004-03-21 devnull 		crt->m[i] = mpcopy(m[i]);
 36 b3f61791 2004-03-21 devnull 
 37 cbeb0b26 2006-04-01 devnull 	/* precompute the products */
 38 b3f61791 2004-03-21 devnull 	u = mpcopy(mpone);
 39 b3f61791 2004-03-21 devnull 	for(i = 0; i < n; i++){
 40 b3f61791 2004-03-21 devnull 		mpmul(u, m[i], u);
 41 b3f61791 2004-03-21 devnull 		crt->p[i] = mpcopy(u);
 42 b3f61791 2004-03-21 devnull 	}
 43 b3f61791 2004-03-21 devnull 
 44 cbeb0b26 2006-04-01 devnull 	/* precompute the coefficients */
 45 b3f61791 2004-03-21 devnull 	for(i = 1; i < n; i++){
 46 b3f61791 2004-03-21 devnull 		crt->c[i] = mpcopy(mpone);
 47 b3f61791 2004-03-21 devnull 		for(j = 0; j < i; j++){
 48 b3f61791 2004-03-21 devnull 			mpinvert(m[j], m[i], u);
 49 b3f61791 2004-03-21 devnull 			mpmul(u, crt->c[i], u);
 50 b3f61791 2004-03-21 devnull 			mpmod(u, m[i], crt->c[i]);
 51 b3f61791 2004-03-21 devnull 		}
 52 b3f61791 2004-03-21 devnull 	}
 53 b3f61791 2004-03-21 devnull 
 54 b3f61791 2004-03-21 devnull 	mpfree(u);
 55 b3f61791 2004-03-21 devnull 
 56 fa325e9b 2020-01-10 cross 	return crt;
 57 b3f61791 2004-03-21 devnull }
 58 b3f61791 2004-03-21 devnull 
 59 b3f61791 2004-03-21 devnull void
 60 b3f61791 2004-03-21 devnull crtprefree(CRTpre *crt)
 61 b3f61791 2004-03-21 devnull {
 62 b3f61791 2004-03-21 devnull 	int i;
 63 b3f61791 2004-03-21 devnull 
 64 b3f61791 2004-03-21 devnull 	for(i = 0; i < crt->n; i++){
 65 b3f61791 2004-03-21 devnull 		if(i != 0)
 66 b3f61791 2004-03-21 devnull 			mpfree(crt->c[i]);
 67 b3f61791 2004-03-21 devnull 		mpfree(crt->p[i]);
 68 b3f61791 2004-03-21 devnull 		mpfree(crt->m[i]);
 69 b3f61791 2004-03-21 devnull 	}
 70 b3f61791 2004-03-21 devnull 	free(crt);
 71 b3f61791 2004-03-21 devnull }
 72 b3f61791 2004-03-21 devnull 
 73 cbeb0b26 2006-04-01 devnull /* convert to residues, returns a newly created structure */
 74 b3f61791 2004-03-21 devnull CRTres*
 75 b3f61791 2004-03-21 devnull crtin(CRTpre *crt, mpint *x)
 76 b3f61791 2004-03-21 devnull {
 77 b3f61791 2004-03-21 devnull 	int i;
 78 b3f61791 2004-03-21 devnull 	CRTres *res;
 79 b3f61791 2004-03-21 devnull 
 80 b3f61791 2004-03-21 devnull 	res = malloc(sizeof(CRTres)+sizeof(mpint)*crt->n);
 81 b3f61791 2004-03-21 devnull 	if(res == nil)
 82 b3f61791 2004-03-21 devnull 		sysfatal("crtin: %r");
 83 b3f61791 2004-03-21 devnull 	res->n = crt->n;
 84 b3f61791 2004-03-21 devnull 	for(i = 0; i < res->n; i++){
 85 b3f61791 2004-03-21 devnull 		res->r[i] = mpnew(0);
 86 b3f61791 2004-03-21 devnull 		mpmod(x, crt->m[i], res->r[i]);
 87 b3f61791 2004-03-21 devnull 	}
 88 b3f61791 2004-03-21 devnull 	return res;
 89 b3f61791 2004-03-21 devnull }
 90 b3f61791 2004-03-21 devnull 
 91 cbeb0b26 2006-04-01 devnull /* garners algorithm for converting residue form to linear */
 92 b3f61791 2004-03-21 devnull void
 93 b3f61791 2004-03-21 devnull crtout(CRTpre *crt, CRTres *res, mpint *x)
 94 b3f61791 2004-03-21 devnull {
 95 b3f61791 2004-03-21 devnull 	mpint *u;
 96 b3f61791 2004-03-21 devnull 	int i;
 97 b3f61791 2004-03-21 devnull 
 98 b3f61791 2004-03-21 devnull 	u = mpnew(0);
 99 b3f61791 2004-03-21 devnull 	mpassign(res->r[0], x);
100 b3f61791 2004-03-21 devnull 
101 b3f61791 2004-03-21 devnull 	for(i = 1; i < crt->n; i++){
102 b3f61791 2004-03-21 devnull 		mpsub(res->r[i], x, u);
103 b3f61791 2004-03-21 devnull 		mpmul(u, crt->c[i], u);
104 b3f61791 2004-03-21 devnull 		mpmod(u, crt->m[i], u);
105 b3f61791 2004-03-21 devnull 		mpmul(u, crt->p[i-1], u);
106 b3f61791 2004-03-21 devnull 		mpadd(x, u, x);
107 b3f61791 2004-03-21 devnull 	}
108 b3f61791 2004-03-21 devnull 
109 b3f61791 2004-03-21 devnull 	mpfree(u);
110 b3f61791 2004-03-21 devnull }
111 b3f61791 2004-03-21 devnull 
112 cbeb0b26 2006-04-01 devnull /* free the residue */
113 b3f61791 2004-03-21 devnull void
114 b3f61791 2004-03-21 devnull crtresfree(CRTres *res)
115 b3f61791 2004-03-21 devnull {
116 b3f61791 2004-03-21 devnull 	int i;
117 b3f61791 2004-03-21 devnull 
118 b3f61791 2004-03-21 devnull 	for(i = 0; i < res->n; i++)
119 b3f61791 2004-03-21 devnull 		mpfree(res->r[i]);
120 b3f61791 2004-03-21 devnull 	free(res);
121 b3f61791 2004-03-21 devnull }