diff options
| -rw-r--r-- | crypto/src/math/Primes.cs | 287 |
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; - } } } } |