A few improvements to the fixed-point comb

2 files changed, 28 insertions, 10 deletions

diff --git a/crypto/src/math/ec/multiplier/FixedPointCombMultiplier.cs b/crypto/src/math/ec/multiplier/FixedPointCombMultiplier.cs
index 51ed5d7c5..bbfe71a0d 100644
--- a/crypto/src/math/ec/multiplier/FixedPointCombMultiplier.cs
+++ b/crypto/src/math/ec/multiplier/FixedPointCombMultiplier.cs
@@ -7,23 +7,39 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
     {
         protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k)
         {
-            int width = 4;
+            ECCurve c = p.Curve;
+            int size = FixedPointUtilities.GetCombSize(c);
+
+            if (k.BitLength > size)
+            {
+                /*
+                 * TODO The comb works best when the scalars are less than the (possibly unknown) order.
+                 * Still, if we want to handle larger scalars, we could allow customization of the comb
+                 * size, or alternatively we could deal with the 'extra' bits either by running the comb
+                 * multiple times as necessary, or by using an alternative multiplier as prelude.
+                 */
+                throw new InvalidOperationException("fixed-point comb doesn't support scalars larger than the curve order");
+            }
+
+            // TODO Call method to let subclasses select width
+            int width = size > 257 ? 6 : 5;
 
             FixedPointPreCompInfo info = FixedPointUtilities.Precompute(p, width);
             ECPoint[] lookupTable = info.PreComp;
 
-            ECCurve c = p.Curve;
             int d = (c.Order.BitLength + width - 1) / width;
 
             ECPoint R = c.Infinity;
 
-            for (int i = d - 1; i >= 0; --i)
+            int top = d * width - 1;
+            for (int i = 0; i < d; ++i)
             {
                 int index = 0;
-                for (int j = width - 1; j >= 0; --j)
+
+                for (int j = top - i; j >= 0; j -= d)
                 {
                     index <<= 1;
-                    if (k.TestBit(j * d + i))
+                    if (k.TestBit(j))
                     {
                         index |= 1;
                     }
diff --git a/crypto/src/math/ec/multiplier/FixedPointUtilities.cs b/crypto/src/math/ec/multiplier/FixedPointUtilities.cs
index ddce74d31..8a04fcdc1 100644
--- a/crypto/src/math/ec/multiplier/FixedPointUtilities.cs
+++ b/crypto/src/math/ec/multiplier/FixedPointUtilities.cs
@@ -4,6 +4,12 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
 {
     public class FixedPointUtilities
     {
+        public static int GetCombSize(ECCurve c)
+        {
+            BigInteger order = c.Order;
+            return order == null ? c.FieldSize + 1 : order.BitLength;
+        }
+
         public static FixedPointPreCompInfo GetFixedPointPreCompInfo(PreCompInfo preCompInfo)
         {
             if ((preCompInfo != null) && (preCompInfo is FixedPointPreCompInfo))
@@ -24,11 +30,7 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
 
             if (lookupTable == null || lookupTable.Length != n)
             {
-                BigInteger order = c.Order;
-                if (order == null)
-                    throw new InvalidOperationException("fixed-point precomputation needs the curve order");
-
-                int bits = order.BitLength;
+                int bits = GetCombSize(c);
                 int d = (bits + width - 1) / width;
 
                 ECPoint[] pow2Table = new ECPoint[width];