diff --git a/crypto/src/math/ec/ECAlgorithms.cs b/crypto/src/math/ec/ECAlgorithms.cs
index 0b8836b6b..628680e24 100644
--- a/crypto/src/math/ec/ECAlgorithms.cs
+++ b/crypto/src/math/ec/ECAlgorithms.cs
@@ -168,25 +168,61 @@ namespace Org.BouncyCastle.Math.EC
return R;
}
- internal static ECPoint ImplShamirsTrickWNaf(ECPoint P, BigInteger k, ECPoint Q, BigInteger l)
+ internal static ECPoint ImplShamirsTrickWNaf(ECPoint P, BigInteger k,
+ ECPoint Q, BigInteger l)
{
+ bool negK = k.SignValue < 0, negL = l.SignValue < 0;
+
+ k = k.Abs();
+ l = l.Abs();
+
int widthP = System.Math.Max(2, System.Math.Min(16, WNafUtilities.GetWindowSize(k.BitLength)));
int widthQ = System.Math.Max(2, System.Math.Min(16, WNafUtilities.GetWindowSize(l.BitLength)));
WNafPreCompInfo infoP = WNafUtilities.Precompute(P, widthP, true);
WNafPreCompInfo infoQ = WNafUtilities.Precompute(Q, widthQ, true);
- ECPoint[] preCompP = infoP.PreComp;
- ECPoint[] preCompQ = infoQ.PreComp;
- ECPoint[] preCompNegP = infoP.PreCompNeg;
- ECPoint[] preCompNegQ = infoQ.PreCompNeg;
+ ECPoint[] preCompP = negK ? infoP.PreCompNeg : infoP.PreComp;
+ ECPoint[] preCompQ = negL ? infoQ.PreCompNeg : infoQ.PreComp;
+ ECPoint[] preCompNegP = negK ? infoP.PreComp : infoP.PreCompNeg;
+ ECPoint[] preCompNegQ = negL ? infoQ.PreComp : infoQ.PreCompNeg;
byte[] wnafP = WNafUtilities.GenerateWindowNaf(widthP, k);
byte[] wnafQ = WNafUtilities.GenerateWindowNaf(widthQ, l);
+ return ImplShamirsTrickWNaf(preCompP, preCompNegP, wnafP, preCompQ, preCompNegQ, wnafQ);
+ }
+
+ internal static ECPoint ImplShamirsTrickWNaf(ECPoint P, BigInteger k, ECPointMap pointMapQ, BigInteger l)
+ {
+ bool negK = k.SignValue < 0, negL = l.SignValue < 0;
+
+ k = k.Abs();
+ l = l.Abs();
+
+ int width = System.Math.Max(2, System.Math.Min(16, WNafUtilities.GetWindowSize(System.Math.Max(k.BitLength, l.BitLength))));
+
+ ECPoint Q = WNafUtilities.MapPointWithPrecomp(P, width, true, pointMapQ);
+ WNafPreCompInfo infoP = WNafUtilities.GetWNafPreCompInfo(P);
+ WNafPreCompInfo infoQ = WNafUtilities.GetWNafPreCompInfo(Q);
+
+ ECPoint[] preCompP = negK ? infoP.PreCompNeg : infoP.PreComp;
+ ECPoint[] preCompQ = negL ? infoQ.PreCompNeg : infoQ.PreComp;
+ ECPoint[] preCompNegP = negK ? infoP.PreComp : infoP.PreCompNeg;
+ ECPoint[] preCompNegQ = negL ? infoQ.PreComp : infoQ.PreCompNeg;
+
+ byte[] wnafP = WNafUtilities.GenerateWindowNaf(width, k);
+ byte[] wnafQ = WNafUtilities.GenerateWindowNaf(width, l);
+
+ return ImplShamirsTrickWNaf(preCompP, preCompNegP, wnafP, preCompQ, preCompNegQ, wnafQ);
+ }
+
+ private static ECPoint ImplShamirsTrickWNaf(ECPoint[] preCompP, ECPoint[] preCompNegP, byte[] wnafP,
+ ECPoint[] preCompQ, ECPoint[] preCompNegQ, byte[] wnafQ)
+ {
int len = System.Math.Max(wnafP.Length, wnafQ.Length);
- ECCurve curve = P.Curve;
+ ECCurve curve = preCompP[0].Curve;
ECPoint infinity = curve.Infinity;
ECPoint R = infinity;
diff --git a/crypto/src/math/ec/ECCurve.cs b/crypto/src/math/ec/ECCurve.cs
index a84863ce6..50ff88e82 100644
--- a/crypto/src/math/ec/ECCurve.cs
+++ b/crypto/src/math/ec/ECCurve.cs
@@ -2,6 +2,7 @@ using System;
using System.Collections;
using Org.BouncyCastle.Math.EC.Abc;
+using Org.BouncyCastle.Math.EC.Endo;
using Org.BouncyCastle.Math.EC.Multiplier;
using Org.BouncyCastle.Math.Field;
using Org.BouncyCastle.Utilities;
@@ -30,12 +31,14 @@ namespace Org.BouncyCastle.Math.EC
{
protected ECCurve outer;
protected int coord;
+ protected ECEndomorphism endomorphism;
protected ECMultiplier multiplier;
- internal Config(ECCurve outer, int coord, ECMultiplier multiplier)
+ internal Config(ECCurve outer, int coord, ECEndomorphism endomorphism, ECMultiplier multiplier)
{
this.outer = outer;
this.coord = coord;
+ this.endomorphism = endomorphism;
this.multiplier = multiplier;
}
@@ -45,6 +48,12 @@ namespace Org.BouncyCastle.Math.EC
return this;
}
+ public Config SetEndomorphism(ECEndomorphism endomorphism)
+ {
+ this.endomorphism = endomorphism;
+ return this;
+ }
+
public Config SetMultiplier(ECMultiplier multiplier)
{
this.multiplier = multiplier;
@@ -65,6 +74,7 @@ namespace Org.BouncyCastle.Math.EC
}
c.m_coord = coord;
+ c.m_endomorphism = endomorphism;
c.m_multiplier = multiplier;
return c;
@@ -76,6 +86,7 @@ namespace Org.BouncyCastle.Math.EC
protected BigInteger m_order, m_cofactor;
protected int m_coord = COORD_AFFINE;
+ protected ECEndomorphism m_endomorphism = null;
protected ECMultiplier m_multiplier = null;
protected ECCurve(IFiniteField field)
@@ -88,7 +99,7 @@ namespace Org.BouncyCastle.Math.EC
public virtual Config Configure()
{
- return new Config(this, this.m_coord, this.m_multiplier);
+ return new Config(this, this.m_coord, this.m_endomorphism, this.m_multiplier);
}
public virtual ECPoint CreatePoint(BigInteger x, BigInteger y)
@@ -110,6 +121,12 @@ namespace Org.BouncyCastle.Math.EC
protected virtual ECMultiplier CreateDefaultMultiplier()
{
+ GlvEndomorphism glvEndomorphism = m_endomorphism as GlvEndomorphism;
+ if (glvEndomorphism != null)
+ {
+ return new GlvMultiplier(this, glvEndomorphism);
+ }
+
return new WNafL2RMultiplier();
}
@@ -296,6 +313,11 @@ namespace Org.BouncyCastle.Math.EC
protected abstract ECPoint DecompressPoint(int yTilde, BigInteger X1);
+ public virtual ECEndomorphism GetEndomorphism()
+ {
+ return m_endomorphism;
+ }
+
/**
* Sets the default <code>ECMultiplier</code>, unless already set.
*/
diff --git a/crypto/src/math/ec/ECPointMap.cs b/crypto/src/math/ec/ECPointMap.cs
new file mode 100644
index 000000000..e78c80065
--- /dev/null
+++ b/crypto/src/math/ec/ECPointMap.cs
@@ -0,0 +1,9 @@
+using System;
+
+namespace Org.BouncyCastle.Math.EC
+{
+ public interface ECPointMap
+ {
+ ECPoint Map(ECPoint p);
+ }
+}
diff --git a/crypto/src/math/ec/ScaleXPointMap.cs b/crypto/src/math/ec/ScaleXPointMap.cs
new file mode 100644
index 000000000..f8a363b24
--- /dev/null
+++ b/crypto/src/math/ec/ScaleXPointMap.cs
@@ -0,0 +1,20 @@
+using System;
+
+namespace Org.BouncyCastle.Math.EC
+{
+ public class ScaleXPointMap
+ : ECPointMap
+ {
+ protected readonly ECFieldElement scale;
+
+ public ScaleXPointMap(ECFieldElement scale)
+ {
+ this.scale = scale;
+ }
+
+ public virtual ECPoint Map(ECPoint p)
+ {
+ return p.ScaleX(scale);
+ }
+ }
+}
diff --git a/crypto/src/math/ec/ScaleYPointMap.cs b/crypto/src/math/ec/ScaleYPointMap.cs
new file mode 100644
index 000000000..1c4795b70
--- /dev/null
+++ b/crypto/src/math/ec/ScaleYPointMap.cs
@@ -0,0 +1,20 @@
+using System;
+
+namespace Org.BouncyCastle.Math.EC
+{
+ public class ScaleYPointMap
+ : ECPointMap
+ {
+ protected readonly ECFieldElement scale;
+
+ public ScaleYPointMap(ECFieldElement scale)
+ {
+ this.scale = scale;
+ }
+
+ public virtual ECPoint Map(ECPoint p)
+ {
+ return p.ScaleY(scale);
+ }
+ }
+}
diff --git a/crypto/src/math/ec/endo/ECEndomorphism.cs b/crypto/src/math/ec/endo/ECEndomorphism.cs
new file mode 100644
index 000000000..dfb321368
--- /dev/null
+++ b/crypto/src/math/ec/endo/ECEndomorphism.cs
@@ -0,0 +1,11 @@
+using System;
+
+namespace Org.BouncyCastle.Math.EC.Endo
+{
+ public interface ECEndomorphism
+ {
+ ECPointMap PointMap { get; }
+
+ bool HasEfficientPointMap { get; }
+ }
+}
diff --git a/crypto/src/math/ec/endo/GlvEndomorphism.cs b/crypto/src/math/ec/endo/GlvEndomorphism.cs
new file mode 100644
index 000000000..f65bdd613
--- /dev/null
+++ b/crypto/src/math/ec/endo/GlvEndomorphism.cs
@@ -0,0 +1,10 @@
+using System;
+
+namespace Org.BouncyCastle.Math.EC.Endo
+{
+ public interface GlvEndomorphism
+ : ECEndomorphism
+ {
+ BigInteger[] DecomposeScalar(BigInteger k);
+ }
+}
diff --git a/crypto/src/math/ec/endo/GlvTypeBEndomorphism.cs b/crypto/src/math/ec/endo/GlvTypeBEndomorphism.cs
new file mode 100644
index 000000000..d234d88bf
--- /dev/null
+++ b/crypto/src/math/ec/endo/GlvTypeBEndomorphism.cs
@@ -0,0 +1,55 @@
+using System;
+
+namespace Org.BouncyCastle.Math.EC.Endo
+{
+ public class GlvTypeBEndomorphism
+ : GlvEndomorphism
+ {
+ protected readonly ECCurve m_curve;
+ protected readonly GlvTypeBParameters m_parameters;
+ protected readonly ECPointMap m_pointMap;
+
+ public GlvTypeBEndomorphism(ECCurve curve, GlvTypeBParameters parameters)
+ {
+ this.m_curve = curve;
+ this.m_parameters = parameters;
+ this.m_pointMap = new ScaleXPointMap(curve.FromBigInteger(parameters.Beta));
+ }
+
+ public virtual BigInteger[] DecomposeScalar(BigInteger k)
+ {
+ int bits = m_parameters.Bits;
+ BigInteger b1 = CalculateB(k, m_parameters.G1, bits);
+ BigInteger b2 = CalculateB(k, m_parameters.G2, bits);
+
+ BigInteger[] v1 = m_parameters.V1, v2 = m_parameters.V2;
+ BigInteger a = k.Subtract((b1.Multiply(v1[0])).Add(b2.Multiply(v2[0])));
+ BigInteger b = (b1.Multiply(v1[1])).Add(b2.Multiply(v2[1])).Negate();
+
+ return new BigInteger[]{ a, b };
+ }
+
+ public virtual ECPointMap PointMap
+ {
+ get { return m_pointMap; }
+ }
+
+ public virtual bool HasEfficientPointMap
+ {
+ get { return true; }
+ }
+
+ protected virtual BigInteger CalculateB(BigInteger k, BigInteger g, int t)
+ {
+ bool negative = (g.SignValue < 0);
+ BigInteger b = k.Multiply(g.Abs());
+ bool extra = b.TestBit(t - 1);
+ b = b.ShiftRight(t);
+ if (extra)
+ {
+ b = b.Add(BigInteger.One);
+ }
+ return negative ? b.Negate() : b;
+ }
+ }
+}
diff --git a/crypto/src/math/ec/endo/GlvTypeBParameters.cs b/crypto/src/math/ec/endo/GlvTypeBParameters.cs
new file mode 100644
index 000000000..f93dfaf2b
--- /dev/null
+++ b/crypto/src/math/ec/endo/GlvTypeBParameters.cs
@@ -0,0 +1,60 @@
+using System;
+
+namespace Org.BouncyCastle.Math.EC.Endo
+{
+ public class GlvTypeBParameters
+ {
+ protected readonly BigInteger m_beta;
+ protected readonly BigInteger m_lambda;
+ protected readonly BigInteger[] m_v1, m_v2;
+ protected readonly BigInteger m_g1, m_g2;
+ protected readonly int m_bits;
+
+ public GlvTypeBParameters(BigInteger beta, BigInteger lambda, BigInteger[] v1, BigInteger[] v2,
+ BigInteger g1, BigInteger g2, int bits)
+ {
+ this.m_beta = beta;
+ this.m_lambda = lambda;
+ this.m_v1 = v1;
+ this.m_v2 = v2;
+ this.m_g1 = g1;
+ this.m_g2 = g2;
+ this.m_bits = bits;
+ }
+
+ public virtual BigInteger Beta
+ {
+ get { return m_beta; }
+ }
+
+ public virtual BigInteger Lambda
+ {
+ get { return m_lambda; }
+ }
+
+ public virtual BigInteger[] V1
+ {
+ get { return m_v1; }
+ }
+
+ public virtual BigInteger[] V2
+ {
+ get { return m_v2; }
+ }
+
+ public virtual BigInteger G1
+ {
+ get { return m_g1; }
+ }
+
+ public virtual BigInteger G2
+ {
+ get { return m_g2; }
+ }
+
+ public virtual int Bits
+ {
+ get { return m_bits; }
+ }
+ }
+}
diff --git a/crypto/src/math/ec/multiplier/WNafUtilities.cs b/crypto/src/math/ec/multiplier/WNafUtilities.cs
index 179d6d6eb..98e4f545f 100644
--- a/crypto/src/math/ec/multiplier/WNafUtilities.cs
+++ b/crypto/src/math/ec/multiplier/WNafUtilities.cs
@@ -268,6 +268,11 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
return wnaf;
}
+ 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))
@@ -309,6 +314,45 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
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;
@@ -335,7 +379,7 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
ECPoint twiceP = wnafPreCompInfo.Twice;
if (twiceP == null)
{
- twiceP = preComp[0].Twice().Normalize();
+ twiceP = preComp[0].Twice();
wnafPreCompInfo.Twice = twiceP;
}
|
