This is an automated email from the ASF dual-hosted git repository. kmccusker pushed a commit to branch update in repository https://gitbox.apache.org/repos/asf/incubator-milagro-crypto.git
commit 6fcc677ec2dac3e54e39219819f441915feb9eb4 Author: Kealan McCusker <[email protected]> AuthorDate: Thu Jun 13 10:26:30 2019 +0100 update code --- version3/c/arch.h | 7 ++---- version3/c/big.c | 14 ++++++++++++ version3/c/big.h | 8 +++++++ version3/c/rom_curve_BN254CX.c | 2 +- version3/cpp/big.cpp | 14 ++++++++++++ version3/cpp/big.h | 8 +++++++ version3/cpp/ecp.cpp | 2 +- version3/cpp/rom_field_NIST521.cpp | 2 +- version3/go/DBIG.go | 11 +++++++++ version3/go/ROM_SECP256K1_64.go | 2 +- version3/java/DBIG32.java | 10 ++++++++ version3/java/DBIG64.java | 10 ++++++++ version3/js/fp.js | 4 ++-- version3/js/fp12.js | 47 +++++++++++++++++++++----------------- version3/readme.txt | 5 ++-- version3/rust/src/dbig.rs | 16 +++++++++++++ version3/rust/src/ecp.rs | 19 +++++---------- version3/rust/src/ecp2.rs | 4 +--- version3/rust/src/fp.rs | 4 +++- version3/swift/dbig.swift | 9 ++++++++ 20 files changed, 146 insertions(+), 52 deletions(-) diff --git a/version3/c/arch.h b/version3/c/arch.h index 1de0332..aa726db 100644 --- a/version3/c/arch.h +++ b/version3/c/arch.h @@ -110,12 +110,9 @@ /**< Note - no 128-bit type available */ #else #define chunk int64_t /**< C type corresponding to word length */ -#ifdef __GNUC__ -#define dchunk __int128 /**< Always define double length chunk type if available - GCC supports 128 bit type ??? */ -#endif -#ifdef __clang__ -#define dchunk __int128 +#if defined(__SIZEOF_INT128__) && __SIZEOF_INT128__ == 16 +#define dchunk __int128 /**< Always define double length chunk type if available (supported by GCC & Clang on 64-bit architectures) */ #endif #endif diff --git a/version3/c/big.c b/version3/c/big.c index 3b1a655..664cccf 100644 --- a/version3/c/big.c +++ b/version3/c/big.c @@ -1466,6 +1466,20 @@ void BIG_XXX_mod2m(BIG_XXX x,int m) for (i=wd+1; i<NLEN_XXX; i++) x[i]=0; } +/* set x = x mod 2^m */ +void BIG_XXX_dmod2m(DBIG_XXX x,int m) +{ + int i,wd,bt; + chunk msk; + BIG_XXX_norm(x); + + wd=m/BASEBITS_XXX; + bt=m%BASEBITS_XXX; + msk=((chunk)1<<bt)-1; + x[wd]&=msk; + for (i=wd+1; i<DNLEN_XXX; i++) x[i]=0; +} + // new /* Convert to DBIG number from byte array of given length */ void BIG_XXX_dfromBytesLen(DBIG_XXX a,char *b,int s) diff --git a/version3/c/big.h b/version3/c/big.h index 36b0c7c..7874450 100644 --- a/version3/c/big.h +++ b/version3/c/big.h @@ -553,6 +553,14 @@ extern void BIG_XXX_invmodp(BIG_XXX x,BIG_XXX y,BIG_XXX n); */ extern void BIG_XXX_mod2m(BIG_XXX x,int m); +/** @brief Calculate x=x mod 2^m + * + Truncation + @param x DBIG number, on reduced mod 2^m + @param m new truncated size +*/ +extern void BIG_XXX_dmod2m(DBIG_XXX x,int m); + /** @brief Calculates a*b+c+*d * Calculate partial product of a.b, add in carry c, and add total to d diff --git a/version3/c/rom_curve_BN254CX.c b/version3/c/rom_curve_BN254CX.c index 4b85d21..5543f54 100644 --- a/version3/c/rom_curve_BN254CX.c +++ b/version3/c/rom_curve_BN254CX.c @@ -58,7 +58,7 @@ const BIG_256_28 CURVE_BB_BN254CX[4][4]= {{{0x32B0CBD,0x11C0A63,0x906CE7E,0xD6EE #if CHUNK==64 const int CURVE_Cof_I_BN254CX= 1; -const int CURVE_A_BN254CX= 1; +const int CURVE_A_BN254CX= 0; const int CURVE_B_I_BN254CX= 2; const BIG_256_56 CURVE_B_BN254CX= {0x2L,0x0L,0x0L,0x0L,0x0L}; const BIG_256_56 CURVE_Order_BN254CX= {0x11C0A636EB1F6DL,0xD6EE0CC906CEBEL,0x647A6366D2C43FL,0x8702A0DB0BDDFL,0x24000000L}; diff --git a/version3/cpp/big.cpp b/version3/cpp/big.cpp index ae72936..761a9bf 100644 --- a/version3/cpp/big.cpp +++ b/version3/cpp/big.cpp @@ -1439,6 +1439,20 @@ void XXX::BIG_mod2m(BIG x,int m) for (i=wd+1; i<NLEN_XXX; i++) x[i]=0; } +/* set x = x mod 2^m */ +void XXX::BIG_dmod2m(DBIG x,int m) +{ + int i,wd,bt; + chunk msk; + BIG_norm(x); + + wd=m/BASEBITS_XXX; + bt=m%BASEBITS_XXX; + msk=((chunk)1<<bt)-1; + x[wd]&=msk; + for (i=wd+1; i<DNLEN_XXX; i++) x[i]=0; +} + // new /* Convert to DBIG number from byte array of given length */ void XXX::BIG_dfromBytesLen(DBIG a,char *b,int s) diff --git a/version3/cpp/big.h b/version3/cpp/big.h index 1f4f451..08c50e3 100644 --- a/version3/cpp/big.h +++ b/version3/cpp/big.h @@ -537,6 +537,14 @@ extern void BIG_invmodp(BIG x,BIG y,BIG n); */ extern void BIG_mod2m(BIG x,int m); +/** @brief Calculate x=x mod 2^m + * + Truncation + @param x DBIG number, on reduced mod 2^m + @param m new truncated size +*/ +extern void BIG_dmod2m(DBIG x,int m); + /** @brief Calculates a*b+c+*d * Calculate partial product of a.b, add in carry c, and add total to d diff --git a/version3/cpp/ecp.cpp b/version3/cpp/ecp.cpp index 020c667..237e04e 100644 --- a/version3/cpp/ecp.cpp +++ b/version3/cpp/ecp.cpp @@ -257,7 +257,7 @@ int ZZZ::ECP_get(BIG x,ECP *P) { ECP W; ECP_copy(&W,P); - ECP_affine(W); + ECP_affine(&W); if (ECP_isinf(&W)) return -1; FP_redc(x,&(W.x)); return 0; diff --git a/version3/cpp/rom_field_NIST521.cpp b/version3/cpp/rom_field_NIST521.cpp index a92393c..2521618 100644 --- a/version3/cpp/rom_field_NIST521.cpp +++ b/version3/cpp/rom_field_NIST521.cpp @@ -23,7 +23,7 @@ const chunk MConst= 0x1; #if CHUNK==64 -using namespace B528_56; +using namespace B528_60; // Base Bits= 60 const BIG Modulus= {0xFFFFFFFFFFFFFFFL,0xFFFFFFFFFFFFFFFL,0xFFFFFFFFFFFFFFFL,0xFFFFFFFFFFFFFFFL,0xFFFFFFFFFFFFFFFL,0xFFFFFFFFFFFFFFFL,0xFFFFFFFFFFFFFFFL,0xFFFFFFFFFFFFFFFL,0x1FFFFFFFFFFL}; diff --git a/version3/go/DBIG.go b/version3/go/DBIG.go index d3afc77..e73ba22 100644 --- a/version3/go/DBIG.go +++ b/version3/go/DBIG.go @@ -169,6 +169,17 @@ func (r *DBIG) shr(k uint) { } } +/* set x = x mod 2^m */ +func (r *BIG) mod2m(m uint) { + wd := int(m / BASEBITS) + bt := m % BASEBITS + msk := (Chunk(1) << bt) - 1 + r.w[wd] &= msk + for i := wd + 1; i < DNLEN; i++ { + r.w[i] = 0 + } +} + /* reduces this DBIG mod a BIG, and returns the BIG */ func (r *DBIG) mod(c *BIG) *BIG { r.norm() diff --git a/version3/go/ROM_SECP256K1_64.go b/version3/go/ROM_SECP256K1_64.go index ef4ae91..1dc205c 100644 --- a/version3/go/ROM_SECP256K1_64.go +++ b/version3/go/ROM_SECP256K1_64.go @@ -19,7 +19,7 @@ under the License. /* Fixed Data in ROM - Field and Curve parameters */ -package NIST256 +package SECP256K1 // Base Bits= 56 diff --git a/version3/java/DBIG32.java b/version3/java/DBIG32.java index c5a6d94..f010f5b 100644 --- a/version3/java/DBIG32.java +++ b/version3/java/DBIG32.java @@ -228,6 +228,16 @@ public class DBIG { return new BIG(this); } + /* set x = x mod 2^m */ + public void mod2m(int m) + { + int i,wd,bt; + wd=m/CONFIG_BIG.BASEBITS; + bt=m%CONFIG_BIG.BASEBITS; + w[wd]&=((cast_to_chunk(1)<<bt)-1); + for (i=wd+1;i<BIG.DNLEN;i++) w[i]=0; + } + /* return this/c */ public BIG div(BIG c) { diff --git a/version3/java/DBIG64.java b/version3/java/DBIG64.java index 473f40b..db1d70e 100644 --- a/version3/java/DBIG64.java +++ b/version3/java/DBIG64.java @@ -226,6 +226,16 @@ public class DBIG { return new BIG(this); } + /* set x = x mod 2^m */ + public void mod2m(int m) + { + int i,wd,bt; + wd=m/CONFIG_BIG.BASEBITS; + bt=m%CONFIG_BIG.BASEBITS; + w[wd]&=((cast_to_chunk(1)<<bt)-1); + for (i=wd+1;i<BIG.DNLEN;i++) w[i]=0; + } + /* return this/c */ public BIG div(BIG c) { diff --git a/version3/js/fp.js b/version3/js/fp.js index 925c20b..8b96743 100644 --- a/version3/js/fp.js +++ b/version3/js/fp.js @@ -31,7 +31,7 @@ var FP = function(ctx) { } else { this.f = new ctx.BIG(x); this.XES = 1; - if (x!=0) + if (!this.f.iszilch()) this.nres(); } }; @@ -185,7 +185,7 @@ var FP = function(ctx) { /* set this=1 */ one: function() { this.f.one(); - return this.nres(); + this.nres(); }, /* normalise this */ diff --git a/version3/js/fp12.js b/version3/js/fp12.js index c68f3cd..45f2595 100644 --- a/version3/js/fp12.js +++ b/version3/js/fp12.js @@ -26,27 +26,32 @@ var FP12 = function(ctx) { /* general purpose constructor */ var FP12 = function(d, e, f) { - if (!isNaN(d)) - { - this.a = new ctx.FP4(d); - this.b = new ctx.FP4(0); - this.c = new ctx.FP4(0); - if (d==1) this.stype=ctx.FP.ONE; - else this.stype=ctx.FP.SPARSER; - } - else - { - if (d instanceof FP12) { - this.a = new ctx.FP4(d.a); - this.b = new ctx.FP4(d.b); - this.c = new ctx.FP4(d.c); - } else { - this.a = new ctx.FP4(d); - this.b = new ctx.FP4(e); - this.c = new ctx.FP4(f); - } - this.stype=ctx.FP.DENSE; - } + if (d instanceof FP12) { + // ignore e, d, which are assumed be undefined in this case + this.a = new ctx.FP4(d.a); + this.b = new ctx.FP4(d.b); + this.c = new ctx.FP4(d.c); + this.stype=ctx.FP.DENSE; + } else if (typeof d !== "undefined" && typeof e !== "undefined" && typeof f !== "undefined") { + // all 3 components set to (can be anything that the FP4 constructor supports) + this.a = new ctx.FP4(d); + this.b = new ctx.FP4(e); + this.c = new ctx.FP4(f); + this.stype=ctx.FP.DENSE; + } else if (typeof d === "number") { + // first component is number + this.a = new ctx.FP4(d); + this.b = new ctx.FP4(0); + this.c = new ctx.FP4(0); + if (d==1) this.stype=ctx.FP.ONE; + else this.stype=ctx.FP.SPARSER; + } else { + // other cases, including `new ctx.FP12()` fall back to zero + this.a = new ctx.FP4(0); + this.b = new ctx.FP4(0); + this.c = new ctx.FP4(0); + this.stype=ctx.FP.ZERO; + } }; FP12.prototype = { diff --git a/version3/readme.txt b/version3/readme.txt index e648fc1..0e3dcd9 100644 --- a/version3/readme.txt +++ b/version3/readme.txt @@ -2,15 +2,14 @@ Several helper programs are provided to assist with the addition of new elliptic curves. Note that these programs will not be needed if using -one of the supported curves. These programs must be build using the MIRACL +one of the supported curves. These programs must be built using the MIRACL library. See source code for compilation instructions bigtobig.cpp - converts to BIG number format check.cpp - checks for optimal choice of number base -bestpair.cpp - finds best BN, BLS12 and BLS24 pairing-friendly curves -(Note - the library does not currently support BLS24 curves) +bestpair.cpp - finds best BN, BLS12, BLS24 and BLS48 pairing-friendly curves romgen.cpp - rough-and-ready program used to help generate ROM files for all of the different languages. diff --git a/version3/rust/src/dbig.rs b/version3/rust/src/dbig.rs index d987d97..353443a 100644 --- a/version3/rust/src/dbig.rs +++ b/version3/rust/src/dbig.rs @@ -22,10 +22,15 @@ use super::big; use super::big::BIG; use super::super::arch::Chunk; +#[derive(Copy)] pub struct DBIG { pub w: [Chunk; big::DNLEN], } +impl Clone for DBIG { + fn clone(&self) -> DBIG { *self } +} + impl DBIG { pub fn new() -> DBIG { DBIG { @@ -243,6 +248,17 @@ impl DBIG { return a; } + /* set x = x mod 2^m */ + pub fn mod2m(&mut self, m: usize) { + let wd = m / big::BASEBITS; + let bt = m % big::BASEBITS; + let msk = (1 << bt) - 1; + self.w[wd] &= msk; + for i in wd + 1..big::DNLEN { + self.w[i] = 0 + } + } + /* return number of bits */ pub fn nbits(&mut self) -> usize { let mut k = big::DNLEN - 1; diff --git a/version3/rust/src/ecp.rs b/version3/rust/src/ecp.rs index a6856a8..9e7b29c 100644 --- a/version3/rust/src/ecp.rs +++ b/version3/rust/src/ecp.rs @@ -192,20 +192,11 @@ impl ECP { /* test for O point-at-infinity */ pub fn is_infinity(&self) -> bool { - let xx = FP::new_copy(&self.x); - let zz = FP::new_copy(&self.z); - - if CURVETYPE == CurveType::EDWARDS { - let yy = FP::new_copy(&self.y); - return xx.iszilch() && yy.equals(&zz); - } - if CURVETYPE == CurveType::WEIERSTRASS { - return xx.iszilch() && zz.iszilch(); + match CURVETYPE { + CurveType::EDWARDS=> self.x.iszilch() && self.y.equals(&self.z), + CurveType::WEIERSTRASS => self.x.iszilch() && self.z.iszilch(), + CurveType::MONTGOMERY => self.z.iszilch(), } - if CURVETYPE == CurveType::MONTGOMERY { - return zz.iszilch(); - } - return true; } /* Conditional swap of P and Q dependant on d */ @@ -1202,6 +1193,7 @@ impl ECP { return S; } + // Multiply itself by cofactor of the curve pub fn cfp(&mut self) { let cf = rom::CURVE_COF_I; if cf == 1 { @@ -1223,6 +1215,7 @@ impl ECP { self.copy(&P); } + // Map a given byte slice to a point on the curve. The byte slice should be atleast the size of the modulus #[allow(non_snake_case)] pub fn mapit(h: &[u8]) -> ECP { let mut q = BIG::new_ints(&rom::MODULUS); diff --git a/version3/rust/src/ecp2.rs b/version3/rust/src/ecp2.rs index bd44e40..afd9376 100644 --- a/version3/rust/src/ecp2.rs +++ b/version3/rust/src/ecp2.rs @@ -96,9 +96,7 @@ impl ECP2 { /* Test this=O? */ pub fn is_infinity(&self) -> bool { - let xx = FP2::new_copy(&self.x); - let zz = FP2::new_copy(&self.z); - return xx.iszilch() && zz.iszilch(); + self.x.iszilch() && self.z.iszilch() } /* copy self=P */ diff --git a/version3/rust/src/fp.rs b/version3/rust/src/fp.rs index 5db950e..57345c1 100644 --- a/version3/rust/src/fp.rs +++ b/version3/rust/src/fp.rs @@ -312,7 +312,7 @@ impl FP { return r; } - // find appoximation to quotient of a/m + // find approximation to quotient of a/m // Out by at most 2. // Note that MAXXES is bounded to be 2-bits less than half a word fn quo(n: &BIG, m: &BIG) -> isize { @@ -590,6 +590,8 @@ impl FP { y.sqr(); self.mul(&y); } else { + // Constant time inversion using Fermat's little theorem. + // Fermat's little theorem says for a prime p and for any a < p, a^p = a % p => a^(p-1) = 1 % p => a^(p-2) = a^-1 % p let mut m2 = BIG::new_ints(&rom::MODULUS); m2.dec(2); m2.norm(); diff --git a/version3/swift/dbig.swift b/version3/swift/dbig.swift index 00e449b..7630d32 100644 --- a/version3/swift/dbig.swift +++ b/version3/swift/dbig.swift @@ -135,6 +135,15 @@ } return 0; } + /* set x = x mod 2^m */ + mutating func mod2m(_ m: UInt) + { + let wd=Int(m/CONFIG_BIG.BASEBITS) + let bt=m%CONFIG_BIG.BASEBITS + let msk=Chunk(1<<bt)-1; + w[wd]&=msk; + for i in wd+1 ..< CONFIG_BIG.DNLEN {w[i]=0} + } /* normalise BIG - force all digits < 2^BASEBITS */ mutating func norm() {
