diff options
| -rw-r--r-- | crypto/src/crypto/generators/DHParametersHelper.cs | 10 | ||||
| -rw-r--r-- | crypto/src/crypto/generators/NaccacheSternKeyPairGenerator.cs | 4 | ||||
| -rw-r--r-- | crypto/src/crypto/generators/RsaKeyPairGenerator.cs | 2 | ||||
| -rw-r--r-- | crypto/src/math/BigInteger.cs | 55 |
4 files changed, 41 insertions, 30 deletions
diff --git a/crypto/src/crypto/generators/DHParametersHelper.cs b/crypto/src/crypto/generators/DHParametersHelper.cs index bf2de2add..385690430 100644 --- a/crypto/src/crypto/generators/DHParametersHelper.cs +++ b/crypto/src/crypto/generators/DHParametersHelper.cs @@ -44,10 +44,10 @@ namespace Org.BouncyCastle.Crypto.Generators p = q.ShiftLeft(1).Add(BigInteger.One); - if (!p.IsProbablePrime(certainty)) + if (!p.IsProbablePrime(certainty, true)) continue; - if (certainty > 2 && !q.IsProbablePrime(certainty - 2)) + if (certainty > 2 && !q.IsProbablePrime(certainty, true)) continue; break; @@ -92,15 +92,15 @@ namespace Org.BouncyCastle.Crypto.Generators if (q.BitLength != qLength) continue; - if (!q.RabinMillerTest(2, random)) + if (!q.RabinMillerTest(2, random, true)) continue; p = q.ShiftLeft(1).Add(BigInteger.One); - if (!p.RabinMillerTest(certainty, random)) + if (!p.RabinMillerTest(certainty, random, true)) continue; - if (certainty > 2 && !q.RabinMillerTest(certainty - 2, random)) + if (certainty > 2 && !q.RabinMillerTest(certainty - 2, random, true)) continue; /* diff --git a/crypto/src/crypto/generators/NaccacheSternKeyPairGenerator.cs b/crypto/src/crypto/generators/NaccacheSternKeyPairGenerator.cs index afc566d87..618ca9a1c 100644 --- a/crypto/src/crypto/generators/NaccacheSternKeyPairGenerator.cs +++ b/crypto/src/crypto/generators/NaccacheSternKeyPairGenerator.cs @@ -98,7 +98,7 @@ namespace Org.BouncyCastle.Crypto.Generators p = _p.Multiply(_2au).Add(BigInteger.One); - if (!p.IsProbablePrime(certainty)) + if (!p.IsProbablePrime(certainty, true)) continue; for (;;) @@ -110,7 +110,7 @@ namespace Org.BouncyCastle.Crypto.Generators q = _q.Multiply(_2bv).Add(BigInteger.One); - if (q.IsProbablePrime(certainty)) + if (q.IsProbablePrime(certainty, true)) break; } diff --git a/crypto/src/crypto/generators/RsaKeyPairGenerator.cs b/crypto/src/crypto/generators/RsaKeyPairGenerator.cs index 2613b902b..449976550 100644 --- a/crypto/src/crypto/generators/RsaKeyPairGenerator.cs +++ b/crypto/src/crypto/generators/RsaKeyPairGenerator.cs @@ -150,7 +150,7 @@ namespace Org.BouncyCastle.Crypto.Generators if (p.Mod(e).Equals(One)) continue; - if (!p.IsProbablePrime(parameters.Certainty)) + if (!p.IsProbablePrime(parameters.Certainty, true)) continue; if (!eIsKnownOddPrime && !e.Gcd(p.Subtract(One)).Equals(One)) diff --git a/crypto/src/math/BigInteger.cs b/crypto/src/math/BigInteger.cs index 7c73334de..3d0509fe0 100644 --- a/crypto/src/math/BigInteger.cs +++ b/crypto/src/math/BigInteger.cs @@ -702,7 +702,7 @@ namespace Org.BouncyCastle.Math if (certainty < 1) break; - if (CheckProbablePrime(certainty, random)) + if (CheckProbablePrime(certainty, random, true)) break; if (bitLength > 32) @@ -714,7 +714,7 @@ namespace Org.BouncyCastle.Math this.magnitude[this.magnitude.Length - 1] ^= ((random.Next() + 1) << 1); this.mQuote = 0; - if (CheckProbablePrime(certainty, random)) + if (CheckProbablePrime(certainty, random, true)) return; } } @@ -1340,8 +1340,12 @@ namespace Org.BouncyCastle.Math * probability of 1 - (1/2)**certainty. * <p>From Knuth Vol 2, pg 395.</p> */ - public bool IsProbablePrime( - int certainty) + public bool IsProbablePrime(int certainty) + { + return IsProbablePrime(certainty, false); + } + + internal bool IsProbablePrime(int certainty, bool randomlySelected) { if (certainty <= 0) return true; @@ -1354,12 +1358,10 @@ namespace Org.BouncyCastle.Math if (n.Equals(One)) return false; - return n.CheckProbablePrime(certainty, RandomSource); + return n.CheckProbablePrime(certainty, RandomSource, randomlySelected); } - private bool CheckProbablePrime( - int certainty, - Random random) + private bool CheckProbablePrime(int certainty, Random random, bool randomlySelected) { Debug.Assert(certainty > 0); Debug.Assert(CompareTo(Two) > 0); @@ -1395,7 +1397,7 @@ namespace Org.BouncyCastle.Math // TODO Is it worth trying to create a hybrid of these two? - return RabinMillerTest(certainty, random); + return RabinMillerTest(certainty, random, randomlySelected); // return SolovayStrassenTest(certainty, random); // bool rbTest = RabinMillerTest(certainty, random); @@ -1408,25 +1410,34 @@ namespace Org.BouncyCastle.Math public bool RabinMillerTest(int certainty, Random random) { + return RabinMillerTest(certainty, random, false); + } + + internal bool RabinMillerTest(int certainty, Random random, bool randomlySelected) + { int bits = BitLength; Debug.Assert(certainty > 0); Debug.Assert(bits > 2); Debug.Assert(TestBit(0)); - int itersFor100Cert = bits >= 1024 ? 4 - : bits >= 512 ? 8 - : bits >= 256 ? 16 - : 50; - - int iterations; - if (certainty < 100) + int iterations = ((certainty - 1) / 2) + 1; + if (randomlySelected) { - iterations = System.Math.Min(itersFor100Cert, ((certainty - 1) / 2) + 1); - } - else - { - iterations = itersFor100Cert + ((certainty - 100 + 1) / 2); + int itersFor100Cert = bits >= 1024 ? 4 + : bits >= 512 ? 8 + : bits >= 256 ? 16 + : 50; + + if (certainty < 100) + { + iterations = System.Math.Min(itersFor100Cert, iterations); + } + else + { + iterations -= 50; + iterations += itersFor100Cert; + } } // let n = 1 + d . 2^s @@ -2509,7 +2520,7 @@ namespace Org.BouncyCastle.Math BigInteger n = Inc().SetBit(0); - while (!n.CheckProbablePrime(100, RandomSource)) + while (!n.CheckProbablePrime(100, RandomSource, false)) { n = n.Add(Two); } |