diff options
Diffstat (limited to 'crypto/src/math/ec/multiplier')
20 files changed, 1220 insertions, 220 deletions
diff --git a/crypto/src/math/ec/multiplier/AbstractECMultiplier.cs b/crypto/src/math/ec/multiplier/AbstractECMultiplier.cs new file mode 100644 index 000000000..517881323 --- /dev/null +++ b/crypto/src/math/ec/multiplier/AbstractECMultiplier.cs @@ -0,0 +1,24 @@ +namespace Org.BouncyCastle.Math.EC.Multiplier +{ + public abstract class AbstractECMultiplier + : ECMultiplier + { + public virtual ECPoint Multiply(ECPoint p, BigInteger k) + { + int sign = k.SignValue; + if (sign == 0 || p.IsInfinity) + return p.Curve.Infinity; + + ECPoint positive = MultiplyPositive(p, k.Abs()); + ECPoint result = sign > 0 ? positive : positive.Negate(); + + /* + * Although the various multipliers ought not to produce invalid output under normal + * circumstances, a final check here is advised to guard against fault attacks. + */ + return ECAlgorithms.ValidatePoint(result); + } + + protected abstract ECPoint MultiplyPositive(ECPoint p, BigInteger k); + } +} diff --git a/crypto/src/math/ec/multiplier/DoubleAddMultiplier.cs b/crypto/src/math/ec/multiplier/DoubleAddMultiplier.cs new file mode 100644 index 000000000..18a72c0a2 --- /dev/null +++ b/crypto/src/math/ec/multiplier/DoubleAddMultiplier.cs @@ -0,0 +1,24 @@ +namespace Org.BouncyCastle.Math.EC.Multiplier +{ + public class DoubleAddMultiplier + : AbstractECMultiplier + { + /** + * Joye's double-add algorithm. + */ + protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k) + { + ECPoint[] R = new ECPoint[]{ p.Curve.Infinity, p }; + + int n = k.BitLength; + for (int i = 0; i < n; ++i) + { + int b = k.TestBit(i) ? 1 : 0; + int bp = 1 - b; + R[bp] = R[bp].TwicePlus(R[b]); + } + + return R[0]; + } + } +} diff --git a/crypto/src/math/ec/multiplier/ECMultiplier.cs b/crypto/src/math/ec/multiplier/ECMultiplier.cs index c6d768ea8..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. - */ - internal 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/FixedPointCombMultiplier.cs b/crypto/src/math/ec/multiplier/FixedPointCombMultiplier.cs new file mode 100644 index 000000000..a8ef5a77a --- /dev/null +++ b/crypto/src/math/ec/multiplier/FixedPointCombMultiplier.cs @@ -0,0 +1,59 @@ +using System; + +namespace Org.BouncyCastle.Math.EC.Multiplier +{ + public class FixedPointCombMultiplier + : AbstractECMultiplier + { + protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k) + { + ECCurve c = p.Curve; + int size = FixedPointUtilities.GetCombSize(c); + + if (k.BitLength > size) + { + /* + * TODO The comb works best when the scalars are less than the (possibly unknown) order. + * Still, if we want to handle larger scalars, we could allow customization of the comb + * size, or alternatively we could deal with the 'extra' bits either by running the comb + * multiple times as necessary, or by using an alternative multiplier as prelude. + */ + throw new InvalidOperationException("fixed-point comb doesn't support scalars larger than the curve order"); + } + + int minWidth = GetWidthForCombSize(size); + + FixedPointPreCompInfo info = FixedPointUtilities.Precompute(p, minWidth); + ECPoint[] lookupTable = info.PreComp; + int width = info.Width; + + int d = (size + width - 1) / width; + + ECPoint R = c.Infinity; + + int top = d * width - 1; + for (int i = 0; i < d; ++i) + { + int index = 0; + + for (int j = top - i; j >= 0; j -= d) + { + index <<= 1; + if (k.TestBit(j)) + { + index |= 1; + } + } + + R = R.TwicePlus(lookupTable[index]); + } + + return R; + } + + protected virtual int GetWidthForCombSize(int combSize) + { + return combSize > 257 ? 6 : 5; + } + } +} diff --git a/crypto/src/math/ec/multiplier/FixedPointPreCompInfo.cs b/crypto/src/math/ec/multiplier/FixedPointPreCompInfo.cs new file mode 100644 index 000000000..56a6326a1 --- /dev/null +++ b/crypto/src/math/ec/multiplier/FixedPointPreCompInfo.cs @@ -0,0 +1,34 @@ +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; + + /** + * The width used for the precomputation. If a larger width precomputation + * is already available this may be larger than was requested, so calling + * code should refer to the actual width. + */ + protected int m_width = -1; + + public virtual ECPoint[] PreComp + { + get { return m_preComp; } + set { this.m_preComp = value; } + } + + public virtual int Width + { + get { return m_width; } + set { this.m_width = 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..d927d010b --- /dev/null +++ b/crypto/src/math/ec/multiplier/FixedPointUtilities.cs @@ -0,0 +1,72 @@ +using System; + +namespace Org.BouncyCastle.Math.EC.Multiplier +{ + public class FixedPointUtilities + { + public static readonly string PRECOMP_NAME = "bc_fixed_point"; + + public static int GetCombSize(ECCurve c) + { + BigInteger order = c.Order; + return order == null ? c.FieldSize + 1 : order.BitLength; + } + + 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 minWidth) + { + ECCurve c = p.Curve; + + int n = 1 << minWidth; + FixedPointPreCompInfo info = GetFixedPointPreCompInfo(c.GetPreCompInfo(p, PRECOMP_NAME)); + ECPoint[] lookupTable = info.PreComp; + + if (lookupTable == null || lookupTable.Length < n) + { + int bits = GetCombSize(c); + int d = (bits + minWidth - 1) / minWidth; + + ECPoint[] pow2Table = new ECPoint[minWidth]; + pow2Table[0] = p; + for (int i = 1; i < minWidth; ++i) + { + pow2Table[i] = pow2Table[i - 1].TimesPow2(d); + } + + c.NormalizeAll(pow2Table); + + lookupTable = new ECPoint[n]; + lookupTable[0] = c.Infinity; + + for (int bit = minWidth - 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; + info.Width = minWidth; + + c.SetPreCompInfo(p, PRECOMP_NAME, info); + } + + return info; + } + } +} diff --git a/crypto/src/math/ec/multiplier/GlvMultiplier.cs b/crypto/src/math/ec/multiplier/GlvMultiplier.cs new file mode 100644 index 000000000..f19049474 --- /dev/null +++ b/crypto/src/math/ec/multiplier/GlvMultiplier.cs @@ -0,0 +1,40 @@ +using System; + +using Org.BouncyCastle.Math.EC.Endo; + +namespace Org.BouncyCastle.Math.EC.Multiplier +{ + public class GlvMultiplier + : AbstractECMultiplier + { + protected readonly ECCurve curve; + protected readonly GlvEndomorphism glvEndomorphism; + + public GlvMultiplier(ECCurve curve, GlvEndomorphism glvEndomorphism) + { + if (curve == null || curve.Order == null) + throw new ArgumentException("Need curve with known group order", "curve"); + + this.curve = curve; + this.glvEndomorphism = glvEndomorphism; + } + + protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k) + { + if (!curve.Equals(p.Curve)) + throw new InvalidOperationException(); + + BigInteger n = p.Curve.Order; + BigInteger[] ab = glvEndomorphism.DecomposeScalar(k.Mod(n)); + BigInteger a = ab[0], b = ab[1]; + + ECPointMap pointMap = glvEndomorphism.PointMap; + if (glvEndomorphism.HasEfficientPointMap) + { + return ECAlgorithms.ImplShamirsTrickWNaf(p, a, pointMap, b); + } + + return ECAlgorithms.ImplShamirsTrickWNaf(p, a, pointMap.Map(p), b); + } + } +} diff --git a/crypto/src/math/ec/multiplier/MixedNafR2LMultiplier.cs b/crypto/src/math/ec/multiplier/MixedNafR2LMultiplier.cs new file mode 100644 index 000000000..a4c201832 --- /dev/null +++ b/crypto/src/math/ec/multiplier/MixedNafR2LMultiplier.cs @@ -0,0 +1,75 @@ +using System; + +namespace Org.BouncyCastle.Math.EC.Multiplier +{ + /** + * Class implementing the NAF (Non-Adjacent Form) multiplication algorithm (right-to-left) using + * mixed coordinates. + */ + public class MixedNafR2LMultiplier + : AbstractECMultiplier + { + protected readonly int additionCoord, doublingCoord; + + /** + * By default, addition will be done in Jacobian coordinates, and doubling will be done in + * Modified Jacobian coordinates (independent of the original coordinate system of each point). + */ + public MixedNafR2LMultiplier() + : this(ECCurve.COORD_JACOBIAN, ECCurve.COORD_JACOBIAN_MODIFIED) + { + } + + public MixedNafR2LMultiplier(int additionCoord, int doublingCoord) + { + this.additionCoord = additionCoord; + this.doublingCoord = doublingCoord; + } + + protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k) + { + ECCurve curveOrig = p.Curve; + + ECCurve curveAdd = ConfigureCurve(curveOrig, additionCoord); + ECCurve curveDouble = ConfigureCurve(curveOrig, doublingCoord); + + int[] naf = WNafUtilities.GenerateCompactNaf(k); + + ECPoint Ra = curveAdd.Infinity; + ECPoint Td = curveDouble.ImportPoint(p); + + int zeroes = 0; + for (int i = 0; i < naf.Length; ++i) + { + int ni = naf[i]; + int digit = ni >> 16; + zeroes += ni & 0xFFFF; + + Td = Td.TimesPow2(zeroes); + + ECPoint Tj = curveAdd.ImportPoint(Td); + if (digit < 0) + { + Tj = Tj.Negate(); + } + + Ra = Ra.Add(Tj); + + zeroes = 1; + } + + return curveOrig.ImportPoint(Ra); + } + + protected virtual ECCurve ConfigureCurve(ECCurve c, int coord) + { + if (c.CoordinateSystem == coord) + return c; + + if (!c.SupportsCoordinateSystem(coord)) + throw new ArgumentException("Coordinate system " + coord + " not supported by this curve", "coord"); + + return c.Configure().SetCoordinateSystem(coord).Create(); + } + } +} diff --git a/crypto/src/math/ec/multiplier/MontgomeryLadderMultiplier.cs b/crypto/src/math/ec/multiplier/MontgomeryLadderMultiplier.cs new file mode 100644 index 000000000..e2470a383 --- /dev/null +++ b/crypto/src/math/ec/multiplier/MontgomeryLadderMultiplier.cs @@ -0,0 +1,25 @@ +namespace Org.BouncyCastle.Math.EC.Multiplier +{ + public class MontgomeryLadderMultiplier + : AbstractECMultiplier + { + /** + * Montgomery ladder. + */ + protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k) + { + ECPoint[] R = new ECPoint[]{ p.Curve.Infinity, p }; + + int n = k.BitLength; + int i = n; + while (--i >= 0) + { + int b = k.TestBit(i) ? 1 : 0; + int bp = 1 - b; + R[bp] = R[bp].Add(R[b]); + R[b] = R[b].Twice(); + } + return R[0]; + } + } +} diff --git a/crypto/src/math/ec/multiplier/NafL2RMultiplier.cs b/crypto/src/math/ec/multiplier/NafL2RMultiplier.cs new file mode 100644 index 000000000..ac80cf905 --- /dev/null +++ b/crypto/src/math/ec/multiplier/NafL2RMultiplier.cs @@ -0,0 +1,30 @@ +namespace Org.BouncyCastle.Math.EC.Multiplier +{ + /** + * Class implementing the NAF (Non-Adjacent Form) multiplication algorithm (left-to-right). + */ + public class NafL2RMultiplier + : AbstractECMultiplier + { + protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k) + { + int[] naf = WNafUtilities.GenerateCompactNaf(k); + + ECPoint addP = p.Normalize(), subP = addP.Negate(); + + ECPoint R = p.Curve.Infinity; + + 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/NafR2LMultiplier.cs b/crypto/src/math/ec/multiplier/NafR2LMultiplier.cs new file mode 100644 index 000000000..1fa69fae8 --- /dev/null +++ b/crypto/src/math/ec/multiplier/NafR2LMultiplier.cs @@ -0,0 +1,31 @@ +namespace Org.BouncyCastle.Math.EC.Multiplier +{ + /** + * Class implementing the NAF (Non-Adjacent Form) multiplication algorithm (right-to-left). + */ + public class NafR2LMultiplier + : AbstractECMultiplier + { + protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k) + { + int[] naf = WNafUtilities.GenerateCompactNaf(k); + + ECPoint R0 = p.Curve.Infinity, R1 = p; + + int zeroes = 0; + for (int i = 0; i < naf.Length; ++i) + { + int ni = naf[i]; + int digit = ni >> 16; + zeroes += ni & 0xFFFF; + + R1 = R1.TimesPow2(zeroes); + R0 = R0.Add(digit < 0 ? R1.Negate() : R1); + + zeroes = 1; + } + + return R0; + } + } +} diff --git a/crypto/src/math/ec/multiplier/PreCompInfo.cs b/crypto/src/math/ec/multiplier/PreCompInfo.cs index d379508c8..5c3289286 100644 --- a/crypto/src/math/ec/multiplier/PreCompInfo.cs +++ b/crypto/src/math/ec/multiplier/PreCompInfo.cs @@ -5,7 +5,7 @@ namespace Org.BouncyCastle.Math.EC.Multiplier * algorithms. Used as a Memento (see GOF patterns) for * <code>WNafMultiplier</code>. */ - internal interface PreCompInfo + public interface PreCompInfo { } } diff --git a/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs b/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs index cdccffc2d..4848ada39 100644 --- a/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs +++ b/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs @@ -1,30 +1,11 @@ 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 + : AbstractECMultiplier + { + protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k) + { + return ECAlgorithms.ReferenceMultiply(p, k); + } + } } diff --git a/crypto/src/math/ec/multiplier/WNafL2RMultiplier.cs b/crypto/src/math/ec/multiplier/WNafL2RMultiplier.cs new file mode 100644 index 000000000..f671f6a5c --- /dev/null +++ b/crypto/src/math/ec/multiplier/WNafL2RMultiplier.cs @@ -0,0 +1,98 @@ +using System; + +namespace Org.BouncyCastle.Math.EC.Multiplier +{ + /** + * Class implementing the WNAF (Window Non-Adjacent Form) multiplication + * algorithm. + */ + public class WNafL2RMultiplier + : AbstractECMultiplier + { + /** + * 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>. + */ + protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k) + { + // Clamp the window width in the range [2, 16] + int width = System.Math.Max(2, System.Math.Min(16, GetWindowSize(k.BitLength))); + + WNafPreCompInfo wnafPreCompInfo = WNafUtilities.Precompute(p, width, true); + ECPoint[] preComp = wnafPreCompInfo.PreComp; + ECPoint[] preCompNeg = wnafPreCompInfo.PreCompNeg; + + int[] wnaf = WNafUtilities.GenerateCompactWindowNaf(width, k); + + ECPoint R = p.Curve.Infinity; + + int i = wnaf.Length; + + /* + * NOTE: We try to optimize the first window using the precomputed points to substitute an + * addition for 2 or more doublings. + */ + if (i > 1) + { + int wi = wnaf[--i]; + int digit = wi >> 16, zeroes = wi & 0xFFFF; + + int n = System.Math.Abs(digit); + ECPoint[] table = digit < 0 ? preCompNeg : preComp; + + // Optimization can only be used for values in the lower half of the table + if ((n << 2) < (1 << width)) + { + int highest = LongArray.BitLengths[n]; + + // TODO Get addition/doubling cost ratio from curve and compare to 'scale' to see if worth substituting? + int scale = width - highest; + int lowBits = n ^ (1 << (highest - 1)); + + int i1 = ((1 << (width - 1)) - 1); + int i2 = (lowBits << scale) + 1; + R = table[i1 >> 1].Add(table[i2 >> 1]); + + zeroes -= scale; + + //Console.WriteLine("Optimized: 2^" + scale + " * " + n + " = " + i1 + " + " + i2); + } + else + { + R = table[n >> 1]; + } + + R = R.TimesPow2(zeroes); + } + + while (i > 0) + { + int wi = wnaf[--i]; + int digit = wi >> 16, zeroes = wi & 0xFFFF; + + int n = System.Math.Abs(digit); + ECPoint[] table = digit < 0 ? preCompNeg : preComp; + ECPoint r = table[n >> 1]; + + R = R.TwicePlus(r); + R = R.TimesPow2(zeroes); + } + + return R; + } + + /** + * 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..865b9073e --- /dev/null +++ b/crypto/src/math/ec/multiplier/WNafUtilities.cs @@ -0,0 +1,469 @@ +using System; + +namespace Org.BouncyCastle.Math.EC.Multiplier +{ + public abstract class WNafUtilities + { + public static readonly string PRECOMP_NAME = "bc_wnaf"; + + private static readonly int[] DEFAULT_WINDOW_SIZE_CUTOFFS = new int[]{ 13, 41, 121, 337, 897, 2305 }; + + private static readonly byte[] EMPTY_BYTES = new byte[0]; + private static readonly int[] EMPTY_INTS = new int[0]; + + public static int[] GenerateCompactNaf(BigInteger k) + { + if ((k.BitLength >> 16) != 0) + throw new ArgumentException("must have bitlength < 2^16", "k"); + if (k.SignValue == 0) + return EMPTY_INTS; + + BigInteger _3k = k.ShiftLeft(1).Add(k); + + int bits = _3k.BitLength; + int[] naf = new int[bits >> 1]; + + BigInteger diff = _3k.Xor(k); + + int highBit = bits - 1, length = 0, zeroes = 0; + for (int i = 1; i < highBit; ++i) + { + if (!diff.TestBit(i)) + { + ++zeroes; + continue; + } + + int digit = k.TestBit(i) ? -1 : 1; + naf[length++] = (digit << 16) | zeroes; + zeroes = 1; + ++i; + } + + naf[length++] = (1 << 16) | zeroes; + + 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"); + if (k.SignValue == 0) + return EMPTY_INTS; + + 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) + { + if (k.SignValue == 0) + return EMPTY_BYTES; + + BigInteger _3k = k.ShiftLeft(1).Add(k); + + int digits = _3k.BitLength - 1; + byte[] naf = new byte[digits]; + + BigInteger diff = _3k.Xor(k); + + for (int i = 1; i < digits; ++i) + { + if (diff.TestBit(i)) + { + naf[i - 1] = (byte)(k.TestBit(i) ? -1 : 1); + ++i; + } + } + + naf[digits - 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 = &sum;<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"); + if (k.SignValue == 0) + return EMPTY_BYTES; + + 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 int GetNafWeight(BigInteger k) + { + if (k.SignValue == 0) + return 0; + + BigInteger _3k = k.ShiftLeft(1).Add(k); + BigInteger diff = _3k.Xor(k); + + return diff.BitCount; + } + + public static WNafPreCompInfo GetWNafPreCompInfo(ECPoint p) + { + return GetWNafPreCompInfo(p.Curve.GetPreCompInfo(p, PRECOMP_NAME)); + } + + 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 ECPoint MapPointWithPrecomp(ECPoint p, int width, bool includeNegated, + ECPointMap pointMap) + { + ECCurve c = p.Curve; + WNafPreCompInfo wnafPreCompP = Precompute(p, width, includeNegated); + + ECPoint q = pointMap.Map(p); + WNafPreCompInfo wnafPreCompQ = GetWNafPreCompInfo(c.GetPreCompInfo(q, PRECOMP_NAME)); + + ECPoint twiceP = wnafPreCompP.Twice; + if (twiceP != null) + { + ECPoint twiceQ = pointMap.Map(twiceP); + wnafPreCompQ.Twice = twiceQ; + } + + ECPoint[] preCompP = wnafPreCompP.PreComp; + ECPoint[] preCompQ = new ECPoint[preCompP.Length]; + for (int i = 0; i < preCompP.Length; ++i) + { + preCompQ[i] = pointMap.Map(preCompP[i]); + } + wnafPreCompQ.PreComp = preCompQ; + + if (includeNegated) + { + ECPoint[] preCompNegQ = new ECPoint[preCompQ.Length]; + for (int i = 0; i < preCompNegQ.Length; ++i) + { + preCompNegQ[i] = preCompQ[i].Negate(); + } + wnafPreCompQ.PreCompNeg = preCompNegQ; + } + + c.SetPreCompInfo(q, PRECOMP_NAME, wnafPreCompQ); + + return q; + } + + public static WNafPreCompInfo Precompute(ECPoint p, int width, bool includeNegated) + { + ECCurve c = p.Curve; + WNafPreCompInfo wnafPreCompInfo = GetWNafPreCompInfo(c.GetPreCompInfo(p, PRECOMP_NAME)); + + 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) + { + preComp = ResizeTable(preComp, reqPreCompLen); + if (reqPreCompLen == 2) + { + preComp[1] = preComp[0].ThreeTimes(); + } + else + { + ECPoint twiceP = wnafPreCompInfo.Twice; + if (twiceP == null) + { + twiceP = preComp[0].Twice(); + wnafPreCompInfo.Twice = twiceP; + } + + 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, PRECOMP_NAME, 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..dda778eea 100644 --- a/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs +++ b/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs @@ -4,117 +4,113 @@ 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 + : AbstractECMultiplier + { + // TODO Create WTauNafUtilities class and move various functionality into it + internal static readonly string PRECOMP_NAME = "bc_wtnaf"; - F2mPoint p = (F2mPoint)point; + /** + * 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>. + */ + protected override ECPoint MultiplyPositive(ECPoint point, BigInteger k) + { + if (!(point is F2mPoint)) + throw new ArgumentException("Only F2mPoint can be used in WTauNafMultiplier"); - F2mCurve curve = (F2mCurve) p.Curve; - int m = curve.M; - sbyte a = (sbyte) curve.A.ToBigInteger().IntValue; - sbyte mu = curve.GetMu(); - BigInteger[] s = curve.GetSi(); + 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(); - 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, PRECOMP_NAME), 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 = (a == 0) ? Tnaf.Alpha0 : 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, PRECOMP_NAME, pre); + } + else + { + pu = ((WTauNafPreCompInfo)preCompInfo).PreComp; + } - return q; - } - } + // q = infinity + F2mPoint q = (F2mPoint)curve.Infinity; + for (int i = u.Length - 1; i >= 0; i--) + { + q = Tnaf.Tau(q); + sbyte ui = u[i]; + if (ui != 0) + { + if (ui > 0) + { + q = q.AddSimple(pu[ui]); + } + else + { + // u[i] < 0 + q = q.SubtractSimple(pu[-ui]); + } + } + } + + 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; } + } + } } diff --git a/crypto/src/math/ec/multiplier/ZSignedDigitL2RMultiplier.cs b/crypto/src/math/ec/multiplier/ZSignedDigitL2RMultiplier.cs new file mode 100644 index 000000000..554ac61b3 --- /dev/null +++ b/crypto/src/math/ec/multiplier/ZSignedDigitL2RMultiplier.cs @@ -0,0 +1,29 @@ +namespace Org.BouncyCastle.Math.EC.Multiplier +{ + public class ZSignedDigitL2RMultiplier + : AbstractECMultiplier + { + /** + * 'Zeroless' Signed Digit Left-to-Right. + */ + protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k) + { + ECPoint addP = p.Normalize(), subP = addP.Negate(); + + ECPoint R0 = addP; + + int n = k.BitLength; + int s = k.GetLowestSetBit(); + + int i = n; + while (--i > s) + { + R0 = R0.TwicePlus(k.TestBit(i) ? addP : subP); + } + + R0 = R0.TimesPow2(s); + + return R0; + } + } +} diff --git a/crypto/src/math/ec/multiplier/ZSignedDigitR2LMultiplier.cs b/crypto/src/math/ec/multiplier/ZSignedDigitR2LMultiplier.cs new file mode 100644 index 000000000..91c06cbb8 --- /dev/null +++ b/crypto/src/math/ec/multiplier/ZSignedDigitR2LMultiplier.cs @@ -0,0 +1,30 @@ +namespace Org.BouncyCastle.Math.EC.Multiplier +{ + public class ZSignedDigitR2LMultiplier + : AbstractECMultiplier + { + /** + * 'Zeroless' Signed Digit Right-to-Left. + */ + protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k) + { + ECPoint R0 = p.Curve.Infinity, R1 = p; + + int n = k.BitLength; + int s = k.GetLowestSetBit(); + + R1 = R1.TimesPow2(s); + + int i = s; + while (++i < n) + { + R0 = R0.Add(k.TestBit(i) ? R1 : R1.Negate()); + R1 = R1.Twice(); + } + + R0 = R0.Add(R1); + + return R0; + } + } +} |