Apply low-hamming-weight NAF check for more generators

3 files changed, 135 insertions, 90 deletions

diff --git a/crypto/src/crypto/generators/DHKeyGeneratorHelper.cs b/crypto/src/crypto/generators/DHKeyGeneratorHelper.cs
index d05c51e80..68aba64f7 100644
--- a/crypto/src/crypto/generators/DHKeyGeneratorHelper.cs
+++ b/crypto/src/crypto/generators/DHKeyGeneratorHelper.cs
@@ -2,6 +2,7 @@ using System;
 
 using Org.BouncyCastle.Crypto.Parameters;
 using Org.BouncyCastle.Math;
+using Org.BouncyCastle.Math.EC.Multiplier;
 using Org.BouncyCastle.Security;
 using Org.BouncyCastle.Utilities;
 
@@ -23,7 +24,15 @@ namespace Org.BouncyCastle.Crypto.Generators
 
             if (limit != 0)
             {
-                return new BigInteger(limit, random).SetBit(limit - 1);
+                int minWeight = limit >> 2;
+                for (;;)
+                {
+                    BigInteger x = new BigInteger(limit, random).SetBit(limit - 1);
+                    if (WNafUtilities.GetNafWeight(x) >= minWeight)
+                    {
+                        return x;
+                    }
+                }
             }
 
             BigInteger min = BigInteger.Two;
@@ -40,7 +49,17 @@ namespace Org.BouncyCastle.Crypto.Generators
             }
             BigInteger max = q.Subtract(BigInteger.Two);
 
-            return BigIntegers.CreateRandomInRange(min, max, random);
+            {
+                int minWeight = max.BitLength >> 2;
+                for (;;)
+                {
+                    BigInteger x = BigIntegers.CreateRandomInRange(min, max, random);
+                    if (WNafUtilities.GetNafWeight(x) >= minWeight)
+                    {
+                        return x;
+                    }
+                }
+            }
         }
 
         internal BigInteger CalculatePublic(
diff --git a/crypto/src/crypto/generators/DsaKeyPairGenerator.cs b/crypto/src/crypto/generators/DsaKeyPairGenerator.cs
index bb8ec591b..1c9ce5a16 100644
--- a/crypto/src/crypto/generators/DsaKeyPairGenerator.cs
+++ b/crypto/src/crypto/generators/DsaKeyPairGenerator.cs
@@ -1,8 +1,10 @@
 using System;
-using Org.BouncyCastle.Math;
-using Org.BouncyCastle.Security;
+
 using Org.BouncyCastle.Crypto;
 using Org.BouncyCastle.Crypto.Parameters;
+using Org.BouncyCastle.Math;
+using Org.BouncyCastle.Math.EC.Multiplier;
+using Org.BouncyCastle.Security;
 using Org.BouncyCastle.Utilities;
 
 namespace Org.BouncyCastle.Crypto.Generators
@@ -11,51 +13,60 @@ namespace Org.BouncyCastle.Crypto.Generators
      * a DSA key pair generator.
      *
      * This Generates DSA keys in line with the method described
-	 * in <i>FIPS 186-3 B.1 FFC Key Pair Generation</i>.
+     * in <i>FIPS 186-3 B.1 FFC Key Pair Generation</i>.
      */
     public class DsaKeyPairGenerator
-		: IAsymmetricCipherKeyPairGenerator
+        : IAsymmetricCipherKeyPairGenerator
     {
+        private static readonly BigInteger One = BigInteger.One;
+
         private DsaKeyGenerationParameters param;
 
-		public void Init(
-			KeyGenerationParameters parameters)
+        public void Init(
+            KeyGenerationParameters parameters)
         {
-			if (parameters == null)
-				throw new ArgumentNullException("parameters");
+            if (parameters == null)
+                throw new ArgumentNullException("parameters");
 
-			// Note: If we start accepting instances of KeyGenerationParameters,
-			// must apply constraint checking on strength (see DsaParametersGenerator.Init)
+            // Note: If we start accepting instances of KeyGenerationParameters,
+            // must apply constraint checking on strength (see DsaParametersGenerator.Init)
 
-			this.param = (DsaKeyGenerationParameters) parameters;
+            this.param = (DsaKeyGenerationParameters) parameters;
         }
 
-		public AsymmetricCipherKeyPair GenerateKeyPair()
+        public AsymmetricCipherKeyPair GenerateKeyPair()
         {
-			DsaParameters dsaParams = param.Parameters;
+            DsaParameters dsaParams = param.Parameters;
 
-			BigInteger x = GeneratePrivateKey(dsaParams.Q, param.Random);
-			BigInteger y = CalculatePublicKey(dsaParams.P, dsaParams.G, x);
+            BigInteger x = GeneratePrivateKey(dsaParams.Q, param.Random);
+            BigInteger y = CalculatePublicKey(dsaParams.P, dsaParams.G, x);
 
-			return new AsymmetricCipherKeyPair(
-				new DsaPublicKeyParameters(y, dsaParams),
-				new DsaPrivateKeyParameters(x, dsaParams));
+            return new AsymmetricCipherKeyPair(
+                new DsaPublicKeyParameters(y, dsaParams),
+                new DsaPrivateKeyParameters(x, dsaParams));
         }
 
-		private static BigInteger GeneratePrivateKey(BigInteger q, SecureRandom random)
-		{
-			// TODO Prefer this method? (change test cases that used fixed random)
-			// B.1.1 Key Pair Generation Using Extra Random Bits
-//	        BigInteger c = new BigInteger(q.BitLength + 64, random);
-//	        return c.Mod(q.Subtract(BigInteger.One)).Add(BigInteger.One);
-
-			// B.1.2 Key Pair Generation by Testing Candidates
-			return BigIntegers.CreateRandomInRange(BigInteger.One, q.Subtract(BigInteger.One), random);
-		}
-
-		private static BigInteger CalculatePublicKey(BigInteger p, BigInteger g, BigInteger x)
-		{
-			return g.ModPow(x, p);
-		}
-	}
+        private static BigInteger GeneratePrivateKey(BigInteger q, SecureRandom random)
+        {
+            // B.1.2 Key Pair Generation by Testing Candidates
+            int minWeight = q.BitLength >> 2;
+            for (;;)
+            {
+                // TODO Prefer this method? (change test cases that used fixed random)
+                // B.1.1 Key Pair Generation Using Extra Random Bits
+                //BigInteger x = new BigInteger(q.BitLength + 64, random).Mod(q.Subtract(One)).Add(One);
+
+                BigInteger x = BigIntegers.CreateRandomInRange(One, q.Subtract(One), random);
+                if (WNafUtilities.GetNafWeight(x) >= minWeight)
+                {
+                    return x;
+                }
+            }
+        }
+
+        private static BigInteger CalculatePublicKey(BigInteger p, BigInteger g, BigInteger x)
+        {
+            return g.ModPow(x, p);
+        }
+    }
 }
diff --git a/crypto/src/crypto/generators/GOST3410KeyPairGenerator.cs b/crypto/src/crypto/generators/GOST3410KeyPairGenerator.cs
index 5878da64b..013b81810 100644
--- a/crypto/src/crypto/generators/GOST3410KeyPairGenerator.cs
+++ b/crypto/src/crypto/generators/GOST3410KeyPairGenerator.cs
@@ -3,71 +3,86 @@ using System;
 using Org.BouncyCastle.Asn1.CryptoPro;
 using Org.BouncyCastle.Crypto.Parameters;
 using Org.BouncyCastle.Math;
+using Org.BouncyCastle.Math.EC.Multiplier;
 using Org.BouncyCastle.Security;
 
 namespace Org.BouncyCastle.Crypto.Generators
 {
-	/**
-	 * a GOST3410 key pair generator.
-	 * This generates GOST3410 keys in line with the method described
-	 * in GOST R 34.10-94.
-	 */
-	public class Gost3410KeyPairGenerator
-		: IAsymmetricCipherKeyPairGenerator
-	{
-		private Gost3410KeyGenerationParameters param;
+    /**
+     * a GOST3410 key pair generator.
+     * This generates GOST3410 keys in line with the method described
+     * in GOST R 34.10-94.
+     */
+    public class Gost3410KeyPairGenerator
+        : IAsymmetricCipherKeyPairGenerator
+    {
+        private Gost3410KeyGenerationParameters param;
 
-		public void Init(
-			KeyGenerationParameters parameters)
-		{
-			if (parameters is Gost3410KeyGenerationParameters)
-			{
-				this.param = (Gost3410KeyGenerationParameters) parameters;
-			}
-			else
-			{
-				Gost3410KeyGenerationParameters kgp = new Gost3410KeyGenerationParameters(
-					parameters.Random,
-					CryptoProObjectIdentifiers.GostR3410x94CryptoProA);
+        public void Init(
+            KeyGenerationParameters parameters)
+        {
+            if (parameters is Gost3410KeyGenerationParameters)
+            {
+                this.param = (Gost3410KeyGenerationParameters) parameters;
+            }
+            else
+            {
+                Gost3410KeyGenerationParameters kgp = new Gost3410KeyGenerationParameters(
+                    parameters.Random,
+                    CryptoProObjectIdentifiers.GostR3410x94CryptoProA);
 
-				if (parameters.Strength != kgp.Parameters.P.BitLength - 1)
-				{
-					// TODO Should we complain?
-				}
+                if (parameters.Strength != kgp.Parameters.P.BitLength - 1)
+                {
+                    // TODO Should we complain?
+                }
 
-				this.param = kgp;
-			}
-		}
+                this.param = kgp;
+            }
+        }
 
-		public AsymmetricCipherKeyPair GenerateKeyPair()
-		{
-			SecureRandom random = param.Random;
-			Gost3410Parameters gost3410Params = param.Parameters;
+        public AsymmetricCipherKeyPair GenerateKeyPair()
+        {
+            SecureRandom random = param.Random;
+            Gost3410Parameters gost3410Params = param.Parameters;
 
-			BigInteger q = gost3410Params.Q;
-			BigInteger x;
-			do
-			{
-				x = new BigInteger(256, random);
-			}
-			while (x.SignValue < 1 || x.CompareTo(q) >= 0);
+            BigInteger q = gost3410Params.Q, x;
 
-			BigInteger p = gost3410Params.P;
-			BigInteger a = gost3410Params.A;
+            int minWeight = 64;
+            for (;;)
+            {
+                x = new BigInteger(256, random);
 
-			// calculate the public key.
-			BigInteger y = a.ModPow(x, p);
+                if (x.SignValue < 1 || x.CompareTo(q) >= 0)
+                    continue;
 
-			if (param.PublicKeyParamSet != null)
-			{
-				return new AsymmetricCipherKeyPair(
-					new Gost3410PublicKeyParameters(y, param.PublicKeyParamSet),
-					new Gost3410PrivateKeyParameters(x, param.PublicKeyParamSet));
-			}
+                /*
+                 * 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(x) < minWeight)
+                    continue;
 
-			return new AsymmetricCipherKeyPair(
-				new Gost3410PublicKeyParameters(y, gost3410Params),
-				new Gost3410PrivateKeyParameters(x, gost3410Params));
-		}
-	}
+                break;
+            }
+
+            BigInteger p = gost3410Params.P;
+            BigInteger a = gost3410Params.A;
+
+            // calculate the public key.
+            BigInteger y = a.ModPow(x, p);
+
+            if (param.PublicKeyParamSet != null)
+            {
+                return new AsymmetricCipherKeyPair(
+                    new Gost3410PublicKeyParameters(y, param.PublicKeyParamSet),
+                    new Gost3410PrivateKeyParameters(x, param.PublicKeyParamSet));
+            }
+
+            return new AsymmetricCipherKeyPair(
+                new Gost3410PublicKeyParameters(y, gost3410Params),
+                new Gost3410PrivateKeyParameters(x, gost3410Params));
+        }
+    }
 }