Use ImportPoint to make sure points are on same curve

Add MontgomeryTrick method

1 files changed, 49 insertions, 15 deletions

diff --git a/crypto/src/math/ec/ECAlgorithms.cs b/crypto/src/math/ec/ECAlgorithms.cs
index 06288132b..070c8326c 100644
--- a/crypto/src/math/ec/ECAlgorithms.cs
+++ b/crypto/src/math/ec/ECAlgorithms.cs
@@ -18,17 +18,15 @@ namespace Org.BouncyCastle.Math.EC
             return c.Field.Dimension == 1;
         }
 
-        public static ECPoint SumOfTwoMultiplies(ECPoint P, BigInteger a,
-            ECPoint Q, BigInteger b)
+        public static ECPoint SumOfTwoMultiplies(ECPoint P, BigInteger a, ECPoint Q, BigInteger b)
         {
-            ECCurve c = P.Curve;
-            if (!c.Equals(Q.Curve))
-                throw new ArgumentException("P and Q must be on same curve");
+            ECCurve cp = P.Curve;
+            Q = ImportPoint(cp, Q);
 
             // Point multiplication for Koblitz curves (using WTNAF) beats Shamir's trick
-            if (c is F2mCurve)
+            if (cp is F2mCurve)
             {
-                F2mCurve f2mCurve = (F2mCurve) c;
+                F2mCurve f2mCurve = (F2mCurve) cp;
                 if (f2mCurve.IsKoblitz)
                 {
                     return P.Multiply(a).Add(Q.Multiply(b));
@@ -56,19 +54,55 @@ namespace Org.BouncyCastle.Math.EC
         * 8: end for
         * 9: return R
         */
-        public static ECPoint ShamirsTrick(
-            ECPoint		P,
-            BigInteger	k,
-            ECPoint		Q,
-            BigInteger	l)
+        public static ECPoint ShamirsTrick(ECPoint P, BigInteger k, ECPoint Q, BigInteger l)
         {
-            if (!P.Curve.Equals(Q.Curve))
-                throw new ArgumentException("P and Q must be on same curve");
+            ECCurve cp = P.Curve;
+            Q = ImportPoint(cp, Q);
 
             return ImplShamirsTrick(P, k, Q, l);
         }
 
-        private static ECPoint ImplShamirsTrick(ECPoint P, BigInteger k,
+        public static ECPoint ImportPoint(ECCurve c, ECPoint p)
+        {
+            ECCurve cp = p.Curve;
+            if (!c.Equals(cp))
+                throw new ArgumentException("Point must be on the same curve");
+
+            return c.ImportPoint(p);
+        }
+
+        public static void MontgomeryTrick(ECFieldElement[] zs, int off, int len)
+        {
+            /*
+             * Uses the "Montgomery Trick" to invert many field elements, with only a single actual
+             * field inversion. See e.g. the paper:
+             * "Fast Multi-scalar Multiplication Methods on Elliptic Curves with Precomputation Strategy Using Montgomery Trick"
+             * by Katsuyuki Okeya, Kouichi Sakurai.
+             */
+
+            ECFieldElement[] c = new ECFieldElement[len];
+            c[0] = zs[off];
+
+            int i = 0;
+            while (++i < len)
+            {
+                c[i] = c[i - 1].Multiply(zs[off + i]);
+            }
+
+            ECFieldElement u = c[--i].Invert();
+
+            while (i > 0)
+            {
+                int j = off + i--;
+                ECFieldElement tmp = zs[j];
+                zs[j] = c[i].Multiply(u);
+                u = u.Multiply(tmp);
+            }
+
+            zs[off] = u;
+        }
+
+        internal static ECPoint ImplShamirsTrick(ECPoint P, BigInteger k,
             ECPoint Q, BigInteger l)
         {
             int m = System.Math.Max(k.BitLength, l.BitLength);