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 2019/11/18 17:26:06 UTC
[incubator-milagro-crypto-c] branch review-bls updated (a4d9072 ->
7440384)
This is an automated email from the ASF dual-hosted git repository.
sandreoli pushed a change to branch review-bls
in repository https://gitbox.apache.org/repos/asf/incubator-milagro-crypto-c.git.
from a4d9072 remove unnecessary scalar multiplication API
add 3deae89 updated BLS to accept non null terminated input char array
add c854acc update VERSION
add ae66b60 fix doxygen for BLS
add 6faaba4 format code
add 520a180 Merge pull request #54 from apache/issue53
new 7440384 Merge branch 'develop' into review-bls
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
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(-)
[incubator-milagro-crypto-c] 01/01: Merge branch 'develop' into
review-bls
Posted by sa...@apache.org.
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 <sa...@yahoo.it>
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};