From d5b186492a09c1aee253998670fc843e6087fe6e Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Fri, 2 Aug 2019 18:41:24 +0700 Subject: Add experimental support for GLV Type A endomorphisms --- crypto/src/math/ec/ECPoint.cs | 24 +++++++++ crypto/src/math/ec/ScaleXNegateYPointMap.cs | 20 +++++++ crypto/src/math/ec/ScaleYNegateXPointMap.cs | 20 +++++++ crypto/src/math/ec/endo/EndoUtilities.cs | 34 ++++++++++++ crypto/src/math/ec/endo/GlvTypeAEndomorphism.cs | 38 +++++++++++++ crypto/src/math/ec/endo/GlvTypeAParameters.cs | 32 +++++++++++ crypto/src/math/ec/endo/GlvTypeBEndomorphism.cs | 31 +++-------- crypto/src/math/ec/endo/GlvTypeBParameters.cs | 41 ++++++++------ crypto/src/math/ec/endo/ScalarSplitParameters.cs | 69 ++++++++++++++++++++++++ 9 files changed, 270 insertions(+), 39 deletions(-) create mode 100644 crypto/src/math/ec/ScaleXNegateYPointMap.cs create mode 100644 crypto/src/math/ec/ScaleYNegateXPointMap.cs create mode 100644 crypto/src/math/ec/endo/EndoUtilities.cs create mode 100644 crypto/src/math/ec/endo/GlvTypeAEndomorphism.cs create mode 100644 crypto/src/math/ec/endo/GlvTypeAParameters.cs create mode 100644 crypto/src/math/ec/endo/ScalarSplitParameters.cs (limited to 'crypto/src/math') diff --git a/crypto/src/math/ec/ECPoint.cs b/crypto/src/math/ec/ECPoint.cs index 425424e32..6a7c3ecf0 100644 --- a/crypto/src/math/ec/ECPoint.cs +++ b/crypto/src/math/ec/ECPoint.cs @@ -306,6 +306,13 @@ namespace Org.BouncyCastle.Math.EC : Curve.CreateRawPoint(RawXCoord.Multiply(scale), RawYCoord, RawZCoords, IsCompressed); } + public virtual ECPoint ScaleXNegateY(ECFieldElement scale) + { + return IsInfinity + ? this + : Curve.CreateRawPoint(RawXCoord.Multiply(scale), RawYCoord.Negate(), RawZCoords, IsCompressed); + } + public virtual ECPoint ScaleY(ECFieldElement scale) { return IsInfinity @@ -313,6 +320,13 @@ namespace Org.BouncyCastle.Math.EC : Curve.CreateRawPoint(RawXCoord, RawYCoord.Multiply(scale), RawZCoords, IsCompressed); } + public virtual ECPoint ScaleYNegateX(ECFieldElement scale) + { + return IsInfinity + ? this + : Curve.CreateRawPoint(RawXCoord.Negate(), RawYCoord.Multiply(scale), RawZCoords, IsCompressed); + } + public override bool Equals(object obj) { return Equals(obj as ECPoint); @@ -1500,6 +1514,11 @@ namespace Org.BouncyCastle.Math.EC } } + public override ECPoint ScaleXNegateY(ECFieldElement scale) + { + return ScaleX(scale); + } + public override ECPoint ScaleY(ECFieldElement scale) { if (this.IsInfinity) @@ -1524,6 +1543,11 @@ namespace Org.BouncyCastle.Math.EC } } + public override ECPoint ScaleYNegateX(ECFieldElement scale) + { + return ScaleY(scale); + } + public override ECPoint Subtract(ECPoint b) { if (b.IsInfinity) diff --git a/crypto/src/math/ec/ScaleXNegateYPointMap.cs b/crypto/src/math/ec/ScaleXNegateYPointMap.cs new file mode 100644 index 000000000..b0466a633 --- /dev/null +++ b/crypto/src/math/ec/ScaleXNegateYPointMap.cs @@ -0,0 +1,20 @@ +using System; + +namespace Org.BouncyCastle.Math.EC +{ + public class ScaleXNegateYPointMap + : ECPointMap + { + protected readonly ECFieldElement scale; + + public ScaleXNegateYPointMap(ECFieldElement scale) + { + this.scale = scale; + } + + public virtual ECPoint Map(ECPoint p) + { + return p.ScaleXNegateY(scale); + } + } +} diff --git a/crypto/src/math/ec/ScaleYNegateXPointMap.cs b/crypto/src/math/ec/ScaleYNegateXPointMap.cs new file mode 100644 index 000000000..6a7fed12e --- /dev/null +++ b/crypto/src/math/ec/ScaleYNegateXPointMap.cs @@ -0,0 +1,20 @@ +using System; + +namespace Org.BouncyCastle.Math.EC +{ + public class ScaleYNegateXPointMap + : ECPointMap + { + protected readonly ECFieldElement scale; + + public ScaleYNegateXPointMap(ECFieldElement scale) + { + this.scale = scale; + } + + public virtual ECPoint Map(ECPoint p) + { + return p.ScaleYNegateX(scale); + } + } +} diff --git a/crypto/src/math/ec/endo/EndoUtilities.cs b/crypto/src/math/ec/endo/EndoUtilities.cs new file mode 100644 index 000000000..16916e632 --- /dev/null +++ b/crypto/src/math/ec/endo/EndoUtilities.cs @@ -0,0 +1,34 @@ +using System; + +using Org.BouncyCastle.Math; + +namespace Org.BouncyCastle.Math.EC.Endo +{ + public abstract class EndoUtilities + { + public static BigInteger[] DecomposeScalar(ScalarSplitParameters p, BigInteger k) + { + int bits = p.Bits; + BigInteger b1 = CalculateB(k, p.G1, bits); + BigInteger b2 = CalculateB(k, p.G2, bits); + + BigInteger a = k.Subtract((b1.Multiply(p.V1A)).Add(b2.Multiply(p.V2A))); + BigInteger b = (b1.Multiply(p.V1B)).Add(b2.Multiply(p.V2B)).Negate(); + + return new BigInteger[]{ a, b }; + } + + private static BigInteger CalculateB(BigInteger k, BigInteger g, int t) + { + bool negative = (g.SignValue < 0); + BigInteger b = k.Multiply(g.Abs()); + bool extra = b.TestBit(t - 1); + b = b.ShiftRight(t); + if (extra) + { + b = b.Add(BigInteger.One); + } + return negative ? b.Negate() : b; + } + } +} diff --git a/crypto/src/math/ec/endo/GlvTypeAEndomorphism.cs b/crypto/src/math/ec/endo/GlvTypeAEndomorphism.cs new file mode 100644 index 000000000..fda8f154c --- /dev/null +++ b/crypto/src/math/ec/endo/GlvTypeAEndomorphism.cs @@ -0,0 +1,38 @@ +using System; + +namespace Org.BouncyCastle.Math.EC.Endo +{ + public class GlvTypeAEndomorphism + : GlvEndomorphism + { + protected readonly GlvTypeAParameters m_parameters; + protected readonly ECPointMap m_pointMap; + + public GlvTypeAEndomorphism(ECCurve curve, GlvTypeAParameters parameters) + { + /* + * NOTE: 'curve' MUST only be used to create a suitable ECFieldElement. Due to the way + * ECCurve configuration works, 'curve' will not be the actual instance of ECCurve that the + * endomorphism is being used with. + */ + + this.m_parameters = parameters; + this.m_pointMap = new ScaleYNegateXPointMap(curve.FromBigInteger(parameters.I)); + } + + public virtual BigInteger[] DecomposeScalar(BigInteger k) + { + return EndoUtilities.DecomposeScalar(m_parameters.SplitParams, k); + } + + public virtual ECPointMap PointMap + { + get { return m_pointMap; } + } + + public virtual bool HasEfficientPointMap + { + get { return true; } + } + } +} diff --git a/crypto/src/math/ec/endo/GlvTypeAParameters.cs b/crypto/src/math/ec/endo/GlvTypeAParameters.cs new file mode 100644 index 000000000..68464c530 --- /dev/null +++ b/crypto/src/math/ec/endo/GlvTypeAParameters.cs @@ -0,0 +1,32 @@ +using System; + +namespace Org.BouncyCastle.Math.EC.Endo +{ + public class GlvTypeAParameters + { + protected readonly BigInteger m_i, m_lambda; + protected readonly ScalarSplitParameters m_splitParams; + + public GlvTypeAParameters(BigInteger i, BigInteger lambda, ScalarSplitParameters splitParams) + { + this.m_i = i; + this.m_lambda = lambda; + this.m_splitParams = splitParams; + } + + public virtual BigInteger I + { + get { return m_i; } + } + + public virtual BigInteger Lambda + { + get { return m_lambda; } + } + + public virtual ScalarSplitParameters SplitParams + { + get { return m_splitParams; } + } + } +} diff --git a/crypto/src/math/ec/endo/GlvTypeBEndomorphism.cs b/crypto/src/math/ec/endo/GlvTypeBEndomorphism.cs index d234d88bf..e4f12fed9 100644 --- a/crypto/src/math/ec/endo/GlvTypeBEndomorphism.cs +++ b/crypto/src/math/ec/endo/GlvTypeBEndomorphism.cs @@ -5,28 +5,24 @@ namespace Org.BouncyCastle.Math.EC.Endo public class GlvTypeBEndomorphism : GlvEndomorphism { - protected readonly ECCurve m_curve; protected readonly GlvTypeBParameters m_parameters; protected readonly ECPointMap m_pointMap; public GlvTypeBEndomorphism(ECCurve curve, GlvTypeBParameters parameters) { - this.m_curve = curve; + /* + * NOTE: 'curve' MUST only be used to create a suitable ECFieldElement. Due to the way + * ECCurve configuration works, 'curve' will not be the actual instance of ECCurve that the + * endomorphism is being used with. + */ + this.m_parameters = parameters; this.m_pointMap = new ScaleXPointMap(curve.FromBigInteger(parameters.Beta)); } public virtual BigInteger[] DecomposeScalar(BigInteger k) { - int bits = m_parameters.Bits; - BigInteger b1 = CalculateB(k, m_parameters.G1, bits); - BigInteger b2 = CalculateB(k, m_parameters.G2, bits); - - BigInteger[] v1 = m_parameters.V1, v2 = m_parameters.V2; - BigInteger a = k.Subtract((b1.Multiply(v1[0])).Add(b2.Multiply(v2[0]))); - BigInteger b = (b1.Multiply(v1[1])).Add(b2.Multiply(v2[1])).Negate(); - - return new BigInteger[]{ a, b }; + return EndoUtilities.DecomposeScalar(m_parameters.SplitParams, k); } public virtual ECPointMap PointMap @@ -38,18 +34,5 @@ namespace Org.BouncyCastle.Math.EC.Endo { get { return true; } } - - protected virtual BigInteger CalculateB(BigInteger k, BigInteger g, int t) - { - bool negative = (g.SignValue < 0); - BigInteger b = k.Multiply(g.Abs()); - bool extra = b.TestBit(t - 1); - b = b.ShiftRight(t); - if (extra) - { - b = b.Add(BigInteger.One); - } - return negative ? b.Negate() : b; - } } } diff --git a/crypto/src/math/ec/endo/GlvTypeBParameters.cs b/crypto/src/math/ec/endo/GlvTypeBParameters.cs index f93dfaf2b..5e2937be8 100644 --- a/crypto/src/math/ec/endo/GlvTypeBParameters.cs +++ b/crypto/src/math/ec/endo/GlvTypeBParameters.cs @@ -4,22 +4,23 @@ namespace Org.BouncyCastle.Math.EC.Endo { public class GlvTypeBParameters { - protected readonly BigInteger m_beta; - protected readonly BigInteger m_lambda; - protected readonly BigInteger[] m_v1, m_v2; - protected readonly BigInteger m_g1, m_g2; - protected readonly int m_bits; + protected readonly BigInteger m_beta, m_lambda; + protected readonly ScalarSplitParameters m_splitParams; + [Obsolete("Use constructor taking a ScalarSplitParameters instead")] public GlvTypeBParameters(BigInteger beta, BigInteger lambda, BigInteger[] v1, BigInteger[] v2, BigInteger g1, BigInteger g2, int bits) { this.m_beta = beta; this.m_lambda = lambda; - this.m_v1 = v1; - this.m_v2 = v2; - this.m_g1 = g1; - this.m_g2 = g2; - this.m_bits = bits; + this.m_splitParams = new ScalarSplitParameters(v1, v2, g1, g2, bits); + } + + public GlvTypeBParameters(BigInteger beta, BigInteger lambda, ScalarSplitParameters splitParams) + { + this.m_beta = beta; + this.m_lambda = lambda; + this.m_splitParams = splitParams; } public virtual BigInteger Beta @@ -32,29 +33,39 @@ namespace Org.BouncyCastle.Math.EC.Endo get { return m_lambda; } } + public virtual ScalarSplitParameters SplitParams + { + get { return m_splitParams; } + } + + [Obsolete("Access via SplitParams instead")] public virtual BigInteger[] V1 { - get { return m_v1; } + get { return new BigInteger[] { m_splitParams.V1A, m_splitParams.V1B }; } } + [Obsolete("Access via SplitParams instead")] public virtual BigInteger[] V2 { - get { return m_v2; } + get { return new BigInteger[] { m_splitParams.V2A, m_splitParams.V2B }; } } + [Obsolete("Access via SplitParams instead")] public virtual BigInteger G1 { - get { return m_g1; } + get { return m_splitParams.G1; } } + [Obsolete("Access via SplitParams instead")] public virtual BigInteger G2 { - get { return m_g2; } + get { return m_splitParams.G2; } } + [Obsolete("Access via SplitParams instead")] public virtual int Bits { - get { return m_bits; } + get { return m_splitParams.Bits; } } } } diff --git a/crypto/src/math/ec/endo/ScalarSplitParameters.cs b/crypto/src/math/ec/endo/ScalarSplitParameters.cs new file mode 100644 index 000000000..18d0bdb9e --- /dev/null +++ b/crypto/src/math/ec/endo/ScalarSplitParameters.cs @@ -0,0 +1,69 @@ +using System; + +using Org.BouncyCastle.Math; + +namespace Org.BouncyCastle.Math.EC.Endo +{ + public class ScalarSplitParameters + { + private static void CheckVector(BigInteger[] v, string name) + { + if (v == null || v.Length != 2 || v[0] == null || v[1] == null) + throw new ArgumentException("Must consist of exactly 2 (non-null) values", name); + } + + protected readonly BigInteger m_v1A, m_v1B, m_v2A, m_v2B; + protected readonly BigInteger m_g1, m_g2; + protected readonly int m_bits; + + public ScalarSplitParameters(BigInteger[] v1, BigInteger[] v2, BigInteger g1, + BigInteger g2, int bits) + { + CheckVector(v1, "v1"); + CheckVector(v2, "v2"); + + this.m_v1A = v1[0]; + this.m_v1B = v1[1]; + this.m_v2A = v2[0]; + this.m_v2B = v2[1]; + this.m_g1 = g1; + this.m_g2 = g2; + this.m_bits = bits; + } + + public virtual BigInteger V1A + { + get { return m_v1A; } + } + + public virtual BigInteger V1B + { + get { return m_v1B; } + } + + public virtual BigInteger V2A + { + get { return m_v2A; } + } + + public virtual BigInteger V2B + { + get { return m_v2B; } + } + + public virtual BigInteger G1 + { + get { return m_g1; } + } + + public virtual BigInteger G2 + { + get { return m_g2; } + } + + public virtual int Bits + { + get { return m_bits; } + } + } +} -- cgit 1.4.1