Add Miller-Rabin methods

1 files changed, 319 insertions, 45 deletions

diff --git a/crypto/src/math/Primes.cs b/crypto/src/math/Primes.cs
index b57977983..55d739f34 100644
--- a/crypto/src/math/Primes.cs
+++ b/crypto/src/math/Primes.cs
@@ -1,10 +1,14 @@
 using System;
 
 using Org.BouncyCastle.Crypto;
+using Org.BouncyCastle.Security;
 using Org.BouncyCastle.Utilities;
 
 namespace Org.BouncyCastle.Math
 {
+    /**
+     * Utility methods for generating primes and testing for primality.
+     */
     public static class Primes
     {
         private static readonly BigInteger One = BigInteger.One;
@@ -12,7 +16,54 @@ namespace Org.BouncyCastle.Math
         private static readonly BigInteger Three = BigInteger.Three;
 
         /**
-         * Used to return the output from the {@linkplain #generateSTRandomPrime(Digest) Shawe-Taylor Random_Prime Routine} 
+         * Used to return the output from the
+         * {@linkplain Primes#enhancedMRProbablePrimeTest(BigInteger, SecureRandom, int) Enhanced
+         * Miller-Rabin Probabilistic Primality Test}
+         */
+        public class MROutput
+        {
+            internal static MROutput ProbablyPrime()
+            {
+                return new MROutput(false, null);
+            }
+
+            internal static MROutput ProvablyCompositeWithFactor(BigInteger factor)
+            {
+                return new MROutput(true, factor);
+            }
+
+            internal static MROutput ProvablyCompositeNotPrimePower()
+            {
+                return new MROutput(true, null);
+            }
+
+            private readonly bool mProvablyComposite;
+            private readonly BigInteger mFactor;
+
+            private MROutput(bool provablyComposite, BigInteger factor)
+            {
+                this.mProvablyComposite = provablyComposite;
+                this.mFactor = factor;
+            }
+
+            public BigInteger Factor
+            {
+                get { return mFactor; }
+            }
+
+            public bool IsProvablyComposite
+            {
+                get { return mProvablyComposite; }
+            }
+
+            public bool IsNotPrimePower
+            {
+                get { return mProvablyComposite && mFactor == null; }
+            }
+        }
+
+        /**
+         * Used to return the output from the {@linkplain Primes#generateSTRandomPrime(Digest, int, byte[]) Shawe-Taylor Random_Prime Routine} 
          */
         public class STOutput
         {
@@ -51,11 +102,11 @@ namespace Org.BouncyCastle.Math
          * @param hash
          *            the {@link Digest} instance to use (as "Hash()"). Cannot be null.
          * @param length
-         *            the length (in bits) of the prime to be generated. Must be >= 2.
+         *            the length (in bits) of the prime to be generated. Must be at least 2.
          * @param inputSeed
          *            the seed to be used for the generation of the requested prime. Cannot be null or
          *            empty.
-         * @returns an {@link STOutput} instance containing the requested prime.
+         * @return an {@link STOutput} instance containing the requested prime.
          */
         public static STOutput GenerateSTRandomPrime(IDigest hash, int length, byte[] inputSeed)
         {
@@ -71,6 +122,269 @@ namespace Org.BouncyCastle.Math
             return ImplSTRandomPrime(hash, length, Arrays.Clone(inputSeed));
         }
 
+        /**
+         * FIPS 186-4 C.3.2 Enhanced Miller-Rabin Probabilistic Primality Test
+         * 
+         * Run several iterations of the Miller-Rabin algorithm with randomly-chosen bases. This is an
+         * alternative to {@link #isMRProbablePrime(BigInteger, SecureRandom, int)} that provides more
+         * information about a composite candidate, which may be useful when generating or validating
+         * RSA moduli.
+         * 
+         * @param candidate
+         *            the {@link BigInteger} instance to test for primality.
+         * @param random
+         *            the source of randomness to use to choose bases.
+         * @param iterations
+         *            the number of randomly-chosen bases to perform the test for.
+         * @return an {@link MROutput} instance that can be further queried for details.
+         */
+        public static MROutput EnhancedMRProbablePrimeTest(BigInteger candidate, SecureRandom random, int iterations)
+        {
+            CheckCandidate(candidate, "candidate");
+
+            if (random == null)
+                throw new ArgumentNullException("random");
+            if (iterations < 1)
+                throw new ArgumentException("must be > 0", "iterations");
+
+            if (candidate.BitLength == 2)
+                return MROutput.ProbablyPrime();
+
+            if (!candidate.TestBit(0))
+                return MROutput.ProvablyCompositeWithFactor(Two);
+
+            BigInteger w = candidate;
+            BigInteger wSubOne = candidate.Subtract(One);
+            BigInteger wSubTwo = candidate.Subtract(Two);
+
+            int a = wSubOne.GetLowestSetBit();
+            BigInteger m = wSubOne.ShiftRight(a);
+
+            for (int i = 0; i < iterations; ++i)
+            {
+                BigInteger b = BigIntegers.CreateRandomInRange(Two, wSubTwo, random);
+                BigInteger g = b.Gcd(w);
+
+                if (g.CompareTo(One) > 0)
+                    return MROutput.ProvablyCompositeWithFactor(g);
+
+                BigInteger z = b.ModPow(m, w);
+
+                if (z.Equals(One) || z.Equals(wSubOne))
+                    continue;
+
+                bool primeToBase = false;
+
+                BigInteger x = z;
+                for (int j = 1; j < a; ++j)
+                {
+                    z = z.ModPow(Two, w);
+
+                    if (z.Equals(wSubOne))
+                    {
+                        primeToBase = true;
+                        break;
+                    }
+
+                    if (z.Equals(One))
+                        break;
+
+                    x = z;
+                }
+
+                if (!primeToBase)
+                {
+                    if (!z.Equals(One))
+                    {
+                        x = z;
+                        z = z.ModPow(Two, w);
+
+                        if (!z.Equals(One))
+                        {
+                            x = z;
+                        }
+                    }
+
+                    g = x.Subtract(One).Gcd(w);
+
+                    if (g.CompareTo(One) > 0)
+                        return MROutput.ProvablyCompositeWithFactor(g);
+
+                    return MROutput.ProvablyCompositeNotPrimePower();
+                }
+            }
+
+            return MROutput.ProbablyPrime();
+        }
+
+        /**
+         * A fast check for small divisors, up to some implementation-specific limit.
+         * 
+         * @param candidate
+         *            the {@link BigInteger} instance to test for division by small factors.
+         * 
+         * @return <code>true</code> if the candidate is found to have any small factors,
+         *         <code>false</code> otherwise.
+         */
+        public static bool HasAnySmallFactors(BigInteger candidate)
+        {
+            CheckCandidate(candidate, "candidate");
+
+            return ImplHasAnySmallFactors(candidate);
+        }
+
+        /**
+         * FIPS 186-4 C.3.1 Miller-Rabin Probabilistic Primality Test
+         * 
+         * Run several iterations of the Miller-Rabin algorithm with randomly-chosen bases.
+         * 
+         * @param candidate
+         *            the {@link BigInteger} instance to test for primality.
+         * @param random
+         *            the source of randomness to use to choose bases.
+         * @param iterations
+         *            the number of randomly-chosen bases to perform the test for.
+         * @return <code>false</code> if any witness to compositeness is found amongst the chosen bases
+         *         (so <code>candidate</code> is definitely NOT prime), or else <code>true</code>
+         *         (indicating primality with some probability dependent on the number of iterations
+         *         that were performed).
+         */
+        public static bool IsMRProbablePrime(BigInteger candidate, SecureRandom random, int iterations)
+        {
+            CheckCandidate(candidate, "candidate");
+
+            if (random == null)
+                throw new ArgumentException("cannot be null", "random");
+            if (iterations < 1)
+                throw new ArgumentException("must be > 0", "iterations");
+
+            if (candidate.BitLength == 2)
+                return true;
+            if (!candidate.TestBit(0))
+                return false;
+
+            BigInteger w = candidate;
+            BigInteger wSubOne = candidate.Subtract(One);
+            BigInteger wSubTwo = candidate.Subtract(Two);
+
+            int a = wSubOne.GetLowestSetBit();
+            BigInteger m = wSubOne.ShiftRight(a);
+
+            for (int i = 0; i < iterations; ++i)
+            {
+                BigInteger b = BigIntegers.CreateRandomInRange(Two, wSubTwo, random);
+
+                if (!ImplMRProbablePrimeToBase(w, wSubOne, m, a, b))
+                    return false;
+            }
+
+            return true;
+        }
+
+        /**
+         * FIPS 186-4 C.3.1 Miller-Rabin Probabilistic Primality Test (to a fixed base).
+         * 
+         * Run a single iteration of the Miller-Rabin algorithm against the specified base.
+         * 
+         * @param candidate
+         *            the {@link BigInteger} instance to test for primality.
+         * @param baseValue
+         *            the base value to use for this iteration.
+         * @return <code>false</code> if the specified base is a witness to compositeness (so
+         *         <code>candidate</code> is definitely NOT prime), or else <code>true</code>.
+         */
+        public static bool IsMRProbablePrimeToBase(BigInteger candidate, BigInteger baseValue)
+        {
+            CheckCandidate(candidate, "candidate");
+            CheckCandidate(baseValue, "baseValue");
+
+            if (baseValue.CompareTo(candidate.Subtract(One)) >= 0)
+                throw new ArgumentException("must be < ('candidate' - 1)", "baseValue");
+
+            if (candidate.BitLength == 2)
+                return true;
+
+            BigInteger w = candidate;
+            BigInteger wSubOne = candidate.Subtract(One);
+
+            int a = wSubOne.GetLowestSetBit();
+            BigInteger m = wSubOne.ShiftRight(a);
+
+            return ImplMRProbablePrimeToBase(w, wSubOne, m, a, baseValue);
+        }
+
+        private static void CheckCandidate(BigInteger n, string name)
+        {
+            if (n == null || n.SignValue < 1 || n.BitLength < 2)
+                throw new ArgumentException("must be non-null and >= 2", name);
+        }
+
+        private static bool ImplHasAnySmallFactors(BigInteger x)
+        {
+            /*
+             * Bundle trial divisors into ~32-bit moduli then use fast tests on the ~32-bit remainders.
+             */
+            int m = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23;
+            int r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+            if ((r & 1) != 0 && (r % 3) != 0 && (r % 5) != 0 && (r % 7) != 0 && (r % 11) != 0
+                && (r % 13) != 0 && (r % 17) != 0 && (r % 19) != 0 && (r % 23) != 0)
+            {
+                m = 29 * 31 * 37 * 41 * 43;
+                r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+                if ((r % 29) != 0 && (r % 31) != 0 && (r % 37) != 0 && (r % 41) != 0 && (r % 43) != 0)
+                {
+                    m = 47 * 53 * 59 * 61 * 67;
+                    r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+                    if ((r % 47) != 0 && (r % 53) != 0 && (r % 59) != 0 && (r % 61) != 0 && (r % 67) != 0)
+                    {
+                        m = 71 * 73 * 79 * 83;
+                        r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+                        if ((r % 71) != 0 && (r % 73) != 0 && (r % 79) != 0 && (r % 83) != 0)
+                        {
+                            m = 89 * 97 * 101 * 103;
+                            r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+                            if ((r % 89) != 0 && (r % 97) != 0 && (r % 101) != 0 && (r % 103) != 0)
+                            {
+                                m = 107 * 109 * 113 * 127;
+                                r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+                                if ((r % 107) != 0 && (r % 109) != 0 && (r % 113) != 0 && (r % 127) != 0)
+                                {
+                                    return false;
+                                }
+                            }
+                        }
+                    }
+                }
+            }
+            return true;
+        }
+
+        private static bool ImplMRProbablePrimeToBase(BigInteger w, BigInteger wSubOne, BigInteger m, int a, BigInteger b)
+        {
+            BigInteger z = b.ModPow(m, w);
+
+            if (z.Equals(One) || z.Equals(wSubOne))
+                return true;
+
+            bool result = false;
+
+            for (int j = 1; j < a; ++j)
+            {
+                z = z.ModPow(Two, w);
+
+                if (z.Equals(wSubOne))
+                {
+                    result = true;
+                    break;
+                }
+
+                if (z.Equals(One))
+                    return false;
+            }
+
+            return result;
+        }
+
         private static STOutput ImplSTRandomPrime(IDigest d, int length, byte[] primeSeed)
         {
             int dLen = d.GetDigestSize();
@@ -131,7 +445,7 @@ namespace Org.BouncyCastle.Math
 
                 /*
                  * TODO Since the candidate primes are generated by constant steps ('c0x2'),
-                 * sieving could be used here in place of the 'mightBePrime' approach.
+                 * sieving could be used here in place of the 'HasAnySmallFactors' approach.
                  */
                 for (;;)
                 {
@@ -149,7 +463,7 @@ namespace Org.BouncyCastle.Math
                      * 
                      * NOTE: 'primeSeed' is still incremented as if we performed the full check!
                      */
-                    if (MightBePrime(c))
+                    if (!ImplHasAnySmallFactors(c))
                     {
                         BigInteger a = HashGen(d, primeSeed, iterations + 1);
                         a = a.Mod(c.Subtract(Three)).Add(Two);
@@ -266,45 +580,5 @@ namespace Org.BouncyCastle.Math
                 }
             }
         }
-
-        private static bool MightBePrime(BigInteger x)
-        {
-            /*
-             * Bundle trial divisors into ~32-bit moduli then use fast tests on the ~32-bit remainders.
-             */
-            int m = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23;
-            int r = x.Mod(BigInteger.ValueOf(m)).IntValue;
-            if ((r & 1) != 0 && (r % 3) != 0 && (r % 5) != 0 && (r % 7) != 0 && (r % 11) != 0
-                && (r % 13) != 0 && (r % 17) != 0 && (r % 19) != 0 && (r % 23) != 0)
-            {
-                m = 29 * 31 * 37 * 41 * 43;
-                r = x.Mod(BigInteger.ValueOf(m)).IntValue;
-                if ((r % 29) != 0 && (r % 31) != 0 && (r % 37) != 0 && (r % 41) != 0 && (r % 43) != 0)
-                {
-                    m = 47 * 53 * 59 * 61 * 67;
-                    r = x.Mod(BigInteger.ValueOf(m)).IntValue;
-                    if ((r % 47) != 0 && (r % 53) != 0 && (r % 59) != 0 && (r % 61) != 0 && (r % 67) != 0)
-                    {
-                        m = 71 * 73 * 79 * 83;
-                        r = x.Mod(BigInteger.ValueOf(m)).IntValue;
-                        if ((r % 71) != 0 && (r % 73) != 0 && (r % 79) != 0 && (r % 83) != 0)
-                        {
-                            m = 89 * 97 * 101 * 103;
-                            r = x.Mod(BigInteger.ValueOf(m)).IntValue;
-                            if ((r % 89) != 0 && (r % 97) != 0 && (r % 101) != 0 && (r % 103) != 0)
-                            {
-                                m = 107 * 109 * 113 * 127;
-                                r = x.Mod(BigInteger.ValueOf(m)).IntValue;
-                                if ((r % 107) != 0 && (r % 109) != 0 && (r % 113) != 0 && (r % 127) != 0)
-                                {
-                                    return true;
-                                }
-                            }
-                        }
-                    }
-                }
-            }
-            return false;
-        }
     }
 }