diff options
Diffstat (limited to 'bcprov/src/main/java/org/bouncycastle/crypto/generators/RSAKeyPairGenerator.java')
| -rw-r--r-- | bcprov/src/main/java/org/bouncycastle/crypto/generators/RSAKeyPairGenerator.java | 132 |
1 files changed, 94 insertions, 38 deletions
diff --git a/bcprov/src/main/java/org/bouncycastle/crypto/generators/RSAKeyPairGenerator.java b/bcprov/src/main/java/org/bouncycastle/crypto/generators/RSAKeyPairGenerator.java index 7277045e..f23f654b 100644 --- a/bcprov/src/main/java/org/bouncycastle/crypto/generators/RSAKeyPairGenerator.java +++ b/bcprov/src/main/java/org/bouncycastle/crypto/generators/RSAKeyPairGenerator.java @@ -8,6 +8,7 @@ import org.bouncycastle.crypto.KeyGenerationParameters; import org.bouncycastle.crypto.params.RSAKeyGenerationParameters; import org.bouncycastle.crypto.params.RSAKeyParameters; import org.bouncycastle.crypto.params.RSAPrivateCrtKeyParameters; +import org.bouncycastle.math.Primes; import org.bouncycastle.math.ec.WNafUtil; /** @@ -19,10 +20,12 @@ public class RSAKeyPairGenerator private static final BigInteger ONE = BigInteger.valueOf(1); private RSAKeyGenerationParameters param; + private int iterations; public void init(KeyGenerationParameters param) { this.param = (RSAKeyGenerationParameters)param; + this.iterations = getNumberOfIterations(this.param.getStrength(), this.param.getCertainty()); } public AsymmetricCipherKeyPair generateKeyPair() @@ -30,36 +33,46 @@ public class RSAKeyPairGenerator AsymmetricCipherKeyPair result = null; boolean done = false; - while (!done) + // + // p and q values should have a length of half the strength in bits + // + int strength = param.getStrength(); + int pbitlength = (strength + 1) / 2; + int qbitlength = strength - pbitlength; + int mindiffbits = (strength / 2) - 100; + + if (mindiffbits < strength / 3) { - BigInteger p, q, n, d, e, pSub1, qSub1, phi, lcm, dLowerBound; + mindiffbits = strength / 3; + } - // - // p and q values should have a length of half the strength in bits - // - int strength = param.getStrength(); - int pbitlength = (strength + 1) / 2; - int qbitlength = strength - pbitlength; - int mindiffbits = strength / 3; - int minWeight = strength >> 2; + int minWeight = strength >> 2; - e = param.getPublicExponent(); + // d lower bound is 2^(strength / 2) + BigInteger dLowerBound = BigInteger.valueOf(2).pow(strength / 2); + // squared bound (sqrt(2)*2^(nlen/2-1))^2 + BigInteger squaredBound = ONE.shiftLeft(strength - 1); + // 2^(nlen/2 - 100) + BigInteger minDiff = ONE.shiftLeft(mindiffbits); - // TODO Consider generating safe primes for p, q (see DHParametersHelper.generateSafePrimes) - // (then p-1 and q-1 will not consist of only small factors - see "Pollard's algorithm") + while (!done) + { + BigInteger p, q, n, d, e, pSub1, qSub1, gcd, lcm; - p = chooseRandomPrime(pbitlength, e); + e = param.getPublicExponent(); + + p = chooseRandomPrime(pbitlength, e, squaredBound); // // generate a modulus of the required length // - for (;;) + for (; ; ) { - q = chooseRandomPrime(qbitlength, e); + q = chooseRandomPrime(qbitlength, e, squaredBound); // p and q should not be too close together (or equal!) BigInteger diff = q.subtract(p).abs(); - if (diff.bitLength() < mindiffbits) + if (diff.bitLength() < mindiffbits || diff.compareTo(minDiff) <= 0) { continue; } @@ -80,14 +93,14 @@ public class RSAKeyPairGenerator } /* - * Require a minimum weight of the NAF representation, since low-weight composites may + * Require a minimum weight of the NAF representation, since low-weight composites may * be weak against a version of the number-field-sieve for factoring. * * See "The number field sieve for integers of low weight", Oliver Schirokauer. */ if (WNafUtil.getNafWeight(n) < minWeight) { - p = chooseRandomPrime(pbitlength, e); + p = chooseRandomPrime(pbitlength, e, squaredBound); continue; } @@ -96,26 +109,22 @@ public class RSAKeyPairGenerator if (p.compareTo(q) < 0) { - phi = p; + gcd = p; p = q; - q = phi; + q = gcd; } pSub1 = p.subtract(ONE); qSub1 = q.subtract(ONE); - phi = pSub1.multiply(qSub1); - lcm = phi.divide(pSub1.gcd(qSub1)); + gcd = pSub1.gcd(qSub1); + lcm = pSub1.divide(gcd).multiply(qSub1); // // calculate the private exponent // d = e.modInverse(lcm); - // if d is less than or equal to dLowerBound, we need to start over - // also, for backward compatibility, if d is not the same as - // e.modInverse(phi), we need to start over - - if (d.bitLength() <= qbitlength || !d.equals(e.modInverse(phi))) + if (d.compareTo(dLowerBound) <= 0) { continue; } @@ -143,33 +152,80 @@ public class RSAKeyPairGenerator /** * Choose a random prime value for use with RSA - * + * * @param bitlength the bit-length of the returned prime - * @param e the RSA public exponent - * @return a prime p, with (p-1) relatively prime to e + * @param e the RSA public exponent + * @return A prime p, with (p-1) relatively prime to e */ - protected BigInteger chooseRandomPrime(int bitlength, BigInteger e) + protected BigInteger chooseRandomPrime(int bitlength, BigInteger e, BigInteger sqrdBound) { - for (;;) + for (int i = 0; i != 5 * bitlength; i++) { BigInteger p = new BigInteger(bitlength, 1, param.getRandom()); - + if (p.mod(e).equals(ONE)) { continue; } - - if (!p.isProbablePrime(param.getCertainty())) + + if (p.multiply(p).compareTo(sqrdBound) < 0) + { + continue; + } + + if (!isProbablePrime(p)) { continue; } - if (!e.gcd(p.subtract(ONE)).equals(ONE)) + if (!e.gcd(p.subtract(ONE)).equals(ONE)) { continue; } - + return p; } + + throw new IllegalStateException("unable to generate prime number for RSA key"); + } + + protected boolean isProbablePrime(BigInteger x) + { + /* + * Primes class for FIPS 186-4 C.3 primality checking + */ + return !Primes.hasAnySmallFactors(x) && Primes.isMRProbablePrime(x, param.getRandom(), iterations); + } + + private static int getNumberOfIterations(int bits, int certainty) + { + /* + * NOTE: We enforce a minimum 'certainty' of 100 for bits >= 1024 (else 80). Where the + * certainty is higher than the FIPS 186-4 tables (C.2/C.3) cater to, extra iterations + * are added at the "worst case rate" for the excess. + */ + if (bits >= 1536) + { + return certainty <= 100 ? 3 + : certainty <= 128 ? 4 + : 4 + (certainty - 128 + 1) / 2; + } + else if (bits >= 1024) + { + return certainty <= 100 ? 4 + : certainty <= 112 ? 5 + : 5 + (certainty - 112 + 1) / 2; + } + else if (bits >= 512) + { + return certainty <= 80 ? 5 + : certainty <= 100 ? 7 + : 7 + (certainty - 100 + 1) / 2; + } + else + { + return certainty <= 80 ? 40 + : 40 + (certainty - 80 + 1) / 2; + } } } |