Save an inversion in ECDSA verification for common cases

2 files changed, 67 insertions, 2 deletions

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)
         {