From b27039585917e3c0651de353faef68fe6bbc68d9 Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Mon, 27 Jan 2014 11:40:00 +0700 Subject: Port of latest EC multipliers from Java --- .../src/math/ec/multiplier/AbstractECMultiplier.cs | 18 ++++ .../src/math/ec/multiplier/DoubleAddMultiplier.cs | 24 ++++++ crypto/src/math/ec/multiplier/FpNafMultiplier.cs | 30 ------- .../math/ec/multiplier/MixedNafR2LMultiplier.cs | 75 +++++++++++++++++ .../ec/multiplier/MontgomeryLadderMultiplier.cs | 25 ++++++ crypto/src/math/ec/multiplier/NafL2RMultiplier.cs | 30 +++++++ crypto/src/math/ec/multiplier/NafR2LMultiplier.cs | 31 +++++++ .../src/math/ec/multiplier/ReferenceMultiplier.cs | 4 +- crypto/src/math/ec/multiplier/WNafL2RMultiplier.cs | 98 ++++++++++++++++++++++ crypto/src/math/ec/multiplier/WNafMultiplier.cs | 98 ---------------------- crypto/src/math/ec/multiplier/WTauNafMultiplier.cs | 34 +++----- .../ec/multiplier/ZSignedDigitL2RMultiplier.cs | 29 +++++++ .../ec/multiplier/ZSignedDigitR2LMultiplier.cs | 30 +++++++ 13 files changed, 374 insertions(+), 152 deletions(-) create mode 100644 crypto/src/math/ec/multiplier/AbstractECMultiplier.cs create mode 100644 crypto/src/math/ec/multiplier/DoubleAddMultiplier.cs delete mode 100644 crypto/src/math/ec/multiplier/FpNafMultiplier.cs create mode 100644 crypto/src/math/ec/multiplier/MixedNafR2LMultiplier.cs create mode 100644 crypto/src/math/ec/multiplier/MontgomeryLadderMultiplier.cs create mode 100644 crypto/src/math/ec/multiplier/NafL2RMultiplier.cs create mode 100644 crypto/src/math/ec/multiplier/NafR2LMultiplier.cs create mode 100644 crypto/src/math/ec/multiplier/WNafL2RMultiplier.cs delete mode 100644 crypto/src/math/ec/multiplier/WNafMultiplier.cs create mode 100644 crypto/src/math/ec/multiplier/ZSignedDigitL2RMultiplier.cs create mode 100644 crypto/src/math/ec/multiplier/ZSignedDigitR2LMultiplier.cs (limited to 'crypto/src/math/ec/multiplier') diff --git a/crypto/src/math/ec/multiplier/AbstractECMultiplier.cs b/crypto/src/math/ec/multiplier/AbstractECMultiplier.cs new file mode 100644 index 000000000..fe683726f --- /dev/null +++ b/crypto/src/math/ec/multiplier/AbstractECMultiplier.cs @@ -0,0 +1,18 @@ +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()); + return sign > 0 ? positive : positive.Negate(); + } + + 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/FpNafMultiplier.cs b/crypto/src/math/ec/multiplier/FpNafMultiplier.cs deleted file mode 100644 index e7efa2a44..000000000 --- a/crypto/src/math/ec/multiplier/FpNafMultiplier.cs +++ /dev/null @@ -1,30 +0,0 @@ -namespace Org.BouncyCastle.Math.EC.Multiplier -{ - /** - * Class implementing the NAF (Non-Adjacent Form) multiplication algorithm (left-to-right). - */ - public class FpNafMultiplier - : ECMultiplier - { - public virtual ECPoint Multiply(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/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/ReferenceMultiplier.cs b/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs index a3763848e..832fd7be4 100644 --- a/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs +++ b/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs @@ -1,7 +1,7 @@ namespace Org.BouncyCastle.Math.EC.Multiplier { public class ReferenceMultiplier - : ECMultiplier + : AbstractECMultiplier { /** * Simple shift-and-add multiplication. Serves as reference implementation @@ -12,7 +12,7 @@ namespace Org.BouncyCastle.Math.EC.Multiplier * @param k The factor by which to multiply. * @return The result of the point multiplication k * p. */ - public virtual ECPoint Multiply(ECPoint p, BigInteger k) + protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k) { ECPoint q = p.Curve.Infinity; int t = k.BitLength; 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 this by an integer k using the + * Window NAF method. + * @param k The integer by which this is multiplied. + * @return A new ECPoint which equals this + * multiplied by k. + */ + 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/WNafMultiplier.cs b/crypto/src/math/ec/multiplier/WNafMultiplier.cs deleted file mode 100644 index 06ad76031..000000000 --- a/crypto/src/math/ec/multiplier/WNafMultiplier.cs +++ /dev/null @@ -1,98 +0,0 @@ -using System; - -namespace Org.BouncyCastle.Math.EC.Multiplier -{ - /** - * Class implementing the WNAF (Window Non-Adjacent Form) multiplication - * algorithm. - */ - public class WNafMultiplier - : ECMultiplier - { - /** - * Multiplies this by an integer k using the - * Window NAF method. - * @param k The integer by which this is multiplied. - * @return A new ECPoint which equals this - * multiplied by k. - */ - public virtual ECPoint Multiply(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/WTauNafMultiplier.cs b/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs index c2f78da93..b87b87000 100644 --- a/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs +++ b/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs @@ -9,7 +9,7 @@ namespace Org.BouncyCastle.Math.EC.Multiplier * τ-adic Non-Adjacent Form) algorithm. */ public class WTauNafMultiplier - : ECMultiplier + : AbstractECMultiplier { /** * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint} @@ -19,14 +19,13 @@ namespace Org.BouncyCastle.Math.EC.Multiplier * @param k The integer by which to multiply k. * @return p multiplied by k. */ - public virtual ECPoint Multiply(ECPoint point, BigInteger k) + protected override ECPoint MultiplyPositive(ECPoint point, BigInteger k) { if (!(point is F2mPoint)) throw new ArgumentException("Only F2mPoint can be used in WTauNafMultiplier"); F2mPoint p = (F2mPoint)point; - - F2mCurve curve = (F2mCurve) p.Curve; + F2mCurve curve = (F2mCurve)p.Curve; int m = curve.M; sbyte a = (sbyte) curve.A.ToBigInteger().IntValue; sbyte mu = curve.GetMu(); @@ -50,16 +49,7 @@ namespace Org.BouncyCastle.Math.EC.Multiplier 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; - } + ZTauElement[] alpha = (a == 0) ? Tnaf.Alpha0 : Tnaf.Alpha1; BigInteger tw = Tnaf.GetTw(mu, Tnaf.Width); @@ -78,11 +68,10 @@ namespace Org.BouncyCastle.Math.EC.Multiplier * @param u The the WTNAF of λ.. * @return λ * p */ - private static F2mPoint MultiplyFromWTnaf(F2mPoint p, sbyte[] u, - PreCompInfo preCompInfo) + private static F2mPoint MultiplyFromWTnaf(F2mPoint p, sbyte[] u, PreCompInfo preCompInfo) { F2mCurve curve = (F2mCurve)p.Curve; - sbyte a = (sbyte) curve.A.ToBigInteger().IntValue; + sbyte a = (sbyte)curve.A.ToBigInteger().IntValue; F2mPoint[] pu; if ((preCompInfo == null) || !(preCompInfo is WTauNafPreCompInfo)) @@ -99,20 +88,21 @@ namespace Org.BouncyCastle.Math.EC.Multiplier } // q = infinity - F2mPoint q = (F2mPoint) p.Curve.Infinity; + F2mPoint q = (F2mPoint)curve.Infinity; for (int i = u.Length - 1; i >= 0; i--) { q = Tnaf.Tau(q); - if (u[i] != 0) + sbyte ui = u[i]; + if (ui != 0) { - if (u[i] > 0) + if (ui > 0) { - q = q.AddSimple(pu[u[i]]); + q = q.AddSimple(pu[ui]); } else { // u[i] < 0 - q = q.SubtractSimple(pu[-u[i]]); + q = q.SubtractSimple(pu[-ui]); } } } 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; + } + } +} -- cgit 1.4.1