Improve caching behaviour for algorithms using endomorphisms

9 files changed, 187 insertions, 19 deletions

diff --git a/crypto/BouncyCastle.Android.csproj b/crypto/BouncyCastle.Android.csproj
index 2c2c44f86..c1c53fc52 100644
--- a/crypto/BouncyCastle.Android.csproj
+++ b/crypto/BouncyCastle.Android.csproj
@@ -1342,6 +1342,7 @@
     <Compile Include="src\math\ec\custom\sec\SecT571R1Curve.cs" />
     <Compile Include="src\math\ec\custom\sec\SecT571R1Point.cs" />
     <Compile Include="src\math\ec\endo\ECEndomorphism.cs" />
+    <Compile Include="src\math\ec\endo\EndoPreCompInfo.cs" />
     <Compile Include="src\math\ec\endo\EndoUtilities.cs" />
     <Compile Include="src\math\ec\endo\GlvEndomorphism.cs" />
     <Compile Include="src\math\ec\endo\GlvTypeAEndomorphism.cs" />
diff --git a/crypto/BouncyCastle.csproj b/crypto/BouncyCastle.csproj
index 6a5e58829..3ba21ac66 100644
--- a/crypto/BouncyCastle.csproj
+++ b/crypto/BouncyCastle.csproj
@@ -1336,6 +1336,7 @@
     <Compile Include="src\math\ec\custom\sec\SecT571R1Curve.cs" />
     <Compile Include="src\math\ec\custom\sec\SecT571R1Point.cs" />
     <Compile Include="src\math\ec\endo\ECEndomorphism.cs" />
+    <Compile Include="src\math\ec\endo\EndoPreCompInfo.cs" />
     <Compile Include="src\math\ec\endo\EndoUtilities.cs" />
     <Compile Include="src\math\ec\endo\GlvEndomorphism.cs" />
     <Compile Include="src\math\ec\endo\GlvTypeAEndomorphism.cs" />
diff --git a/crypto/BouncyCastle.iOS.csproj b/crypto/BouncyCastle.iOS.csproj
index 8194180f5..b6810009b 100644
--- a/crypto/BouncyCastle.iOS.csproj
+++ b/crypto/BouncyCastle.iOS.csproj
@@ -1337,6 +1337,7 @@
     <Compile Include="src\math\ec\custom\sec\SecT571R1Curve.cs" />
     <Compile Include="src\math\ec\custom\sec\SecT571R1Point.cs" />
     <Compile Include="src\math\ec\endo\ECEndomorphism.cs" />
+    <Compile Include="src\math\ec\endo\EndoPreCompInfo.cs" />
     <Compile Include="src\math\ec\endo\EndoUtilities.cs" />
     <Compile Include="src\math\ec\endo\GlvEndomorphism.cs" />
     <Compile Include="src\math\ec\endo\GlvTypeAEndomorphism.cs" />
diff --git a/crypto/crypto.csproj b/crypto/crypto.csproj
index 4e6330818..7789d1858 100644
--- a/crypto/crypto.csproj
+++ b/crypto/crypto.csproj
@@ -6569,6 +6569,11 @@
                     BuildAction = "Compile"
                 />
                 <File
+                    RelPath = "src\math\ec\endo\EndoPreCompInfo.cs"
+                    SubType = "Code"
+                    BuildAction = "Compile"
+                />
+                <File
                     RelPath = "src\math\ec\endo\EndoUtilities.cs"
                     SubType = "Code"
                     BuildAction = "Compile"
diff --git a/crypto/src/math/ec/ECAlgorithms.cs b/crypto/src/math/ec/ECAlgorithms.cs
index 14658ac81..69139df01 100644
--- a/crypto/src/math/ec/ECAlgorithms.cs
+++ b/crypto/src/math/ec/ECAlgorithms.cs
@@ -288,7 +288,7 @@ namespace Org.BouncyCastle.Math.EC
             return ImplShamirsTrickWNaf(preCompP, preCompNegP, wnafP, preCompQ, preCompNegQ, wnafQ);
         }
 
-        internal static ECPoint ImplShamirsTrickWNaf(ECPoint P, BigInteger k, ECPointMap pointMapQ, BigInteger l)
+        internal static ECPoint ImplShamirsTrickWNaf(ECEndomorphism endomorphism, ECPoint P, BigInteger k, BigInteger l)
         {
             bool negK = k.SignValue < 0, negL = l.SignValue < 0;
 
@@ -297,9 +297,9 @@ namespace Org.BouncyCastle.Math.EC
 
             int minWidth = WNafUtilities.GetWindowSize(System.Math.Max(k.BitLength, l.BitLength), 8);
 
-            ECPoint Q = WNafUtilities.MapPointWithPrecomp(P, minWidth, true, pointMapQ); 
-            WNafPreCompInfo infoP = WNafUtilities.GetWNafPreCompInfo(P);
-            WNafPreCompInfo infoQ = WNafUtilities.GetWNafPreCompInfo(Q);
+            WNafPreCompInfo infoP = WNafUtilities.Precompute(P, minWidth, true);
+            ECPoint Q = EndoUtilities.MapPoint(endomorphism, P);
+            WNafPreCompInfo infoQ = WNafUtilities.PrecomputeWithPointMap(Q, endomorphism.PointMap, infoP, true);
 
             int widthP = System.Math.Min(8, infoP.Width);
             int widthQ = System.Math.Min(8, infoQ.Width);
@@ -405,24 +405,24 @@ namespace Org.BouncyCastle.Math.EC
                 abs[j++] = ab[1];
             }
 
-            ECPointMap pointMap = glvEndomorphism.PointMap;
             if (glvEndomorphism.HasEfficientPointMap)
             {
-                return ECAlgorithms.ImplSumOfMultiplies(ps, pointMap, abs);
+                return ImplSumOfMultiplies(glvEndomorphism, ps, abs);
             }
 
             ECPoint[] pqs = new ECPoint[len << 1];
             for (int i = 0, j = 0; i < len; ++i)
             {
-                ECPoint p = ps[i], q = pointMap.Map(p);
+                ECPoint p = ps[i];
+                ECPoint q = EndoUtilities.MapPoint(glvEndomorphism, p); 
                 pqs[j++] = p;
                 pqs[j++] = q;
             }
 
-            return ECAlgorithms.ImplSumOfMultiplies(pqs, abs);
+            return ImplSumOfMultiplies(pqs, abs);
         }
 
-        internal static ECPoint ImplSumOfMultiplies(ECPoint[] ps, ECPointMap pointMap, BigInteger[] ks)
+        internal static ECPoint ImplSumOfMultiplies(ECEndomorphism endomorphism, ECPoint[] ps, BigInteger[] ks)
         {
             int halfCount = ps.Length, fullCount = halfCount << 1;
 
@@ -430,6 +430,8 @@ namespace Org.BouncyCastle.Math.EC
             WNafPreCompInfo[] infos = new WNafPreCompInfo[fullCount];
             byte[][] wnafs = new byte[fullCount][];
 
+            ECPointMap pointMap = endomorphism.PointMap;
+
             for (int i = 0; i < halfCount; ++i)
             {
                 int j0 = i << 1, j1 = j0 + 1;
@@ -438,10 +440,11 @@ namespace Org.BouncyCastle.Math.EC
                 BigInteger kj1 = ks[j1]; negs[j1] = kj1.SignValue < 0; kj1 = kj1.Abs();
 
                 int minWidth = WNafUtilities.GetWindowSize(System.Math.Max(kj0.BitLength, kj1.BitLength), 8);
-                ECPoint P = ps[i], Q = WNafUtilities.MapPointWithPrecomp(P, minWidth, true, pointMap);
 
-                WNafPreCompInfo infoP = WNafUtilities.GetWNafPreCompInfo(P);
-                WNafPreCompInfo infoQ = WNafUtilities.GetWNafPreCompInfo(Q);
+                ECPoint P = ps[i];
+                WNafPreCompInfo infoP = WNafUtilities.Precompute(P, minWidth, true);
+                ECPoint Q = EndoUtilities.MapPoint(endomorphism, P);
+                WNafPreCompInfo infoQ = WNafUtilities.PrecomputeWithPointMap(Q, pointMap, infoP, true);
 
                 int widthP = System.Math.Min(8, infoP.Width);
                 int widthQ = System.Math.Min(8, infoQ.Width);
diff --git a/crypto/src/math/ec/endo/EndoPreCompInfo.cs b/crypto/src/math/ec/endo/EndoPreCompInfo.cs
new file mode 100644
index 000000000..cb926fc98
--- /dev/null
+++ b/crypto/src/math/ec/endo/EndoPreCompInfo.cs
@@ -0,0 +1,26 @@
+using System;
+
+using Org.BouncyCastle.Math.EC.Multiplier;
+
+namespace Org.BouncyCastle.Math.EC.Endo
+{
+    public class EndoPreCompInfo
+        : PreCompInfo
+    {
+        protected ECEndomorphism m_endomorphism;
+
+        protected ECPoint m_mappedPoint;
+
+        public virtual ECEndomorphism Endomorphism
+        {
+            get { return m_endomorphism; }
+            set { this.m_endomorphism = value; }
+        }
+
+        public virtual ECPoint MappedPoint
+        {
+            get { return m_mappedPoint; }
+            set { this.m_mappedPoint = value; }
+        }
+    }
+}
diff --git a/crypto/src/math/ec/endo/EndoUtilities.cs b/crypto/src/math/ec/endo/EndoUtilities.cs
index 16916e632..843103bca 100644
--- a/crypto/src/math/ec/endo/EndoUtilities.cs
+++ b/crypto/src/math/ec/endo/EndoUtilities.cs
@@ -1,11 +1,13 @@
 using System;
 
-using Org.BouncyCastle.Math;
+using Org.BouncyCastle.Math.EC.Multiplier;
 
 namespace Org.BouncyCastle.Math.EC.Endo
 {
     public abstract class EndoUtilities
     {
+        public static readonly string PRECOMP_NAME = "bc_endo";
+
         public static BigInteger[] DecomposeScalar(ScalarSplitParameters p, BigInteger k)
         {
             int bits = p.Bits;
@@ -18,6 +20,13 @@ namespace Org.BouncyCastle.Math.EC.Endo
             return new BigInteger[]{ a, b };
         }
 
+        public static ECPoint MapPoint(ECEndomorphism endomorphism, ECPoint p)
+        {
+            EndoPreCompInfo precomp = (EndoPreCompInfo)p.Curve.Precompute(p, PRECOMP_NAME,
+                new MapPointCallback(endomorphism, p));
+            return precomp.MappedPoint;
+        }
+
         private static BigInteger CalculateB(BigInteger k, BigInteger g, int t)
         {
             bool negative = (g.SignValue < 0);
@@ -30,5 +39,41 @@ namespace Org.BouncyCastle.Math.EC.Endo
             }
             return negative ? b.Negate() : b;
         }
+
+        private class MapPointCallback
+            : IPreCompCallback
+        {
+            private readonly ECEndomorphism m_endomorphism;
+            private readonly ECPoint m_point;
+
+            internal MapPointCallback(ECEndomorphism endomorphism, ECPoint point)
+            {
+                this.m_endomorphism = endomorphism;
+                this.m_point = point;
+            }
+
+            public PreCompInfo Precompute(PreCompInfo existing)
+            {
+                EndoPreCompInfo existingEndo = existing as EndoPreCompInfo;
+
+                if (CheckExisting(existingEndo, m_endomorphism))
+                    return existingEndo;
+
+                ECPoint mappedPoint = m_endomorphism.PointMap.Map(m_point);
+
+                EndoPreCompInfo result = new EndoPreCompInfo();
+                result.Endomorphism = m_endomorphism;
+                result.MappedPoint = mappedPoint;
+                return result;
+            }
+
+            private bool CheckExisting(EndoPreCompInfo existingEndo, ECEndomorphism endomorphism)
+            {
+                return null != existingEndo
+                    && existingEndo.Endomorphism == endomorphism
+                    && existingEndo.MappedPoint != null;
+            }
+
+        }
     }
 }
diff --git a/crypto/src/math/ec/multiplier/GlvMultiplier.cs b/crypto/src/math/ec/multiplier/GlvMultiplier.cs
index f19049474..9ef7d6e24 100644
--- a/crypto/src/math/ec/multiplier/GlvMultiplier.cs
+++ b/crypto/src/math/ec/multiplier/GlvMultiplier.cs
@@ -28,13 +28,14 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
             BigInteger[] ab = glvEndomorphism.DecomposeScalar(k.Mod(n));
             BigInteger a = ab[0], b = ab[1];
 
-            ECPointMap pointMap = glvEndomorphism.PointMap;
             if (glvEndomorphism.HasEfficientPointMap)
             {
-                return ECAlgorithms.ImplShamirsTrickWNaf(p, a, pointMap, b);
+                return ECAlgorithms.ImplShamirsTrickWNaf(glvEndomorphism, p, a, b);
             }
 
-            return ECAlgorithms.ImplShamirsTrickWNaf(p, a, pointMap.Map(p), b);
+            ECPoint q = EndoUtilities.MapPoint(glvEndomorphism, p);
+
+            return ECAlgorithms.ImplShamirsTrickWNaf(p, a, q, b);
         }
     }
 }
diff --git a/crypto/src/math/ec/multiplier/WNafUtilities.cs b/crypto/src/math/ec/multiplier/WNafUtilities.cs
index 01599d777..65d876449 100644
--- a/crypto/src/math/ec/multiplier/WNafUtilities.cs
+++ b/crypto/src/math/ec/multiplier/WNafUtilities.cs
@@ -361,6 +361,7 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
             return System.Math.Max(2, System.Math.Min(maxWidth, w + 2));
         }
 
+        [Obsolete]
         public static ECPoint MapPointWithPrecomp(ECPoint p, int minWidth, bool includeNegated,
             ECPointMap pointMap)
         {
@@ -374,7 +375,15 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
 
         public static WNafPreCompInfo Precompute(ECPoint p, int minWidth, bool includeNegated)
         {
-            return (WNafPreCompInfo)p.Curve.Precompute(p, PRECOMP_NAME, new WNafCallback(p, minWidth, includeNegated));
+            return (WNafPreCompInfo)p.Curve.Precompute(p, PRECOMP_NAME,
+                new PrecomputeCallback(p, minWidth, includeNegated));
+        }
+
+        public static WNafPreCompInfo PrecomputeWithPointMap(ECPoint p, ECPointMap pointMap, WNafPreCompInfo fromWNaf,
+            bool includeNegated)
+        {
+            return (WNafPreCompInfo)p.Curve.Precompute(p, PRECOMP_NAME,
+                new PrecomputeWithPointMapCallback(p, pointMap, fromWNaf, includeNegated));
         }
 
         private static byte[] Trim(byte[] a, int length)
@@ -485,14 +494,14 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
             }
         }
 
-        private class WNafCallback
+        private class PrecomputeCallback
             : IPreCompCallback
         {
             private readonly ECPoint m_p;
             private readonly int m_minWidth;
             private readonly bool m_includeNegated;
 
-            internal WNafCallback(ECPoint p, int minWidth, bool includeNegated)
+            internal PrecomputeCallback(ECPoint p, int minWidth, bool includeNegated)
             {
                 this.m_p = p;
                 this.m_minWidth = minWidth;
@@ -665,5 +674,81 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
                 return null != table && table.Length >= reqLen;
             }
         }
+
+        private class PrecomputeWithPointMapCallback
+            : IPreCompCallback
+        {
+            private readonly ECPoint m_point;
+            private readonly ECPointMap m_pointMap;
+            private readonly WNafPreCompInfo m_fromWNaf;
+            private readonly bool m_includeNegated;
+
+            internal PrecomputeWithPointMapCallback(ECPoint point, ECPointMap pointMap, WNafPreCompInfo fromWNaf,
+                bool includeNegated)
+            {
+                this.m_point = point;
+                this.m_pointMap = pointMap;
+                this.m_fromWNaf = fromWNaf;
+                this.m_includeNegated = includeNegated;
+            }
+
+            public PreCompInfo Precompute(PreCompInfo existing)
+            {
+                WNafPreCompInfo existingWNaf = existing as WNafPreCompInfo;
+
+                int width = m_fromWNaf.Width;
+                int reqPreCompLen = m_fromWNaf.PreComp.Length;
+
+                if (CheckExisting(existingWNaf, width, reqPreCompLen, m_includeNegated))
+                    return existingWNaf;
+
+                /*
+                 * TODO Ideally this method would support incremental calculation, but given the
+                 * existing use-cases it would be of little-to-no benefit.
+                 */
+                WNafPreCompInfo result = new WNafPreCompInfo();
+
+                ECPoint twiceFrom = m_fromWNaf.Twice;
+                if (null != twiceFrom)
+                {
+                    ECPoint twice = m_pointMap.Map(twiceFrom);
+                    result.Twice = twice;
+                }
+
+                ECPoint[] preCompFrom = m_fromWNaf.PreComp;
+                ECPoint[] preComp = new ECPoint[preCompFrom.Length];
+                for (int i = 0; i < preCompFrom.Length; ++i)
+                {
+                    preComp[i] = m_pointMap.Map(preCompFrom[i]);
+                }
+                result.PreComp = preComp;
+                result.Width = width;
+
+                if (m_includeNegated)
+                {
+                    ECPoint[] preCompNeg = new ECPoint[preComp.Length];
+                    for (int i = 0; i < preCompNeg.Length; ++i)
+                    {
+                        preCompNeg[i] = preComp[i].Negate();
+                    }
+                    result.PreCompNeg = preCompNeg;
+                }
+
+                return result;
+            }
+
+            private bool CheckExisting(WNafPreCompInfo existingWNaf, int width, int reqPreCompLen, bool includeNegated)
+            {
+                return null != existingWNaf
+                    && existingWNaf.Width >= width
+                    && CheckTable(existingWNaf.PreComp, reqPreCompLen)
+                    && (!includeNegated || CheckTable(existingWNaf.PreCompNeg, reqPreCompLen));
+            }
+
+            private bool CheckTable(ECPoint[] table, int reqLen)
+            {
+                return null != table && table.Length >= reqLen;
+            }
+        }
     }
 }