diff options
author | Peter Dettman <peter.dettman@bouncycastle.org> | 2014-02-04 13:04:17 +0400 |
---|---|---|
committer | Peter Dettman <peter.dettman@bouncycastle.org> | 2014-02-04 13:04:17 +0400 |
commit | 81fd698870753b9e32845bb02e8e99ad81fa7f65 (patch) | |
tree | 97a529725779b2b8fd6e588fc4fec72da1f00de5 /core/src | |
parent | bdb3388c6313cf25a9ff474e1f6e9ffcdafb6b52 (diff) |
Initial work on a fixed-point comb multiplier
Diffstat (limited to 'core/src')
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; + } +} |