From 9754265de37d45b8e92d6ab80f3faca97af97eaa Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Thu, 24 Jul 2014 11:34:27 +0700 Subject: Apply low-hamming-weight NAF check for more generators --- .../src/crypto/generators/DHKeyGeneratorHelper.cs | 23 +++- .../src/crypto/generators/DsaKeyPairGenerator.cs | 79 +++++++------ .../crypto/generators/GOST3410KeyPairGenerator.cs | 123 ++++++++++++--------- 3 files changed, 135 insertions(+), 90 deletions(-) (limited to 'crypto') 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 FIPS 186-3 B.1 FFC Key Pair Generation. + * in FIPS 186-3 B.1 FFC Key Pair Generation. */ 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)); + } + } } -- cgit 1.4.1