123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122 |
- #include "os.h"
- #include <mp.h>
- #include <libsec.h>
- // chinese remainder theorem
- //
- // handbook of applied cryptography, menezes et al, 1997, pp 610 - 613
- struct CRTpre
- {
- int n; // number of moduli
- mpint **m; // pointer to moduli
- mpint **c; // precomputed coefficients
- mpint **p; // precomputed products
- mpint *a[1]; // local storage
- };
- // setup crt info, returns a newly created structure
- CRTpre*
- crtpre(int n, mpint **m)
- {
- CRTpre *crt;
- int i, j;
- mpint *u;
- crt = malloc(sizeof(CRTpre)+sizeof(mpint)*3*n);
- if(crt == nil)
- sysfatal("crtpre: %r");
- crt->m = crt->a;
- crt->c = crt->a+n;
- crt->p = crt->c+n;
- crt->n = n;
- // make a copy of the moduli
- for(i = 0; i < n; i++)
- crt->m[i] = mpcopy(m[i]);
- // precompute the products
- u = mpcopy(mpone);
- for(i = 0; i < n; i++){
- mpmul(u, m[i], u);
- crt->p[i] = mpcopy(u);
- }
- // precompute the coefficients
- for(i = 1; i < n; i++){
- crt->c[i] = mpcopy(mpone);
- for(j = 0; j < i; j++){
- mpinvert(m[j], m[i], u);
- mpmul(u, crt->c[i], u);
- mpmod(u, m[i], crt->c[i]);
- }
- }
- mpfree(u);
- return crt;
- }
- void
- crtprefree(CRTpre *crt)
- {
- int i;
- for(i = 0; i < crt->n; i++){
- if(i != 0)
- mpfree(crt->c[i]);
- mpfree(crt->p[i]);
- mpfree(crt->m[i]);
- }
- free(crt);
- }
- // convert to residues, returns a newly created structure
- CRTres*
- crtin(CRTpre *crt, mpint *x)
- {
- int i;
- CRTres *res;
- res = malloc(sizeof(CRTres)+sizeof(mpint)*crt->n);
- if(res == nil)
- sysfatal("crtin: %r");
- res->n = crt->n;
- for(i = 0; i < res->n; i++){
- res->r[i] = mpnew(0);
- mpmod(x, crt->m[i], res->r[i]);
- }
- return res;
- }
- // garners algorithm for converting residue form to linear
- void
- crtout(CRTpre *crt, CRTres *res, mpint *x)
- {
- mpint *u;
- int i;
- u = mpnew(0);
- mpassign(res->r[0], x);
- for(i = 1; i < crt->n; i++){
- mpsub(res->r[i], x, u);
- mpmul(u, crt->c[i], u);
- mpmod(u, crt->m[i], u);
- mpmul(u, crt->p[i-1], u);
- mpadd(x, u, x);
- }
- mpfree(u);
- }
- // free the residue
- void
- crtresfree(CRTres *res)
- {
- int i;
- for(i = 0; i < res->n; i++)
- mpfree(res->r[i]);
- free(res);
- }
|