From a1f04c18f436a7206c990e1c1625250f5dee93b3 Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Wed, 22 Jan 2014 12:47:20 +0700 Subject: Add foundations for supporting other coordinate systems Add curve configuration Multipliers now live on the curve instead of points --- crypto/src/math/ec/ECCurve.cs | 236 ++++++++++++++++++--- crypto/src/math/ec/ECPoint.cs | 75 ++----- .../src/math/ec/test/ECPointPerformanceTest.cs | 44 +++- crypto/test/src/math/ec/test/ECPointTest.cs | 2 +- 4 files changed, 260 insertions(+), 97 deletions(-) diff --git a/crypto/src/math/ec/ECCurve.cs b/crypto/src/math/ec/ECCurve.cs index 6f4492e5c..2db6bdc80 100644 --- a/crypto/src/math/ec/ECCurve.cs +++ b/crypto/src/math/ec/ECCurve.cs @@ -2,6 +2,7 @@ using System; using System.Collections; using Org.BouncyCastle.Math.EC.Abc; +using Org.BouncyCastle.Math.EC.Multiplier; using Org.BouncyCastle.Math.Field; using Org.BouncyCastle.Utilities; @@ -10,9 +11,72 @@ namespace Org.BouncyCastle.Math.EC /// Base class for an elliptic curve. public abstract class ECCurve { + public const int COORD_AFFINE = 0; + public const int COORD_HOMOGENEOUS = 1; + public const int COORD_JACOBIAN = 2; + public const int COORD_JACOBIAN_CHUDNOVSKY = 3; + public const int COORD_JACOBIAN_MODIFIED = 4; + public const int COORD_LAMBDA_AFFINE = 5; + public const int COORD_LAMBDA_PROJECTIVE = 6; + public const int COORD_SKEWED = 7; + + public static int[] GetAllCoordinateSystems() + { + return new int[]{ COORD_AFFINE, COORD_HOMOGENEOUS, COORD_JACOBIAN, COORD_JACOBIAN_CHUDNOVSKY, + COORD_JACOBIAN_MODIFIED, COORD_LAMBDA_AFFINE, COORD_LAMBDA_PROJECTIVE, COORD_SKEWED }; + } + + public class Config + { + protected ECCurve outer; + protected int coord; + protected ECMultiplier multiplier; + + internal Config(ECCurve outer, int coord, ECMultiplier multiplier) + { + this.outer = outer; + this.coord = coord; + this.multiplier = multiplier; + } + + public Config SetCoordinateSystem(int coord) + { + this.coord = coord; + return this; + } + + public Config SetMultiplier(ECMultiplier multiplier) + { + this.multiplier = multiplier; + return this; + } + + public ECCurve Create() + { + if (!outer.SupportsCoordinateSystem(coord)) + { + throw new InvalidOperationException("unsupported coordinate system"); + } + + ECCurve c = outer.CloneCurve(); + if (c == outer) + { + throw new InvalidOperationException("implementation returned current curve"); + } + + c.m_coord = coord; + c.m_multiplier = multiplier; + + return c; + } + } + protected IFiniteField m_field; protected ECFieldElement m_a, m_b; + protected int m_coord = COORD_AFFINE; + protected ECMultiplier m_multiplier = null; + protected ECCurve(IFiniteField field) { this.m_field = field; @@ -20,7 +84,48 @@ namespace Org.BouncyCastle.Math.EC public abstract int FieldSize { get; } public abstract ECFieldElement FromBigInteger(BigInteger x); + + public virtual Config Configure() + { + return new Config(this, this.m_coord, this.m_multiplier); + } + + public virtual ECPoint CreatePoint(BigInteger x, BigInteger y) + { + return CreatePoint(x, y, false); + } + public abstract ECPoint CreatePoint(BigInteger x, BigInteger y, bool withCompression); + + protected abstract ECCurve CloneCurve(); + + protected virtual ECMultiplier CreateDefaultMultiplier() + { + return new WNafMultiplier(); + } + + public virtual bool SupportsCoordinateSystem(int coord) + { + return coord == COORD_AFFINE; + } + + public virtual ECPoint ImportPoint(ECPoint p) + { + if (this == p.Curve) + { + return p; + } + if (p.IsInfinity) + { + return Infinity; + } + + // TODO Default behaviour could be improved if the two curves have the same coordinate system by copying any Z coordinates. + p = p.Normalize(); + + return CreatePoint(p.X.ToBigInteger(), p.Y.ToBigInteger(), p.withCompression); + } + public abstract ECPoint Infinity { get; } public virtual IFiniteField Field @@ -38,6 +143,11 @@ namespace Org.BouncyCastle.Math.EC get { return m_b; } } + public virtual int CoordinateSystem + { + get { return m_coord; } + } + public virtual bool Equals(ECCurve other) { if (this == other) @@ -63,6 +173,21 @@ namespace Org.BouncyCastle.Math.EC protected abstract ECPoint DecompressPoint(int yTilde, BigInteger X1); + /** + * Sets the default ECMultiplier, unless already set. + */ + public virtual ECMultiplier GetMultiplier() + { + lock (this) + { + if (this.m_multiplier == null) + { + this.m_multiplier = CreateDefaultMultiplier(); + } + return this.m_multiplier; + } + } + /** * Decode a point on this curve from its ASN.1 encoding. The different * encodings are taken account of, including point compression for @@ -126,37 +251,58 @@ namespace Org.BouncyCastle.Math.EC public class FpCurve : ECCurve { - private readonly BigInteger q, r; - private readonly FpPoint infinity; + private const int FP_DEFAULT_COORDS = COORD_AFFINE; + + protected readonly BigInteger m_q, m_r; + protected readonly FpPoint m_infinity; public FpCurve(BigInteger q, BigInteger a, BigInteger b) : base(FiniteFields.GetPrimeField(q)) { - this.q = q; - this.r = FpFieldElement.CalculateResidue(q); + this.m_q = q; + this.m_r = FpFieldElement.CalculateResidue(q); + this.m_infinity = new FpPoint(this, null, null); + this.m_a = FromBigInteger(a); this.m_b = FromBigInteger(b); - this.infinity = new FpPoint(this, null, null); + this.m_coord = FP_DEFAULT_COORDS; + } + + protected FpCurve(BigInteger q, BigInteger r, ECFieldElement a, ECFieldElement b) + : base(FiniteFields.GetPrimeField(q)) + { + this.m_q = q; + this.m_r = r; + this.m_infinity = new FpPoint(this, null, null); + + this.m_a = a; + this.m_b = b; + this.m_coord = FP_DEFAULT_COORDS; } - public BigInteger Q + protected override ECCurve CloneCurve() { - get { return q; } + return new FpCurve(m_q, m_r, m_a, m_b); + } + + public virtual BigInteger Q + { + get { return m_q; } } public override ECPoint Infinity { - get { return infinity; } + get { return m_infinity; } } public override int FieldSize { - get { return q.BitLength; } + get { return m_q.BitLength; } } public override ECFieldElement FromBigInteger(BigInteger x) { - return new FpFieldElement(this.q, this.r, x); + return new FpFieldElement(this.m_q, this.m_r, x); } public override ECPoint CreatePoint( @@ -206,6 +352,8 @@ namespace Org.BouncyCastle.Math.EC */ public class F2mCurve : ECCurve { + private const int F2M_DEFAULT_COORDS = COORD_AFFINE; + private static IFiniteField BuildField(int m, int k1, int k2, int k3) { if (k1 == 0) @@ -280,7 +428,7 @@ namespace Org.BouncyCastle.Math.EC /** * The point at infinity on this curve. */ - private readonly F2mPoint infinity; + protected readonly F2mPoint m_infinity; /** * The parameter μ of the elliptic curve if this is @@ -417,7 +565,7 @@ namespace Org.BouncyCastle.Math.EC this.k3 = k3; this.n = n; this.h = h; - this.infinity = new F2mPoint(this, null, null); + this.m_infinity = new F2mPoint(this, null, null); if (k1 == 0) throw new ArgumentException("k1 must be > 0"); @@ -438,11 +586,43 @@ namespace Org.BouncyCastle.Math.EC this.m_a = FromBigInteger(a); this.m_b = FromBigInteger(b); + this.m_coord = F2M_DEFAULT_COORDS; + } + + protected F2mCurve(int m, int k1, int k2, int k3, ECFieldElement a, ECFieldElement b, BigInteger order, BigInteger cofactor) + : base(BuildField(m, k1, k2, k3)) + { + this.m = m; + this.k1 = k1; + this.k2 = k2; + this.k3 = k3; + this.n = order; + this.h = cofactor; + + this.m_infinity = new F2mPoint(this, null, null); + this.m_a = a; + this.m_b = b; + this.m_coord = F2M_DEFAULT_COORDS; + } + + protected override ECCurve CloneCurve() + { + return new F2mCurve(m, k1, k2, k3, m_a, m_b, n, h); + } + + protected override ECMultiplier CreateDefaultMultiplier() + { + if (IsKoblitz) + { + return new WTauNafMultiplier(); + } + + return base.CreateDefaultMultiplier(); } public override ECPoint Infinity { - get { return infinity; } + get { return m_infinity; } } public override int FieldSize @@ -459,7 +639,7 @@ namespace Org.BouncyCastle.Math.EC * Returns true if this is a Koblitz curve (ABC curve). * @return true if this is a Koblitz curve (ABC curve), false otherwise */ - public bool IsKoblitz + public virtual bool IsKoblitz { get { @@ -473,7 +653,7 @@ namespace Org.BouncyCastle.Math.EC * @throws ArgumentException if the given ECCurve is not a * Koblitz curve. */ - internal sbyte GetMu() + internal virtual sbyte GetMu() { if (mu == 0) { @@ -494,7 +674,7 @@ namespace Org.BouncyCastle.Math.EC * s1 used for partial modular reduction for * Koblitz curves. */ - internal BigInteger[] GetSi() + internal virtual BigInteger[] GetSi() { if (si == null) { @@ -539,7 +719,7 @@ namespace Org.BouncyCastle.Math.EC else { ECFieldElement beta = xp.Add(m_a).Add(m_b.Multiply(xp.Square().Invert())); - ECFieldElement z = solveQuadradicEquation(beta); + ECFieldElement z = SolveQuadradicEquation(beta); if (z == null) throw new ArithmeticException("Invalid point compression"); @@ -565,21 +745,23 @@ namespace Org.BouncyCastle.Math.EC * @return the solution for z2 + z = beta or * null if no solution exists. */ - private ECFieldElement solveQuadradicEquation(ECFieldElement beta) + private ECFieldElement SolveQuadradicEquation(ECFieldElement beta) { - if (beta.ToBigInteger().SignValue == 0) + if (beta.IsZero) { - return FromBigInteger(BigInteger.Zero); + return beta; } + ECFieldElement zeroElement = FromBigInteger(BigInteger.Zero); + ECFieldElement z = null; - ECFieldElement gamma = FromBigInteger(BigInteger.Zero); + ECFieldElement gamma = null; - while (gamma.ToBigInteger().SignValue == 0) + Random rand = new Random(); + do { - ECFieldElement t = FromBigInteger(new BigInteger(m, new Random())); - z = FromBigInteger(BigInteger.Zero); - + ECFieldElement t = FromBigInteger(new BigInteger(m, rand)); + z = zeroElement; ECFieldElement w = beta; for (int i = 1; i <= m - 1; i++) { @@ -587,12 +769,14 @@ namespace Org.BouncyCastle.Math.EC z = z.Square().Add(w2.Multiply(t)); w = w2.Add(beta); } - if (w.ToBigInteger().SignValue != 0) + if (!w.IsZero) { return null; } gamma = z.Square().Add(z); } + while (gamma.IsZero); + return z; } diff --git a/crypto/src/math/ec/ECPoint.cs b/crypto/src/math/ec/ECPoint.cs index d81558939..1b00b764f 100644 --- a/crypto/src/math/ec/ECPoint.cs +++ b/crypto/src/math/ec/ECPoint.cs @@ -16,7 +16,6 @@ namespace Org.BouncyCastle.Math.EC internal readonly ECCurve curve; internal readonly ECFieldElement x, y; internal readonly bool withCompression; - internal ECMultiplier multiplier = null; internal PreCompInfo preCompInfo = null; protected internal ECPoint( @@ -49,6 +48,18 @@ namespace Org.BouncyCastle.Math.EC get { return y; } } + + /** + * Normalization ensures that any projective coordinate is 1, and therefore that the x, y + * coordinates reflect those of the equivalent point in an affine coordinate system. + * + * @return a new ECPoint instance representing the same point, but with normalized coordinates + */ + public virtual ECPoint Normalize() + { + return this; + } + public bool IsInfinity { get { return x == null && y == null; } @@ -91,17 +102,6 @@ namespace Org.BouncyCastle.Math.EC return hc; } -// /** -// * Mainly for testing. Explicitly set the ECMultiplier. -// * @param multiplier The ECMultiplier to be used to multiply -// * this ECPoint. -// */ -// internal void SetECMultiplier( -// ECMultiplier multiplier) -// { -// this.multiplier = multiplier; -// } - /** * Sets the PreCompInfo. Used by ECMultipliers * to save the precomputation for this ECPoint to store the @@ -137,23 +137,6 @@ namespace Org.BouncyCastle.Math.EC { return TwicePlus(this); } - - /** - * Sets the appropriate ECMultiplier, unless already set. - */ - internal virtual void AssertECMultiplier() - { - if (this.multiplier == null) - { - lock (this) - { - if (this.multiplier == null) - { - this.multiplier = new WNafMultiplier(); - } - } - } - } } public abstract class ECPointBase @@ -222,8 +205,7 @@ namespace Org.BouncyCastle.Math.EC if (k.SignValue == 0) return this.curve.Infinity; - AssertECMultiplier(); - return this.multiplier.Multiply(this, k, preCompInfo); + return this.Curve.GetMultiplier().Multiply(this, k, preCompInfo); } } @@ -271,7 +253,7 @@ namespace Org.BouncyCastle.Math.EC { get { - return this.Y.ToBigInteger().TestBit(0); + return this.Y.TestBitZero(); } } @@ -541,8 +523,7 @@ namespace Org.BouncyCastle.Math.EC // X9.62 4.2.2 and 4.3.6: // if x = 0 then ypTilde := 0, else ypTilde is the rightmost // bit of y * x^(-1) - return this.X.ToBigInteger().SignValue != 0 - && this.Y.Multiply(this.X.Invert()).ToBigInteger().TestBit(0); + return !this.X.IsZero && this.Y.Divide(this.X).TestBitZero(); } } @@ -658,7 +639,7 @@ namespace Org.BouncyCastle.Math.EC // if x1 == 0, then (x1, y1) == (x1, x1 + y1) // and hence this = -this and thus 2(x1, y1) == infinity - if (this.x.ToBigInteger().SignValue == 0) + if (this.x.IsZero) return this.curve.Infinity; F2mFieldElement lambda = (F2mFieldElement) this.x.Add(this.y.Divide(this.x)); @@ -674,29 +655,5 @@ namespace Org.BouncyCastle.Math.EC { return new F2mPoint(curve, this.x, this.x.Add(this.y), withCompression); } - - /** - * Sets the appropriate ECMultiplier, unless already set. - */ - internal override void AssertECMultiplier() - { - if (this.multiplier == null) - { - lock (this) - { - if (this.multiplier == null) - { - if (((F2mCurve) this.curve).IsKoblitz) - { - this.multiplier = new WTauNafMultiplier(); - } - else - { - this.multiplier = new WNafMultiplier(); - } - } - } - } - } } } diff --git a/crypto/test/src/math/ec/test/ECPointPerformanceTest.cs b/crypto/test/src/math/ec/test/ECPointPerformanceTest.cs index 380004d96..6b9e2efce 100644 --- a/crypto/test/src/math/ec/test/ECPointPerformanceTest.cs +++ b/crypto/test/src/math/ec/test/ECPointPerformanceTest.cs @@ -27,6 +27,9 @@ namespace Org.BouncyCastle.Math.EC.Tests public const int PRE_ROUNDS = 10; public const int NUM_ROUNDS = 100; + private static string[] COORD_NAMES = new string[]{ "AFFINE", "HOMOGENEOUS", "JACOBIAN", "JACOBIAN-CHUDNOVSKY", + "JACOBIAN-MODIFIED", "LAMBDA-AFFINE", "LAMBDA-PROJECTIVE", "SKEWED" }; + private void RandMult(string curveName) { X9ECParameters spec = ECNamedCurveTable.GetByName(curveName); @@ -44,26 +47,45 @@ namespace Org.BouncyCastle.Math.EC.Tests private void RandMult(string label, X9ECParameters spec) { + ECCurve C = spec.Curve; ECPoint G = (ECPoint)spec.G; BigInteger n = spec.N; + SecureRandom random = new SecureRandom(); random.SetSeed(DateTimeUtilities.CurrentUnixMs()); Console.WriteLine(label); - double avgDuration = RandMult(random, G, n); - string coordName = "AFFINE"; - StringBuilder sb = new StringBuilder(); - sb.Append(" "); - sb.Append(coordName); - for (int j = coordName.Length; j < 30; ++j) + int[] coords = ECCurve.GetAllCoordinateSystems(); + for (int i = 0; i < coords.Length; ++i) { - sb.Append(' '); + int coord = coords[i]; + if (C.SupportsCoordinateSystem(coord)) + { + ECCurve c = C; + ECPoint g = G; + + if (c.CoordinateSystem != coord) + { + c = C.Configure().SetCoordinateSystem(coord).Create(); + g = c.ImportPoint(G); + } + + double avgDuration = RandMult(random, g, n); + string coordName = COORD_NAMES[coord]; + StringBuilder sb = new StringBuilder(); + sb.Append(" "); + sb.Append(coordName); + for (int j = coordName.Length; j < 30; ++j) + { + sb.Append(' '); + } + sb.Append(": "); + sb.Append(avgDuration); + sb.Append("ms"); + Console.WriteLine(sb.ToString()); + } } - sb.Append(": "); - sb.Append(avgDuration); - sb.Append("ms"); - Console.WriteLine(sb.ToString()); } private double RandMult(SecureRandom random, ECPoint g, BigInteger n) diff --git a/crypto/test/src/math/ec/test/ECPointTest.cs b/crypto/test/src/math/ec/test/ECPointTest.cs index 696448544..6c628c29c 100644 --- a/crypto/test/src/math/ec/test/ECPointTest.cs +++ b/crypto/test/src/math/ec/test/ECPointTest.cs @@ -56,7 +56,7 @@ namespace Org.BouncyCastle.Math.EC.Tests { p[i] = curve.CreatePoint( new BigInteger(pointSource[2 * i].ToString()), - new BigInteger(pointSource[2 * i + 1].ToString()), false); + new BigInteger(pointSource[2 * i + 1].ToString())); } } } -- cgit 1.4.1