diff options
author | Peter Dettman <peter.dettman@bouncycastle.org> | 2014-01-23 18:21:40 +0700 |
---|---|---|
committer | Peter Dettman <peter.dettman@bouncycastle.org> | 2014-01-23 18:21:40 +0700 |
commit | 0f05a8dc4b27623d96b08f7619c056a4e65baa9b (patch) | |
tree | 18169d7c4c8fbea895811eba8fbe7a9b9e6250ab /crypto/src/math/ec/multiplier | |
parent | Use ImportPoint to make sure points are on same curve (diff) | |
download | BouncyCastle.NET-ed25519-0f05a8dc4b27623d96b08f7619c056a4e65baa9b.tar.xz |
Port of several interrelated things from Java build:
- Z coordinates for points - More point normalization code - Curve management of point precomp info - Add WNafUtilities and use in multipliers/ECAlgorithms - Make various fields/classes protected/public
Diffstat (limited to 'crypto/src/math/ec/multiplier')
-rw-r--r-- | crypto/src/math/ec/multiplier/ECMultiplier.cs | 30 | ||||
-rw-r--r-- | crypto/src/math/ec/multiplier/FpNafMultiplier.cs | 41 | ||||
-rw-r--r-- | crypto/src/math/ec/multiplier/ReferenceMultiplier.cs | 61 | ||||
-rw-r--r-- | crypto/src/math/ec/multiplier/WNafMultiplier.cs | 274 | ||||
-rw-r--r-- | crypto/src/math/ec/multiplier/WNafPreCompInfo.cs | 76 | ||||
-rw-r--r-- | crypto/src/math/ec/multiplier/WNafUtilities.cs | 394 | ||||
-rw-r--r-- | crypto/src/math/ec/multiplier/WTauNafMultiplier.cs | 207 | ||||
-rw-r--r-- | crypto/src/math/ec/multiplier/WTauNafPreCompInfo.cs | 57 |
8 files changed, 688 insertions, 452 deletions
diff --git a/crypto/src/math/ec/multiplier/ECMultiplier.cs b/crypto/src/math/ec/multiplier/ECMultiplier.cs index ad576ff55..8d6136b34 100644 --- a/crypto/src/math/ec/multiplier/ECMultiplier.cs +++ b/crypto/src/math/ec/multiplier/ECMultiplier.cs @@ -1,18 +1,18 @@ namespace Org.BouncyCastle.Math.EC.Multiplier { - /** - * Interface for classes encapsulating a point multiplication algorithm - * for <code>ECPoint</code>s. - */ - public interface ECMultiplier - { - /** - * Multiplies the <code>ECPoint p</code> by <code>k</code>, i.e. - * <code>p</code> is added <code>k</code> times to itself. - * @param p The <code>ECPoint</code> to be multiplied. - * @param k The factor by which <code>p</code> i multiplied. - * @return <code>p</code> multiplied by <code>k</code>. - */ - ECPoint Multiply(ECPoint p, BigInteger k, PreCompInfo preCompInfo); - } + /** + * Interface for classes encapsulating a point multiplication algorithm + * for <code>ECPoint</code>s. + */ + public interface ECMultiplier + { + /** + * Multiplies the <code>ECPoint p</code> by <code>k</code>, i.e. + * <code>p</code> is added <code>k</code> times to itself. + * @param p The <code>ECPoint</code> to be multiplied. + * @param k The factor by which <code>p</code> is multiplied. + * @return <code>p</code> multiplied by <code>k</code>. + */ + ECPoint Multiply(ECPoint p, BigInteger k); + } } diff --git a/crypto/src/math/ec/multiplier/FpNafMultiplier.cs b/crypto/src/math/ec/multiplier/FpNafMultiplier.cs index 3453e5600..e7efa2a44 100644 --- a/crypto/src/math/ec/multiplier/FpNafMultiplier.cs +++ b/crypto/src/math/ec/multiplier/FpNafMultiplier.cs @@ -1,38 +1,27 @@ namespace Org.BouncyCastle.Math.EC.Multiplier { /** - * Class implementing the NAF (Non-Adjacent Form) multiplication algorithm. - */ - internal class FpNafMultiplier + * Class implementing the NAF (Non-Adjacent Form) multiplication algorithm (left-to-right). + */ + public class FpNafMultiplier : ECMultiplier { - /** - * D.3.2 pg 101 - * @see org.bouncycastle.math.ec.multiplier.ECMultiplier#multiply(org.bouncycastle.math.ec.ECPoint, java.math.BigInteger) - */ - public ECPoint Multiply(ECPoint p, BigInteger k, PreCompInfo preCompInfo) + public virtual ECPoint Multiply(ECPoint p, BigInteger k) { - // TODO Probably should try to add this - // BigInteger e = k.Mod(n); // n == order of p - BigInteger e = k; - BigInteger h = e.Multiply(BigInteger.Three); + int[] naf = WNafUtilities.GenerateCompactNaf(k); - ECPoint neg = p.Negate(); - ECPoint R = p; + ECPoint addP = p.Normalize(), subP = addP.Negate(); - for (int i = h.BitLength - 2; i > 0; --i) - { - bool hBit = h.TestBit(i); - bool eBit = e.TestBit(i); + ECPoint R = p.Curve.Infinity; - if (hBit == eBit) - { - R = R.Twice(); - } - else - { - R = R.TwicePlus(hBit ? p : neg); - } + int i = naf.Length; + while (--i >= 0) + { + int ni = naf[i]; + int digit = ni >> 16, zeroes = ni & 0xFFFF; + + R = R.TwicePlus(digit < 0 ? subP : addP); + R = R.TimesPow2(zeroes); } return R; diff --git a/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs b/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs index cdccffc2d..a3763848e 100644 --- a/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs +++ b/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs @@ -1,30 +1,37 @@ namespace Org.BouncyCastle.Math.EC.Multiplier { - internal class ReferenceMultiplier - : ECMultiplier - { - /** - * Simple shift-and-add multiplication. Serves as reference implementation - * to verify (possibly faster) implementations in - * {@link org.bouncycastle.math.ec.ECPoint ECPoint}. - * - * @param p The point to multiply. - * @param k The factor by which to multiply. - * @return The result of the point multiplication <code>k * p</code>. - */ - public ECPoint Multiply(ECPoint p, BigInteger k, PreCompInfo preCompInfo) - { - ECPoint q = p.Curve.Infinity; - int t = k.BitLength; - for (int i = 0; i < t; i++) - { - if (k.TestBit(i)) - { - q = q.Add(p); - } - p = p.Twice(); - } - return q; - } - } + public class ReferenceMultiplier + : ECMultiplier + { + /** + * Simple shift-and-add multiplication. Serves as reference implementation + * to verify (possibly faster) implementations in + * {@link org.bouncycastle.math.ec.ECPoint ECPoint}. + * + * @param p The point to multiply. + * @param k The factor by which to multiply. + * @return The result of the point multiplication <code>k * p</code>. + */ + public virtual ECPoint Multiply(ECPoint p, BigInteger k) + { + ECPoint q = p.Curve.Infinity; + int t = k.BitLength; + if (t > 0) + { + if (k.TestBit(0)) + { + q = p; + } + for (int i = 1; i < t; i++) + { + p = p.Twice(); + if (k.TestBit(i)) + { + q = q.Add(p); + } + } + } + return q; + } + } } diff --git a/crypto/src/math/ec/multiplier/WNafMultiplier.cs b/crypto/src/math/ec/multiplier/WNafMultiplier.cs index 570ceee95..c2bb8c465 100644 --- a/crypto/src/math/ec/multiplier/WNafMultiplier.cs +++ b/crypto/src/math/ec/multiplier/WNafMultiplier.cs @@ -6,238 +6,98 @@ namespace Org.BouncyCastle.Math.EC.Multiplier * Class implementing the WNAF (Window Non-Adjacent Form) multiplication * algorithm. */ - internal class WNafMultiplier - : ECMultiplier + public class WNafMultiplier + : 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>sbyte[]</code>. - */ - public sbyte[] WindowNaf(sbyte width, BigInteger k) + * 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 virtual ECPoint Multiply(ECPoint p, BigInteger k) { - // The window NAF is at most 1 element longer than the binary - // representation of the integer k. sbyte 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. - sbyte[] wnaf = new sbyte[k.BitLength + 1]; + // Clamp the window width in the range [2, 16] + int width = System.Math.Max(2, System.Math.Min(16, GetWindowSize(k.BitLength))); - // 2^width as short and BigInteger - short pow2wB = (short)(1 << width); - BigInteger pow2wBI = BigInteger.ValueOf(pow2wB); + WNafPreCompInfo wnafPreCompInfo = WNafUtilities.Precompute(p, width, true); + ECPoint[] preComp = wnafPreCompInfo.PreComp; + ECPoint[] preCompNeg = wnafPreCompInfo.PreCompNeg; - int i = 0; + int[] wnaf = WNafUtilities.GenerateCompactWindowNaf(width, k); - // The actual length of the WNAF - int length = 0; + ECPoint R = p.Curve.Infinity; - // while k >= 1 - while (k.SignValue > 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] = (sbyte)(remainder.IntValue - pow2wB); - } - else - { - wnaf[i] = (sbyte)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 - sbyte[] wnafShort = new sbyte[length]; - Array.Copy(wnaf, 0, wnafShort, 0, length); - return wnafShort; - } + int i = wnaf.Length; - /** - * 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 is WNafPreCompInfo)) + /* + * NOTE This code optimizes the first window using the precomputed points to substitute an + * addition for 2 or more doublings. + */ + if (i > 1) { - wnafPreCompInfo = (WNafPreCompInfo)preCompInfo; - } - else - { - // Ignore empty PreCompInfo or PreCompInfo of incorrect type - wnafPreCompInfo = new WNafPreCompInfo(); - } - - // floor(log2(k)) - int m = k.BitLength; + int wi = wnaf[--i]; + int digit = wi >> 16, zeroes = wi & 0xFFFF; + + int n = System.Math.Abs(digit); + ECPoint[] table = digit < 0 ? preCompNeg : preComp; + + /* + * NOTE: We use this optimization conservatively, since some coordinate systems have + * significantly cheaper doubling relative to addition. + * + * (n << 2) selects precomputed values in the lower half of the table + * (n << 3) selects precomputed values in the lower quarter of the table + */ + //if ((n << 2) < (1 << width)) + if ((n << 3) < (1 << width)) + { + int highest = LongArray.BitLengths[n]; + int lowBits = n ^ (1 << (highest - 1)); + int scale = width - highest; - // width of the Window NAF - sbyte width; + int i1 = ((1 << (width - 1)) - 1); + int i2 = (lowBits << scale) + 1; + R = table[i1 >> 1].Add(table[i2 >> 1]); - // Required length of precomputation array - int reqPreCompLen; + zeroes -= scale; - // 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; + // Console.WriteLine("Optimized: 2^" + scale + " * " + n + " = " + i1 + " + " + i2); } 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; - } - } - } - } + R = table[n >> 1]; } - } - - // 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; + R = R.TimesPow2(zeroes); } - if (twiceP == null) + while (i > 0) { - // Compute twice(p) - twiceP = p.Twice(); - } + int wi = wnaf[--i]; + int digit = wi >> 16, zeroes = wi & 0xFFFF; - 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]; - Array.Copy(oldPreComp, 0, preComp, 0, preCompLen); + int n = System.Math.Abs(digit); + ECPoint[] table = digit < 0 ? preCompNeg : preComp; + ECPoint r = table[n >> 1]; - 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]); - } + R = R.TwicePlus(r); + R = R.TimesPow2(zeroes); } - // Compute the Window NAF of the desired width - sbyte[] wnaf = WindowNaf(width, k); - int l = wnaf.Length; - - // Apply the Window NAF to p using the precomputed ECPoint values. - ECPoint q = p.Curve.Infinity; - for (int i = l - 1; i >= 0; i--) - { - int wi = wnaf[i]; - if (wi == 0) - { - q = q.Twice(); - } - else - { - int n = System.Math.Abs(wi); - ECPoint r = preComp[n >> 1]; - if (wi < 0) - { - r = r.Negate(); - } - - q = q.TwicePlus(r); - } - } + return R; + } - // Set PreCompInfo in ECPoint, such that it is available for next - // multiplication. - wnafPreCompInfo.SetPreComp(preComp); - wnafPreCompInfo.SetTwiceP(twiceP); - p.SetPreCompInfo(wnafPreCompInfo); - return q; + /** + * Determine window width to use for a scalar multiplication of the given size. + * + * @param bits the bit-length of the scalar to multiply by + * @return the window size to use + */ + protected virtual int GetWindowSize(int bits) + { + return WNafUtilities.GetWindowSize(bits); } } } diff --git a/crypto/src/math/ec/multiplier/WNafPreCompInfo.cs b/crypto/src/math/ec/multiplier/WNafPreCompInfo.cs index d9305dace..7e0a73154 100644 --- a/crypto/src/math/ec/multiplier/WNafPreCompInfo.cs +++ b/crypto/src/math/ec/multiplier/WNafPreCompInfo.cs @@ -1,46 +1,46 @@ namespace Org.BouncyCastle.Math.EC.Multiplier { - /** - * Class holding precomputation data for the WNAF (Window Non-Adjacent Form) - * algorithm. - */ - internal class WNafPreCompInfo - : PreCompInfo - { - /** - * Array holding the precomputed <code>ECPoint</code>s used for the Window - * NAF multiplication in <code> - * {@link org.bouncycastle.math.ec.multiplier.WNafMultiplier.multiply() - * WNafMultiplier.multiply()}</code>. - */ - private ECPoint[] preComp = null; + /** + * Class holding precomputation data for the WNAF (Window Non-Adjacent Form) + * algorithm. + */ + public class WNafPreCompInfo + : PreCompInfo + { + /** + * Array holding the precomputed <code>ECPoint</code>s used for a Window + * NAF multiplication. + */ + protected ECPoint[] m_preComp = null; - /** - * Holds an <code>ECPoint</code> representing twice(this). Used for the - * Window NAF multiplication in <code> - * {@link org.bouncycastle.math.ec.multiplier.WNafMultiplier.multiply() - * WNafMultiplier.multiply()}</code>. - */ - private ECPoint twiceP = null; + /** + * Array holding the negations of the precomputed <code>ECPoint</code>s used + * for a Window NAF multiplication. + */ + protected ECPoint[] m_preCompNeg = null; - internal ECPoint[] GetPreComp() - { - return preComp; - } + /** + * Holds an <code>ECPoint</code> representing Twice(this). Used for the + * Window NAF multiplication to create or extend the precomputed values. + */ + protected ECPoint m_twice = null; - internal void SetPreComp(ECPoint[] preComp) - { - this.preComp = preComp; - } + public virtual ECPoint[] PreComp + { + get { return m_preComp; } + set { this.m_preComp = value; } + } - internal ECPoint GetTwiceP() - { - return twiceP; - } + public virtual ECPoint[] PreCompNeg + { + get { return m_preCompNeg; } + set { this.m_preCompNeg = value; } + } - internal void SetTwiceP(ECPoint twiceThis) - { - this.twiceP = twiceThis; - } - } + public virtual ECPoint Twice + { + get { return m_twice; } + set { this.m_twice = value; } + } + } } diff --git a/crypto/src/math/ec/multiplier/WNafUtilities.cs b/crypto/src/math/ec/multiplier/WNafUtilities.cs new file mode 100644 index 000000000..d8b0c6e6a --- /dev/null +++ b/crypto/src/math/ec/multiplier/WNafUtilities.cs @@ -0,0 +1,394 @@ +using System; + +using Org.BouncyCastle.Math; + +namespace Org.BouncyCastle.Math.EC.Multiplier +{ + public abstract class WNafUtilities + { + private static int[] DEFAULT_WINDOW_SIZE_CUTOFFS = new int[]{ 13, 41, 121, 337, 897, 2305 }; + + public static int[] GenerateCompactNaf(BigInteger k) + { + if ((k.BitLength >> 16) != 0) + throw new ArgumentException("must have bitlength < 2^16", "k"); + + BigInteger _3k = k.ShiftLeft(1).Add(k); + + int digits = _3k.BitLength - 1; + int[] naf = new int[(digits + 1) >> 1]; + + int length = 0, zeroes = 0; + for (int i = 1; i <= digits; ++i) + { + bool _3kBit = _3k.TestBit(i); + bool kBit = k.TestBit(i); + + if (_3kBit == kBit) + { + ++zeroes; + } + else + { + int digit = kBit ? -1 : 1; + naf[length++] = (digit << 16) | zeroes; + zeroes = 0; + } + } + + if (naf.Length > length) + { + naf = Trim(naf, length); + } + + return naf; + } + + public static int[] GenerateCompactWindowNaf(int width, BigInteger k) + { + if (width == 2) + { + return GenerateCompactNaf(k); + } + + if (width < 2 || width > 16) + throw new ArgumentException("must be in the range [2, 16]", "width"); + if ((k.BitLength >> 16) != 0) + throw new ArgumentException("must have bitlength < 2^16", "k"); + + int[] wnaf = new int[k.BitLength / width + 1]; + + // 2^width and a mask and sign bit set accordingly + int pow2 = 1 << width; + int mask = pow2 - 1; + int sign = pow2 >> 1; + + bool carry = false; + int length = 0, pos = 0; + + while (pos <= k.BitLength) + { + if (k.TestBit(pos) == carry) + { + ++pos; + continue; + } + + k = k.ShiftRight(pos); + + int digit = k.IntValue & mask; + if (carry) + { + ++digit; + } + + carry = (digit & sign) != 0; + if (carry) + { + digit -= pow2; + } + + int zeroes = length > 0 ? pos - 1 : pos; + wnaf[length++] = (digit << 16) | zeroes; + pos = width; + } + + // Reduce the WNAF array to its actual length + if (wnaf.Length > length) + { + wnaf = Trim(wnaf, length); + } + + return wnaf; + } + + public static byte[] GenerateJsf(BigInteger g, BigInteger h) + { + int digits = System.Math.Max(g.BitLength, h.BitLength) + 1; + byte[] jsf = new byte[digits]; + + BigInteger k0 = g, k1 = h; + int j = 0, d0 = 0, d1 = 0; + + int offset = 0; + while ((d0 | d1) != 0 || k0.BitLength > offset || k1.BitLength > offset) + { + int n0 = ((int)((uint)k0.IntValue >> offset) + d0) & 7; + int n1 = ((int)((uint)k1.IntValue >> offset) + d1) & 7; + + int u0 = n0 & 1; + if (u0 != 0) + { + u0 -= (n0 & 2); + if ((n0 + u0) == 4 && (n1 & 3) == 2) + { + u0 = -u0; + } + } + + int u1 = n1 & 1; + if (u1 != 0) + { + u1 -= (n1 & 2); + if ((n1 + u1) == 4 && (n0 & 3) == 2) + { + u1 = -u1; + } + } + + if ((d0 << 1) == 1 + u0) + { + d0 ^= 1; + } + if ((d1 << 1) == 1 + u1) + { + d1 ^= 1; + } + + if (++offset == 30) + { + offset = 0; + k0 = k0.ShiftRight(30); + k1 = k1.ShiftRight(30); + } + + jsf[j++] = (byte)((u0 << 4) | (u1 & 0xF)); + } + + // Reduce the JSF array to its actual length + if (jsf.Length > j) + { + jsf = Trim(jsf, j); + } + + return jsf; + } + + public static byte[] GenerateNaf(BigInteger k) + { + BigInteger _3k = k.ShiftLeft(1).Add(k); + + int digits = _3k.BitLength - 1; + byte[] naf = new byte[digits]; + + for (int i = 1; i <= digits; ++i) + { + bool _3kBit = _3k.TestBit(i); + bool kBit = k.TestBit(i); + + naf[i - 1] = (byte)(_3kBit == kBit ? 0 : kBit ? -1 : 1); + } + + return naf; + } + + /** + * 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 static byte[] GenerateWindowNaf(int width, BigInteger k) + { + if (width == 2) + { + return GenerateNaf(k); + } + + if (width < 2 || width > 8) + throw new ArgumentException("must be in the range [2, 8]", "width"); + + byte[] wnaf = new byte[k.BitLength + 1]; + + // 2^width and a mask and sign bit set accordingly + int pow2 = 1 << width; + int mask = pow2 - 1; + int sign = pow2 >> 1; + + bool carry = false; + int length = 0, pos = 0; + + while (pos <= k.BitLength) + { + if (k.TestBit(pos) == carry) + { + ++pos; + continue; + } + + k = k.ShiftRight(pos); + + int digit = k.IntValue & mask; + if (carry) + { + ++digit; + } + + carry = (digit & sign) != 0; + if (carry) + { + digit -= pow2; + } + + length += (length > 0) ? pos - 1 : pos; + wnaf[length++] = (byte)digit; + pos = width; + } + + // Reduce the WNAF array to its actual length + if (wnaf.Length > length) + { + wnaf = Trim(wnaf, length); + } + + return wnaf; + } + + public static WNafPreCompInfo GetWNafPreCompInfo(PreCompInfo preCompInfo) + { + if ((preCompInfo != null) && (preCompInfo is WNafPreCompInfo)) + { + return (WNafPreCompInfo)preCompInfo; + } + + return new WNafPreCompInfo(); + } + + /** + * Determine window width to use for a scalar multiplication of the given size. + * + * @param bits the bit-length of the scalar to multiply by + * @return the window size to use + */ + public static int GetWindowSize(int bits) + { + return GetWindowSize(bits, DEFAULT_WINDOW_SIZE_CUTOFFS); + } + + /** + * Determine window width to use for a scalar multiplication of the given size. + * + * @param bits the bit-length of the scalar to multiply by + * @param windowSizeCutoffs a monotonically increasing list of bit sizes at which to increment the window width + * @return the window size to use + */ + public static int GetWindowSize(int bits, int[] windowSizeCutoffs) + { + int w = 0; + for (; w < windowSizeCutoffs.Length; ++w) + { + if (bits < windowSizeCutoffs[w]) + { + break; + } + } + return w + 2; + } + + public static WNafPreCompInfo Precompute(ECPoint p, int width, bool includeNegated) + { + ECCurve c = p.Curve; + WNafPreCompInfo wnafPreCompInfo = GetWNafPreCompInfo(c.GetPreCompInfo(p)); + + ECPoint[] preComp = wnafPreCompInfo.PreComp; + if (preComp == null) + { + preComp = new ECPoint[]{ p }; + } + + int preCompLen = preComp.Length; + int reqPreCompLen = 1 << System.Math.Max(0, width - 2); + + if (preCompLen < reqPreCompLen) + { + ECPoint twiceP = wnafPreCompInfo.Twice; + if (twiceP == null) + { + twiceP = preComp[0].Twice().Normalize(); + wnafPreCompInfo.Twice = twiceP; + } + + preComp = ResizeTable(preComp, reqPreCompLen); + + /* + * TODO Okeya/Sakurai paper has precomputation trick and "Montgomery's Trick" to speed this up. + * Also, co-Z arithmetic could avoid the subsequent normalization too. + */ + 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]); + } + + /* + * Having oft-used operands in affine form makes operations faster. + */ + c.NormalizeAll(preComp); + } + + wnafPreCompInfo.PreComp = preComp; + + if (includeNegated) + { + ECPoint[] preCompNeg = wnafPreCompInfo.PreCompNeg; + + int pos; + if (preCompNeg == null) + { + pos = 0; + preCompNeg = new ECPoint[reqPreCompLen]; + } + else + { + pos = preCompNeg.Length; + if (pos < reqPreCompLen) + { + preCompNeg = ResizeTable(preCompNeg, reqPreCompLen); + } + } + + while (pos < reqPreCompLen) + { + preCompNeg[pos] = preComp[pos].Negate(); + ++pos; + } + + wnafPreCompInfo.PreCompNeg = preCompNeg; + } + + c.SetPreCompInfo(p, wnafPreCompInfo); + + return wnafPreCompInfo; + } + + private static byte[] Trim(byte[] a, int length) + { + byte[] result = new byte[length]; + Array.Copy(a, 0, result, 0, result.Length); + return result; + } + + private static int[] Trim(int[] a, int length) + { + int[] result = new int[length]; + Array.Copy(a, 0, result, 0, result.Length); + return result; + } + + private static ECPoint[] ResizeTable(ECPoint[] a, int length) + { + ECPoint[] result = new ECPoint[length]; + Array.Copy(a, 0, result, 0, a.Length); + return result; + } + } +} diff --git a/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs b/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs index f1a605770..c2f78da93 100644 --- a/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs +++ b/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs @@ -4,117 +4,120 @@ using Org.BouncyCastle.Math.EC.Abc; namespace Org.BouncyCastle.Math.EC.Multiplier { - /** - * Class implementing the WTNAF (Window - * <code>τ</code>-adic Non-Adjacent Form) algorithm. - */ - internal class WTauNafMultiplier - : ECMultiplier - { - /** - * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} - * by <code>k</code> using the reduced <code>τ</code>-adic NAF (RTNAF) - * method. - * @param p The F2mPoint to multiply. - * @param k The integer by which to multiply <code>k</code>. - * @return <code>p</code> multiplied by <code>k</code>. - */ - public ECPoint Multiply(ECPoint point, BigInteger k, PreCompInfo preCompInfo) - { - if (!(point is F2mPoint)) - throw new ArgumentException("Only F2mPoint can be used in WTauNafMultiplier"); + /** + * Class implementing the WTNAF (Window + * <code>τ</code>-adic Non-Adjacent Form) algorithm. + */ + public class WTauNafMultiplier + : ECMultiplier + { + /** + * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} + * by <code>k</code> using the reduced <code>τ</code>-adic NAF (RTNAF) + * method. + * @param p The F2mPoint to multiply. + * @param k The integer by which to multiply <code>k</code>. + * @return <code>p</code> multiplied by <code>k</code>. + */ + public virtual ECPoint Multiply(ECPoint point, BigInteger k) + { + if (!(point is F2mPoint)) + throw new ArgumentException("Only F2mPoint can be used in WTauNafMultiplier"); - F2mPoint p = (F2mPoint)point; + F2mPoint p = (F2mPoint)point; - F2mCurve curve = (F2mCurve) p.Curve; - int m = curve.M; - sbyte a = (sbyte) curve.A.ToBigInteger().IntValue; - sbyte mu = curve.GetMu(); - BigInteger[] s = curve.GetSi(); + F2mCurve curve = (F2mCurve) p.Curve; + int m = curve.M; + sbyte a = (sbyte) curve.A.ToBigInteger().IntValue; + sbyte mu = curve.GetMu(); + BigInteger[] s = curve.GetSi(); - ZTauElement rho = Tnaf.PartModReduction(k, m, a, s, mu, (sbyte)10); + ZTauElement rho = Tnaf.PartModReduction(k, m, a, s, mu, (sbyte)10); - return MultiplyWTnaf(p, rho, preCompInfo, a, mu); - } + return MultiplyWTnaf(p, rho, curve.GetPreCompInfo(p), a, mu); + } - /** - * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} - * by an element <code>λ</code> of <code><b>Z</b>[τ]</code> using - * the <code>τ</code>-adic NAF (TNAF) method. - * @param p The F2mPoint to multiply. - * @param lambda The element <code>λ</code> of - * <code><b>Z</b>[τ]</code> of which to compute the - * <code>[τ]</code>-adic NAF. - * @return <code>p</code> multiplied by <code>λ</code>. - */ - private F2mPoint MultiplyWTnaf(F2mPoint p, ZTauElement lambda, - PreCompInfo preCompInfo, sbyte a, sbyte mu) - { - ZTauElement[] alpha; - if (a == 0) - { - alpha = Tnaf.Alpha0; - } - else - { - // a == 1 - alpha = Tnaf.Alpha1; - } + /** + * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} + * by an element <code>λ</code> of <code><b>Z</b>[τ]</code> using + * the <code>τ</code>-adic NAF (TNAF) method. + * @param p The F2mPoint to multiply. + * @param lambda The element <code>λ</code> of + * <code><b>Z</b>[τ]</code> of which to compute the + * <code>[τ]</code>-adic NAF. + * @return <code>p</code> multiplied by <code>λ</code>. + */ + private F2mPoint MultiplyWTnaf(F2mPoint p, ZTauElement lambda, + PreCompInfo preCompInfo, sbyte a, sbyte mu) + { + ZTauElement[] alpha; + if (a == 0) + { + alpha = Tnaf.Alpha0; + } + else + { + // a == 1 + alpha = Tnaf.Alpha1; + } - BigInteger tw = Tnaf.GetTw(mu, Tnaf.Width); + BigInteger tw = Tnaf.GetTw(mu, Tnaf.Width); - sbyte[]u = Tnaf.TauAdicWNaf(mu, lambda, Tnaf.Width, - BigInteger.ValueOf(Tnaf.Pow2Width), tw, alpha); + sbyte[]u = Tnaf.TauAdicWNaf(mu, lambda, Tnaf.Width, + BigInteger.ValueOf(Tnaf.Pow2Width), tw, alpha); - return MultiplyFromWTnaf(p, u, preCompInfo); - } - - /** - * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} - * by an element <code>λ</code> of <code><b>Z</b>[τ]</code> - * using the window <code>τ</code>-adic NAF (TNAF) method, given the - * WTNAF of <code>λ</code>. - * @param p The F2mPoint to multiply. - * @param u The the WTNAF of <code>λ</code>.. - * @return <code>λ * p</code> - */ - private static F2mPoint MultiplyFromWTnaf(F2mPoint p, sbyte[] u, - PreCompInfo preCompInfo) - { - F2mCurve curve = (F2mCurve)p.Curve; - sbyte a = (sbyte) curve.A.ToBigInteger().IntValue; + return MultiplyFromWTnaf(p, u, preCompInfo); + } + + /** + * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} + * by an element <code>λ</code> of <code><b>Z</b>[τ]</code> + * using the window <code>τ</code>-adic NAF (TNAF) method, given the + * WTNAF of <code>λ</code>. + * @param p The F2mPoint to multiply. + * @param u The the WTNAF of <code>λ</code>.. + * @return <code>λ * p</code> + */ + private static F2mPoint MultiplyFromWTnaf(F2mPoint p, sbyte[] u, + PreCompInfo preCompInfo) + { + F2mCurve curve = (F2mCurve)p.Curve; + sbyte a = (sbyte) curve.A.ToBigInteger().IntValue; - F2mPoint[] pu; - if ((preCompInfo == null) || !(preCompInfo is WTauNafPreCompInfo)) - { - pu = Tnaf.GetPreComp(p, a); - p.SetPreCompInfo(new WTauNafPreCompInfo(pu)); - } - else - { - pu = ((WTauNafPreCompInfo)preCompInfo).GetPreComp(); - } + F2mPoint[] pu; + if ((preCompInfo == null) || !(preCompInfo is WTauNafPreCompInfo)) + { + pu = Tnaf.GetPreComp(p, a); - // q = infinity - F2mPoint q = (F2mPoint) p.Curve.Infinity; - for (int i = u.Length - 1; i >= 0; i--) - { - q = Tnaf.Tau(q); - if (u[i] != 0) - { - if (u[i] > 0) - { - q = q.AddSimple(pu[u[i]]); - } - else - { - // u[i] < 0 - q = q.SubtractSimple(pu[-u[i]]); - } - } - } + WTauNafPreCompInfo pre = new WTauNafPreCompInfo(); + pre.PreComp = pu; + curve.SetPreCompInfo(p, pre); + } + else + { + pu = ((WTauNafPreCompInfo)preCompInfo).PreComp; + } - return q; - } - } + // q = infinity + F2mPoint q = (F2mPoint) p.Curve.Infinity; + for (int i = u.Length - 1; i >= 0; i--) + { + q = Tnaf.Tau(q); + if (u[i] != 0) + { + if (u[i] > 0) + { + q = q.AddSimple(pu[u[i]]); + } + else + { + // u[i] < 0 + q = q.SubtractSimple(pu[-u[i]]); + } + } + } + + return q; + } + } } diff --git a/crypto/src/math/ec/multiplier/WTauNafPreCompInfo.cs b/crypto/src/math/ec/multiplier/WTauNafPreCompInfo.cs index cede4a05d..3c18404c0 100644 --- a/crypto/src/math/ec/multiplier/WTauNafPreCompInfo.cs +++ b/crypto/src/math/ec/multiplier/WTauNafPreCompInfo.cs @@ -1,41 +1,24 @@ namespace Org.BouncyCastle.Math.EC.Multiplier { - /** - * Class holding precomputation data for the WTNAF (Window - * <code>τ</code>-adic Non-Adjacent Form) algorithm. - */ - internal class WTauNafPreCompInfo - : PreCompInfo - { - /** - * Array holding the precomputed <code>F2mPoint</code>s used for the - * WTNAF multiplication in <code> - * {@link org.bouncycastle.math.ec.multiplier.WTauNafMultiplier.multiply() - * WTauNafMultiplier.multiply()}</code>. - */ - private readonly F2mPoint[] preComp; + /** + * Class holding precomputation data for the WTNAF (Window + * <code>τ</code>-adic Non-Adjacent Form) algorithm. + */ + public class WTauNafPreCompInfo + : PreCompInfo + { + /** + * Array holding the precomputed <code>F2mPoint</code>s used for the + * WTNAF multiplication in <code> + * {@link org.bouncycastle.math.ec.multiplier.WTauNafMultiplier.multiply() + * WTauNafMultiplier.multiply()}</code>. + */ + protected F2mPoint[] m_preComp; - /** - * Constructor for <code>WTauNafPreCompInfo</code> - * @param preComp Array holding the precomputed <code>F2mPoint</code>s - * used for the WTNAF multiplication in <code> - * {@link org.bouncycastle.math.ec.multiplier.WTauNafMultiplier.multiply() - * WTauNafMultiplier.multiply()}</code>. - */ - internal WTauNafPreCompInfo(F2mPoint[] preComp) - { - this.preComp = preComp; - } - - /** - * @return the array holding the precomputed <code>F2mPoint</code>s - * used for the WTNAF multiplication in <code> - * {@link org.bouncycastle.math.ec.multiplier.WTauNafMultiplier.multiply() - * WTauNafMultiplier.multiply()}</code>. - */ - internal F2mPoint[] GetPreComp() - { - return preComp; - } - } + public virtual F2mPoint[] PreComp + { + get { return m_preComp; } + set { this.m_preComp = value; } + } + } } |