Initial work on a fixed-point comb multiplier

3 files changed, 127 insertions, 0 deletions

diff --git a/core/src/main/java/org/bouncycastle/math/ec/FixedPointCombMultiplier.java b/core/src/main/java/org/bouncycastle/math/ec/FixedPointCombMultiplier.java
new file mode 100644
index 00000000..29c1fd3f
--- /dev/null
+++ b/core/src/main/java/org/bouncycastle/math/ec/FixedPointCombMultiplier.java
@@ -0,0 +1,36 @@
+package org.bouncycastle.math.ec;
+
+import java.math.BigInteger;
+
+public class FixedPointCombMultiplier extends AbstractECMultiplier
+{
+    protected ECPoint multiplyPositive(ECPoint p, BigInteger k)
+    {
+        int width = 4;
+
+        FixedPointPreCompInfo info = FixedPointUtil.precompute(p, width);
+        ECPoint[] lookupTable = info.getPreComp();
+
+        ECCurve c = p.getCurve();
+        int d = (c.getOrder().bitLength() + width - 1) / width;
+
+        ECPoint R = c.getInfinity();
+
+        for (int i = d - 1; i >= 0; --i)
+        {
+            int index = 0;
+            for (int j = width - 1; j >= 0; --j)
+            {
+                index <<= 1;
+                if (k.testBit(j * d + i))
+                {
+                    index |= 1;
+                }
+            }
+
+            R = R.twicePlus(lookupTable[index]);
+        }
+
+        return R;
+    }
+}
diff --git a/core/src/main/java/org/bouncycastle/math/ec/FixedPointPreCompInfo.java b/core/src/main/java/org/bouncycastle/math/ec/FixedPointPreCompInfo.java
new file mode 100644
index 00000000..7cfb7f47
--- /dev/null
+++ b/core/src/main/java/org/bouncycastle/math/ec/FixedPointPreCompInfo.java
@@ -0,0 +1,23 @@
+package org.bouncycastle.math.ec;
+
+/**
+ * Class holding precomputation data for fixed-point multiplications.
+ */
+public class FixedPointPreCompInfo implements PreCompInfo
+{
+    /**
+     * Array holding the precomputed <code>ECPoint</code>s used for a fixed
+     * point multiplication.
+     */
+    protected ECPoint[] preComp = null;
+
+    public ECPoint[] getPreComp()
+    {
+        return preComp;
+    }
+
+    public void setPreComp(ECPoint[] preComp)
+    {
+        this.preComp = preComp;
+    }
+}
diff --git a/core/src/main/java/org/bouncycastle/math/ec/FixedPointUtil.java b/core/src/main/java/org/bouncycastle/math/ec/FixedPointUtil.java
new file mode 100644
index 00000000..4c0d0b04
--- /dev/null
+++ b/core/src/main/java/org/bouncycastle/math/ec/FixedPointUtil.java
@@ -0,0 +1,68 @@
+package org.bouncycastle.math.ec;
+
+import java.math.BigInteger;
+
+public class FixedPointUtil
+{
+    public static FixedPointPreCompInfo getFixedPointPreCompInfo(PreCompInfo preCompInfo)
+    {
+        if ((preCompInfo != null) && (preCompInfo instanceof FixedPointPreCompInfo))
+        {
+            return (FixedPointPreCompInfo)preCompInfo;
+        }
+
+        return new FixedPointPreCompInfo();
+    }
+
+    public static FixedPointPreCompInfo precompute(ECPoint p, int width)
+    {
+        ECCurve c = p.getCurve();
+
+        int n = 1 << width;
+        FixedPointPreCompInfo info = getFixedPointPreCompInfo(c.getPreCompInfo(p));
+        ECPoint[] lookupTable = info.getPreComp();
+
+        if (lookupTable == null || lookupTable.length != n)
+        {
+            BigInteger order = c.getOrder();
+            if (order == null)
+            {
+                throw new IllegalStateException("fixed-point precomputation needs the curve order");
+            }
+
+            int bits = order.bitLength();
+            int d = (bits + width - 1) / width;
+
+            ECPoint[] pow2Table = new ECPoint[width];
+            pow2Table[0] = p;
+            for (int i = 1; i < width; ++i)
+            {
+                pow2Table[i] = pow2Table[i - 1].timesPow2(d);
+            }
+    
+            c.normalizeAll(pow2Table);
+    
+            lookupTable = new ECPoint[n];
+            lookupTable[0] = c.getInfinity();
+    
+            for (int bit = width - 1; bit >= 0; --bit)
+            {
+                ECPoint pow2 = pow2Table[bit];
+
+                int step = 1 << bit;
+                for (int i = step; i < n; i += (step << 1))
+                {
+                    lookupTable[i] = lookupTable[i - step].add(pow2);
+                }
+            }
+    
+            c.normalizeAll(lookupTable);
+
+            info.setPreComp(lookupTable);
+
+            c.setPreCompInfo(p, info);
+        }
+
+        return info;
+    }
+}