diff --git a/crypto/src/crypto/signers/ECDsaSigner.cs b/crypto/src/crypto/signers/ECDsaSigner.cs
index 9821732c2..0c6117ebb 100644
--- a/crypto/src/crypto/signers/ECDsaSigner.cs
+++ b/crypto/src/crypto/signers/ECDsaSigner.cs
@@ -15,6 +15,8 @@ namespace Org.BouncyCastle.Crypto.Signers
public class ECDsaSigner
: IDsa
{
+ private static readonly BigInteger Eight = BigInteger.ValueOf(8);
+
protected readonly IDsaKCalculator kCalculator;
protected ECKeyParameters key = null;
@@ -149,13 +151,49 @@ namespace Org.BouncyCastle.Crypto.Signers
ECPoint G = key.Parameters.G;
ECPoint Q = ((ECPublicKeyParameters) key).Q;
- ECPoint point = ECAlgorithms.SumOfTwoMultiplies(G, u1, Q, u2).Normalize();
+ ECPoint point = ECAlgorithms.SumOfTwoMultiplies(G, u1, Q, u2);
if (point.IsInfinity)
return false;
- BigInteger v = point.AffineXCoord.ToBigInteger().Mod(n);
+ /*
+ * If possible, avoid normalizing the point (to save a modular inversion in the curve field).
+ *
+ * There are ~cofactor elements of the curve field that reduce (modulo the group order) to 'r'.
+ * If the cofactor is known and small, we generate those possible field values and project each
+ * of them to the same "denominator" (depending on the particular projective coordinates in use)
+ * as the calculated point.X. If any of the projected values matches point.X, then we have:
+ * (point.X / Denominator mod p) mod n == r
+ * as required, and verification succeeds.
+ *
+ * Based on an original idea by Gregory Maxwell (https://github.com/gmaxwell), as implemented in
+ * the libsecp256k1 project (https://github.com/bitcoin/secp256k1).
+ */
+ ECCurve curve = point.Curve;
+ if (curve != null)
+ {
+ BigInteger cofactor = curve.Cofactor;
+ if (cofactor != null && cofactor.CompareTo(Eight) <= 0)
+ {
+ ECFieldElement D = GetDenominator(curve.CoordinateSystem, point);
+ if (D != null && !D.IsZero)
+ {
+ ECFieldElement X = point.XCoord;
+ while (curve.IsValidFieldElement(r))
+ {
+ ECFieldElement R = curve.FromBigInteger(r).Multiply(D);
+ if (R.Equals(X))
+ {
+ return true;
+ }
+ r = r.Add(n);
+ }
+ return false;
+ }
+ }
+ }
+ BigInteger v = point.Normalize().AffineXCoord.ToBigInteger().Mod(n);
return v.Equals(r);
}
@@ -177,6 +215,22 @@ namespace Org.BouncyCastle.Crypto.Signers
return new FixedPointCombMultiplier();
}
+ protected virtual ECFieldElement GetDenominator(int coordinateSystem, ECPoint p)
+ {
+ switch (coordinateSystem)
+ {
+ case ECCurve.COORD_HOMOGENEOUS:
+ case ECCurve.COORD_LAMBDA_PROJECTIVE:
+ return p.GetZCoord(0);
+ case ECCurve.COORD_JACOBIAN:
+ case ECCurve.COORD_JACOBIAN_CHUDNOVSKY:
+ case ECCurve.COORD_JACOBIAN_MODIFIED:
+ return p.GetZCoord(0).Square();
+ default:
+ return null;
+ }
+ }
+
protected virtual SecureRandom InitSecureRandom(bool needed, SecureRandom provided)
{
return !needed ? null : (provided != null) ? provided : new SecureRandom();
diff --git a/crypto/src/math/ec/ECCurve.cs b/crypto/src/math/ec/ECCurve.cs
index fa2c72570..6ccd97e7b 100644
--- a/crypto/src/math/ec/ECCurve.cs
+++ b/crypto/src/math/ec/ECCurve.cs
@@ -96,6 +96,7 @@ namespace Org.BouncyCastle.Math.EC
public abstract int FieldSize { get; }
public abstract ECFieldElement FromBigInteger(BigInteger x);
+ public abstract bool IsValidFieldElement(BigInteger x);
public virtual Config Configure()
{
@@ -477,6 +478,11 @@ namespace Org.BouncyCastle.Math.EC
{
}
+ public override bool IsValidFieldElement(BigInteger x)
+ {
+ return x != null && x.SignValue >= 0 && x.CompareTo(Field.Characteristic) < 0;
+ }
+
protected override ECPoint DecompressPoint(int yTilde, BigInteger X1)
{
ECFieldElement x = FromBigInteger(X1);
@@ -670,6 +676,11 @@ namespace Org.BouncyCastle.Math.EC
{
}
+ public override bool IsValidFieldElement(BigInteger x)
+ {
+ return x != null && x.SignValue >= 0 && x.BitLength <= FieldSize;
+ }
+
[Obsolete("Per-point compression property will be removed")]
public override ECPoint CreatePoint(BigInteger x, BigInteger y, bool withCompression)
{
|
