Initial work on a fixed-point comb multiplier
3 files changed, 126 insertions, 0 deletions
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;
+ }
+ }
+}
|
