diff options
| -rw-r--r-- | crypto/src/crypto/generators/NaccacheSternKeyPairGenerator.cs | 2 | ||||
| -rw-r--r-- | crypto/src/crypto/generators/RSABlindingFactorGenerator.cs | 9 | ||||
| -rw-r--r-- | crypto/src/crypto/parameters/RsaKeyParameters.cs | 19 | ||||
| -rw-r--r-- | crypto/src/math/raw/Mod.cs | 223 | ||||
| -rw-r--r-- | crypto/src/util/BigIntegers.cs | 64 | ||||
| -rw-r--r-- | crypto/test/src/crypto/test/RsaTest.cs | 21 |
6 files changed, 289 insertions, 49 deletions
diff --git a/crypto/src/crypto/generators/NaccacheSternKeyPairGenerator.cs b/crypto/src/crypto/generators/NaccacheSternKeyPairGenerator.cs index 09f4b3db9..8db9db728 100644 --- a/crypto/src/crypto/generators/NaccacheSternKeyPairGenerator.cs +++ b/crypto/src/crypto/generators/NaccacheSternKeyPairGenerator.cs @@ -112,7 +112,7 @@ namespace Org.BouncyCastle.Crypto.Generators break; } - if (!sigma.Gcd(_p.Multiply(_q)).Equals(BigInteger.One)) + if (!BigIntegers.ModOddIsCoprime(_p.Multiply(_q), sigma)) { //Console.WriteLine("sigma.gcd(_p.mult(_q)) != 1!\n _p: " + _p +"\n _q: "+ _q ); continue; diff --git a/crypto/src/crypto/generators/RSABlindingFactorGenerator.cs b/crypto/src/crypto/generators/RSABlindingFactorGenerator.cs index a9eeb46df..410d37c63 100644 --- a/crypto/src/crypto/generators/RSABlindingFactorGenerator.cs +++ b/crypto/src/crypto/generators/RSABlindingFactorGenerator.cs @@ -3,6 +3,7 @@ using System; using Org.BouncyCastle.Crypto.Parameters; using Org.BouncyCastle.Math; using Org.BouncyCastle.Security; +using Org.BouncyCastle.Utilities; namespace Org.BouncyCastle.Crypto.Generators { @@ -50,15 +51,13 @@ namespace Org.BouncyCastle.Crypto.Generators BigInteger m = key.Modulus; int length = m.BitLength - 1; // must be less than m.BitLength - BigInteger factor; - BigInteger gcd; + BigInteger factor; do { - factor = new BigInteger(length, random); - gcd = factor.Gcd(m); + factor = BigIntegers.CreateRandomBigInteger(length, random); } - while (factor.SignValue == 0 || factor.Equals(BigInteger.One) || !gcd.Equals(BigInteger.One)); + while (factor.CompareTo(BigInteger.Two) < 0 || !BigIntegers.ModOddIsCoprime(m, factor)); return factor; } diff --git a/crypto/src/crypto/parameters/RsaKeyParameters.cs b/crypto/src/crypto/parameters/RsaKeyParameters.cs index f7e88a2b8..8826bb1ab 100644 --- a/crypto/src/crypto/parameters/RsaKeyParameters.cs +++ b/crypto/src/crypto/parameters/RsaKeyParameters.cs @@ -17,16 +17,29 @@ namespace Org.BouncyCastle.Crypto.Parameters + "f3cfd51e474afb6bc6974f78db8aba8e9e517fded658591ab7502bd41849462f", 16); + private static bool HasAnySmallFactors(BigInteger modulus) + { + BigInteger M = modulus, X = SmallPrimesProduct; + if (modulus.CompareTo(SmallPrimesProduct) < 0) + { + M = SmallPrimesProduct; + X = modulus; + } + + return !BigIntegers.ModOddIsCoprimeVar(M, X); + } + private static BigInteger Validate(BigInteger modulus) { if ((modulus.IntValue & 1) == 0) throw new ArgumentException("RSA modulus is even", nameof(modulus)); - if (!modulus.Gcd(SmallPrimesProduct).Equals(BigInteger.One)) - throw new ArgumentException("RSA modulus has a small prime factor", nameof(modulus)); int maxBitLength = ImplGetInteger("Org.BouncyCastle.Rsa.MaxSize", 16384); if (modulus.BitLength > maxBitLength) - throw new ArgumentException("modulus value out of range"); + throw new ArgumentException("RSA modulus out of range", nameof(modulus)); + + if (HasAnySmallFactors(modulus)) + throw new ArgumentException("RSA modulus has a small prime factor", nameof(modulus)); // TODO: add additional primePower/Composite test - expensive!! diff --git a/crypto/src/math/raw/Mod.cs b/crypto/src/math/raw/Mod.cs index bc5942711..984c4808d 100644 --- a/crypto/src/math/raw/Mod.cs +++ b/crypto/src/math/raw/Mod.cs @@ -112,7 +112,7 @@ namespace Org.BouncyCastle.Math.Raw Decode30(bits, D, 0, z, 0); Debug.Assert(0 != Nat.LessThan(m.Length, z, m)); - return (uint)(EqualTo(len30, F, 1) & EqualToZero(len30, G)); + return (uint)(EqualTo(len30, F, 1) & EqualTo(len30, G, 0)); #endif } @@ -163,7 +163,7 @@ namespace Org.BouncyCastle.Math.Raw Decode30(bits, D, z); Debug.Assert(0 != Nat.LessThan(m.Length, z, m)); - return (uint)(EqualTo(len30, F, 1) & EqualToZero(len30, G)); + return (uint)(EqualTo(len30, F, 1) & EqualTo(len30, G, 0)); } #endif @@ -199,7 +199,7 @@ namespace Org.BouncyCastle.Math.Raw int maxDivsteps = GetMaximumDivsteps(bits) - clz; int divsteps = 0; - while (!EqualToZeroVar_Unlikely(lenFG, G)) + while (!EqualToVar(lenFG, G, 0)) { if (divsteps >= maxDivsteps) return false; @@ -231,7 +231,7 @@ namespace Org.BouncyCastle.Math.Raw } Debug.Assert(0 == signF); - if (!EqualToOneVar_Expected(lenFG, F)) + if (!EqualToVar(lenFG, F, 1)) return false; if (signD < 0) @@ -282,7 +282,7 @@ namespace Org.BouncyCastle.Math.Raw int maxDivsteps = GetMaximumDivsteps(bits) - clz; int divsteps = 0; - while (!EqualToZeroVar_Unlikely(lenFG, G)) + while (!EqualToVar(lenFG, G, 0)) { if (divsteps >= maxDivsteps) return false; @@ -314,7 +314,7 @@ namespace Org.BouncyCastle.Math.Raw } Debug.Assert(0 == signF); - if (!EqualToOneVar_Expected(lenFG, F)) + if (!EqualToVar(lenFG, F, 1)) return false; if (signD < 0) @@ -330,6 +330,182 @@ namespace Org.BouncyCastle.Math.Raw } #endif +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint ModOddIsCoprime(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x) + { + int len32 = m.Length; + Debug.Assert(len32 > 0); + Debug.Assert((m[0] & 1) != 0); + Debug.Assert(m[len32 - 1] != 0); + + int bits = (len32 << 5) - Integers.NumberOfLeadingZeros((int)m[len32 - 1]); + int len30 = (bits + 29) / 30; + + int allocSize = len30 * 3; + Span<int> alloc = (allocSize * Integers.NumBytes <= MaxStackAlloc) + ? stackalloc int[allocSize] + : new int[allocSize]; + + Span<int> t = stackalloc int[4]; + Span<int> F = alloc[..len30]; alloc = alloc[len30..]; + Span<int> G = alloc[..len30]; alloc = alloc[len30..]; + Span<int> M = alloc[..len30]; + + Encode30(bits, x, G); + Encode30(bits, m, M); + M.CopyTo(F); + + int delta = 0; + int maxDivsteps = GetMaximumDivsteps(bits); + + for (int divSteps = 0; divSteps < maxDivsteps; divSteps += 30) + { + delta = Divsteps30(delta, F[0], G[0], t); + UpdateFG30(len30, F, G, t); + } + + int signF = F[len30 - 1] >> 31; + CNegate30(len30, signF, F); + + return (uint)(EqualTo(len30, F, 1) & EqualTo(len30, G, 0)); + } +#else + public static uint ModOddIsCoprime(uint[] m, uint[] x) + { + int len32 = m.Length; + Debug.Assert(len32 > 0); + Debug.Assert((m[0] & 1) != 0); + Debug.Assert(m[len32 - 1] != 0); + + int bits = (len32 << 5) - Integers.NumberOfLeadingZeros((int)m[len32 - 1]); + int len30 = (bits + 29) / 30; + + int[] t = new int[4]; + int[] F = new int[len30]; + int[] G = new int[len30]; + int[] M = new int[len30]; + + Encode30(bits, x, 0, G, 0); + Encode30(bits, m, 0, M, 0); + Array.Copy(M, 0, F, 0, len30); + + int delta = 0; + int maxDivsteps = GetMaximumDivsteps(bits); + + for (int divSteps = 0; divSteps < maxDivsteps; divSteps += 30) + { + delta = Divsteps30(delta, F[0], G[0], t); + UpdateFG30(len30, F, G, t); + } + + int signF = F[len30 - 1] >> 31; + CNegate30(len30, signF, F); + + return (uint)(EqualTo(len30, F, 1) & EqualTo(len30, G, 0)); + } +#endif + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static bool ModOddIsCoprimeVar(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x) + { + int len32 = m.Length; + Debug.Assert(len32 > 0); + Debug.Assert((m[0] & 1) != 0); + Debug.Assert(m[len32 - 1] != 0); + + int bits = (len32 << 5) - Integers.NumberOfLeadingZeros((int)m[len32 - 1]); + int len30 = (bits + 29) / 30; + + int allocSize = len30 * 3; + Span<int> alloc = (allocSize * Integers.NumBytes <= MaxStackAlloc) + ? stackalloc int[allocSize] + : new int[allocSize]; + + Span<int> t = stackalloc int[4]; + Span<int> F = alloc[..len30]; alloc = alloc[len30..]; + Span<int> G = alloc[..len30]; alloc = alloc[len30..]; + Span<int> M = alloc[..len30]; + + Encode30(bits, x, G); + Encode30(bits, m, M); + M.CopyTo(F); + + int clz = System.Math.Max(0, bits - 1 - Nat.GetBitLength(len32, x)); + int eta = -1 - clz; + int lenFG = len30; + int maxDivsteps = GetMaximumDivsteps(bits) - clz; + + int divsteps = 0; + while (!EqualToVar(lenFG, G, 0)) + { + if (divsteps >= maxDivsteps) + return false; + + divsteps += 30; + + eta = Divsteps30Var(eta, F[0], G[0], t); + UpdateFG30(lenFG, F, G, t); + lenFG = TrimFG30Var(lenFG, F, G); + } + + int signF = F[lenFG - 1] >> 31; + if (signF < 0) + { + signF = Negate30(lenFG, F); + } + Debug.Assert(0 == signF); + + return EqualToVar(lenFG, F, 1); + } +#else + public static bool ModOddIsCoprimeVar(uint[] m, uint[] x) + { + int len32 = m.Length; + Debug.Assert(len32 > 0); + Debug.Assert((m[0] & 1) != 0); + Debug.Assert(m[len32 - 1] != 0); + + int bits = (len32 << 5) - Integers.NumberOfLeadingZeros((int)m[len32 - 1]); + int len30 = (bits + 29) / 30; + + int[] t = new int[4]; + int[] F = new int[len30]; + int[] G = new int[len30]; + int[] M = new int[len30]; + + Encode30(bits, x, 0, G, 0); + Encode30(bits, m, 0, M, 0); + Array.Copy(M, 0, F, 0, len30); + + int clz = System.Math.Max(0, bits - 1 - Nat.GetBitLength(len32, x)); + int eta = -1 - clz; + int lenFG = len30; + int maxDivsteps = GetMaximumDivsteps(bits) - clz; + + int divsteps = 0; + while (!EqualToVar(lenFG, G, 0)) + { + if (divsteps >= maxDivsteps) + return false; + + divsteps += 30; + + eta = Divsteps30Var(eta, F[0], G[0], t); + UpdateFG30(lenFG, F, G, t); + lenFG = TrimFG30Var(lenFG, F, G); + } + + int signF = F[lenFG - 1] >> 31; + if (signF < 0) + { + signF = Negate30(lenFG, F); + } + Debug.Assert(0 == signF); + + return EqualToVar(lenFG, F, 1); + } +#endif + public static uint[] Random(SecureRandom random, uint[] p) { int len = p.Length; @@ -692,41 +868,12 @@ namespace Org.BouncyCastle.Math.Raw } #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER - private static bool EqualToOneVar_Expected(int len, ReadOnlySpan<int> x) + private static bool EqualToVar(int len, ReadOnlySpan<int> x, int y) #else - private static bool EqualToOneVar_Expected(int len, int[] x) + private static bool EqualToVar(int len, int[] x, int y) #endif { - int d = x[0] ^ 1; - for (int i = 1; i < len; ++i) - { - d |= x[i]; - } - return d == 0; - } - -#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER - private static int EqualToZero(int len, ReadOnlySpan<int> x) -#else - private static int EqualToZero(int len, int[] x) -#endif - { - int d = 0; - for (int i = 0; i < len; ++i) - { - d |= x[i]; - } - d = (int)((uint)d >> 1) | (d & 1); - return (d - 1) >> 31; - } - -#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER - private static bool EqualToZeroVar_Unlikely(int len, ReadOnlySpan<int> x) -#else - private static bool EqualToZeroVar_Unlikely(int len, int[] x) -#endif - { - int d = x[0]; + int d = x[0] ^ y; if (d != 0) return false; diff --git a/crypto/src/util/BigIntegers.cs b/crypto/src/util/BigIntegers.cs index d1b15f869..8c2068688 100644 --- a/crypto/src/util/BigIntegers.cs +++ b/crypto/src/util/BigIntegers.cs @@ -265,5 +265,69 @@ namespace Org.BouncyCastle.Utilities return Nat.ToBigInteger(len, z); } } + + public static bool ModOddIsCoprime(BigInteger M, BigInteger X) + { + if (!M.TestBit(0)) + throw new ArgumentException("must be odd", nameof(M)); + if (M.SignValue != 1) + throw new ArithmeticException("BigInteger: modulus not positive"); + if (X.SignValue < 0 || X.CompareTo(M) >= 0) + { + X = X.Mod(M); + } + + int bits = M.BitLength; + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + if (bits <= 2048) + { + int len = Nat.GetLengthForBits(bits); + Span<uint> m = stackalloc uint[len]; + Span<uint> x = stackalloc uint[len]; + Nat.FromBigInteger(bits, M, m); + Nat.FromBigInteger(bits, X, x); + return 0 != Mod.ModOddIsCoprime(m, x); + } + else +#endif + { + uint[] m = Nat.FromBigInteger(bits, M); + uint[] x = Nat.FromBigInteger(bits, X); + return 0 != Mod.ModOddIsCoprime(m, x); + } + } + + public static bool ModOddIsCoprimeVar(BigInteger M, BigInteger X) + { + if (!M.TestBit(0)) + throw new ArgumentException("must be odd", nameof(M)); + if (M.SignValue != 1) + throw new ArithmeticException("BigInteger: modulus not positive"); + if (X.SignValue < 0 || X.CompareTo(M) >= 0) + { + X = X.Mod(M); + } + + int bits = M.BitLength; + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + if (bits <= 2048) + { + int len = Nat.GetLengthForBits(bits); + Span<uint> m = stackalloc uint[len]; + Span<uint> x = stackalloc uint[len]; + Nat.FromBigInteger(bits, M, m); + Nat.FromBigInteger(bits, X, x); + return Mod.ModOddIsCoprimeVar(m, x); + } + else +#endif + { + uint[] m = Nat.FromBigInteger(bits, M); + uint[] x = Nat.FromBigInteger(bits, X); + return Mod.ModOddIsCoprimeVar(m, x); + } + } } } diff --git a/crypto/test/src/crypto/test/RsaTest.cs b/crypto/test/src/crypto/test/RsaTest.cs index 3c01baa85..58c10f59c 100644 --- a/crypto/test/src/crypto/test/RsaTest.cs +++ b/crypto/test/src/crypto/test/RsaTest.cs @@ -2,7 +2,6 @@ using System; using NUnit.Framework; -using Org.BouncyCastle.Crypto; using Org.BouncyCastle.Crypto.Digests; using Org.BouncyCastle.Crypto.Encodings; using Org.BouncyCastle.Crypto.Engines; @@ -751,5 +750,23 @@ namespace Org.BouncyCastle.Crypto.Tests Assert.AreEqual(Name + ": Okay", resultText); } - } + + [Test, Explicit] + public void BenchPublicKeyModulusValidation() + { + SecureRandom secureRandom = SecureRandom.GetInstance("SHA512PRNG", false); + secureRandom.SetSeed(2); + + var kpg = new RsaKeyPairGenerator(); + kpg.Init(new RsaKeyGenerationParameters(BigInteger.ValueOf(0x11), secureRandom, 2048, 100)); + + var kp = kpg.GenerateKeyPair(); + var pub = (RsaKeyParameters)kp.Public; + + for (int i = 0; i < 1000000; ++i) + { + new RsaKeyParameters(false, pub.Modulus, pub.Exponent); + } + } + } } |