Port of latest EC multipliers from Java

11 files changed, 252 insertions, 30 deletions

diff --git a/crypto/src/math/ec/multiplier/AbstractECMultiplier.cs b/crypto/src/math/ec/multiplier/AbstractECMultiplier.cs
new file mode 100644
index 000000000..fe683726f
--- /dev/null
+++ b/crypto/src/math/ec/multiplier/AbstractECMultiplier.cs
@@ -0,0 +1,18 @@
+namespace Org.BouncyCastle.Math.EC.Multiplier
+{
+    public abstract class AbstractECMultiplier
+        : ECMultiplier
+    {
+        public virtual ECPoint Multiply(ECPoint p, BigInteger k)
+        {
+            int sign = k.SignValue;
+            if (sign == 0 || p.IsInfinity)
+                return p.Curve.Infinity;
+
+            ECPoint positive = MultiplyPositive(p, k.Abs());
+            return sign > 0 ? positive : positive.Negate();
+        }
+
+        protected abstract ECPoint MultiplyPositive(ECPoint p, BigInteger k);
+    }
+}
diff --git a/crypto/src/math/ec/multiplier/DoubleAddMultiplier.cs b/crypto/src/math/ec/multiplier/DoubleAddMultiplier.cs
new file mode 100644
index 000000000..18a72c0a2
--- /dev/null
+++ b/crypto/src/math/ec/multiplier/DoubleAddMultiplier.cs
@@ -0,0 +1,24 @@
+namespace Org.BouncyCastle.Math.EC.Multiplier
+{
+    public class DoubleAddMultiplier
+        : AbstractECMultiplier
+    {
+        /**
+         * Joye's double-add algorithm.
+         */
+        protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k)
+        {
+            ECPoint[] R = new ECPoint[]{ p.Curve.Infinity, p };
+
+            int n = k.BitLength;
+            for (int i = 0; i < n; ++i)
+            {
+                int b = k.TestBit(i) ? 1 : 0;
+                int bp = 1 - b;
+                R[bp] = R[bp].TwicePlus(R[b]);
+            }
+
+            return R[0];
+        }
+    }
+}
diff --git a/crypto/src/math/ec/multiplier/MixedNafR2LMultiplier.cs b/crypto/src/math/ec/multiplier/MixedNafR2LMultiplier.cs
new file mode 100644
index 000000000..a4c201832
--- /dev/null
+++ b/crypto/src/math/ec/multiplier/MixedNafR2LMultiplier.cs
@@ -0,0 +1,75 @@
+using System;
+
+namespace Org.BouncyCastle.Math.EC.Multiplier
+{
+    /**
+     * Class implementing the NAF (Non-Adjacent Form) multiplication algorithm (right-to-left) using
+     * mixed coordinates.
+     */
+    public class MixedNafR2LMultiplier 
+        : AbstractECMultiplier
+    {
+        protected readonly int additionCoord, doublingCoord;
+
+        /**
+         * By default, addition will be done in Jacobian coordinates, and doubling will be done in
+         * Modified Jacobian coordinates (independent of the original coordinate system of each point).
+         */
+        public MixedNafR2LMultiplier()
+            : this(ECCurve.COORD_JACOBIAN, ECCurve.COORD_JACOBIAN_MODIFIED)
+        {
+        }
+
+        public MixedNafR2LMultiplier(int additionCoord, int doublingCoord)
+        {
+            this.additionCoord = additionCoord;
+            this.doublingCoord = doublingCoord;
+        }
+
+        protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k)
+        {
+            ECCurve curveOrig = p.Curve;
+
+            ECCurve curveAdd = ConfigureCurve(curveOrig, additionCoord);
+            ECCurve curveDouble = ConfigureCurve(curveOrig, doublingCoord);
+
+            int[] naf = WNafUtilities.GenerateCompactNaf(k);
+
+            ECPoint Ra = curveAdd.Infinity;
+            ECPoint Td = curveDouble.ImportPoint(p);
+
+            int zeroes = 0;
+            for (int i = 0; i < naf.Length; ++i)
+            {
+                int ni = naf[i];
+                int digit = ni >> 16;
+                zeroes += ni & 0xFFFF;
+
+                Td = Td.TimesPow2(zeroes);
+
+                ECPoint Tj = curveAdd.ImportPoint(Td);
+                if (digit < 0)
+                {
+                    Tj = Tj.Negate();
+                }
+
+                Ra = Ra.Add(Tj);
+
+                zeroes = 1;
+            }
+
+            return curveOrig.ImportPoint(Ra);
+        }
+
+        protected virtual ECCurve ConfigureCurve(ECCurve c, int coord)
+        {
+            if (c.CoordinateSystem == coord)
+                return c;
+
+            if (!c.SupportsCoordinateSystem(coord))
+                throw new ArgumentException("Coordinate system " + coord + " not supported by this curve", "coord");
+
+            return c.Configure().SetCoordinateSystem(coord).Create();
+        }
+    }
+}
diff --git a/crypto/src/math/ec/multiplier/MontgomeryLadderMultiplier.cs b/crypto/src/math/ec/multiplier/MontgomeryLadderMultiplier.cs
new file mode 100644
index 000000000..e2470a383
--- /dev/null
+++ b/crypto/src/math/ec/multiplier/MontgomeryLadderMultiplier.cs
@@ -0,0 +1,25 @@
+namespace Org.BouncyCastle.Math.EC.Multiplier
+{
+    public class MontgomeryLadderMultiplier 
+        : AbstractECMultiplier
+    {
+        /**
+         * Montgomery ladder.
+         */
+        protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k)
+        {
+            ECPoint[] R = new ECPoint[]{ p.Curve.Infinity, p };
+
+            int n = k.BitLength;
+            int i = n;
+            while (--i >= 0)
+            {
+                int b = k.TestBit(i) ? 1 : 0;
+                int bp = 1 - b;
+                R[bp] = R[bp].Add(R[b]);
+                R[b] = R[b].Twice();
+            }
+            return R[0];
+        }
+    }
+}
diff --git a/crypto/src/math/ec/multiplier/FpNafMultiplier.cs b/crypto/src/math/ec/multiplier/NafL2RMultiplier.cs
index e7efa2a44..ac80cf905 100644
--- a/crypto/src/math/ec/multiplier/FpNafMultiplier.cs
+++ b/crypto/src/math/ec/multiplier/NafL2RMultiplier.cs
@@ -3,10 +3,10 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
     /**
      * Class implementing the NAF (Non-Adjacent Form) multiplication algorithm (left-to-right).
      */
-    public class FpNafMultiplier
-        : ECMultiplier
+    public class NafL2RMultiplier
+        : AbstractECMultiplier
     {
-        public virtual ECPoint Multiply(ECPoint p, BigInteger k)
+        protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k)
         {
             int[] naf = WNafUtilities.GenerateCompactNaf(k);
 
diff --git a/crypto/src/math/ec/multiplier/NafR2LMultiplier.cs b/crypto/src/math/ec/multiplier/NafR2LMultiplier.cs
new file mode 100644
index 000000000..1fa69fae8
--- /dev/null
+++ b/crypto/src/math/ec/multiplier/NafR2LMultiplier.cs
@@ -0,0 +1,31 @@
+namespace Org.BouncyCastle.Math.EC.Multiplier
+{
+    /**
+     * Class implementing the NAF (Non-Adjacent Form) multiplication algorithm (right-to-left).
+     */
+    public class NafR2LMultiplier 
+        : AbstractECMultiplier
+    {
+        protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k)
+        {
+            int[] naf = WNafUtilities.GenerateCompactNaf(k);
+
+            ECPoint R0 = p.Curve.Infinity, R1 = p;
+
+            int zeroes = 0;
+            for (int i = 0; i < naf.Length; ++i)
+            {
+                int ni = naf[i];
+                int digit = ni >> 16;
+                zeroes += ni & 0xFFFF;
+
+                R1 = R1.TimesPow2(zeroes);
+                R0 = R0.Add(digit < 0 ? R1.Negate() : R1);
+
+                zeroes = 1;
+            }
+
+            return R0;
+        }
+    }
+}
diff --git a/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs b/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs
index a3763848e..832fd7be4 100644
--- a/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs
+++ b/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs
@@ -1,7 +1,7 @@
 namespace Org.BouncyCastle.Math.EC.Multiplier
 {
     public class ReferenceMultiplier
-        : ECMultiplier
+        : AbstractECMultiplier
     {
         /**
          * Simple shift-and-add multiplication. Serves as reference implementation
@@ -12,7 +12,7 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
          * @param k The factor by which to multiply.
          * @return The result of the point multiplication <code>k * p</code>.
          */
-        public virtual ECPoint Multiply(ECPoint p, BigInteger k)
+        protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k)
         {
             ECPoint q = p.Curve.Infinity;
             int t = k.BitLength;
diff --git a/crypto/src/math/ec/multiplier/WNafMultiplier.cs b/crypto/src/math/ec/multiplier/WNafL2RMultiplier.cs
index 06ad76031..f671f6a5c 100644
--- a/crypto/src/math/ec/multiplier/WNafMultiplier.cs
+++ b/crypto/src/math/ec/multiplier/WNafL2RMultiplier.cs
@@ -6,8 +6,8 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
     * Class implementing the WNAF (Window Non-Adjacent Form) multiplication
     * algorithm.
     */
-    public class WNafMultiplier
-        : ECMultiplier
+    public class WNafL2RMultiplier
+        : AbstractECMultiplier
     {
         /**
          * Multiplies <code>this</code> by an integer <code>k</code> using the
@@ -16,7 +16,7 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
          * @return A new <code>ECPoint</code> which equals <code>this</code>
          * multiplied by <code>k</code>.
          */
-        public virtual ECPoint Multiply(ECPoint p, BigInteger k)
+        protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k)
         {
             // Clamp the window width in the range [2, 16]
             int width = System.Math.Max(2, System.Math.Min(16, GetWindowSize(k.BitLength)));
diff --git a/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs b/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs
index c2f78da93..b87b87000 100644
--- a/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs
+++ b/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs
@@ -9,7 +9,7 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
     * <code>&#964;</code>-adic Non-Adjacent Form) algorithm.
     */
     public class WTauNafMultiplier
-        : ECMultiplier
+        : AbstractECMultiplier
     {
         /**
         * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint}
@@ -19,14 +19,13 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
         * @param k The integer by which to multiply <code>k</code>.
         * @return <code>p</code> multiplied by <code>k</code>.
         */
-        public virtual ECPoint Multiply(ECPoint point, BigInteger k)
+        protected override ECPoint MultiplyPositive(ECPoint point, BigInteger k)
         {
             if (!(point is F2mPoint))
                 throw new ArgumentException("Only F2mPoint can be used in WTauNafMultiplier");
 
             F2mPoint p = (F2mPoint)point;
-
-            F2mCurve curve = (F2mCurve) p.Curve;
+            F2mCurve curve = (F2mCurve)p.Curve;
             int m = curve.M;
             sbyte a = (sbyte) curve.A.ToBigInteger().IntValue;
             sbyte mu = curve.GetMu();
@@ -50,16 +49,7 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
         private F2mPoint MultiplyWTnaf(F2mPoint p, ZTauElement lambda,
             PreCompInfo preCompInfo, sbyte a, sbyte mu)
         {
-            ZTauElement[] alpha;
-            if (a == 0)
-            {
-                alpha = Tnaf.Alpha0;
-            }
-            else
-            {
-                // a == 1
-                alpha = Tnaf.Alpha1;
-            }
+            ZTauElement[] alpha = (a == 0) ? Tnaf.Alpha0 : Tnaf.Alpha1;
 
             BigInteger tw = Tnaf.GetTw(mu, Tnaf.Width);
 
@@ -78,11 +68,10 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
         * @param u The the WTNAF of <code>&#955;</code>..
         * @return <code>&#955; * p</code>
         */
-        private static F2mPoint MultiplyFromWTnaf(F2mPoint p, sbyte[] u,
-            PreCompInfo preCompInfo)
+        private static F2mPoint MultiplyFromWTnaf(F2mPoint p, sbyte[] u, PreCompInfo preCompInfo)
         {
             F2mCurve curve = (F2mCurve)p.Curve;
-            sbyte a = (sbyte) curve.A.ToBigInteger().IntValue;
+            sbyte a = (sbyte)curve.A.ToBigInteger().IntValue;
 
             F2mPoint[] pu;
             if ((preCompInfo == null) || !(preCompInfo is WTauNafPreCompInfo))
@@ -99,20 +88,21 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
             }
 
             // q = infinity
-            F2mPoint q = (F2mPoint) p.Curve.Infinity;
+            F2mPoint q = (F2mPoint)curve.Infinity;
             for (int i = u.Length - 1; i >= 0; i--)
             {
                 q = Tnaf.Tau(q);
-                if (u[i] != 0)
+                sbyte ui = u[i];
+                if (ui != 0)
                 {
-                    if (u[i] > 0)
+                    if (ui > 0)
                     {
-                        q = q.AddSimple(pu[u[i]]);
+                        q = q.AddSimple(pu[ui]);
                     }
                     else
                     {
                         // u[i] < 0
-                        q = q.SubtractSimple(pu[-u[i]]);
+                        q = q.SubtractSimple(pu[-ui]);
                     }
                 }
             }
diff --git a/crypto/src/math/ec/multiplier/ZSignedDigitL2RMultiplier.cs b/crypto/src/math/ec/multiplier/ZSignedDigitL2RMultiplier.cs
new file mode 100644
index 000000000..554ac61b3
--- /dev/null
+++ b/crypto/src/math/ec/multiplier/ZSignedDigitL2RMultiplier.cs
@@ -0,0 +1,29 @@
+namespace Org.BouncyCastle.Math.EC.Multiplier
+{
+    public class ZSignedDigitL2RMultiplier 
+        : AbstractECMultiplier
+    {
+        /**
+         * 'Zeroless' Signed Digit Left-to-Right.
+         */
+        protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k)
+        {
+            ECPoint addP = p.Normalize(), subP = addP.Negate();
+
+            ECPoint R0 = addP;
+
+            int n = k.BitLength;
+            int s = k.GetLowestSetBit();
+
+            int i = n;
+            while (--i > s)
+            {
+                R0 = R0.TwicePlus(k.TestBit(i) ? addP : subP);
+            }
+
+            R0 = R0.TimesPow2(s);
+
+            return R0;
+        }
+    }
+}
diff --git a/crypto/src/math/ec/multiplier/ZSignedDigitR2LMultiplier.cs b/crypto/src/math/ec/multiplier/ZSignedDigitR2LMultiplier.cs
new file mode 100644
index 000000000..91c06cbb8
--- /dev/null
+++ b/crypto/src/math/ec/multiplier/ZSignedDigitR2LMultiplier.cs
@@ -0,0 +1,30 @@
+namespace Org.BouncyCastle.Math.EC.Multiplier
+{
+    public class ZSignedDigitR2LMultiplier 
+        : AbstractECMultiplier
+    {
+        /**
+         * 'Zeroless' Signed Digit Right-to-Left.
+         */
+        protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k)
+        {
+            ECPoint R0 = p.Curve.Infinity, R1 = p;
+
+            int n = k.BitLength;
+            int s = k.GetLowestSetBit();
+
+            R1 = R1.TimesPow2(s);
+
+            int i = s;
+            while (++i < n)
+            {
+                R0 = R0.Add(k.TestBit(i) ? R1 : R1.Negate());
+                R1 = R1.Twice();
+            }
+
+            R0 = R0.Add(R1);
+
+            return R0;
+        }
+    }
+}