diff options
Diffstat (limited to 'core/src/main/java/org/bouncycastle/math/ec/WNafMultiplier.java')
| -rw-r--r-- | core/src/main/java/org/bouncycastle/math/ec/WNafMultiplier.java | 240 |
1 files changed, 240 insertions, 0 deletions
diff --git a/core/src/main/java/org/bouncycastle/math/ec/WNafMultiplier.java b/core/src/main/java/org/bouncycastle/math/ec/WNafMultiplier.java new file mode 100644 index 00000000..10c8ed24 --- /dev/null +++ b/core/src/main/java/org/bouncycastle/math/ec/WNafMultiplier.java @@ -0,0 +1,240 @@ +package org.bouncycastle.math.ec; + +import java.math.BigInteger; + +/** + * Class implementing the WNAF (Window Non-Adjacent Form) multiplication + * algorithm. + */ +class WNafMultiplier implements ECMultiplier +{ + /** + * Computes the Window NAF (non-adjacent Form) of an integer. + * @param width The width <code>w</code> of the Window NAF. The width is + * defined as the minimal number <code>w</code>, such that for any + * <code>w</code> consecutive digits in the resulting representation, at + * most one is non-zero. + * @param k The integer of which the Window NAF is computed. + * @return The Window NAF of the given width, such that the following holds: + * <code>k = ∑<sub>i=0</sub><sup>l-1</sup> k<sub>i</sub>2<sup>i</sup> + * </code>, where the <code>k<sub>i</sub></code> denote the elements of the + * returned <code>byte[]</code>. + */ + public byte[] windowNaf(byte width, BigInteger k) + { + // The window NAF is at most 1 element longer than the binary + // representation of the integer k. byte can be used instead of short or + // int unless the window width is larger than 8. For larger width use + // short or int. However, a width of more than 8 is not efficient for + // m = log2(q) smaller than 2305 Bits. Note: Values for m larger than + // 1000 Bits are currently not used in practice. + byte[] wnaf = new byte[k.bitLength() + 1]; + + // 2^width as short and BigInteger + short pow2wB = (short)(1 << width); + BigInteger pow2wBI = BigInteger.valueOf(pow2wB); + + int i = 0; + + // The actual length of the WNAF + int length = 0; + + // while k >= 1 + while (k.signum() > 0) + { + // if k is odd + if (k.testBit(0)) + { + // k mod 2^width + BigInteger remainder = k.mod(pow2wBI); + + // if remainder > 2^(width - 1) - 1 + if (remainder.testBit(width - 1)) + { + wnaf[i] = (byte)(remainder.intValue() - pow2wB); + } + else + { + wnaf[i] = (byte)remainder.intValue(); + } + // wnaf[i] is now in [-2^(width-1), 2^(width-1)-1] + + k = k.subtract(BigInteger.valueOf(wnaf[i])); + length = i; + } + else + { + wnaf[i] = 0; + } + + // k = k/2 + k = k.shiftRight(1); + i++; + } + + length++; + + // Reduce the WNAF array to its actual length + byte[] wnafShort = new byte[length]; + System.arraycopy(wnaf, 0, wnafShort, 0, length); + return wnafShort; + } + + /** + * Multiplies <code>this</code> by an integer <code>k</code> using the + * Window NAF method. + * @param k The integer by which <code>this</code> is multiplied. + * @return A new <code>ECPoint</code> which equals <code>this</code> + * multiplied by <code>k</code>. + */ + public ECPoint multiply(ECPoint p, BigInteger k, PreCompInfo preCompInfo) + { + WNafPreCompInfo wnafPreCompInfo; + + if ((preCompInfo != null) && (preCompInfo instanceof WNafPreCompInfo)) + { + wnafPreCompInfo = (WNafPreCompInfo)preCompInfo; + } + else + { + // Ignore empty PreCompInfo or PreCompInfo of incorrect type + wnafPreCompInfo = new WNafPreCompInfo(); + } + + // floor(log2(k)) + int m = k.bitLength(); + + // width of the Window NAF + byte width; + + // Required length of precomputation array + int reqPreCompLen; + + // Determine optimal width and corresponding length of precomputation + // array based on literature values + if (m < 13) + { + width = 2; + reqPreCompLen = 1; + } + else + { + if (m < 41) + { + width = 3; + reqPreCompLen = 2; + } + else + { + if (m < 121) + { + width = 4; + reqPreCompLen = 4; + } + else + { + if (m < 337) + { + width = 5; + reqPreCompLen = 8; + } + else + { + if (m < 897) + { + width = 6; + reqPreCompLen = 16; + } + else + { + if (m < 2305) + { + width = 7; + reqPreCompLen = 32; + } + else + { + width = 8; + reqPreCompLen = 127; + } + } + } + } + } + } + + // The length of the precomputation array + int preCompLen = 1; + + ECPoint[] preComp = wnafPreCompInfo.getPreComp(); + ECPoint twiceP = wnafPreCompInfo.getTwiceP(); + + // Check if the precomputed ECPoints already exist + if (preComp == null) + { + // Precomputation must be performed from scratch, create an empty + // precomputation array of desired length + preComp = new ECPoint[]{ p }; + } + else + { + // Take the already precomputed ECPoints to start with + preCompLen = preComp.length; + } + + if (twiceP == null) + { + // Compute twice(p) + twiceP = p.twice(); + } + + if (preCompLen < reqPreCompLen) + { + // Precomputation array must be made bigger, copy existing preComp + // array into the larger new preComp array + ECPoint[] oldPreComp = preComp; + preComp = new ECPoint[reqPreCompLen]; + System.arraycopy(oldPreComp, 0, preComp, 0, preCompLen); + + for (int i = preCompLen; i < reqPreCompLen; i++) + { + // Compute the new ECPoints for the precomputation array. + // The values 1, 3, 5, ..., 2^(width-1)-1 times p are + // computed + preComp[i] = twiceP.add(preComp[i - 1]); + } + } + + // Compute the Window NAF of the desired width + byte[] wnaf = windowNaf(width, k); + int l = wnaf.length; + + // Apply the Window NAF to p using the precomputed ECPoint values. + ECPoint q = p.getCurve().getInfinity(); + for (int i = l - 1; i >= 0; i--) + { + q = q.twice(); + + if (wnaf[i] != 0) + { + if (wnaf[i] > 0) + { + q = q.add(preComp[(wnaf[i] - 1)/2]); + } + else + { + // wnaf[i] < 0 + q = q.subtract(preComp[(-wnaf[i] - 1)/2]); + } + } + } + + // Set PreCompInfo in ECPoint, such that it is available for next + // multiplication. + wnafPreCompInfo.setPreComp(preComp); + wnafPreCompInfo.setTwiceP(twiceP); + p.setPreCompInfo(wnafPreCompInfo); + return q; + } + +} |