This is an automated email from the ASF dual-hosted git repository. sandreoli pushed a commit to branch add-multiple-exponent-api in repository https://gitbox.apache.org/repos/asf/incubator-milagro-crypto-c.git
commit 6b8acfae014308a1e3e12a17430b989d85753d6b Author: Samuele Andreoli <[email protected]> AuthorDate: Mon Feb 3 17:08:59 2020 +0000 Add support for non constant time multiple exponentiation --- include/ff.h.in | 42 ++++++++++++++++++++ src/ff.c.in | 83 +++++++++++++++++++++++++++++++++++++++ test/test_ff_consistency_WWW.c.in | 57 ++++++++++++++++++++++++++- 3 files changed, 181 insertions(+), 1 deletion(-) diff --git a/include/ff.h.in b/include/ff.h.in index 043acc6..7096162 100644 --- a/include/ff.h.in +++ b/include/ff.h.in @@ -295,6 +295,48 @@ extern void FF_WWW_pow(BIG_XXX *r,BIG_XXX *x,BIG_XXX *e,BIG_XXX *p,int n); @param n size of FF in BIGs */ extern void FF_WWW_pow2(BIG_XXX *r,BIG_XXX *x,BIG_XXX e,BIG_XXX *y,BIG_XXX f,BIG_XXX *m,int n); +/** @brief Calculate r=x^e.y^f mod p. Faster but non constant time + * + @param r FF instance, on exit = x^e.y^f mod p + @param x FF instance + @param e BIG exponent + @param y FF instance + @param f BIG exponent + @param p FF modulus + @param n size of FF in BIGs + @param en size of exponent in BIGs + */ +void FF_WWW_bpow2(BIG_XXX *r,BIG_XXX *x,BIG_XXX *e, BIG_XXX *y, BIG_XXX *f, BIG_XXX *p,int n, int en); +/** @brief Calculate r=x^e.y^f.z^g mod p. Faster but non constant time + * + @param r FF instance, on exit = x^e.y^f.z^g mod p + @param x FF instance + @param e BIG exponent + @param y FF instance + @param f BIG exponent + @param z FF instance + @param g BIG exponent + @param p FF modulus + @param n size of FF in BIGs + @param en size of exponent in BIGs + */ +void FF_WWW_pow3(BIG_XXX *r,BIG_XXX *x,BIG_XXX *e, BIG_XXX *y, BIG_XXX *f, BIG_XXX *z, BIG_XXX *g, BIG_XXX *p, int n, int en); +/** @brief Calculate r=x^e.y^f.z^g.w^h mod p. Faster but non constant time + * + @param r FF instance, on exit = x^e.y^f.z^g.w^h mod p + @param x FF instance + @param e BIG exponent + @param y FF instance + @param f BIG exponent + @param z FF instance + @param g BIG exponent + @param w FF instance + @param h BIG exponent + @param p FF modulus + @param n size of FF in BIGs + @param en size of exponent in BIGs + */ +extern void FF_WWW_pow4(BIG_XXX *r,BIG_XXX *x,BIG_XXX *e, BIG_XXX *y, BIG_XXX *f, BIG_XXX *z, BIG_XXX *g, BIG_XXX *w, BIG_XXX *h, BIG_XXX *p, int n, int en); /** @brief Test if an FF has factor in common with integer s * @param x FF instance to be tested diff --git a/src/ff.c.in b/src/ff.c.in index e1eada0..2ce8da1 100644 --- a/src/ff.c.in +++ b/src/ff.c.in @@ -963,6 +963,89 @@ void FF_WWW_pow2(BIG_XXX r[],BIG_XXX x[],BIG_XXX e,BIG_XXX y[],BIG_XXX f,BIG_XXX FF_WWW_redc(r,p,ND,n); } +/* Compute prod(x_i^e_i) mod p. Faster but not constant time */ +void FF_WWW_pown(BIG_XXX *r, BIG_XXX *x[], BIG_XXX *e[], BIG_XXX *p, int xlen, int elen, int n) +{ +#ifndef C99 + BIG_XXX products[15][FFLEN_WWW], ND[FFLEN_WWW]; +#else + BIG_XXX products[(1<<n)-1][xlen], ND[xlen]; +#endif + + int i, j, b; + + FF_WWW_invmod2m(ND, p, xlen); + + // Precompute the possible products between the bases + for (i = 1; i < (1<<n); i++) + { + // Select less significant non zero bit + for (j = 0; (i & (1<<j)) == 0; j++); + b = 1 << j; + + if (i == b) + { + // case 0..010..0. It identifies one of the bases + FF_WWW_copy(products[i-1], x[j], xlen); + FF_WWW_nres(products[i-1], p, xlen); + } + else + { + // Split into b and i-b. Both are already computed since 0 < b < i + FF_WWW_modmul(products[i-1], products[i-b-1], products[b-1], p, ND, xlen); + } + } + + FF_WWW_one(r, xlen); + FF_WWW_nres(r, p, xlen); + + // Compute final result using a simple square and multiply + for (i = 8 * MODBYTES_XXX * elen - 1; i >= 0; i--) + { + FF_WWW_modsqr(r,r,p,ND,xlen); + + // Build the index for the product using the exponent bit + // for each of the bases, from last to first + b = 0; + for (j = n; j > 0; j--) + { + b<<=1; + b+=BIG_XXX_bit(e[j-1][i/BIGBITS_XXX], i%BIGBITS_XXX); + } + + if (b != 0) + { + FF_WWW_modmul(r, r, products[b-1], p, ND, xlen); + } + } + + FF_WWW_redc(r, p, ND, xlen); +} + +void FF_WWW_bpow2(BIG_XXX *r,BIG_XXX *x,BIG_XXX *e, BIG_XXX *y, BIG_XXX *f, BIG_XXX *p,int n, int en) +{ + BIG_XXX *x_s[] = {x,y}; + BIG_XXX *e_s[] = {e,f}; + + FF_WWW_pown(r, x_s, e_s, p, n, en, 2); +} + +void FF_WWW_pow3(BIG_XXX *r,BIG_XXX *x,BIG_XXX *e, BIG_XXX *y, BIG_XXX *f, BIG_XXX *z, BIG_XXX *g, BIG_XXX *p, int n, int en) +{ + BIG_XXX *x_s[] = {x,y,z}; + BIG_XXX *e_s[] = {e,f,g}; + + FF_WWW_pown(r, x_s, e_s, p, n, en, 3); +} + +void FF_WWW_pow4(BIG_XXX *r,BIG_XXX *x,BIG_XXX *e, BIG_XXX *y, BIG_XXX *f, BIG_XXX *z, BIG_XXX *g, BIG_XXX *w, BIG_XXX *h, BIG_XXX *p, int n, int en) +{ + BIG_XXX *x_s[] = {x,y,z,w}; + BIG_XXX *e_s[] = {e,f,g,h}; + + FF_WWW_pown(r, x_s, e_s, p, n, en, 4); +} + static sign32 igcd(sign32 x,sign32 y) { /* integer GCD, returns GCD of x and y */ diff --git a/test/test_ff_consistency_WWW.c.in b/test/test_ff_consistency_WWW.c.in index 12d3a1d..56fa552 100644 --- a/test/test_ff_consistency_WWW.c.in +++ b/test/test_ff_consistency_WWW.c.in @@ -48,7 +48,7 @@ int main() octet OCT = {0,FS_WWW,oct}; BIG_XXX A[HFLEN_WWW], B[HFLEN_WWW], C[HFLEN_WWW], D[HFLEN_WWW]; - BIG_XXX F[FFLEN_WWW], G[FFLEN_WWW], H[FFLEN_WWW], L[FFLEN_WWW], P[FFLEN_WWW], Q[FFLEN_WWW], N[FFLEN_WWW]; + BIG_XXX E[FFLEN_WWW], F[FFLEN_WWW], G[FFLEN_WWW], H[FFLEN_WWW], L[FFLEN_WWW], P[FFLEN_WWW], Q[FFLEN_WWW], N[FFLEN_WWW]; /* Fake random source */ RAND_clean(&RNG); @@ -282,6 +282,61 @@ int main() } } + /* Testing multiple power */ + FF_WWW_random(A, &RNG, HFLEN_WWW); + FF_WWW_random(B, &RNG, HFLEN_WWW); + FF_WWW_random(C, &RNG, HFLEN_WWW); + FF_WWW_random(D, &RNG, HFLEN_WWW); + + FF_WWW_random(E, &RNG, HFLEN_WWW); + FF_WWW_random(F, &RNG, HFLEN_WWW); + FF_WWW_random(G, &RNG, HFLEN_WWW); + FF_WWW_random(H, &RNG, HFLEN_WWW); + +#if WWW == 4096 + // P is too small for dmod if using ff_4096 + FF_WWW_copy(P, N, HFLEN_WWW); +#endif + + FF_WWW_pow(L, A, E, P, HFLEN_WWW); + FF_WWW_pow(N, B, F, P, HFLEN_WWW); + FF_WWW_mul(Q, L, N, HFLEN_WWW); + FF_WWW_dmod(L, Q, P, HFLEN_WWW); + + FF_WWW_bpow2(N, A, E, B, F, P, HFLEN_WWW, HFLEN_WWW); + + if(FF_WWW_comp(N, L, HFLEN_WWW)) + { + printf("ERROR testing bpow2"); + exit(EXIT_FAILURE); + } + + // Test triple exponent + FF_WWW_pow(N, C, G, P, HFLEN_WWW); + FF_WWW_mul(Q, L, N, HFLEN_WWW); + FF_WWW_dmod(L, Q, P, HFLEN_WWW); + + FF_WWW_pow3(N, A, E, B, F, C, G, P, HFLEN_WWW, HFLEN_WWW); + + if(FF_WWW_comp(N, L, HFLEN_WWW)) + { + printf("ERROR testing pow3"); + exit(EXIT_FAILURE); + } + + // Test quadruple exponent + FF_WWW_pow(N, D, H, P, HFLEN_WWW); + FF_WWW_mul(Q, L, N, HFLEN_WWW); + FF_WWW_dmod(L, Q, P, HFLEN_WWW); + + FF_WWW_pow4(N, A, E, B, F, C, G, D, H, P, HFLEN_WWW, HFLEN_WWW); + + if(FF_WWW_comp(N, L, HFLEN_WWW)) + { + printf("ERROR testing pow4"); + exit(EXIT_FAILURE); + } + printf("SUCCESS TEST CONSISTENCY OF FF_WWW PASSED\n"); exit(EXIT_SUCCESS); }
