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;
- }
}
}
}
|
