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; }
+ }
+ }
}
|
