You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@milagro.apache.org by sa...@apache.org on 2020/02/03 17:09:34 UTC
[incubator-milagro-crypto-c] 01/01: Add support for non constant
time multiple exponentiation
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 <sa...@yahoo.it>
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);
}