From 104b98cc2797c4613151b95dc87218eca7f32c98 Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Thu, 13 Mar 2014 22:54:23 +0700 Subject: Port GLV implementation from Java --- crypto/crypto.csproj | 35 +++++++++++++ crypto/src/asn1/sec/SECNamedCurves.cs | 69 ++++++++++++++++++++++--- crypto/src/crypto/ec/CustomNamedCurves.cs | 48 +++++++++++++++-- crypto/src/math/ec/ECAlgorithms.cs | 48 ++++++++++++++--- crypto/src/math/ec/ECCurve.cs | 26 +++++++++- crypto/src/math/ec/ECPointMap.cs | 9 ++++ crypto/src/math/ec/ScaleXPointMap.cs | 20 +++++++ crypto/src/math/ec/ScaleYPointMap.cs | 20 +++++++ crypto/src/math/ec/endo/ECEndomorphism.cs | 11 ++++ crypto/src/math/ec/endo/GlvEndomorphism.cs | 10 ++++ crypto/src/math/ec/endo/GlvTypeBEndomorphism.cs | 55 ++++++++++++++++++++ crypto/src/math/ec/endo/GlvTypeBParameters.cs | 60 +++++++++++++++++++++ crypto/src/math/ec/multiplier/WNafUtilities.cs | 46 ++++++++++++++++- 13 files changed, 439 insertions(+), 18 deletions(-) create mode 100644 crypto/src/math/ec/ECPointMap.cs create mode 100644 crypto/src/math/ec/ScaleXPointMap.cs create mode 100644 crypto/src/math/ec/ScaleYPointMap.cs create mode 100644 crypto/src/math/ec/endo/ECEndomorphism.cs create mode 100644 crypto/src/math/ec/endo/GlvEndomorphism.cs create mode 100644 crypto/src/math/ec/endo/GlvTypeBEndomorphism.cs create mode 100644 crypto/src/math/ec/endo/GlvTypeBParameters.cs diff --git a/crypto/crypto.csproj b/crypto/crypto.csproj index a4d6c7068..195d69a23 100644 --- a/crypto/crypto.csproj +++ b/crypto/crypto.csproj @@ -4648,6 +4648,11 @@ SubType = "Code" BuildAction = "Compile" /> + + + + + + + ECMultiplier, unless already set. */ diff --git a/crypto/src/math/ec/ECPointMap.cs b/crypto/src/math/ec/ECPointMap.cs new file mode 100644 index 000000000..e78c80065 --- /dev/null +++ b/crypto/src/math/ec/ECPointMap.cs @@ -0,0 +1,9 @@ +using System; + +namespace Org.BouncyCastle.Math.EC +{ + public interface ECPointMap + { + ECPoint Map(ECPoint p); + } +} diff --git a/crypto/src/math/ec/ScaleXPointMap.cs b/crypto/src/math/ec/ScaleXPointMap.cs new file mode 100644 index 000000000..f8a363b24 --- /dev/null +++ b/crypto/src/math/ec/ScaleXPointMap.cs @@ -0,0 +1,20 @@ +using System; + +namespace Org.BouncyCastle.Math.EC +{ + public class ScaleXPointMap + : ECPointMap + { + protected readonly ECFieldElement scale; + + public ScaleXPointMap(ECFieldElement scale) + { + this.scale = scale; + } + + public virtual ECPoint Map(ECPoint p) + { + return p.ScaleX(scale); + } + } +} diff --git a/crypto/src/math/ec/ScaleYPointMap.cs b/crypto/src/math/ec/ScaleYPointMap.cs new file mode 100644 index 000000000..1c4795b70 --- /dev/null +++ b/crypto/src/math/ec/ScaleYPointMap.cs @@ -0,0 +1,20 @@ +using System; + +namespace Org.BouncyCastle.Math.EC +{ + public class ScaleYPointMap + : ECPointMap + { + protected readonly ECFieldElement scale; + + public ScaleYPointMap(ECFieldElement scale) + { + this.scale = scale; + } + + public virtual ECPoint Map(ECPoint p) + { + return p.ScaleY(scale); + } + } +} diff --git a/crypto/src/math/ec/endo/ECEndomorphism.cs b/crypto/src/math/ec/endo/ECEndomorphism.cs new file mode 100644 index 000000000..dfb321368 --- /dev/null +++ b/crypto/src/math/ec/endo/ECEndomorphism.cs @@ -0,0 +1,11 @@ +using System; + +namespace Org.BouncyCastle.Math.EC.Endo +{ + public interface ECEndomorphism + { + ECPointMap PointMap { get; } + + bool HasEfficientPointMap { get; } + } +} diff --git a/crypto/src/math/ec/endo/GlvEndomorphism.cs b/crypto/src/math/ec/endo/GlvEndomorphism.cs new file mode 100644 index 000000000..f65bdd613 --- /dev/null +++ b/crypto/src/math/ec/endo/GlvEndomorphism.cs @@ -0,0 +1,10 @@ +using System; + +namespace Org.BouncyCastle.Math.EC.Endo +{ + public interface GlvEndomorphism + : ECEndomorphism + { + BigInteger[] DecomposeScalar(BigInteger k); + } +} diff --git a/crypto/src/math/ec/endo/GlvTypeBEndomorphism.cs b/crypto/src/math/ec/endo/GlvTypeBEndomorphism.cs new file mode 100644 index 000000000..d234d88bf --- /dev/null +++ b/crypto/src/math/ec/endo/GlvTypeBEndomorphism.cs @@ -0,0 +1,55 @@ +using System; + +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; + 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 }; + } + + public virtual ECPointMap PointMap + { + get { return m_pointMap; } + } + + public virtual bool HasEfficientPointMap + { + 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 new file mode 100644 index 000000000..f93dfaf2b --- /dev/null +++ b/crypto/src/math/ec/endo/GlvTypeBParameters.cs @@ -0,0 +1,60 @@ +using System; + +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; + + 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; + } + + public virtual BigInteger Beta + { + get { return m_beta; } + } + + public virtual BigInteger Lambda + { + get { return m_lambda; } + } + + public virtual BigInteger[] V1 + { + get { return m_v1; } + } + + public virtual BigInteger[] V2 + { + get { return m_v2; } + } + + public virtual BigInteger G1 + { + get { return m_g1; } + } + + public virtual BigInteger G2 + { + get { return m_g2; } + } + + public virtual int Bits + { + get { return m_bits; } + } + } +} diff --git a/crypto/src/math/ec/multiplier/WNafUtilities.cs b/crypto/src/math/ec/multiplier/WNafUtilities.cs index 179d6d6eb..98e4f545f 100644 --- a/crypto/src/math/ec/multiplier/WNafUtilities.cs +++ b/crypto/src/math/ec/multiplier/WNafUtilities.cs @@ -268,6 +268,11 @@ namespace Org.BouncyCastle.Math.EC.Multiplier return wnaf; } + public static WNafPreCompInfo GetWNafPreCompInfo(ECPoint p) + { + return GetWNafPreCompInfo(p.Curve.GetPreCompInfo(p, PRECOMP_NAME)); + } + public static WNafPreCompInfo GetWNafPreCompInfo(PreCompInfo preCompInfo) { if ((preCompInfo != null) && (preCompInfo is WNafPreCompInfo)) @@ -309,6 +314,45 @@ namespace Org.BouncyCastle.Math.EC.Multiplier return w + 2; } + public static ECPoint MapPointWithPrecomp(ECPoint p, int width, bool includeNegated, + ECPointMap pointMap) + { + ECCurve c = p.Curve; + WNafPreCompInfo wnafPreCompP = Precompute(p, width, includeNegated); + + ECPoint q = pointMap.Map(p); + WNafPreCompInfo wnafPreCompQ = GetWNafPreCompInfo(c.GetPreCompInfo(q, PRECOMP_NAME)); + + ECPoint twiceP = wnafPreCompP.Twice; + if (twiceP != null) + { + ECPoint twiceQ = pointMap.Map(twiceP); + wnafPreCompQ.Twice = twiceQ; + } + + ECPoint[] preCompP = wnafPreCompP.PreComp; + ECPoint[] preCompQ = new ECPoint[preCompP.Length]; + for (int i = 0; i < preCompP.Length; ++i) + { + preCompQ[i] = pointMap.Map(preCompP[i]); + } + wnafPreCompQ.PreComp = preCompQ; + + if (includeNegated) + { + ECPoint[] preCompNegQ = new ECPoint[preCompQ.Length]; + for (int i = 0; i < preCompNegQ.Length; ++i) + { + preCompNegQ[i] = preCompQ[i].Negate(); + } + wnafPreCompQ.PreCompNeg = preCompNegQ; + } + + c.SetPreCompInfo(q, PRECOMP_NAME, wnafPreCompQ); + + return q; + } + public static WNafPreCompInfo Precompute(ECPoint p, int width, bool includeNegated) { ECCurve c = p.Curve; @@ -335,7 +379,7 @@ namespace Org.BouncyCastle.Math.EC.Multiplier ECPoint twiceP = wnafPreCompInfo.Twice; if (twiceP == null) { - twiceP = preComp[0].Twice().Normalize(); + twiceP = preComp[0].Twice(); wnafPreCompInfo.Twice = twiceP; } -- cgit 1.5.1