diff options
Diffstat (limited to 'crypto/src/math/ec/multiplier')
| -rw-r--r-- | crypto/src/math/ec/multiplier/AbstractECMultiplier.cs | 18 | ||||
| -rw-r--r-- | crypto/src/math/ec/multiplier/DoubleAddMultiplier.cs | 24 | ||||
| -rw-r--r-- | crypto/src/math/ec/multiplier/MixedNafR2LMultiplier.cs | 75 | ||||
| -rw-r--r-- | crypto/src/math/ec/multiplier/MontgomeryLadderMultiplier.cs | 25 | ||||
| -rw-r--r-- | crypto/src/math/ec/multiplier/NafL2RMultiplier.cs (renamed from crypto/src/math/ec/multiplier/FpNafMultiplier.cs) | 6 | ||||
| -rw-r--r-- | crypto/src/math/ec/multiplier/NafR2LMultiplier.cs | 31 | ||||
| -rw-r--r-- | crypto/src/math/ec/multiplier/ReferenceMultiplier.cs | 4 | ||||
| -rw-r--r-- | crypto/src/math/ec/multiplier/WNafL2RMultiplier.cs (renamed from crypto/src/math/ec/multiplier/WNafMultiplier.cs) | 6 | ||||
| -rw-r--r-- | crypto/src/math/ec/multiplier/WTauNafMultiplier.cs | 34 | ||||
| -rw-r--r-- | crypto/src/math/ec/multiplier/ZSignedDigitL2RMultiplier.cs | 29 | ||||
| -rw-r--r-- | crypto/src/math/ec/multiplier/ZSignedDigitR2LMultiplier.cs | 30 |
11 files changed, 252 insertions, 30 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..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/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/FpNafMultiplier.cs b/crypto/src/math/ec/multiplier/NafL2RMultiplier.cs index e7efa2a44..ac80cf905 100644 --- a/crypto/src/math/ec/multiplier/FpNafMultiplier.cs +++ b/crypto/src/math/ec/multiplier/NafL2RMultiplier.cs @@ -3,10 +3,10 @@ namespace Org.BouncyCastle.Math.EC.Multiplier /** * Class implementing the NAF (Non-Adjacent Form) multiplication algorithm (left-to-right). */ - public class FpNafMultiplier - : ECMultiplier + public class NafL2RMultiplier + : AbstractECMultiplier { - public virtual ECPoint Multiply(ECPoint p, BigInteger k) + protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k) { int[] naf = WNafUtilities.GenerateCompactNaf(k); 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 <code>k * p</code>. */ - 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/WNafMultiplier.cs b/crypto/src/math/ec/multiplier/WNafL2RMultiplier.cs index 06ad76031..f671f6a5c 100644 --- a/crypto/src/math/ec/multiplier/WNafMultiplier.cs +++ b/crypto/src/math/ec/multiplier/WNafL2RMultiplier.cs @@ -6,8 +6,8 @@ namespace Org.BouncyCastle.Math.EC.Multiplier * Class implementing the WNAF (Window Non-Adjacent Form) multiplication * algorithm. */ - public class WNafMultiplier - : ECMultiplier + public class WNafL2RMultiplier + : AbstractECMultiplier { /** * Multiplies <code>this</code> by an integer <code>k</code> using the @@ -16,7 +16,7 @@ namespace Org.BouncyCastle.Math.EC.Multiplier * @return A new <code>ECPoint</code> which equals <code>this</code> * multiplied by <code>k</code>. */ - public virtual ECPoint Multiply(ECPoint p, BigInteger 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))); 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 * <code>τ</code>-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 <code>k</code>. * @return <code>p</code> multiplied by <code>k</code>. */ - 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 <code>λ</code>.. * @return <code>λ * p</code> */ - 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; + } + } +} |