Use optimized MR rounds only in random-search contexts

4 files changed, 41 insertions, 30 deletions

diff --git a/crypto/src/crypto/generators/DHParametersHelper.cs b/crypto/src/crypto/generators/DHParametersHelper.cs
index bf2de2add..385690430 100644
--- a/crypto/src/crypto/generators/DHParametersHelper.cs
+++ b/crypto/src/crypto/generators/DHParametersHelper.cs
@@ -44,10 +44,10 @@ namespace Org.BouncyCastle.Crypto.Generators
 
                     p = q.ShiftLeft(1).Add(BigInteger.One);
 
-                    if (!p.IsProbablePrime(certainty))
+                    if (!p.IsProbablePrime(certainty, true))
                         continue;
 
-                    if (certainty > 2 && !q.IsProbablePrime(certainty - 2))
+                    if (certainty > 2 && !q.IsProbablePrime(certainty, true))
                         continue;
 
                     break;
@@ -92,15 +92,15 @@ namespace Org.BouncyCastle.Crypto.Generators
                     if (q.BitLength != qLength)
                         continue;
 
-                    if (!q.RabinMillerTest(2, random))
+                    if (!q.RabinMillerTest(2, random, true))
                         continue;
 
                     p = q.ShiftLeft(1).Add(BigInteger.One);
 
-                    if (!p.RabinMillerTest(certainty, random))
+                    if (!p.RabinMillerTest(certainty, random, true))
                         continue;
 
-                    if (certainty > 2 && !q.RabinMillerTest(certainty - 2, random))
+                    if (certainty > 2 && !q.RabinMillerTest(certainty - 2, random, true))
                         continue;
 
                     /*
diff --git a/crypto/src/crypto/generators/NaccacheSternKeyPairGenerator.cs b/crypto/src/crypto/generators/NaccacheSternKeyPairGenerator.cs
index afc566d87..618ca9a1c 100644
--- a/crypto/src/crypto/generators/NaccacheSternKeyPairGenerator.cs
+++ b/crypto/src/crypto/generators/NaccacheSternKeyPairGenerator.cs
@@ -98,7 +98,7 @@ namespace Org.BouncyCastle.Crypto.Generators
 
 				p = _p.Multiply(_2au).Add(BigInteger.One);
 
-				if (!p.IsProbablePrime(certainty))
+				if (!p.IsProbablePrime(certainty, true))
 					continue;
 
 				for (;;)
@@ -110,7 +110,7 @@ namespace Org.BouncyCastle.Crypto.Generators
 
 					q = _q.Multiply(_2bv).Add(BigInteger.One);
 
-					if (q.IsProbablePrime(certainty))
+					if (q.IsProbablePrime(certainty, true))
 						break;
 				}
 
diff --git a/crypto/src/crypto/generators/RsaKeyPairGenerator.cs b/crypto/src/crypto/generators/RsaKeyPairGenerator.cs
index 2613b902b..449976550 100644
--- a/crypto/src/crypto/generators/RsaKeyPairGenerator.cs
+++ b/crypto/src/crypto/generators/RsaKeyPairGenerator.cs
@@ -150,7 +150,7 @@ namespace Org.BouncyCastle.Crypto.Generators
                 if (p.Mod(e).Equals(One))
                     continue;
 
-                if (!p.IsProbablePrime(parameters.Certainty))
+                if (!p.IsProbablePrime(parameters.Certainty, true))
                     continue;
 
                 if (!eIsKnownOddPrime && !e.Gcd(p.Subtract(One)).Equals(One))
diff --git a/crypto/src/math/BigInteger.cs b/crypto/src/math/BigInteger.cs
index 7c73334de..3d0509fe0 100644
--- a/crypto/src/math/BigInteger.cs
+++ b/crypto/src/math/BigInteger.cs
@@ -702,7 +702,7 @@ namespace Org.BouncyCastle.Math
                 if (certainty < 1)
                     break;
 
-                if (CheckProbablePrime(certainty, random))
+                if (CheckProbablePrime(certainty, random, true))
                     break;
 
                 if (bitLength > 32)
@@ -714,7 +714,7 @@ namespace Org.BouncyCastle.Math
                         this.magnitude[this.magnitude.Length - 1] ^= ((random.Next() + 1) << 1);
                         this.mQuote = 0;
 
-                        if (CheckProbablePrime(certainty, random))
+                        if (CheckProbablePrime(certainty, random, true))
                             return;
                     }
                 }
@@ -1340,8 +1340,12 @@ namespace Org.BouncyCastle.Math
          * probability of 1 - (1/2)**certainty.
          * <p>From Knuth Vol 2, pg 395.</p>
          */
-        public bool IsProbablePrime(
-            int certainty)
+        public bool IsProbablePrime(int certainty)
+        {
+            return IsProbablePrime(certainty, false);
+        }
+
+        internal bool IsProbablePrime(int certainty, bool randomlySelected)
         {
             if (certainty <= 0)
                 return true;
@@ -1354,12 +1358,10 @@ namespace Org.BouncyCastle.Math
             if (n.Equals(One))
                 return false;
 
-            return n.CheckProbablePrime(certainty, RandomSource);
+            return n.CheckProbablePrime(certainty, RandomSource, randomlySelected);
         }
 
-        private bool CheckProbablePrime(
-            int		certainty,
-            Random	random)
+        private bool CheckProbablePrime(int certainty, Random random, bool randomlySelected)
         {
             Debug.Assert(certainty > 0);
             Debug.Assert(CompareTo(Two) > 0);
@@ -1395,7 +1397,7 @@ namespace Org.BouncyCastle.Math
 
 
             // TODO Is it worth trying to create a hybrid of these two?
-            return RabinMillerTest(certainty, random);
+            return RabinMillerTest(certainty, random, randomlySelected);
 //			return SolovayStrassenTest(certainty, random);
 
 //			bool rbTest = RabinMillerTest(certainty, random);
@@ -1408,25 +1410,34 @@ namespace Org.BouncyCastle.Math
 
         public bool RabinMillerTest(int certainty, Random random)
         {
+            return RabinMillerTest(certainty, random, false);
+        }
+
+        internal bool RabinMillerTest(int certainty, Random random, bool randomlySelected)
+        {
             int bits = BitLength;
 
             Debug.Assert(certainty > 0);
             Debug.Assert(bits > 2);
             Debug.Assert(TestBit(0));
 
-            int itersFor100Cert = bits >= 1024 ?  4
-                                : bits >= 512  ?  8
-                                : bits >= 256  ? 16
-                                : 50;
-
-            int iterations;
-            if (certainty < 100)
+            int iterations = ((certainty - 1) / 2) + 1;
+            if (randomlySelected)
             {
-                iterations = System.Math.Min(itersFor100Cert, ((certainty - 1) / 2) + 1);
-            }
-            else
-            {
-                iterations = itersFor100Cert + ((certainty - 100 + 1) / 2);
+                int itersFor100Cert = bits >= 1024 ?  4
+                                    : bits >= 512  ?  8
+                                    : bits >= 256  ? 16
+                                    : 50;
+
+                if (certainty < 100)
+                {
+                    iterations = System.Math.Min(itersFor100Cert, iterations);
+                }
+                else
+                {
+                    iterations -= 50;
+                    iterations += itersFor100Cert;
+                }
             }
 
             // let n = 1 + d . 2^s
@@ -2509,7 +2520,7 @@ namespace Org.BouncyCastle.Math
 
             BigInteger n = Inc().SetBit(0);
 
-            while (!n.CheckProbablePrime(100, RandomSource))
+            while (!n.CheckProbablePrime(100, RandomSource, false))
             {
                 n = n.Add(Two);
             }