diff options
Diffstat (limited to 'crypto/src/math')
| -rw-r--r-- | crypto/src/math/BigInteger.cs | 71 | ||||
| -rw-r--r-- | crypto/src/math/Primes.cs | 103 | ||||
| -rw-r--r-- | crypto/src/math/ec/ECCurve.cs | 11 |
3 files changed, 131 insertions, 54 deletions
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) { |