| package org.bouncycastle.math; |
| |
| import java.math.BigInteger; |
| import java.security.SecureRandom; |
| |
| import org.bouncycastle.crypto.Digest; |
| import org.bouncycastle.util.Arrays; |
| import org.bouncycastle.util.BigIntegers; |
| |
| /** |
| * Utility methods for generating primes and testing for primality. |
| */ |
| public abstract class Primes |
| { |
| public static final int SMALL_FACTOR_LIMIT = 211; |
| |
| private static final BigInteger ONE = BigInteger.valueOf(1); |
| private static final BigInteger TWO = BigInteger.valueOf(2); |
| private static final BigInteger THREE = BigInteger.valueOf(3); |
| |
| /** |
| * Used to return the output from the |
| * {@linkplain Primes#enhancedMRProbablePrimeTest(BigInteger, SecureRandom, int) Enhanced |
| * Miller-Rabin Probabilistic Primality Test} |
| */ |
| public static class MROutput |
| { |
| private static MROutput probablyPrime() |
| { |
| return new MROutput(false, null); |
| } |
| |
| private static MROutput provablyCompositeWithFactor(BigInteger factor) |
| { |
| return new MROutput(true, factor); |
| } |
| |
| private static MROutput provablyCompositeNotPrimePower() |
| { |
| return new MROutput(true, null); |
| } |
| |
| private boolean provablyComposite; |
| private BigInteger factor; |
| |
| private MROutput(boolean provablyComposite, BigInteger factor) |
| { |
| this.provablyComposite = provablyComposite; |
| this.factor = factor; |
| } |
| |
| public BigInteger getFactor() |
| { |
| return factor; |
| } |
| |
| public boolean isProvablyComposite() |
| { |
| return provablyComposite; |
| } |
| |
| public boolean isNotPrimePower() |
| { |
| return provablyComposite && factor == null; |
| } |
| } |
| |
| /** |
| * Used to return the output from the |
| * {@linkplain Primes#generateSTRandomPrime(Digest, int, byte[]) Shawe-Taylor Random_Prime |
| * Routine} |
| */ |
| public static class STOutput |
| { |
| private BigInteger prime; |
| private byte[] primeSeed; |
| private int primeGenCounter; |
| |
| private STOutput(BigInteger prime, byte[] primeSeed, int primeGenCounter) |
| { |
| this.prime = prime; |
| this.primeSeed = primeSeed; |
| this.primeGenCounter = primeGenCounter; |
| } |
| |
| public BigInteger getPrime() |
| { |
| return prime; |
| } |
| |
| public byte[] getPrimeSeed() |
| { |
| return primeSeed; |
| } |
| |
| public int getPrimeGenCounter() |
| { |
| return 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. |
| */ |
| public static STOutput generateSTRandomPrime(Digest hash, int length, byte[] inputSeed) |
| { |
| if (hash == null) |
| { |
| throw new IllegalArgumentException("'hash' cannot be null"); |
| } |
| if (length < 2) |
| { |
| throw new IllegalArgumentException("'length' must be >= 2"); |
| } |
| if (inputSeed == null || inputSeed.length == 0) |
| { |
| throw new IllegalArgumentException("'inputSeed' cannot be null or empty"); |
| } |
| |
| 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 IllegalArgumentException("'random' cannot be null"); |
| } |
| if (iterations < 1) |
| { |
| throw new IllegalArgumentException("'iterations' must be > 0"); |
| } |
| |
| 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; |
| } |
| |
| boolean 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 boolean 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 boolean isMRProbablePrime(BigInteger candidate, SecureRandom random, int iterations) |
| { |
| checkCandidate(candidate, "candidate"); |
| |
| if (random == null) |
| { |
| throw new IllegalArgumentException("'random' cannot be null"); |
| } |
| if (iterations < 1) |
| { |
| throw new IllegalArgumentException("'iterations' must be > 0"); |
| } |
| |
| 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 base |
| * 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 boolean isMRProbablePrimeToBase(BigInteger candidate, BigInteger base) |
| { |
| checkCandidate(candidate, "candidate"); |
| checkCandidate(base, "base"); |
| |
| if (base.compareTo(candidate.subtract(ONE)) >= 0) |
| { |
| throw new IllegalArgumentException("'base' must be < ('candidate' - 1)"); |
| } |
| |
| 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, base); |
| } |
| |
| private static void checkCandidate(BigInteger n, String name) |
| { |
| if (n == null || n.signum() < 1 || n.bitLength() < 2) |
| { |
| throw new IllegalArgumentException("'" + name + "' must be non-null and >= 2"); |
| } |
| } |
| |
| private static boolean 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 % 2) == 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) |
| { |
| return true; |
| } |
| |
| 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) |
| { |
| return true; |
| } |
| |
| 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) |
| { |
| return true; |
| } |
| |
| 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) |
| { |
| return true; |
| } |
| |
| 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) |
| { |
| return true; |
| } |
| |
| 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; |
| } |
| |
| m = 131 * 137 * 139 * 149; |
| r = x.mod(BigInteger.valueOf(m)).intValue(); |
| if ((r % 131) == 0 || (r % 137) == 0 || (r % 139) == 0 || (r % 149) == 0) |
| { |
| return true; |
| } |
| |
| m = 151 * 157 * 163 * 167; |
| r = x.mod(BigInteger.valueOf(m)).intValue(); |
| if ((r % 151) == 0 || (r % 157) == 0 || (r % 163) == 0 || (r % 167) == 0) |
| { |
| return true; |
| } |
| |
| m = 173 * 179 * 181 * 191; |
| r = x.mod(BigInteger.valueOf(m)).intValue(); |
| if ((r % 173) == 0 || (r % 179) == 0 || (r % 181) == 0 || (r % 191) == 0) |
| { |
| return true; |
| } |
| |
| m = 193 * 197 * 199 * 211; |
| r = x.mod(BigInteger.valueOf(m)).intValue(); |
| if ((r % 193) == 0 || (r % 197) == 0 || (r % 199) == 0 || (r % 211) == 0) |
| { |
| return true; |
| } |
| |
| /* |
| * NOTE: Unit tests depend on SMALL_FACTOR_LIMIT matching the |
| * highest small factor tested here. |
| */ |
| return false; |
| } |
| |
| private static boolean 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; |
| } |
| |
| boolean 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(Digest d, int length, byte[] primeSeed) |
| { |
| int dLen = d.getDigestSize(); |
| |
| if (length < 33) |
| { |
| int primeGenCounter = 0; |
| |
| byte[] c0 = new byte[dLen]; |
| byte[] c1 = new byte[dLen]; |
| |
| for (;;) |
| { |
| hash(d, primeSeed, c0, 0); |
| inc(primeSeed, 1); |
| |
| hash(d, primeSeed, c1, 0); |
| inc(primeSeed, 1); |
| |
| int c = extract32(c0) ^ extract32(c1); |
| c &= (-1 >>> (32 - length)); |
| c |= (1 << (length - 1)) | 1; |
| |
| ++primeGenCounter; |
| |
| long c64 = c & 0xFFFFFFFFL; |
| if (isPrime32(c64)) |
| { |
| return new STOutput(BigInteger.valueOf(c64), primeSeed, primeGenCounter); |
| } |
| |
| if (primeGenCounter > (4 * length)) |
| { |
| throw new IllegalStateException("Too many iterations in Shawe-Taylor Random_Prime Routine"); |
| } |
| } |
| } |
| |
| STOutput rec = implSTRandomPrime(d, (length + 3) / 2, primeSeed); |
| |
| BigInteger c0 = rec.getPrime(); |
| primeSeed = rec.getPrimeSeed(); |
| int primeGenCounter = rec.getPrimeGenCounter(); |
| |
| int outlen = 8 * dLen; |
| int iterations = (length - 1) / outlen; |
| |
| int oldCounter = primeGenCounter; |
| |
| BigInteger x = hashGen(d, primeSeed, iterations + 1); |
| x = x.mod(ONE.shiftLeft(length - 1)).setBit(length - 1); |
| |
| BigInteger c0x2 = c0.shiftLeft(1); |
| BigInteger tx2 = x.subtract(ONE).divide(c0x2).add(ONE).shiftLeft(1); |
| int dt = 0; |
| |
| BigInteger c = tx2.multiply(c0).add(ONE); |
| |
| /* |
| * TODO Since the candidate primes are generated by constant steps ('c0x2'), sieving could |
| * be used here in place of the 'hasAnySmallFactors' approach. |
| */ |
| for (;;) |
| { |
| if (c.bitLength() > length) |
| { |
| tx2 = ONE.shiftLeft(length - 1).subtract(ONE).divide(c0x2).add(ONE).shiftLeft(1); |
| c = tx2.multiply(c0).add(ONE); |
| } |
| |
| ++primeGenCounter; |
| |
| /* |
| * This is an optimization of the original algorithm, using trial division to screen out |
| * many non-primes quickly. |
| * |
| * NOTE: 'primeSeed' is still incremented as if we performed the full check! |
| */ |
| if (!implHasAnySmallFactors(c)) |
| { |
| BigInteger a = hashGen(d, primeSeed, iterations + 1); |
| a = a.mod(c.subtract(THREE)).add(TWO); |
| |
| tx2 = tx2.add(BigInteger.valueOf(dt)); |
| dt = 0; |
| |
| 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 IllegalStateException("Too many iterations in Shawe-Taylor Random_Prime Routine"); |
| } |
| |
| dt += 2; |
| c = c.add(c0x2); |
| } |
| } |
| |
| private static int extract32(byte[] bs) |
| { |
| int result = 0; |
| |
| int count = Math.min(4, bs.length); |
| for (int i = 0; i < count; ++i) |
| { |
| int b = bs[bs.length - (i + 1)] & 0xFF; |
| result |= (b << (8 * i)); |
| } |
| |
| return result; |
| } |
| |
| private static void hash(Digest d, byte[] input, byte[] output, int outPos) |
| { |
| d.update(input, 0, input.length); |
| d.doFinal(output, outPos); |
| } |
| |
| private static BigInteger hashGen(Digest d, byte[] seed, int count) |
| { |
| int dLen = d.getDigestSize(); |
| int pos = count * dLen; |
| byte[] buf = new byte[pos]; |
| for (int i = 0; i < count; ++i) |
| { |
| pos -= dLen; |
| hash(d, seed, buf, pos); |
| inc(seed, 1); |
| } |
| return new BigInteger(1, buf); |
| } |
| |
| private static void inc(byte[] seed, int c) |
| { |
| int pos = seed.length; |
| while (c > 0 && --pos >= 0) |
| { |
| c += (seed[pos] & 0xFF); |
| seed[pos] = (byte)c; |
| c >>>= 8; |
| } |
| } |
| |
| private static boolean isPrime32(long x) |
| { |
| if (x >>> 32 != 0L) |
| { |
| throw new IllegalArgumentException("Size limit exceeded"); |
| } |
| |
| /* |
| * Use wheel factorization with 2, 3, 5 to select trial divisors. |
| */ |
| |
| if (x <= 5L) |
| { |
| return x == 2L || x == 3L || x == 5L; |
| } |
| |
| if ((x & 1L) == 0L || (x % 3L) == 0L || (x % 5L) == 0L) |
| { |
| return false; |
| } |
| |
| long[] ds = new long[]{ 1L, 7L, 11L, 13L, 17L, 19L, 23L, 29L }; |
| long base = 0L; |
| for (int pos = 1;; pos = 0) |
| { |
| /* |
| * Trial division by wheel-selected divisors |
| */ |
| while (pos < ds.length) |
| { |
| long d = base + ds[pos]; |
| if (x % d == 0L) |
| { |
| return x < 30L; |
| } |
| ++pos; |
| } |
| |
| base += 30L; |
| |
| if (base * base >= x) |
| { |
| return true; |
| } |
| } |
| } |
| } |