diff options
author | Peter Dettman <peter.dettman@bouncycastle.org> | 2014-04-10 16:44:31 +0400 |
---|---|---|
committer | Peter Dettman <peter.dettman@bouncycastle.org> | 2014-04-10 16:44:31 +0400 |
commit | 83be99efd17ab048494e2756b95e45f23c62cdbc (patch) | |
tree | 0809efc7a485809b96858a9565c42d4f261ccad0 | |
parent | 6703d5e37da115f1d0d1b75ce083da6244ae43f6 (diff) |
Check for low-weight numbers in DH parameter generation and RSA key
generation
-rw-r--r-- | core/src/main/java/org/bouncycastle/crypto/generators/DHParametersHelper.java | 24 | ||||
-rw-r--r-- | core/src/main/java/org/bouncycastle/crypto/generators/RSAKeyPairGenerator.java | 115 |
2 files changed, 83 insertions, 56 deletions
diff --git a/core/src/main/java/org/bouncycastle/crypto/generators/DHParametersHelper.java b/core/src/main/java/org/bouncycastle/crypto/generators/DHParametersHelper.java index 118bc9cc..dc0a5ae1 100644 --- a/core/src/main/java/org/bouncycastle/crypto/generators/DHParametersHelper.java +++ b/core/src/main/java/org/bouncycastle/crypto/generators/DHParametersHelper.java @@ -3,6 +3,7 @@ package org.bouncycastle.crypto.generators; import java.math.BigInteger; import java.security.SecureRandom; +import org.bouncycastle.math.ec.WNafUtil; import org.bouncycastle.util.BigIntegers; class DHParametersHelper @@ -19,6 +20,7 @@ class DHParametersHelper { BigInteger p, q; int qLength = size - 1; + int minWeight = size >>> 2; for (;;) { @@ -27,10 +29,28 @@ class DHParametersHelper // p <- 2q + 1 p = q.shiftLeft(1).add(ONE); - if (p.isProbablePrime(certainty) && (certainty <= 2 || q.isProbablePrime(certainty))) + if (!p.isProbablePrime(certainty)) { - break; + continue; } + + if (certainty > 2 && !q.isProbablePrime(certainty - 2)) + { + continue; + } + + /* + * Require a minimum weight of the NAF representation, since low-weight primes may be + * weak against a version of the number-field-sieve for the discrete-logarithm-problem. + * + * See "The number field sieve for integers of low weight", Oliver Schirokauer. + */ + if (WNafUtil.getNafWeight(p) < minWeight) + { + continue; + } + + break; } return new BigInteger[] { p, q }; diff --git a/core/src/main/java/org/bouncycastle/crypto/generators/RSAKeyPairGenerator.java b/core/src/main/java/org/bouncycastle/crypto/generators/RSAKeyPairGenerator.java index f58069d5..f5945b5f 100644 --- a/core/src/main/java/org/bouncycastle/crypto/generators/RSAKeyPairGenerator.java +++ b/core/src/main/java/org/bouncycastle/crypto/generators/RSAKeyPairGenerator.java @@ -6,6 +6,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.ec.WNafUtil; import java.math.BigInteger; @@ -36,66 +37,27 @@ public class RSAKeyPairGenerator int pbitlength = (strength + 1) / 2; int qbitlength = strength - pbitlength; int mindiffbits = strength / 3; + int minWeight = strength >> 2; e = param.getPublicExponent(); // 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") - // - // generate p, prime and (p-1) relatively prime to e - // - for (;;) - { - p = new BigInteger(pbitlength, 1, param.getRandom()); - - if (p.mod(e).equals(ONE)) - { - continue; - } - - if (!p.isProbablePrime(param.getCertainty())) - { - continue; - } - - if (e.gcd(p.subtract(ONE)).equals(ONE)) - { - break; - } - } + p = chooseRandomPrime(pbitlength, e); // // generate a modulus of the required length // for (;;) { - // generate q, prime and (q-1) relatively prime to e, - // and not equal to p - // - for (;;) + q = chooseRandomPrime(qbitlength, e); + + // p and q should not be too close together (or equal!) + BigInteger diff = q.subtract(p).abs(); + if (diff.bitLength() < mindiffbits) { - q = new BigInteger(qbitlength, 1, param.getRandom()); - - if (q.subtract(p).abs().bitLength() < mindiffbits) - { - continue; - } - - if (q.mod(e).equals(ONE)) - { - continue; - } - - if (!q.isProbablePrime(param.getCertainty())) - { - continue; - } - - if (e.gcd(q.subtract(ONE)).equals(ONE)) - { - break; - } + continue; } // @@ -103,16 +65,29 @@ public class RSAKeyPairGenerator // n = p.multiply(q); - if (n.bitLength() == param.getStrength()) + if (n.bitLength() != strength) { - break; + // + // if we get here our primes aren't big enough, make the largest + // of the two p and try again + // + p = p.max(q); + continue; } - // - // if we get here our primes aren't big enough, make the largest - // of the two p and try again - // - p = p.max(q); + /* + * 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); + continue; + } + + break; } if (p.compareTo(q) < 0) @@ -144,4 +119,36 @@ public class RSAKeyPairGenerator new RSAKeyParameters(false, n, e), new RSAPrivateCrtKeyParameters(n, e, d, p, q, dP, dQ, qInv)); } + + /** + * 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 + */ + protected BigInteger chooseRandomPrime(int bitlength, BigInteger e) + { + for (;;) + { + BigInteger p = new BigInteger(bitlength, 1, param.getRandom()); + + if (p.mod(e).equals(ONE)) + { + continue; + } + + if (!p.isProbablePrime(param.getCertainty())) + { + continue; + } + + if (!e.gcd(p.subtract(ONE)).equals(ONE)) + { + continue; + } + + return p; + } + } } |