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));
|
