diff --git a/crypto/src/math/BigInteger.cs b/crypto/src/math/BigInteger.cs
index ebeb78788..b35701fb3 100644
--- a/crypto/src/math/BigInteger.cs
+++ b/crypto/src/math/BigInteger.cs
@@ -681,6 +681,7 @@ namespace Org.BouncyCastle.Math
int xBits = BitsPerByte * nBytes - bitLength;
byte mask = (byte)(255U >> xBits);
+ byte lead = (byte)(1 << (7 - xBits));
for (;;)
{
@@ -690,7 +691,7 @@ namespace Org.BouncyCastle.Math
b[0] &= mask;
// ensure the leading bit is 1 (to meet the strength requirement)
- b[0] |= (byte)(1 << (7 - xBits));
+ b[0] |= lead;
// ensure the trailing bit is 1 (i.e. must be odd)
b[nBytes - 1] |= 1;
@@ -702,21 +703,15 @@ namespace Org.BouncyCastle.Math
if (certainty < 1)
break;
- if (CheckProbablePrime(certainty, random))
+ if (CheckProbablePrime(certainty, random, true))
break;
- if (bitLength > 32)
+ for (int j = 1; j < (magnitude.Length - 1); ++j)
{
- for (int rep = 0; rep < 10000; ++rep)
- {
- int n = 33 + random.Next(bitLength - 2);
- this.magnitude[this.magnitude.Length - (n >> 5)] ^= (1 << (n & 31));
- this.magnitude[this.magnitude.Length - 1] ^= ((random.Next() + 1) << 1);
- this.mQuote = 0;
+ this.magnitude[j] ^= random.Next();
- if (CheckProbablePrime(certainty, random))
- return;
- }
+ if (CheckProbablePrime(certainty, random, true))
+ return;
}
}
}
@@ -968,7 +963,7 @@ namespace Org.BouncyCastle.Math
//
// BitLen(value) is the number of bits in value.
//
- private static int BitLen(int w)
+ internal static int BitLen(int w)
{
uint v = (uint)w;
uint t = v >> 24;
@@ -1340,8 +1335,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 +1353,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 +1392,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,10 +1405,36 @@ 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(BitLength > 2);
+ Debug.Assert(bits > 2);
Debug.Assert(TestBit(0));
+ int iterations = ((certainty - 1) / 2) + 1;
+ if (randomlySelected)
+ {
+ 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
BigInteger n = this;
int s = n.GetLowestSetBitMaskFirst(-1 << 1);
@@ -1449,10 +1472,8 @@ namespace Org.BouncyCastle.Math
return false;
}
}
-
- certainty -= 2; // composites pass for only 1/4 possible 'a'
}
- while (certainty > 0);
+ while (--iterations > 0);
return true;
}
@@ -2494,7 +2515,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);
}
diff --git a/crypto/src/math/Primes.cs b/crypto/src/math/Primes.cs
index 420c3cc5a..fb279f103 100644
--- a/crypto/src/math/Primes.cs
+++ b/crypto/src/math/Primes.cs
@@ -11,6 +11,8 @@ namespace Org.BouncyCastle.Math
*/
public abstract class Primes
{
+ public static readonly int SmallFactorLimit = 211;
+
private static readonly BigInteger One = BigInteger.One;
private static readonly BigInteger Two = BigInteger.Two;
private static readonly BigInteger Three = BigInteger.Three;
@@ -326,37 +328,80 @@ namespace Org.BouncyCastle.Math
*/
int m = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23;
int r = x.Mod(BigInteger.ValueOf(m)).IntValue;
- if ((r & 1) != 0 && (r % 3) != 0 && (r % 5) != 0 && (r % 7) != 0 && (r % 11) != 0
- && (r % 13) != 0 && (r % 17) != 0 && (r % 19) != 0 && (r % 23) != 0)
+ if ((r % 2) == 0 || (r % 3) == 0 || (r % 5) == 0 || (r % 7) == 0 || (r % 11) == 0 || (r % 13) == 0
+ || (r % 17) == 0 || (r % 19) == 0 || (r % 23) == 0)
{
- m = 29 * 31 * 37 * 41 * 43;
- r = x.Mod(BigInteger.ValueOf(m)).IntValue;
- if ((r % 29) != 0 && (r % 31) != 0 && (r % 37) != 0 && (r % 41) != 0 && (r % 43) != 0)
- {
- m = 47 * 53 * 59 * 61 * 67;
- r = x.Mod(BigInteger.ValueOf(m)).IntValue;
- if ((r % 47) != 0 && (r % 53) != 0 && (r % 59) != 0 && (r % 61) != 0 && (r % 67) != 0)
- {
- m = 71 * 73 * 79 * 83;
- r = x.Mod(BigInteger.ValueOf(m)).IntValue;
- if ((r % 71) != 0 && (r % 73) != 0 && (r % 79) != 0 && (r % 83) != 0)
- {
- m = 89 * 97 * 101 * 103;
- r = x.Mod(BigInteger.ValueOf(m)).IntValue;
- if ((r % 89) != 0 && (r % 97) != 0 && (r % 101) != 0 && (r % 103) != 0)
- {
- m = 107 * 109 * 113 * 127;
- r = x.Mod(BigInteger.ValueOf(m)).IntValue;
- if ((r % 107) != 0 && (r % 109) != 0 && (r % 113) != 0 && (r % 127) != 0)
- {
- return false;
- }
- }
- }
- }
- }
+ return true;
}
- return true;
+
+ m = 29 * 31 * 37 * 41 * 43;
+ r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+ if ((r % 29) == 0 || (r % 31) == 0 || (r % 37) == 0 || (r % 41) == 0 || (r % 43) == 0)
+ {
+ return true;
+ }
+
+ m = 47 * 53 * 59 * 61 * 67;
+ r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+ if ((r % 47) == 0 || (r % 53) == 0 || (r % 59) == 0 || (r % 61) == 0 || (r % 67) == 0)
+ {
+ return true;
+ }
+
+ m = 71 * 73 * 79 * 83;
+ r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+ if ((r % 71) == 0 || (r % 73) == 0 || (r % 79) == 0 || (r % 83) == 0)
+ {
+ return true;
+ }
+
+ m = 89 * 97 * 101 * 103;
+ r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+ if ((r % 89) == 0 || (r % 97) == 0 || (r % 101) == 0 || (r % 103) == 0)
+ {
+ return true;
+ }
+
+ m = 107 * 109 * 113 * 127;
+ r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+ if ((r % 107) == 0 || (r % 109) == 0 || (r % 113) == 0 || (r % 127) == 0)
+ {
+ return true;
+ }
+
+ m = 131 * 137 * 139 * 149;
+ r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+ if ((r % 131) == 0 || (r % 137) == 0 || (r % 139) == 0 || (r % 149) == 0)
+ {
+ return true;
+ }
+
+ m = 151 * 157 * 163 * 167;
+ r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+ if ((r % 151) == 0 || (r % 157) == 0 || (r % 163) == 0 || (r % 167) == 0)
+ {
+ return true;
+ }
+
+ m = 173 * 179 * 181 * 191;
+ r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+ if ((r % 173) == 0 || (r % 179) == 0 || (r % 181) == 0 || (r % 191) == 0)
+ {
+ return true;
+ }
+
+ m = 193 * 197 * 199 * 211;
+ r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+ if ((r % 193) == 0 || (r % 197) == 0 || (r % 199) == 0 || (r % 211) == 0)
+ {
+ return true;
+ }
+
+ /*
+ * NOTE: Unit tests depend on SMALL_FACTOR_LIMIT matching the
+ * highest small factor tested here.
+ */
+ return false;
}
private static bool ImplMRProbablePrimeToBase(BigInteger w, BigInteger wSubOne, BigInteger m, int a, BigInteger b)
diff --git a/crypto/src/math/ec/ECCurve.cs b/crypto/src/math/ec/ECCurve.cs
index fa2c72570..6ccd97e7b 100644
--- a/crypto/src/math/ec/ECCurve.cs
+++ b/crypto/src/math/ec/ECCurve.cs
@@ -96,6 +96,7 @@ namespace Org.BouncyCastle.Math.EC
public abstract int FieldSize { get; }
public abstract ECFieldElement FromBigInteger(BigInteger x);
+ public abstract bool IsValidFieldElement(BigInteger x);
public virtual Config Configure()
{
@@ -477,6 +478,11 @@ namespace Org.BouncyCastle.Math.EC
{
}
+ public override bool IsValidFieldElement(BigInteger x)
+ {
+ return x != null && x.SignValue >= 0 && x.CompareTo(Field.Characteristic) < 0;
+ }
+
protected override ECPoint DecompressPoint(int yTilde, BigInteger X1)
{
ECFieldElement x = FromBigInteger(X1);
@@ -670,6 +676,11 @@ namespace Org.BouncyCastle.Math.EC
{
}
+ public override bool IsValidFieldElement(BigInteger x)
+ {
+ return x != null && x.SignValue >= 0 && x.BitLength <= FieldSize;
+ }
+
[Obsolete("Per-point compression property will be removed")]
public override ECPoint CreatePoint(BigInteger x, BigInteger y, bool withCompression)
{
|
