diff options
Diffstat (limited to 'repackaged_platform/bcprov/src/main/java/com/android/internal/org/bouncycastle/math/Primes.java')
| -rw-r--r-- | repackaged_platform/bcprov/src/main/java/com/android/internal/org/bouncycastle/math/Primes.java | 678 |
1 files changed, 678 insertions, 0 deletions
diff --git a/repackaged_platform/bcprov/src/main/java/com/android/internal/org/bouncycastle/math/Primes.java b/repackaged_platform/bcprov/src/main/java/com/android/internal/org/bouncycastle/math/Primes.java new file mode 100644 index 00000000..dd83736e --- /dev/null +++ b/repackaged_platform/bcprov/src/main/java/com/android/internal/org/bouncycastle/math/Primes.java @@ -0,0 +1,678 @@ +/* GENERATED SOURCE. DO NOT MODIFY. */ +package com.android.internal.org.bouncycastle.math; + +import java.math.BigInteger; +import java.security.SecureRandom; + +import com.android.internal.org.bouncycastle.crypto.Digest; +import com.android.internal.org.bouncycastle.util.Arrays; +import com.android.internal.org.bouncycastle.util.BigIntegers; + +/** + * Utility methods for generating primes and testing for primality. + * @hide This class is not part of the Android public SDK API + */ +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} + * @hide This class is not part of the Android public SDK API + */ + 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} + * @hide This class is not part of the Android public SDK API + */ + 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; + } + } + } +}
\ No newline at end of file |