Add foundations for supporting other coordinate systems

Add curve configuration
Multipliers now live on the curve instead of points

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
     /// <remarks>Base class for an elliptic curve.</remarks>
     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)
@@ -64,6 +174,21 @@ namespace Org.BouncyCastle.Math.EC
         protected abstract ECPoint DecompressPoint(int yTilde, BigInteger X1);
 
         /**
+         * Sets the default <code>ECMultiplier</code>, 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
          * <code>F<sub>p</sub></code> (X9.62 s 4.2.1 pg 17).
@@ -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 <code>&#956;</code> 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
          * <code>s<sub>1</sub></code> 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 <code>z<sup>2</sup> + z = beta</code> or
          *         <code>null</code> 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 <code>ECMultiplier</code>.
-//		 * @param multiplier The <code>ECMultiplier</code> to be used to multiply
-//		 * this <code>ECPoint</code>.
-//		 */
-//		internal void SetECMultiplier(
-//			ECMultiplier multiplier)
-//		{
-//			this.multiplier = multiplier;
-//		}
-
         /**
          * Sets the <code>PreCompInfo</code>. Used by <code>ECMultiplier</code>s
          * to save the precomputation for this <code>ECPoint</code> to store the
@@ -137,23 +137,6 @@ namespace Org.BouncyCastle.Math.EC
         {
             return TwicePlus(this);
         }
-
-        /**
-        * Sets the appropriate <code>ECMultiplier</code>, 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 <code>ECMultiplier</code>, 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()));
                 }
             }
         }