Primes improvements

1 files changed, 101 insertions, 186 deletions

diff --git a/crypto/src/math/Primes.cs b/crypto/src/math/Primes.cs
index fb279f103..79bce32cd 100644
--- a/crypto/src/math/Primes.cs
+++ b/crypto/src/math/Primes.cs
@@ -1,15 +1,14 @@
 using System;
 
 using Org.BouncyCastle.Crypto;
+using Org.BouncyCastle.Crypto.Utilities;
 using Org.BouncyCastle.Security;
 using Org.BouncyCastle.Utilities;
 
 namespace Org.BouncyCastle.Math
 {
-    /**
-     * Utility methods for generating primes and testing for primality.
-     */
-    public abstract class Primes
+    /// <summary>Utility methods for generating primes and testing for primality.</summary>
+    public static class Primes
     {
         public static readonly int SmallFactorLimit = 211;
 
@@ -17,12 +16,10 @@ namespace Org.BouncyCastle.Math
         private static readonly BigInteger Two = BigInteger.Two;
         private static readonly BigInteger Three = BigInteger.Three;
 
-        /**
-         * Used to return the output from the
-         * {@linkplain Primes#enhancedMRProbablePrimeTest(BigInteger, SecureRandom, int) Enhanced
-         * Miller-Rabin Probabilistic Primality Test}
-         */
-        public class MROutput
+        /// <summary>Used to return the output from the
+        /// <see cref="EnhancedMRProbablePrimeTest(BigInteger, SecureRandom, int)">
+        /// Enhanced Miller-Rabin Probabilistic Primality Test</see></summary>
+        public sealed class MROutput
         {
             internal static MROutput ProbablyPrime()
             {
@@ -39,115 +36,83 @@ namespace Org.BouncyCastle.Math
                 return new MROutput(true, null);
             }
 
-            private readonly bool mProvablyComposite;
-            private readonly BigInteger mFactor;
+            private readonly bool m_provablyComposite;
+            private readonly BigInteger m_factor;
 
             private MROutput(bool provablyComposite, BigInteger factor)
             {
-                this.mProvablyComposite = provablyComposite;
-                this.mFactor = factor;
+                m_provablyComposite = provablyComposite;
+                m_factor = factor;
             }
 
-            public BigInteger Factor
-            {
-                get { return mFactor; }
-            }
+            public BigInteger Factor => m_factor;
 
-            public bool IsProvablyComposite
-            {
-                get { return mProvablyComposite; }
-            }
+            public bool IsProvablyComposite => m_provablyComposite;
 
-            public bool IsNotPrimePower
-            {
-                get { return mProvablyComposite && mFactor == null; }
-            }
+            public bool IsNotPrimePower => m_provablyComposite && m_factor == null;
         }
 
-        /**
-         * Used to return the output from the {@linkplain Primes#generateSTRandomPrime(Digest, int, byte[]) Shawe-Taylor Random_Prime Routine} 
-         */
-        public class STOutput
+        /// <summary>Used to return the output from the <see cref="GenerateSTRandomPrime(IDigest, int, byte[])">
+        /// Shawe-Taylor Random_Prime Routine</see></summary>
+        public sealed class STOutput
         {
-            private readonly BigInteger mPrime;
-            private readonly byte[] mPrimeSeed;
-            private readonly int mPrimeGenCounter;
+            private readonly BigInteger m_prime;
+            private readonly byte[] m_primeSeed;
+            private readonly int m_primeGenCounter;
 
             internal STOutput(BigInteger prime, byte[] primeSeed, int primeGenCounter)
             {
-                this.mPrime = prime;
-                this.mPrimeSeed = primeSeed;
-                this.mPrimeGenCounter = primeGenCounter;
+                m_prime = prime;
+                m_primeSeed = primeSeed;
+                m_primeGenCounter = primeGenCounter;
             }
 
-            public BigInteger Prime
-            {
-                get { return mPrime; }
-            }
+            public BigInteger Prime => m_prime;
 
-            public byte[] PrimeSeed
-            {
-                get { return mPrimeSeed; }
-            }
+            public byte[] PrimeSeed => m_primeSeed;
 
-            public int PrimeGenCounter
-            {
-                get { return mPrimeGenCounter; }
-            }
+            public int PrimeGenCounter => m_primeGenCounter;
         }
 
-        /**
-         * FIPS 186-4 C.6 Shawe-Taylor Random_Prime Routine
-         * 
-         * Construct a provable prime number using a hash function.
-         * 
-         * @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 at least 2.
-         * @param inputSeed
-         *            the seed to be used for the generation of the requested prime. Cannot be null or
-         *            empty.
-         * @return an {@link STOutput} instance containing the requested prime.
-         */
+        /// <summary>FIPS 186-4 C.6 Shawe-Taylor Random_Prime Routine.</summary>
+        /// <remarks>Construct a provable prime number using a hash function.</remarks>
+        /// <param name="hash">The <see cref="IDigest"/> instance to use (as "Hash()"). Cannot be null.</param>
+        /// <param name="length">The length (in bits) of the prime to be generated. Must be at least 2.</param>
+        /// <param name="inputSeed">The seed to be used for the generation of the requested prime. Cannot be null or
+        /// empty.</param>
+        /// <returns>An <see cref="STOutput"/> instance containing the requested prime.</returns>
         public static STOutput GenerateSTRandomPrime(IDigest hash, int length, byte[] inputSeed)
         {
             if (hash == null)
-                throw new ArgumentNullException("hash");
+                throw new ArgumentNullException(nameof(hash));
             if (length < 2)
-                throw new ArgumentException("must be >= 2", "length");
+                throw new ArgumentException("must be >= 2", nameof(length));
             if (inputSeed == null)
-                throw new ArgumentNullException("inputSeed");
+                throw new ArgumentNullException(nameof(inputSeed));
             if (inputSeed.Length == 0)
-                throw new ArgumentException("cannot be empty", "inputSeed");
+                throw new ArgumentException("cannot be empty", nameof(inputSeed));
 
             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.
-         */
+        /// <summary>FIPS 186-4 C.3.2 Enhanced Miller-Rabin Probabilistic Primality Test.</summary>
+        /// <remarks>
+        /// Run several iterations of the Miller-Rabin algorithm with randomly-chosen bases. This is an alternative to
+        /// <see cref="IsMRProbablePrime(BigInteger, SecureRandom, int)"/> that provides more information about a
+        /// composite candidate, which may be useful when generating or validating RSA moduli.
+        /// </remarks>
+        /// <param name="candidate">The <see cref="BigInteger"/> instance to test for primality.</param>
+        /// <param name="random">The source of randomness to use to choose bases.</param>
+        /// <param name="iterations">The number of randomly-chosen bases to perform the test for.</param>
+        /// <returns>An <see cref="MROutput"/> instance that can be further queried for details.</returns>
         public static MROutput EnhancedMRProbablePrimeTest(BigInteger candidate, SecureRandom random, int iterations)
         {
-            CheckCandidate(candidate, "candidate");
+            CheckCandidate(candidate, nameof(candidate));
 
             if (random == null)
-                throw new ArgumentNullException("random");
+                throw new ArgumentNullException(nameof(random));
             if (iterations < 1)
-                throw new ArgumentException("must be > 0", "iterations");
+                throw new ArgumentException("must be > 0", nameof(iterations));
 
             if (candidate.BitLength == 2)
                 return MROutput.ProbablyPrime();
@@ -180,7 +145,7 @@ namespace Org.BouncyCastle.Math
                 BigInteger x = z;
                 for (int j = 1; j < a; ++j)
                 {
-                    z = z.ModPow(Two, w);
+                    z = z.Square().Mod(w);
 
                     if (z.Equals(wSubOne))
                     {
@@ -199,7 +164,7 @@ namespace Org.BouncyCastle.Math
                     if (!z.Equals(One))
                     {
                         x = z;
-                        z = z.ModPow(Two, w);
+                        z = z.Square().Mod(w);
 
                         if (!z.Equals(One))
                         {
@@ -219,46 +184,34 @@ namespace Org.BouncyCastle.Math
             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.
-         */
+        /// <summary>A fast check for small divisors, up to some implementation-specific limit.</summary>
+        /// <param name="candidate">The <see cref="BigInteger"/> instance to test for division by small factors.</param>
+        /// <returns><c>true</c> if the candidate is found to have any small factors, <c>false</c> otherwise.</returns>
         public static bool HasAnySmallFactors(BigInteger candidate)
         {
-            CheckCandidate(candidate, "candidate");
+            CheckCandidate(candidate, nameof(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).
-         */
+        /// <summary>FIPS 186-4 C.3.1 Miller-Rabin Probabilistic Primality Test.</summary>
+        /// <remarks>Run several iterations of the Miller-Rabin algorithm with randomly-chosen bases.</remarks>
+        /// <param name="candidate">The <see cref="BigInteger"/> instance to test for primality.</param>
+        /// <param name="random">The source of randomness to use to choose bases.</param>
+        /// <param name="iterations">The number of randomly-chosen bases to perform the test for.</param>
+        /// <returns>
+        /// <c>false</c> if any witness to compositeness is found amongst the chosen bases (so
+        /// <paramref name="candidate"/> is definitely NOT prime), or else <c>true</c> (indicating primality with some
+        /// probability dependent on the number of iterations that were performed).
+        /// </returns>
         public static bool IsMRProbablePrime(BigInteger candidate, SecureRandom random, int iterations)
         {
-            CheckCandidate(candidate, "candidate");
+            CheckCandidate(candidate, nameof(candidate));
 
             if (random == null)
-                throw new ArgumentException("cannot be null", "random");
+                throw new ArgumentException("cannot be null", nameof(random));
             if (iterations < 1)
-                throw new ArgumentException("must be > 0", "iterations");
+                throw new ArgumentException("must be > 0", nameof(iterations));
 
             if (candidate.BitLength == 2)
                 return true;
@@ -283,25 +236,19 @@ namespace Org.BouncyCastle.Math
             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>.
-         */
+        /// <summary>FIPS 186-4 C.3.1 Miller-Rabin Probabilistic Primality Test (to a fixed base).</summary>
+        /// <remarks>Run a single iteration of the Miller-Rabin algorithm against the specified base.</remarks>
+        /// <param name="candidate">The <see cref="BigInteger"/> instance to test for primality.</param>
+        /// <param name="baseValue">The base value to use for this iteration.</param>
+        /// <returns><c>false</c> if <paramref name="baseValue"/> is a witness to compositeness (so
+        /// <paramref name="candidate"/> is definitely NOT prime), or else <c>true</c>.</returns>
         public static bool IsMRProbablePrimeToBase(BigInteger candidate, BigInteger baseValue)
         {
-            CheckCandidate(candidate, "candidate");
-            CheckCandidate(baseValue, "baseValue");
+            CheckCandidate(candidate, nameof(candidate));
+            CheckCandidate(baseValue, nameof(baseValue));
 
             if (baseValue.CompareTo(candidate.Subtract(One)) >= 0)
-                throw new ArgumentException("must be < ('candidate' - 1)", "baseValue");
+                throw new ArgumentException("must be < ('candidate' - 1)", nameof(baseValue));
 
             if (candidate.BitLength == 2)
                 return true;
@@ -411,59 +358,52 @@ namespace Org.BouncyCastle.Math
             if (z.Equals(One) || z.Equals(wSubOne))
                 return true;
 
-            bool result = false;
-
             for (int j = 1; j < a; ++j)
             {
-                z = z.ModPow(Two, w);
+                z = z.Square().Mod(w);
 
                 if (z.Equals(wSubOne))
-                {
-                    result = true;
-                    break;
-                }
+                    return true;
 
                 if (z.Equals(One))
                     return false;
             }
 
-            return result;
+            return false;
         }
 
         private static STOutput ImplSTRandomPrime(IDigest d, int length, byte[] primeSeed)
         {
             int dLen = d.GetDigestSize();
+            int cLen = System.Math.Max(4, dLen);
 
             if (length < 33)
             {
                 int primeGenCounter = 0;
 
-                byte[] c0 = new byte[dLen];
-                byte[] c1 = new byte[dLen];
+                byte[] c0 = new byte[cLen];
+                byte[] c1 = new byte[cLen];
 
                 for (;;)
                 {
-                    Hash(d, primeSeed, c0, 0);
+                    Hash(d, primeSeed, c0, cLen - dLen);
                     Inc(primeSeed, 1);
 
-                    Hash(d, primeSeed, c1, 0);
+                    Hash(d, primeSeed, c1, cLen - dLen);
                     Inc(primeSeed, 1);
 
-                    uint c = Extract32(c0) ^ Extract32(c1);
-                    c &= (uint.MaxValue >> (32 - length));
+                    uint c = Pack.BE_To_UInt32(c0, cLen - 4)
+                           ^ Pack.BE_To_UInt32(c1, cLen - 4);
+                    c &= uint.MaxValue >> (32 - length);
                     c |= (1U << (length - 1)) | 1U;
 
                     ++primeGenCounter;
 
                     if (IsPrime32(c))
-                    {
-                        return new STOutput(BigInteger.ValueOf((long)c), primeSeed, primeGenCounter);
-                    }
+                        return new STOutput(BigInteger.ValueOf(c), primeSeed, primeGenCounter);
 
                     if (primeGenCounter > (4 * length))
-                    {
                         throw new InvalidOperationException("Too many iterations in Shawe-Taylor Random_Prime Routine");
-                    }
                 }
             }
 
@@ -508,7 +448,11 @@ namespace Org.BouncyCastle.Math
                      * 
                      * NOTE: 'primeSeed' is still incremented as if we performed the full check!
                      */
-                    if (!ImplHasAnySmallFactors(c))
+                    if (ImplHasAnySmallFactors(c))
+                    {
+                        Inc(primeSeed, iterations + 1);
+                    }
+                    else
                     {
                         BigInteger a = HashGen(d, primeSeed, iterations + 1);
                         a = a.Mod(c.Subtract(Three)).Add(Two);
@@ -519,19 +463,11 @@ namespace Org.BouncyCastle.Math
                         BigInteger z = a.ModPow(tx2, c);
 
                         if (c.Gcd(z.Subtract(One)).Equals(One) && z.ModPow(c0, c).Equals(One))
-                        {
                             return new STOutput(c, primeSeed, primeGenCounter);
-                        }
-                    }
-                    else
-                    {
-                        Inc(primeSeed, iterations + 1);
                     }
 
                     if (primeGenCounter >= ((4 * length) + oldCounter))
-                    {
                         throw new InvalidOperationException("Too many iterations in Shawe-Taylor Random_Prime Routine");
-                    }
 
                     dt += 2;
                     c = c.Add(c0x2);
@@ -539,20 +475,6 @@ namespace Org.BouncyCastle.Math
             }
         }
 
-        private static uint Extract32(byte[] bs)
-        {
-            uint result = 0;
-
-            int count = System.Math.Min(4, bs.Length);
-            for (int i = 0; i < count; ++i)
-            {
-                uint b = bs[bs.Length - (i + 1)];
-                result |= (b << (8 * i));
-            }
-
-            return result;
-        }
-
         private static void Hash(IDigest d, byte[] input, byte[] output, int outPos)
         {
             d.BlockUpdate(input, 0, input.Length);
@@ -590,19 +512,15 @@ namespace Org.BouncyCastle.Math
              * Use wheel factorization with 2, 3, 5 to select trial divisors.
              */
 
-            if (x <= 5)
-            {
-                return x == 2 || x == 3 || x == 5;
-            }
+            if (x < 32)
+                return ((1 << (int)x) & 0b0010_0000_1000_1010_0010_1000_1010_1100) != 0;
 
-            if ((x & 1) == 0 || (x % 3) == 0 || (x % 5) == 0)
-            {
+            if (((1 << (int)(x % 30U)) & 0b1010_0000_1000_1010_0010_1000_1000_0010U) == 0)
                 return false;
-            }
 
             uint[] ds = new uint[]{ 1, 7, 11, 13, 17, 19, 23, 29 };
             uint b = 0;
-            for (int pos = 1; ; pos = 0)
+            for (int pos = 1;; pos = 0)
             {
                 /*
                  * Trial division by wheel-selected divisors
@@ -611,18 +529,15 @@ namespace Org.BouncyCastle.Math
                 {
                     uint d = b + ds[pos];
                     if (x % d == 0)
-                    {
-                        return x < 30;
-                    }
+                        return false;
+
                     ++pos;
                 }
 
                 b += 30;
 
                 if ((b >> 16 != 0) || (b * b >= x))
-                {
                     return true;
-                }
             }
         }
     }