Take advantage of GLV (when available) in sum-of-multiplies methods

1 files changed, 89 insertions, 7 deletions

diff --git a/crypto/src/math/ec/ECAlgorithms.cs b/crypto/src/math/ec/ECAlgorithms.cs
index 628680e24..6519e81c6 100644
--- a/crypto/src/math/ec/ECAlgorithms.cs
+++ b/crypto/src/math/ec/ECAlgorithms.cs
@@ -1,5 +1,6 @@
 using System;
 
+using Org.BouncyCastle.Math.EC.Endo;
 using Org.BouncyCastle.Math.EC.Multiplier;
 using Org.BouncyCastle.Math.Field;
 
@@ -45,6 +46,12 @@ namespace Org.BouncyCastle.Math.EC
                 imported[i] = ImportPoint(c, ps[i]);
             }
 
+            GlvEndomorphism glvEndomorphism = c.GetEndomorphism() as GlvEndomorphism;
+            if (glvEndomorphism != null)
+            {
+                return ImplSumOfMultipliesGlv(imported, ks, glvEndomorphism);
+            }
+
             return ImplSumOfMultiplies(imported, ks);
         }
 
@@ -63,6 +70,12 @@ namespace Org.BouncyCastle.Math.EC
                 }
             }
 
+            GlvEndomorphism glvEndomorphism = cp.GetEndomorphism() as GlvEndomorphism;
+            if (glvEndomorphism != null)
+            {
+                return ImplSumOfMultipliesGlv(new ECPoint[] { P, Q }, new BigInteger[] { a, b }, glvEndomorphism);
+            }
+
             return ImplShamirsTrickWNaf(P, a, Q, b);
         }
 
@@ -273,20 +286,89 @@ namespace Org.BouncyCastle.Math.EC
         internal static ECPoint ImplSumOfMultiplies(ECPoint[] ps, BigInteger[] ks)
         {
             int count = ps.Length;
-            int[] widths = new int[count];
+            bool[] negs = new bool[count];
             WNafPreCompInfo[] infos = new WNafPreCompInfo[count];
             byte[][] wnafs = new byte[count][];
 
-            int len = 0;
             for (int i = 0; i < count; ++i)
             {
-                widths[i] = System.Math.Max(2, System.Math.Min(16, WNafUtilities.GetWindowSize(ks[i].BitLength)));
-                infos[i] = WNafUtilities.Precompute(ps[i], widths[i], true);
-                wnafs[i] = WNafUtilities.GenerateWindowNaf(widths[i], ks[i]);
+                BigInteger ki = ks[i]; negs[i] = ki.SignValue < 0; ki = ki.Abs();
+
+                int width = System.Math.Max(2, System.Math.Min(16, WNafUtilities.GetWindowSize(ki.BitLength)));
+                infos[i] = WNafUtilities.Precompute(ps[i], width, true);
+                wnafs[i] = WNafUtilities.GenerateWindowNaf(width, ki);
+            }
+
+            return ImplSumOfMultiplies(negs, infos, wnafs);
+        }
+
+        internal static ECPoint ImplSumOfMultipliesGlv(ECPoint[] ps, BigInteger[] ks, GlvEndomorphism glvEndomorphism)
+        {
+            BigInteger n = ps[0].Curve.Order;
+
+            int len = ps.Length;
+
+            BigInteger[] abs = new BigInteger[len << 1];
+            for (int i = 0, j = 0; i < len; ++i)
+            {
+                BigInteger[] ab = glvEndomorphism.DecomposeScalar(ks[i].Mod(n));
+                abs[j++] = ab[0];
+                abs[j++] = ab[1];
+            }
+
+            ECPointMap pointMap = glvEndomorphism.PointMap;
+            if (glvEndomorphism.HasEfficientPointMap)
+            {
+                return ECAlgorithms.ImplSumOfMultiplies(ps, pointMap, abs);
+            }
+
+            ECPoint[] pqs = new ECPoint[len << 1];
+            for (int i = 0, j = 0; i < len; ++i)
+            {
+                ECPoint p = ps[i], q = pointMap.Map(p);
+                pqs[j++] = p;
+                pqs[j++] = q;
+            }
+
+            return ECAlgorithms.ImplSumOfMultiplies(pqs, abs);
+        }
+
+        internal static ECPoint ImplSumOfMultiplies(ECPoint[] ps, ECPointMap pointMap, BigInteger[] ks)
+        {
+            int halfCount = ps.Length, fullCount = halfCount << 1;
+
+            bool[] negs = new bool[fullCount];
+            WNafPreCompInfo[] infos = new WNafPreCompInfo[fullCount];
+            byte[][] wnafs = new byte[fullCount][];
+
+            for (int i = 0; i < halfCount; ++i)
+            {
+                int j0 = i << 1, j1 = j0 + 1;
+
+                BigInteger kj0 = ks[j0]; negs[j0] = kj0.SignValue < 0; kj0 = kj0.Abs();
+                BigInteger kj1 = ks[j1]; negs[j1] = kj1.SignValue < 0; kj1 = kj1.Abs();
+
+                int width = System.Math.Max(2, System.Math.Min(16, WNafUtilities.GetWindowSize(System.Math.Max(kj0.BitLength, kj1.BitLength))));
+
+                ECPoint P = ps[i], Q = WNafUtilities.MapPointWithPrecomp(P, width, true, pointMap);
+                infos[j0] = WNafUtilities.GetWNafPreCompInfo(P);
+                infos[j1] = WNafUtilities.GetWNafPreCompInfo(Q);
+                wnafs[j0] = WNafUtilities.GenerateWindowNaf(width, kj0);
+                wnafs[j1] = WNafUtilities.GenerateWindowNaf(width, kj1);
+            }
+
+            return ImplSumOfMultiplies(negs, infos, wnafs);
+        }
+
+        private static ECPoint ImplSumOfMultiplies(bool[] negs, WNafPreCompInfo[] infos, byte[][] wnafs)
+        {
+            int len = 0, count = wnafs.Length;
+            for (int i = 0; i < count; ++i)
+            {
                 len = System.Math.Max(len, wnafs[i].Length);
             }
 
-            ECCurve curve = ps[0].Curve;
+            ECCurve curve = infos[0].PreComp[0].Curve;
             ECPoint infinity = curve.Infinity;
 
             ECPoint R = infinity;
@@ -304,7 +386,7 @@ namespace Org.BouncyCastle.Math.EC
                     {
                         int n = System.Math.Abs(wi);
                         WNafPreCompInfo info = infos[j];
-                        ECPoint[] table = wi < 0 ? info.PreCompNeg : info.PreComp;
+                        ECPoint[] table = (wi < 0 == negs[j]) ? info.PreCompNeg : info.PreComp;
                         r = r.Add(table[n >> 1]);
                     }
                 }