Check for low-weight numbers in DH parameter generation and RSA key

generation

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