For safe primes, use Legendre symbol

- DH public key validation when 'Q' available
- In particular, greatly speeds up TLS FFDHE groups

2 files changed, 122 insertions, 6 deletions

diff --git a/crypto/src/crypto/parameters/DHPublicKeyParameters.cs b/crypto/src/crypto/parameters/DHPublicKeyParameters.cs
index e7aeeff19..19e732b89 100644
--- a/crypto/src/crypto/parameters/DHPublicKeyParameters.cs
+++ b/crypto/src/crypto/parameters/DHPublicKeyParameters.cs
@@ -2,6 +2,8 @@ using System;
 
 using Org.BouncyCastle.Asn1;
 using Org.BouncyCastle.Math;
+using Org.BouncyCastle.Math.Raw;
+using Org.BouncyCastle.Utilities;
 
 namespace Org.BouncyCastle.Crypto.Parameters
 {
@@ -13,18 +15,33 @@ namespace Org.BouncyCastle.Crypto.Parameters
             if (y == null)
                 throw new ArgumentNullException("y");
 
+            BigInteger p = dhParams.P;
+
             // TLS check
-            if (y.CompareTo(BigInteger.Two) < 0 || y.CompareTo(dhParams.P.Subtract(BigInteger.Two)) > 0)
+            if (y.CompareTo(BigInteger.Two) < 0 || y.CompareTo(p.Subtract(BigInteger.Two)) > 0)
                 throw new ArgumentException("invalid DH public key", "y");
 
-            // we can't validate without Q.
-            if (dhParams.Q != null
-                && !y.ModPow(dhParams.Q, dhParams.P).Equals(BigInteger.One))
+            BigInteger q = dhParams.Q;
+
+            // We can't validate without Q.
+            if (q == null)
+                return y;
+
+            if (p.TestBit(0)
+                && p.BitLength - 1 == q.BitLength
+                && p.ShiftRight(1).Equals(q))
             {
-                throw new ArgumentException("y value does not appear to be in correct group", "y");
+                // Safe prime case
+                if (1 == Legendre(y, p))
+                    return y;
+            }
+            else
+            {
+                if (BigInteger.One.Equals(y.ModPow(q, p)))
+                    return y;
             }
 
-            return y;
+            throw new ArgumentException("value does not appear to be in correct group", "y");
         }
 
         private readonly BigInteger y;
@@ -75,5 +92,76 @@ namespace Org.BouncyCastle.Crypto.Parameters
         {
             return y.GetHashCode() ^ base.GetHashCode();
         }
+
+        private static int Legendre(BigInteger a, BigInteger b)
+        {
+            //int r = 0, bits = b.IntValue;
+
+            //for (;;)
+            //{
+            //    int lowestSetBit = a.GetLowestSetBit();
+            //    a = a.ShiftRight(lowestSetBit);
+            //    r ^= (bits ^ (bits >> 1)) & (lowestSetBit << 1);
+
+            //    int cmp = a.CompareTo(b);
+            //    if (cmp == 0)
+            //        break;
+
+            //    if (cmp < 0)
+            //    {
+            //        BigInteger t = a; a = b; b = t;
+
+            //        int oldBits = bits;
+            //        bits = b.IntValue;
+            //        r ^= oldBits & bits;
+            //    }
+
+            //    a = a.Subtract(b);
+            //}
+
+            //return BigInteger.One.Equals(b) ? (1 - (r & 2)) : 0;
+
+            int bitLength = b.BitLength;
+            uint[] A = Nat.FromBigInteger(bitLength, a);
+            uint[] B = Nat.FromBigInteger(bitLength, b);
+
+            int r = 0;
+
+            int len = B.Length;
+            for (;;)
+            {
+                while (A[0] == 0)
+                {
+                    Nat.ShiftDownWord(len, A, 0);
+                }
+
+                int shift = Integers.NumberOfTrailingZeros((int)A[0]);
+                if (shift > 0)
+                {
+                    Nat.ShiftDownBits(len, A, shift, 0);
+                    int bits = (int)B[0];
+                    r ^= (bits ^ (bits >> 1)) & (shift << 1);
+                }
+
+                int cmp = Nat.Compare(len, A, B);
+                if (cmp == 0)
+                    break;
+
+                if (cmp < 0)
+                {
+                    r ^= (int)(A[0] & B[0]);
+                    uint[] t = A; A = B; B = t;
+                }
+
+                while (A[len - 1] == 0)
+                {
+                    len = len - 1;
+                }
+
+                Nat.Sub(len, A, B, A);
+            }
+
+            return Nat.IsOne(len, B) ? (1 - (r & 2)) : 0;
+        }
     }
 }
diff --git a/crypto/src/math/raw/Nat.cs b/crypto/src/math/raw/Nat.cs
index 8ec328d11..69942661f 100644
--- a/crypto/src/math/raw/Nat.cs
+++ b/crypto/src/math/raw/Nat.cs
@@ -278,6 +278,34 @@ namespace Org.BouncyCastle.Math.Raw
             //}
         }
 
+        public static int Compare(int len, uint[] x, uint[] y)
+        {
+            for (int i = len - 1; i >= 0; --i)
+            {
+                uint x_i = x[i];
+                uint y_i = y[i];
+                if (x_i < y_i)
+                    return -1;
+                if (x_i > y_i)
+                    return 1;
+            }
+            return 0;
+        }
+
+        public static int Compare(int len, uint[] x, int xOff, uint[] y, int yOff)
+        {
+            for (int i = len - 1; i >= 0; --i)
+            {
+                uint x_i = x[xOff + i];
+                uint y_i = y[yOff + i];
+                if (x_i < y_i)
+                    return -1;
+                if (x_i > y_i)
+                    return 1;
+            }
+            return 0;
+        }
+
         public static void Copy(int len, uint[] x, uint[] z)
         {
             Array.Copy(x, 0, z, 0, len);