Initial work on a fixed-point comb multiplier

4 files changed, 141 insertions, 0 deletions

diff --git a/crypto/crypto.csproj b/crypto/crypto.csproj
index da99b5e97..6e4cc23d1 100644
--- a/crypto/crypto.csproj
+++ b/crypto/crypto.csproj
@@ -4809,6 +4809,21 @@
                     BuildAction = "Compile"
                 />
                 <File
+                    RelPath = "src\math\ec\multiplier\FixedPointCombMultiplier.cs"
+                    SubType = "Code"
+                    BuildAction = "Compile"
+                />
+                <File
+                    RelPath = "src\math\ec\multiplier\FixedPointPreCompInfo.cs"
+                    SubType = "Code"
+                    BuildAction = "Compile"
+                />
+                <File
+                    RelPath = "src\math\ec\multiplier\FixedPointUtilities.cs"
+                    SubType = "Code"
+                    BuildAction = "Compile"
+                />
+                <File
                     RelPath = "src\math\ec\multiplier\MixedNafR2LMultiplier.cs"
                     SubType = "Code"
                     BuildAction = "Compile"
diff --git a/crypto/src/math/ec/multiplier/FixedPointCombMultiplier.cs b/crypto/src/math/ec/multiplier/FixedPointCombMultiplier.cs
new file mode 100644
index 000000000..51ed5d7c5
--- /dev/null
+++ b/crypto/src/math/ec/multiplier/FixedPointCombMultiplier.cs
@@ -0,0 +1,38 @@
+using System;
+
+namespace Org.BouncyCastle.Math.EC.Multiplier
+{
+    public class FixedPointCombMultiplier
+        : AbstractECMultiplier
+    {
+        protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k)
+        {
+            int width = 4;
+
+            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 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/crypto/src/math/ec/multiplier/FixedPointPreCompInfo.cs b/crypto/src/math/ec/multiplier/FixedPointPreCompInfo.cs
new file mode 100644
index 000000000..306f40a11
--- /dev/null
+++ b/crypto/src/math/ec/multiplier/FixedPointPreCompInfo.cs
@@ -0,0 +1,21 @@
+namespace Org.BouncyCastle.Math.EC.Multiplier
+{
+    /**
+     * Class holding precomputation data for fixed-point multiplications.
+     */
+    public class FixedPointPreCompInfo
+        : PreCompInfo
+    {
+        /**
+         * Array holding the precomputed <code>ECPoint</code>s used for a fixed
+         * point multiplication.
+         */
+        protected ECPoint[] m_preComp = null;
+
+        public virtual ECPoint[] PreComp
+        {
+            get { return m_preComp; }
+            set { this.m_preComp = value; }
+        }
+    }
+}
diff --git a/crypto/src/math/ec/multiplier/FixedPointUtilities.cs b/crypto/src/math/ec/multiplier/FixedPointUtilities.cs
new file mode 100644
index 000000000..ddce74d31
--- /dev/null
+++ b/crypto/src/math/ec/multiplier/FixedPointUtilities.cs
@@ -0,0 +1,67 @@
+using System;
+
+namespace Org.BouncyCastle.Math.EC.Multiplier
+{
+    public class FixedPointUtilities
+    {
+        public static FixedPointPreCompInfo GetFixedPointPreCompInfo(PreCompInfo preCompInfo)
+        {
+            if ((preCompInfo != null) && (preCompInfo is FixedPointPreCompInfo))
+            {
+                return (FixedPointPreCompInfo)preCompInfo;
+            }
+
+            return new FixedPointPreCompInfo();
+        }
+
+        public static FixedPointPreCompInfo Precompute(ECPoint p, int width)
+        {
+            ECCurve c = p.Curve;
+
+            int n = 1 << width;
+            FixedPointPreCompInfo info = GetFixedPointPreCompInfo(c.GetPreCompInfo(p));
+            ECPoint[] lookupTable = info.PreComp;
+
+            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 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.Infinity;
+
+                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.PreComp = lookupTable;
+
+                c.SetPreCompInfo(p, info);
+            }
+
+            return info;
+        }
+    }
+}