This is an automated email from the ASF dual-hosted git repository. sandreoli pushed a commit to branch review-bls in repository https://gitbox.apache.org/repos/asf/incubator-milagro-crypto-c.git
commit 744038458d21f5a18e3c15f1b5e9e39b486eaec4 Merge: a4d9072 520a180 Author: samuele-andreoli <[email protected]> AuthorDate: Mon Nov 18 17:12:03 2019 +0000 Merge branch 'develop' into review-bls VERSION | 2 +- examples/example_bls_ZZZ.c.in | 39 +++++++++++++++++++++++---------------- examples/example_bls_sss_ZZZ.c.in | 13 ++++++++----- include/bls.h.in | 8 ++++---- include/bls192.h.in | 8 ++++---- include/bls256.h.in | 8 ++++---- src/bls.c.in | 23 ++++++++++++++--------- src/bls192.c.in | 23 ++++++++++++++--------- src/bls256.c.in | 23 ++++++++++++++--------- test/test_bls_ZZZ.c.in | 34 +++++++++++++++++++--------------- test/test_bls_sss_ZZZ.c.in | 11 ++++++----- 11 files changed, 111 insertions(+), 81 deletions(-) diff --cc src/bls.c.in index 29ee66a,2faf5e7..94e6061 --- a/src/bls.c.in +++ b/src/bls.c.in @@@ -38,64 -39,52 +38,65 @@@ static void recover_coefficients(int k BIG_XXX_fromBytes(x2[i],X[i].val); } + // Compute numerators in place using partial products + // to achieve it in O(n) + // c_i = x_0 * ... * x_(i-1) * x_(i+1) * ... * x_(k-1) + + // Compute partial left products + // leave c_0 alone since it only has a right partial product + BIG_XXX_copy(coefs[1], x2[0]); + + for(int i=2; i < k; i++) + { + // lp_i = x_0 * ... * x_(i-1) = lp_(i-1) * x_(i-1) + BIG_XXX_modmul(coefs[i], coefs[i-1], x2[i-1], r); + } + + // Compute partial right products and combine + + // Store partial right products in c_0 so at the end + // of the procedure c_0 = x_1 * ... x_(k-1) + BIG_XXX_copy(coefs[0], x2[k-1]); + + for(int i=k-2; i > 0; i--) + { + // c_i = lp_i * rp_i + BIG_XXX_modmul(coefs[i], coefs[i], coefs[0], r); + + // rp_(i-1) = x_i * ... * x_k = x_i * rp_i + BIG_XXX_modmul(coefs[0], coefs[0], x2[i], r); + } + + BIG_XXX cneg; + BIG_XXX denominator; + BIG_XXX s; + for(int i=0; i<k; i++) { - BIG_XXX numerator; - BIG_XXX_one(numerator); - BIG_XXX denominator; BIG_XXX_one(denominator); + + // cneg = -x_i mod r + BIG_XXX_sub(cneg, r, x2[i]); + for(int j=0; j<k; j++) { - // others = all - current - // current = x2[i] if (i != j) { - // numerator = numerator * other - BIG_XXX_modmul(numerator,numerator,x2[j],r); - - // other - current - BIG_XXX s; - BIG_XXX c; - - // c = -current - BIG_XXX_sub(c,r,x2[i]); - BIG_XXX_add(s,x2[j],c); - - // denominator = denominator * s + // denominator = denominator * (x_j - x_i) + BIG_XXX_add(s,x2[j],cneg); BIG_XXX_modmul(denominator,denominator,s,r); - } - } - BIG_XXX_moddiv(coefs[i], numerator, denominator, r); - } - // Output coefficients - for(int i=0; i<k; i++) - { - BIG_XXX_toBytes(COEFS[i].val,coefs[i]); + BIG_XXX_moddiv(coefs[i], coefs[i], denominator, r); } - return 0; - } - /* hash a message to an ECP point, using SHA3 */ - static void BLS_HASHIT(ECP_ZZZ *P,char *m) + /* hash a message, M, to an ECP point, using SHA3 */ + static void BLS_HASHIT(ECP_ZZZ *P,octet *M) { int i; + int j; sha3 hs; char h[MODBYTES_XXX]; octet HM= {0,sizeof(h),h}; diff --cc src/bls192.c.in index 30fabb5,29b8363..6058456 --- a/src/bls192.c.in +++ b/src/bls192.c.in @@@ -38,64 -39,52 +38,65 @@@ static void recover_coefficients(int k BIG_XXX_fromBytes(x2[i],X[i].val); } + // Compute numerators in place using partial products + // to achieve it in O(n) + // c_i = x_0 * ... * x_(i-1) * x_(i+1) * ... * x_(k-1) + + // Compute partial left products + // leave c_0 alone since it only has a right partial product + BIG_XXX_copy(coefs[1], x2[0]); + + for(int i=2; i < k; i++) + { + // lp_i = x_0 * ... * x_(i-1) = lp_(i-1) * x_(i-1) + BIG_XXX_modmul(coefs[i], coefs[i-1], x2[i-1], r); + } + + // Compute partial right products and combine + + // Store partial right products in c_0 so at the end + // of the procedure c_0 = x_1 * ... x_(k-1) + BIG_XXX_copy(coefs[0], x2[k-1]); + + for(int i=k-2; i > 0; i--) + { + // c_i = lp_i * rp_i + BIG_XXX_modmul(coefs[i], coefs[i], coefs[0], r); + + // rp_(i-1) = x_i * ... * x_k = x_i * rp_i + BIG_XXX_modmul(coefs[0], coefs[0], x2[i], r); + } + + BIG_XXX cneg; + BIG_XXX denominator; + BIG_XXX s; + for(int i=0; i<k; i++) { - BIG_XXX numerator; - BIG_XXX_one(numerator); - BIG_XXX denominator; BIG_XXX_one(denominator); + + // cneg = -x_i mod r + BIG_XXX_sub(cneg, r, x2[i]); + for(int j=0; j<k; j++) { - // others = all - current - // current = x2[i] if (i != j) { - // numerator = numerator * other - BIG_XXX_modmul(numerator,numerator,x2[j],r); - - // other - current - BIG_XXX s; - BIG_XXX c; - - // c = -current - BIG_XXX_sub(c,r,x2[i]); - BIG_XXX_add(s,x2[j],c); - - // denominator = denominator * s + // denominator = denominator * (x_j - x_i) + BIG_XXX_add(s,x2[j],cneg); BIG_XXX_modmul(denominator,denominator,s,r); - } - } - BIG_XXX_moddiv(coefs[i], numerator, denominator, r); - } - // Output coefficients - for(int i=0; i<k; i++) - { - BIG_XXX_toBytes(COEFS[i].val,coefs[i]); + BIG_XXX_moddiv(coefs[i], coefs[i], denominator, r); } - return 0; - } - /* hash a message to an ECP point, using SHA3 */ - static void BLS_HASHIT(ECP_ZZZ *P,char *m) + /* hash a message, M, to an ECP point, using SHA3 */ + static void BLS_HASHIT(ECP_ZZZ *P,octet *M) { int i; + int j; sha3 hs; char h[MODBYTES_XXX]; octet HM= {0,sizeof(h),h}; diff --cc src/bls256.c.in index fad2c9c,a6f2a48..43a90ad --- a/src/bls256.c.in +++ b/src/bls256.c.in @@@ -38,64 -39,52 +38,65 @@@ static void recover_coefficients(int k BIG_XXX_fromBytes(x2[i],X[i].val); } + // Compute numerators in place using partial products + // to achieve it in O(n) + // c_i = x_0 * ... * x_(i-1) * x_(i+1) * ... * x_(k-1) + + // Compute partial left products + // leave c_0 alone since it only has a right partial product + BIG_XXX_copy(coefs[1], x2[0]); + + for(int i=2; i < k; i++) + { + // lp_i = x_0 * ... * x_(i-1) = lp_(i-1) * x_(i-1) + BIG_XXX_modmul(coefs[i], coefs[i-1], x2[i-1], r); + } + + // Compute partial right products and combine + + // Store partial right products in c_0 so at the end + // of the procedure c_0 = x_1 * ... x_(k-1) + BIG_XXX_copy(coefs[0], x2[k-1]); + + for(int i=k-2; i > 0; i--) + { + // c_i = lp_i * rp_i + BIG_XXX_modmul(coefs[i], coefs[i], coefs[0], r); + + // rp_(i-1) = x_i * ... * x_k = x_i * rp_i + BIG_XXX_modmul(coefs[0], coefs[0], x2[i], r); + } + + BIG_XXX cneg; + BIG_XXX denominator; + BIG_XXX s; + for(int i=0; i<k; i++) { - BIG_XXX numerator; - BIG_XXX_one(numerator); - BIG_XXX denominator; BIG_XXX_one(denominator); + + // cneg = -x_i mod r + BIG_XXX_sub(cneg, r, x2[i]); + for(int j=0; j<k; j++) { - // others = all - current - // current = x2[i] if (i != j) { - // numerator = numerator * other - BIG_XXX_modmul(numerator,numerator,x2[j],r); - - // other - current - BIG_XXX s; - BIG_XXX c; - - // c = -current - BIG_XXX_sub(c,r,x2[i]); - BIG_XXX_add(s,x2[j],c); - - // denominator = denominator * s + // denominator = denominator * (x_j - x_i) + BIG_XXX_add(s,x2[j],cneg); BIG_XXX_modmul(denominator,denominator,s,r); - } - } - BIG_XXX_moddiv(coefs[i], numerator, denominator, r); - } - // Output coefficients - for(int i=0; i<k; i++) - { - BIG_XXX_toBytes(COEFS[i].val,coefs[i]); + BIG_XXX_moddiv(coefs[i], coefs[i], denominator, r); } - return 0; - } - /* hash a message to an ECP point, using SHA3 */ - static void BLS_HASHIT(ECP_ZZZ *P,char *m) + /* hash a message, M, to an ECP point, using SHA3 */ + static void BLS_HASHIT(ECP_ZZZ *P,octet *M) { int i; + int j; sha3 hs; char h[MODBYTES_XXX]; octet HM= {0,sizeof(h),h};
