Add fast coprime test

6 files changed, 289 insertions, 49 deletions

diff --git a/crypto/src/crypto/generators/NaccacheSternKeyPairGenerator.cs b/crypto/src/crypto/generators/NaccacheSternKeyPairGenerator.cs
index 09f4b3db9..8db9db728 100644
--- a/crypto/src/crypto/generators/NaccacheSternKeyPairGenerator.cs
+++ b/crypto/src/crypto/generators/NaccacheSternKeyPairGenerator.cs
@@ -112,7 +112,7 @@ namespace Org.BouncyCastle.Crypto.Generators
 						break;
 				}
 
-				if (!sigma.Gcd(_p.Multiply(_q)).Equals(BigInteger.One))
+				if (!BigIntegers.ModOddIsCoprime(_p.Multiply(_q), sigma))
 				{
                     //Console.WriteLine("sigma.gcd(_p.mult(_q)) != 1!\n _p: " + _p +"\n _q: "+ _q );
 					continue;
diff --git a/crypto/src/crypto/generators/RSABlindingFactorGenerator.cs b/crypto/src/crypto/generators/RSABlindingFactorGenerator.cs
index a9eeb46df..410d37c63 100644
--- a/crypto/src/crypto/generators/RSABlindingFactorGenerator.cs
+++ b/crypto/src/crypto/generators/RSABlindingFactorGenerator.cs
@@ -3,6 +3,7 @@ using System;
 using Org.BouncyCastle.Crypto.Parameters;
 using Org.BouncyCastle.Math;
 using Org.BouncyCastle.Security;
+using Org.BouncyCastle.Utilities;
 
 namespace Org.BouncyCastle.Crypto.Generators
 {
@@ -50,15 +51,13 @@ namespace Org.BouncyCastle.Crypto.Generators
 
 			BigInteger m = key.Modulus;
 			int length = m.BitLength - 1; // must be less than m.BitLength
-			BigInteger factor;
-			BigInteger gcd;
 
+			BigInteger factor;
 			do
 			{
-				factor = new BigInteger(length, random);
-				gcd = factor.Gcd(m);
+				factor = BigIntegers.CreateRandomBigInteger(length, random);
 			}
-			while (factor.SignValue == 0 || factor.Equals(BigInteger.One) || !gcd.Equals(BigInteger.One));
+			while (factor.CompareTo(BigInteger.Two) < 0 || !BigIntegers.ModOddIsCoprime(m, factor));
 
 			return factor;
 		}
diff --git a/crypto/src/crypto/parameters/RsaKeyParameters.cs b/crypto/src/crypto/parameters/RsaKeyParameters.cs
index f7e88a2b8..8826bb1ab 100644
--- a/crypto/src/crypto/parameters/RsaKeyParameters.cs
+++ b/crypto/src/crypto/parameters/RsaKeyParameters.cs
@@ -17,16 +17,29 @@ namespace Org.BouncyCastle.Crypto.Parameters
                 + "f3cfd51e474afb6bc6974f78db8aba8e9e517fded658591ab7502bd41849462f",
             16);
 
+        private static bool HasAnySmallFactors(BigInteger modulus)
+        {
+            BigInteger M = modulus, X = SmallPrimesProduct;
+            if (modulus.CompareTo(SmallPrimesProduct) < 0)
+            {
+                M = SmallPrimesProduct;
+                X = modulus;
+            }
+
+            return !BigIntegers.ModOddIsCoprimeVar(M, X);
+        }
+
         private static BigInteger Validate(BigInteger modulus)
         {
             if ((modulus.IntValue & 1) == 0)
                 throw new ArgumentException("RSA modulus is even", nameof(modulus));
-            if (!modulus.Gcd(SmallPrimesProduct).Equals(BigInteger.One))
-                throw new ArgumentException("RSA modulus has a small prime factor", nameof(modulus));
 
             int maxBitLength = ImplGetInteger("Org.BouncyCastle.Rsa.MaxSize", 16384);
             if (modulus.BitLength > maxBitLength)
-                throw new ArgumentException("modulus value out of range");
+                throw new ArgumentException("RSA modulus out of range", nameof(modulus));
+
+            if (HasAnySmallFactors(modulus))
+                throw new ArgumentException("RSA modulus has a small prime factor", nameof(modulus));
 
             // TODO: add additional primePower/Composite test - expensive!!
 
diff --git a/crypto/src/math/raw/Mod.cs b/crypto/src/math/raw/Mod.cs
index bc5942711..984c4808d 100644
--- a/crypto/src/math/raw/Mod.cs
+++ b/crypto/src/math/raw/Mod.cs
@@ -112,7 +112,7 @@ namespace Org.BouncyCastle.Math.Raw
             Decode30(bits, D, 0, z, 0);
             Debug.Assert(0 != Nat.LessThan(m.Length, z, m));
 
-            return (uint)(EqualTo(len30, F, 1) & EqualToZero(len30, G));
+            return (uint)(EqualTo(len30, F, 1) & EqualTo(len30, G, 0));
 #endif
         }
 
@@ -163,7 +163,7 @@ namespace Org.BouncyCastle.Math.Raw
             Decode30(bits, D, z);
             Debug.Assert(0 != Nat.LessThan(m.Length, z, m));
 
-            return (uint)(EqualTo(len30, F, 1) & EqualToZero(len30, G));
+            return (uint)(EqualTo(len30, F, 1) & EqualTo(len30, G, 0));
         }
 #endif
 
@@ -199,7 +199,7 @@ namespace Org.BouncyCastle.Math.Raw
             int maxDivsteps = GetMaximumDivsteps(bits) - clz;
 
             int divsteps = 0;
-            while (!EqualToZeroVar_Unlikely(lenFG, G))
+            while (!EqualToVar(lenFG, G, 0))
             {
                 if (divsteps >= maxDivsteps)
                     return false;
@@ -231,7 +231,7 @@ namespace Org.BouncyCastle.Math.Raw
             }
             Debug.Assert(0 == signF);
 
-            if (!EqualToOneVar_Expected(lenFG, F))
+            if (!EqualToVar(lenFG, F, 1))
                 return false;
 
             if (signD < 0)
@@ -282,7 +282,7 @@ namespace Org.BouncyCastle.Math.Raw
             int maxDivsteps = GetMaximumDivsteps(bits) - clz;
 
             int divsteps = 0;
-            while (!EqualToZeroVar_Unlikely(lenFG, G))
+            while (!EqualToVar(lenFG, G, 0))
             {
                 if (divsteps >= maxDivsteps)
                     return false;
@@ -314,7 +314,7 @@ namespace Org.BouncyCastle.Math.Raw
             }
             Debug.Assert(0 == signF);
 
-            if (!EqualToOneVar_Expected(lenFG, F))
+            if (!EqualToVar(lenFG, F, 1))
                 return false;
 
             if (signD < 0)
@@ -330,6 +330,182 @@ namespace Org.BouncyCastle.Math.Raw
         }
 #endif
 
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+        public static uint ModOddIsCoprime(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x)
+        {
+            int len32 = m.Length;
+            Debug.Assert(len32 > 0);
+            Debug.Assert((m[0] & 1) != 0);
+            Debug.Assert(m[len32 - 1] != 0);
+
+            int bits = (len32 << 5) - Integers.NumberOfLeadingZeros((int)m[len32 - 1]);
+            int len30 = (bits + 29) / 30;
+
+            int allocSize = len30 * 3;
+            Span<int> alloc = (allocSize * Integers.NumBytes <= MaxStackAlloc)
+                ? stackalloc int[allocSize]
+                : new int[allocSize];
+
+            Span<int> t = stackalloc int[4];
+            Span<int> F = alloc[..len30]; alloc = alloc[len30..];
+            Span<int> G = alloc[..len30]; alloc = alloc[len30..];
+            Span<int> M = alloc[..len30];
+
+            Encode30(bits, x, G);
+            Encode30(bits, m, M);
+            M.CopyTo(F);
+
+            int delta = 0;
+            int maxDivsteps = GetMaximumDivsteps(bits);
+
+            for (int divSteps = 0; divSteps < maxDivsteps; divSteps += 30)
+            {
+                delta = Divsteps30(delta, F[0], G[0], t);
+                UpdateFG30(len30, F, G, t);
+            }
+
+            int signF = F[len30 - 1] >> 31;
+            CNegate30(len30, signF, F);
+
+            return (uint)(EqualTo(len30, F, 1) & EqualTo(len30, G, 0));
+        }
+#else
+        public static uint ModOddIsCoprime(uint[] m, uint[] x)
+        {
+            int len32 = m.Length;
+            Debug.Assert(len32 > 0);
+            Debug.Assert((m[0] & 1) != 0);
+            Debug.Assert(m[len32 - 1] != 0);
+
+            int bits = (len32 << 5) - Integers.NumberOfLeadingZeros((int)m[len32 - 1]);
+            int len30 = (bits + 29) / 30;
+
+            int[] t = new int[4];
+            int[] F = new int[len30];
+            int[] G = new int[len30];
+            int[] M = new int[len30];
+
+            Encode30(bits, x, 0, G, 0);
+            Encode30(bits, m, 0, M, 0);
+            Array.Copy(M, 0, F, 0, len30);
+
+            int delta = 0;
+            int maxDivsteps = GetMaximumDivsteps(bits);
+
+            for (int divSteps = 0; divSteps < maxDivsteps; divSteps += 30)
+            {
+                delta = Divsteps30(delta, F[0], G[0], t);
+                UpdateFG30(len30, F, G, t);
+            }
+
+            int signF = F[len30 - 1] >> 31;
+            CNegate30(len30, signF, F);
+
+            return (uint)(EqualTo(len30, F, 1) & EqualTo(len30, G, 0));
+        }
+#endif
+
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+        public static bool ModOddIsCoprimeVar(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x)
+        {
+            int len32 = m.Length;
+            Debug.Assert(len32 > 0);
+            Debug.Assert((m[0] & 1) != 0);
+            Debug.Assert(m[len32 - 1] != 0);
+
+            int bits = (len32 << 5) - Integers.NumberOfLeadingZeros((int)m[len32 - 1]);
+            int len30 = (bits + 29) / 30;
+
+            int allocSize = len30 * 3;
+            Span<int> alloc = (allocSize * Integers.NumBytes <= MaxStackAlloc)
+                ? stackalloc int[allocSize]
+                : new int[allocSize];
+
+            Span<int> t = stackalloc int[4];
+            Span<int> F = alloc[..len30]; alloc = alloc[len30..];
+            Span<int> G = alloc[..len30]; alloc = alloc[len30..];
+            Span<int> M = alloc[..len30];
+
+            Encode30(bits, x, G);
+            Encode30(bits, m, M);
+            M.CopyTo(F);
+
+            int clz = System.Math.Max(0, bits - 1 - Nat.GetBitLength(len32, x));
+            int eta = -1 - clz;
+            int lenFG = len30;
+            int maxDivsteps = GetMaximumDivsteps(bits) - clz;
+
+            int divsteps = 0;
+            while (!EqualToVar(lenFG, G, 0))
+            {
+                if (divsteps >= maxDivsteps)
+                    return false;
+
+                divsteps += 30;
+
+                eta = Divsteps30Var(eta, F[0], G[0], t);
+                UpdateFG30(lenFG, F, G, t);
+                lenFG = TrimFG30Var(lenFG, F, G);
+            }
+
+            int signF = F[lenFG - 1] >> 31;
+            if (signF < 0)
+            {
+                signF = Negate30(lenFG, F);
+            }
+            Debug.Assert(0 == signF);
+
+            return EqualToVar(lenFG, F, 1);
+        }
+#else
+        public static bool ModOddIsCoprimeVar(uint[] m, uint[] x)
+        {
+            int len32 = m.Length;
+            Debug.Assert(len32 > 0);
+            Debug.Assert((m[0] & 1) != 0);
+            Debug.Assert(m[len32 - 1] != 0);
+
+            int bits = (len32 << 5) - Integers.NumberOfLeadingZeros((int)m[len32 - 1]);
+            int len30 = (bits + 29) / 30;
+
+            int[] t = new int[4];
+            int[] F = new int[len30];
+            int[] G = new int[len30];
+            int[] M = new int[len30];
+
+            Encode30(bits, x, 0, G, 0);
+            Encode30(bits, m, 0, M, 0);
+            Array.Copy(M, 0, F, 0, len30);
+
+            int clz = System.Math.Max(0, bits - 1 - Nat.GetBitLength(len32, x));
+            int eta = -1 - clz;
+            int lenFG = len30;
+            int maxDivsteps = GetMaximumDivsteps(bits) - clz;
+
+            int divsteps = 0;
+            while (!EqualToVar(lenFG, G, 0))
+            {
+                if (divsteps >= maxDivsteps)
+                    return false;
+
+                divsteps += 30;
+
+                eta = Divsteps30Var(eta, F[0], G[0], t);
+                UpdateFG30(lenFG, F, G, t);
+                lenFG = TrimFG30Var(lenFG, F, G);
+            }
+
+            int signF = F[lenFG - 1] >> 31;
+            if (signF < 0)
+            {
+                signF = Negate30(lenFG, F);
+            }
+            Debug.Assert(0 == signF);
+
+            return EqualToVar(lenFG, F, 1);
+        }
+#endif
+
         public static uint[] Random(SecureRandom random, uint[] p)
         {
             int len = p.Length;
@@ -692,41 +868,12 @@ namespace Org.BouncyCastle.Math.Raw
         }
 
 #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
-        private static bool EqualToOneVar_Expected(int len, ReadOnlySpan<int> x)
+        private static bool EqualToVar(int len, ReadOnlySpan<int> x, int y)
 #else
-        private static bool EqualToOneVar_Expected(int len, int[] x)
+        private static bool EqualToVar(int len, int[] x, int y)
 #endif
         {
-            int d = x[0] ^ 1;
-            for (int i = 1; i < len; ++i)
-            {
-                d |= x[i];
-            }
-            return d == 0;
-        }
-
-#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
-        private static int EqualToZero(int len, ReadOnlySpan<int> x)
-#else
-        private static int EqualToZero(int len, int[] x)
-#endif
-        {
-            int d = 0;
-            for (int i = 0; i < len; ++i)
-            {
-                d |= x[i];
-            }
-            d = (int)((uint)d >> 1) | (d & 1);
-            return (d - 1) >> 31;
-        }
-
-#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
-        private static bool EqualToZeroVar_Unlikely(int len, ReadOnlySpan<int> x)
-#else
-        private static bool EqualToZeroVar_Unlikely(int len, int[] x)
-#endif
-        {
-            int d = x[0];
+            int d = x[0] ^ y;
             if (d != 0)
                 return false;
 
diff --git a/crypto/src/util/BigIntegers.cs b/crypto/src/util/BigIntegers.cs
index d1b15f869..8c2068688 100644
--- a/crypto/src/util/BigIntegers.cs
+++ b/crypto/src/util/BigIntegers.cs
@@ -265,5 +265,69 @@ namespace Org.BouncyCastle.Utilities
                 return Nat.ToBigInteger(len, z);
             }
         }
+
+        public static bool ModOddIsCoprime(BigInteger M, BigInteger X)
+        {
+            if (!M.TestBit(0))
+                throw new ArgumentException("must be odd", nameof(M));
+            if (M.SignValue != 1)
+                throw new ArithmeticException("BigInteger: modulus not positive");
+            if (X.SignValue < 0 || X.CompareTo(M) >= 0)
+            {
+                X = X.Mod(M);
+            }
+
+            int bits = M.BitLength;
+
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+            if (bits <= 2048)
+            {
+                int len = Nat.GetLengthForBits(bits);
+                Span<uint> m = stackalloc uint[len];
+                Span<uint> x = stackalloc uint[len];
+                Nat.FromBigInteger(bits, M, m);
+                Nat.FromBigInteger(bits, X, x);
+                return 0 != Mod.ModOddIsCoprime(m, x);
+            }
+            else
+#endif
+            {
+                uint[] m = Nat.FromBigInteger(bits, M);
+                uint[] x = Nat.FromBigInteger(bits, X);
+                return 0 != Mod.ModOddIsCoprime(m, x);
+            }
+        }
+
+        public static bool ModOddIsCoprimeVar(BigInteger M, BigInteger X)
+        {
+            if (!M.TestBit(0))
+                throw new ArgumentException("must be odd", nameof(M));
+            if (M.SignValue != 1)
+                throw new ArithmeticException("BigInteger: modulus not positive");
+            if (X.SignValue < 0 || X.CompareTo(M) >= 0)
+            {
+                X = X.Mod(M);
+            }
+
+            int bits = M.BitLength;
+
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+            if (bits <= 2048)
+            {
+                int len = Nat.GetLengthForBits(bits);
+                Span<uint> m = stackalloc uint[len];
+                Span<uint> x = stackalloc uint[len];
+                Nat.FromBigInteger(bits, M, m);
+                Nat.FromBigInteger(bits, X, x);
+                return Mod.ModOddIsCoprimeVar(m, x);
+            }
+            else
+#endif
+            {
+                uint[] m = Nat.FromBigInteger(bits, M);
+                uint[] x = Nat.FromBigInteger(bits, X);
+                return Mod.ModOddIsCoprimeVar(m, x);
+            }
+        }
     }
 }
diff --git a/crypto/test/src/crypto/test/RsaTest.cs b/crypto/test/src/crypto/test/RsaTest.cs
index 3c01baa85..58c10f59c 100644
--- a/crypto/test/src/crypto/test/RsaTest.cs
+++ b/crypto/test/src/crypto/test/RsaTest.cs
@@ -2,7 +2,6 @@ using System;
 
 using NUnit.Framework;
 
-using Org.BouncyCastle.Crypto;
 using Org.BouncyCastle.Crypto.Digests;
 using Org.BouncyCastle.Crypto.Encodings;
 using Org.BouncyCastle.Crypto.Engines;
@@ -751,5 +750,23 @@ namespace Org.BouncyCastle.Crypto.Tests
 
 			Assert.AreEqual(Name + ": Okay", resultText);
 		}
-	}
+
+        [Test, Explicit]
+        public void BenchPublicKeyModulusValidation()
+        {
+			SecureRandom secureRandom = SecureRandom.GetInstance("SHA512PRNG", false);
+			secureRandom.SetSeed(2);
+
+            var kpg = new RsaKeyPairGenerator();
+			kpg.Init(new RsaKeyGenerationParameters(BigInteger.ValueOf(0x11), secureRandom, 2048, 100));
+
+			var kp = kpg.GenerateKeyPair();
+			var pub = (RsaKeyParameters)kp.Public;
+
+			for (int i = 0; i < 1000000; ++i)
+            {
+				new RsaKeyParameters(false, pub.Modulus, pub.Exponent);
+            }
+        }
+    }
 }