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

3 files changed, 207 insertions, 167 deletions

diff --git a/crypto/src/crypto/generators/DHParametersHelper.cs b/crypto/src/crypto/generators/DHParametersHelper.cs
index a61b0817e..bf2de2add 100644
--- a/crypto/src/crypto/generators/DHParametersHelper.cs
+++ b/crypto/src/crypto/generators/DHParametersHelper.cs
@@ -1,18 +1,19 @@
 using System;
 
 using Org.BouncyCastle.Math;
+using Org.BouncyCastle.Math.EC.Multiplier;
 using Org.BouncyCastle.Security;
 using Org.BouncyCastle.Utilities;
 
 namespace Org.BouncyCastle.Crypto.Generators
 {
-	internal class DHParametersHelper
-	{
+    internal class DHParametersHelper
+    {
         private static readonly BigInteger Six = BigInteger.ValueOf(6);
 
         private static readonly int[][] primeLists = BigInteger.primeLists;
         private static readonly int[] primeProducts = BigInteger.primeProducts;
-		private static readonly BigInteger[] BigPrimeProducts = ConstructBigPrimeProducts(primeProducts);
+        private static readonly BigInteger[] BigPrimeProducts = ConstructBigPrimeProducts(primeProducts);
 
         private static BigInteger[] ConstructBigPrimeProducts(int[] primeProducts)
         {
@@ -30,90 +31,107 @@ namespace Org.BouncyCastle.Crypto.Generators
          * (see: Handbook of Applied Cryptography 4.86)
          */
         internal static BigInteger[] GenerateSafePrimes(int size, int certainty, SecureRandom random)
-		{
-			BigInteger p, q;
-			int qLength = size - 1;
-
-			if (size <= 32)
-			{
-				for (;;)
-				{
-					q = new BigInteger(qLength, 2, random);
-
-					p = q.ShiftLeft(1).Add(BigInteger.One);
-
-					if (p.IsProbablePrime(certainty)
-						&& (certainty <= 2 || q.IsProbablePrime(certainty)))
-							break;
-				}
-			}
-			else
-			{
-				// Note: Modified from Java version for speed
-				for (;;)
-				{
-					q = new BigInteger(qLength, 0, random);
-
-				retry:
-					for (int i = 0; i < primeLists.Length; ++i)
-					{
-						int test = q.Remainder(BigPrimeProducts[i]).IntValue;
+        {
+            BigInteger p, q;
+            int qLength = size - 1;
+            int minWeight = size >> 2;
+
+            if (size <= 32)
+            {
+                for (;;)
+                {
+                    q = new BigInteger(qLength, 2, random);
+
+                    p = q.ShiftLeft(1).Add(BigInteger.One);
+
+                    if (!p.IsProbablePrime(certainty))
+                        continue;
+
+                    if (certainty > 2 && !q.IsProbablePrime(certainty - 2))
+                        continue;
+
+                    break;
+                }
+            }
+            else
+            {
+                // Note: Modified from Java version for speed
+                for (;;)
+                {
+                    q = new BigInteger(qLength, 0, random);
+
+                retry:
+                    for (int i = 0; i < primeLists.Length; ++i)
+                    {
+                        int test = q.Remainder(BigPrimeProducts[i]).IntValue;
 
                         if (i == 0)
-						{
-							int rem3 = test % 3;
-							if (rem3 != 2)
-							{
-								int diff = 2 * rem3 + 2;
-								q = q.Add(BigInteger.ValueOf(diff));
-								test = (test + diff) % primeProducts[i];
-							}
-						}
-
-						int[] primeList = primeLists[i];
-						for (int j = 0; j < primeList.Length; ++j)
-						{
-							int prime = primeList[j];
-							int qRem = test % prime;
-							if (qRem == 0 || qRem == (prime >> 1))
-							{
-								q = q.Add(Six);
-								goto retry;
-							}
-						}
-					}
-
-
-					if (q.BitLength != qLength)
-						continue;
-
-					if (!q.RabinMillerTest(2, random))
-						continue;
-
-					p = q.ShiftLeft(1).Add(BigInteger.One);
-
-					if (p.RabinMillerTest(certainty, random)
-						&& (certainty <= 2 || q.RabinMillerTest(certainty - 2, random)))
-						break;
-				}
-			}
-
-			return new BigInteger[] { p, q };
-		}
-
-		/*
-		 * Select a high order element of the multiplicative group Zp*
-		 * 
-		 * p and q must be s.t. p = 2*q + 1, where p and q are prime (see generateSafePrimes)
-		 */
-		internal static BigInteger SelectGenerator(BigInteger p, BigInteger q, SecureRandom random)
-		{
-			BigInteger pMinusTwo = p.Subtract(BigInteger.Two);
-			BigInteger g;
-
-			/*
-			 * (see: Handbook of Applied Cryptography 4.80)
-			 */
+                        {
+                            int rem3 = test % 3;
+                            if (rem3 != 2)
+                            {
+                                int diff = 2 * rem3 + 2;
+                                q = q.Add(BigInteger.ValueOf(diff));
+                                test = (test + diff) % primeProducts[i];
+                            }
+                        }
+
+                        int[] primeList = primeLists[i];
+                        for (int j = 0; j < primeList.Length; ++j)
+                        {
+                            int prime = primeList[j];
+                            int qRem = test % prime;
+                            if (qRem == 0 || qRem == (prime >> 1))
+                            {
+                                q = q.Add(Six);
+                                goto retry;
+                            }
+                        }
+                    }
+
+                    if (q.BitLength != qLength)
+                        continue;
+
+                    if (!q.RabinMillerTest(2, random))
+                        continue;
+
+                    p = q.ShiftLeft(1).Add(BigInteger.One);
+
+                    if (!p.RabinMillerTest(certainty, random))
+                        continue;
+
+                    if (certainty > 2 && !q.RabinMillerTest(certainty - 2, random))
+                        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 (WNafUtilities.GetNafWeight(p) < minWeight)
+                        continue;
+
+                    break;
+                }
+            }
+
+            return new BigInteger[] { p, q };
+        }
+
+        /*
+         * Select a high order element of the multiplicative group Zp*
+         * 
+         * p and q must be s.t. p = 2*q + 1, where p and q are prime (see generateSafePrimes)
+         */
+        internal static BigInteger SelectGenerator(BigInteger p, BigInteger q, SecureRandom random)
+        {
+            BigInteger pMinusTwo = p.Subtract(BigInteger.Two);
+            BigInteger g;
+
+            /*
+             * (see: Handbook of Applied Cryptography 4.80)
+             */
 //			do
 //			{
 //				g = BigIntegers.CreateRandomInRange(BigInteger.Two, pMinusTwo, random);
@@ -121,18 +139,18 @@ namespace Org.BouncyCastle.Crypto.Generators
 //			while (g.ModPow(BigInteger.Two, p).Equals(BigInteger.One)
 //				|| g.ModPow(q, p).Equals(BigInteger.One));
 
-			/*
-	         * RFC 2631 2.2.1.2 (and see: Handbook of Applied Cryptography 4.81)
-	         */
-			do
-			{
-				BigInteger h = BigIntegers.CreateRandomInRange(BigInteger.Two, pMinusTwo, random);
+            /*
+             * RFC 2631 2.2.1.2 (and see: Handbook of Applied Cryptography 4.81)
+             */
+            do
+            {
+                BigInteger h = BigIntegers.CreateRandomInRange(BigInteger.Two, pMinusTwo, random);
 
-				g = h.ModPow(BigInteger.Two, p);
-			}
-			while (g.Equals(BigInteger.One));
+                g = h.ModPow(BigInteger.Two, p);
+            }
+            while (g.Equals(BigInteger.One));
 
-			return g;
-		}
-	}
+            return g;
+        }
+    }
 }
diff --git a/crypto/src/crypto/generators/RsaKeyPairGenerator.cs b/crypto/src/crypto/generators/RsaKeyPairGenerator.cs
index 3074aed04..e870f1c08 100644
--- a/crypto/src/crypto/generators/RsaKeyPairGenerator.cs
+++ b/crypto/src/crypto/generators/RsaKeyPairGenerator.cs
@@ -3,6 +3,7 @@ using System;
 using Org.BouncyCastle.Crypto;
 using Org.BouncyCastle.Crypto.Parameters;
 using Org.BouncyCastle.Math;
+using Org.BouncyCastle.Math.EC.Multiplier;
 
 namespace Org.BouncyCastle.Crypto.Generators
 {
@@ -10,107 +11,95 @@ namespace Org.BouncyCastle.Crypto.Generators
      * an RSA key pair generator.
      */
     public class RsaKeyPairGenerator
-		: IAsymmetricCipherKeyPairGenerator
+        : IAsymmetricCipherKeyPairGenerator
     {
-		private static readonly BigInteger DefaultPublicExponent = BigInteger.ValueOf(0x10001);
-		private const int DefaultTests = 12;
+        private static readonly BigInteger DefaultPublicExponent = BigInteger.ValueOf(0x10001);
+        private const int DefaultTests = 12;
 
-		private RsaKeyGenerationParameters param;
+        private RsaKeyGenerationParameters param;
 
-		public void Init(
+        public void Init(
             KeyGenerationParameters parameters)
         {
-			if (parameters is RsaKeyGenerationParameters)
-			{
-				this.param = (RsaKeyGenerationParameters)parameters;
-			}
-			else
-			{
-				this.param = new RsaKeyGenerationParameters(
-					DefaultPublicExponent, parameters.Random, parameters.Strength, DefaultTests);
-			}
+            if (parameters is RsaKeyGenerationParameters)
+            {
+                this.param = (RsaKeyGenerationParameters)parameters;
+            }
+            else
+            {
+                this.param = new RsaKeyGenerationParameters(
+                    DefaultPublicExponent, parameters.Random, parameters.Strength, DefaultTests);
+            }
         }
 
-		public AsymmetricCipherKeyPair GenerateKeyPair()
+        public AsymmetricCipherKeyPair GenerateKeyPair()
         {
             BigInteger p, q, n, d, e, pSub1, qSub1, phi;
 
             //
             // p and q values should have a length of half the strength in bits
             //
-			int strength = param.Strength;
-            int pbitlength = (strength + 1) / 2;
-            int qbitlength = (strength - pbitlength);
-			int mindiffbits = strength / 3;
-
-			e = param.PublicExponent;
-
-			// 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.Random);
+            int strength = param.Strength;
+            int qBitlength = strength >> 1;
+            int pBitlength = strength - qBitlength;
+            int mindiffbits = strength / 3;
+            int minWeight = strength >> 2;
 
-				if (p.Mod(e).Equals(BigInteger.One))
-					continue;
+            e = param.PublicExponent;
 
-				if (!p.IsProbablePrime(param.Certainty))
-					continue;
+            // 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")
 
-				if (e.Gcd(p.Subtract(BigInteger.One)).Equals(BigInteger.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 = new BigInteger(qbitlength, 1, param.Random);
+                q = ChooseRandomPrime(qBitlength, e);
 
-					if (q.Subtract(p).Abs().BitLength < mindiffbits)
-						continue;
-
-					if (q.Mod(e).Equals(BigInteger.One))
-						continue;
-
-					if (!q.IsProbablePrime(param.Certainty))
-						continue;
-
-					if (e.Gcd(q.Subtract(BigInteger.One)).Equals(BigInteger.One)) 
-						break;
-				}
+                // p and q should not be too close together (or equal!)
+                BigInteger diff = q.Subtract(p).Abs();
+                if (diff.BitLength < mindiffbits)
+                    continue;
 
                 //
                 // calculate the modulus
                 //
                 n = p.Multiply(q);
 
-                if (n.BitLength == param.Strength)
-					break;
+                if (n.BitLength != strength)
+                {
+                    //
+                    // 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;
+                }
+
+                /*
+                 * 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 (WNafUtilities.GetNafWeight(n) < minWeight)
+                {
+                    p = ChooseRandomPrime(pBitlength, e);
+                    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);
+                break;
             }
 
-			if (p.CompareTo(q) < 0)
-			{
-				phi = p;
-				p = q;
-				q = phi;
-			}
+            if (p.CompareTo(q) < 0)
+            {
+                phi = p;
+                p = q;
+                q = phi;
+            }
 
             pSub1 = p.Subtract(BigInteger.One);
             qSub1 = q.Subtract(BigInteger.One);
@@ -134,6 +123,28 @@ namespace Org.BouncyCastle.Crypto.Generators
                 new RsaKeyParameters(false, n, e),
                 new RsaPrivateCrtKeyParameters(n, e, d, p, q, dP, dQ, qInv));
         }
-    }
 
+        /// <summary>Choose a random prime value for use with RSA</summary>
+        /// <param name="bitlength">the bit-length of the returned prime</param>
+        /// <param name="e">the RSA public exponent</param>
+        /// <returns>a prime p, with (p-1) relatively prime to e</returns>
+        protected virtual BigInteger ChooseRandomPrime(int bitlength, BigInteger e)
+        {
+            for (;;)
+            {
+                BigInteger p = new BigInteger(bitlength, 1, param.Random);
+
+                if (p.Mod(e).Equals(BigInteger.One))
+                    continue;
+
+                if (!p.IsProbablePrime(param.Certainty))
+                    continue;
+
+                if (!e.Gcd(p.Subtract(BigInteger.One)).Equals(BigInteger.One))
+                    continue;
+
+                return p;
+            }
+        }
+    }
 }
diff --git a/crypto/src/math/ec/multiplier/WNafUtilities.cs b/crypto/src/math/ec/multiplier/WNafUtilities.cs
index 98e4f545f..865b9073e 100644
--- a/crypto/src/math/ec/multiplier/WNafUtilities.cs
+++ b/crypto/src/math/ec/multiplier/WNafUtilities.cs
@@ -268,6 +268,17 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
             return wnaf;
         }
 
+        public static int GetNafWeight(BigInteger k)
+        {
+            if (k.SignValue == 0)
+                return 0;
+
+            BigInteger _3k = k.ShiftLeft(1).Add(k);
+            BigInteger diff = _3k.Xor(k);
+
+            return diff.BitCount;
+        }
+
         public static WNafPreCompInfo GetWNafPreCompInfo(ECPoint p)
         {
             return GetWNafPreCompInfo(p.Curve.GetPreCompInfo(p, PRECOMP_NAME));