A few improvements to the fixed-point comb

1 files changed, 21 insertions, 5 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;
                     }