diff options
Diffstat (limited to 'crypto')
| -rw-r--r-- | crypto/src/crypto/generators/DHParametersHelper.cs | 212 | ||||
| -rw-r--r-- | crypto/src/crypto/generators/RsaKeyPairGenerator.cs | 151 | ||||
| -rw-r--r-- | crypto/src/math/ec/multiplier/WNafUtilities.cs | 11 |
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)); |