diff --git a/crypto/crypto.csproj b/crypto/crypto.csproj
index e89330bc2..7e18a8c90 100644
--- a/crypto/crypto.csproj
+++ b/crypto/crypto.csproj
@@ -4724,12 +4724,37 @@
BuildAction = "Compile"
/>
<File
+ RelPath = "src\math\ec\multiplier\AbstractECMultiplier.cs"
+ SubType = "Code"
+ BuildAction = "Compile"
+ />
+ <File
+ RelPath = "src\math\ec\multiplier\DoubleAddMultiplier.cs"
+ SubType = "Code"
+ BuildAction = "Compile"
+ />
+ <File
RelPath = "src\math\ec\multiplier\ECMultiplier.cs"
SubType = "Code"
BuildAction = "Compile"
/>
<File
- RelPath = "src\math\ec\multiplier\FpNafMultiplier.cs"
+ RelPath = "src\math\ec\multiplier\MixedNafR2LMultiplier.cs"
+ SubType = "Code"
+ BuildAction = "Compile"
+ />
+ <File
+ RelPath = "src\math\ec\multiplier\MontgomeryLadderMultiplier.cs"
+ SubType = "Code"
+ BuildAction = "Compile"
+ />
+ <File
+ RelPath = "src\math\ec\multiplier\NafL2RMultiplier.cs"
+ SubType = "Code"
+ BuildAction = "Compile"
+ />
+ <File
+ RelPath = "src\math\ec\multiplier\NafR2LMultiplier.cs"
SubType = "Code"
BuildAction = "Compile"
/>
@@ -4744,7 +4769,7 @@
BuildAction = "Compile"
/>
<File
- RelPath = "src\math\ec\multiplier\WNafMultiplier.cs"
+ RelPath = "src\math\ec\multiplier\WNafL2RMultiplier.cs"
SubType = "Code"
BuildAction = "Compile"
/>
@@ -4769,6 +4794,16 @@
BuildAction = "Compile"
/>
<File
+ RelPath = "src\math\ec\multiplier\ZSignedDigitL2RMultiplier.cs"
+ SubType = "Code"
+ BuildAction = "Compile"
+ />
+ <File
+ RelPath = "src\math\ec\multiplier\ZSignedDigitR2LMultiplier.cs"
+ SubType = "Code"
+ BuildAction = "Compile"
+ />
+ <File
RelPath = "src\math\field\FiniteFields.cs"
SubType = "Code"
BuildAction = "Compile"
diff --git a/crypto/src/math/ec/ECCurve.cs b/crypto/src/math/ec/ECCurve.cs
index fb12f0475..ed413597a 100644
--- a/crypto/src/math/ec/ECCurve.cs
+++ b/crypto/src/math/ec/ECCurve.cs
@@ -107,7 +107,7 @@ namespace Org.BouncyCastle.Math.EC
protected virtual ECMultiplier CreateDefaultMultiplier()
{
- return new WNafMultiplier();
+ return new WNafL2RMultiplier();
}
public virtual bool SupportsCoordinateSystem(int coord)
diff --git a/crypto/src/math/ec/ECPoint.cs b/crypto/src/math/ec/ECPoint.cs
index eb7128e1d..8f0168e27 100644
--- a/crypto/src/math/ec/ECPoint.cs
+++ b/crypto/src/math/ec/ECPoint.cs
@@ -469,19 +469,9 @@ namespace Org.BouncyCastle.Math.EC
* @param k The multiplicator.
* @return <code>k * this</code>.
*/
- public override ECPoint Multiply(
- BigInteger k)
+ public override ECPoint Multiply(BigInteger k)
{
- if (k.SignValue < 0)
- throw new ArgumentException("The multiplicator cannot be negative", "k");
-
- if (this.IsInfinity)
- return this;
-
- if (k.SignValue == 0)
- return Curve.Infinity;
-
- return Curve.GetMultiplier().Multiply(this, k);
+ return this.Curve.GetMultiplier().Multiply(this, k);
}
}
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;
+ }
+ }
+}
|
