Cache-safety for EC lookup tables

- creation of cache-safe lookup tables delegated to ECCurve
- FixedPointCombMultiplier uses cache-safe lookup table
- FixedPointCombMultiplier avoids BigInteger.TestBit

3 files changed, 39 insertions, 13 deletions

diff --git a/crypto/src/math/ec/multiplier/FixedPointCombMultiplier.cs b/crypto/src/math/ec/multiplier/FixedPointCombMultiplier.cs
index 05bb4000b..adaedb809 100644
--- a/crypto/src/math/ec/multiplier/FixedPointCombMultiplier.cs
+++ b/crypto/src/math/ec/multiplier/FixedPointCombMultiplier.cs
@@ -1,5 +1,7 @@
 using System;
 
+using Org.BouncyCastle.Math.Raw;
+
 namespace Org.BouncyCastle.Math.EC.Multiplier
 {
     public class FixedPointCombMultiplier
@@ -21,36 +23,37 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
                 throw new InvalidOperationException("fixed-point comb doesn't support scalars larger than the curve order");
             }
 
-            int minWidth = GetWidthForCombSize(size);
-
-            FixedPointPreCompInfo info = FixedPointUtilities.Precompute(p, minWidth);
-            ECPoint[] lookupTable = info.PreComp;
+            FixedPointPreCompInfo info = FixedPointUtilities.Precompute(p);
+            ECLookupTable lookupTable = info.LookupTable;
             int width = info.Width;
 
             int d = (size + width - 1) / width;
 
             ECPoint R = c.Infinity;
 
-            int top = d * width - 1;
+            int fullComb = d * width;
+            uint[] K = Nat.FromBigInteger(fullComb, k);
+
+            int top = fullComb - 1;
             for (int i = 0; i < d; ++i)
             {
-                int index = 0;
+                int secretIndex = 0;
 
                 for (int j = top - i; j >= 0; j -= d)
                 {
-                    index <<= 1;
-                    if (k.TestBit(j))
-                    {
-                        index |= 1;
-                    }
+                    secretIndex <<= 1;
+                    secretIndex |= (int)Nat.GetBit(K, j);
                 }
 
-                R = R.TwicePlus(lookupTable[index]);
+                ECPoint add = lookupTable.Lookup(secretIndex);
+
+                R = R.TwicePlus(add);
             }
 
             return R.Add(info.Offset);
         }
 
+        [Obsolete("Is no longer used; remove any overrides in subclasses.")]
         protected virtual int GetWidthForCombSize(int combSize)
         {
             return combSize > 257 ? 6 : 5;
diff --git a/crypto/src/math/ec/multiplier/FixedPointPreCompInfo.cs b/crypto/src/math/ec/multiplier/FixedPointPreCompInfo.cs
index 11bdadc6f..4c0b404df 100644
--- a/crypto/src/math/ec/multiplier/FixedPointPreCompInfo.cs
+++ b/crypto/src/math/ec/multiplier/FixedPointPreCompInfo.cs
@@ -1,4 +1,6 @@
-namespace Org.BouncyCastle.Math.EC.Multiplier
+using System;
+
+namespace Org.BouncyCastle.Math.EC.Multiplier
 {
     /**
      * Class holding precomputation data for fixed-point multiplications.
@@ -12,21 +14,34 @@
          * Array holding the precomputed <code>ECPoint</code>s used for a fixed
          * point multiplication.
          */
+        [Obsolete("Will be removed")]
 		protected ECPoint[] m_preComp = null;
 
         /**
+         * Lookup table for the precomputed <code>ECPoint</code>s used for a fixed point multiplication.
+         */
+        protected ECLookupTable m_lookupTable = null;
+
+        /**
          * The width used for the precomputation. If a larger width precomputation
          * is already available this may be larger than was requested, so calling
          * code should refer to the actual width.
          */
         protected int m_width = -1;
 
+        public virtual ECLookupTable LookupTable
+        {
+            get { return m_lookupTable; }
+            set { this.m_lookupTable = value; }
+        }
+
         public virtual ECPoint Offset
         {
 			get { return m_offset; }
 			set { this.m_offset = value; }
 		}
 
+        [Obsolete("Use 'LookupTable' property instead.")]
         public virtual ECPoint[] PreComp
         {
             get { return m_preComp; }
diff --git a/crypto/src/math/ec/multiplier/FixedPointUtilities.cs b/crypto/src/math/ec/multiplier/FixedPointUtilities.cs
index 8e129a8f3..cc7203314 100644
--- a/crypto/src/math/ec/multiplier/FixedPointUtilities.cs
+++ b/crypto/src/math/ec/multiplier/FixedPointUtilities.cs
@@ -22,9 +22,16 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
             return new FixedPointPreCompInfo();
         }
 
+        [Obsolete("Use 'Precompute(ECPoint)' instead, as minWidth parameter is now ignored")]
         public static FixedPointPreCompInfo Precompute(ECPoint p, int minWidth)
         {
+            return Precompute(p);
+        }
+
+        public static FixedPointPreCompInfo Precompute(ECPoint p)
+        {
             ECCurve c = p.Curve;
+            int minWidth = GetCombSize(c) > 257 ? 6 : 5;
 
             int n = 1 << minWidth;
             FixedPointPreCompInfo info = GetFixedPointPreCompInfo(c.GetPreCompInfo(p, PRECOMP_NAME));
@@ -63,6 +70,7 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
 
                 c.NormalizeAll(lookupTable);
 
+                info.LookupTable = c.CreateCacheSafeLookupTable(lookupTable, 0, lookupTable.Length);
                 info.Offset = pow2Table[minWidth];
                 info.PreComp = lookupTable;
                 info.Width = minWidth;