diff options
| -rw-r--r-- | crypto/src/math/raw/Mod.cs | 92 | ||||
| -rw-r--r-- | crypto/src/math/raw/Nat.cs | 27 | ||||
| -rw-r--r-- | crypto/src/util/BigIntegers.cs | 4 |
3 files changed, 78 insertions, 45 deletions
diff --git a/crypto/src/math/raw/Mod.cs b/crypto/src/math/raw/Mod.cs index 20f445154..bc5942711 100644 --- a/crypto/src/math/raw/Mod.cs +++ b/crypto/src/math/raw/Mod.cs @@ -17,6 +17,8 @@ namespace Org.BouncyCastle.Math.Raw private const int M30 = 0x3FFFFFFF; private const ulong M32UL = 0xFFFFFFFFUL; + private static readonly int MaxStackAlloc = Platform.Is64BitProcess ? 4096 : 1024; + #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER public static void CheckedModOddInverse(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x, Span<uint> z) #else @@ -125,9 +127,10 @@ namespace Org.BouncyCastle.Math.Raw int bits = (len32 << 5) - Integers.NumberOfLeadingZeros((int)m[len32 - 1]); int len30 = (bits + 29) / 30; - Span<int> alloc = len30 <= 50 - ? stackalloc int[len30 * 5] - : new int[len30 * 5]; + int allocSize = len30 * 5; + Span<int> alloc = (allocSize * Integers.NumBytes <= MaxStackAlloc) + ? stackalloc int[allocSize] + : new int[allocSize]; Span<int> t = stackalloc int[4]; Span<int> D = alloc[..len30]; alloc = alloc[len30..]; @@ -189,11 +192,11 @@ namespace Org.BouncyCastle.Math.Raw Encode30(bits, m, 0, M, 0); Array.Copy(M, 0, F, 0, len30); - int clzG = Integers.NumberOfLeadingZeros(G[len30 - 1] | 1) - (len30 * 30 + 2 - bits); - int eta = -1 - clzG; + int clz = System.Math.Max(0, bits - 1 - Nat.GetBitLength(len32, x)); + int eta = -1 - clz; int lenDE = len30, lenFG = len30; int m0Inv32 = (int)Inverse32((uint)M[0]); - int maxDivsteps = GetMaximumDivsteps(bits); + int maxDivsteps = GetMaximumDivsteps(bits) - clz; int divsteps = 0; while (!EqualToZeroVar_Unlikely(lenFG, G)) @@ -206,20 +209,7 @@ namespace Org.BouncyCastle.Math.Raw eta = Divsteps30Var(eta, F[0], G[0], t); UpdateDE30(lenDE, D, E, t, m0Inv32, M); UpdateFG30(lenFG, F, G, t); - - int fn = F[lenFG - 1]; - int gn = G[lenFG - 1]; - - int cond = (lenFG - 2) >> 31; - cond |= fn ^ (fn >> 31); - cond |= gn ^ (gn >> 31); - - if (cond == 0) - { - F[lenFG - 2] |= fn << 30; - G[lenFG - 2] |= gn << 30; - --lenFG; - } + lenFG = TrimFG30Var(lenFG, F, G); } int signF = F[lenFG - 1] >> 31; @@ -268,9 +258,10 @@ namespace Org.BouncyCastle.Math.Raw int bits = (len32 << 5) - Integers.NumberOfLeadingZeros((int)m[len32 - 1]); int len30 = (bits + 29) / 30; - Span<int> alloc = len30 <= 50 - ? stackalloc int[len30 * 5] - : new int[len30 * 5]; + int allocSize = len30 * 5; + Span<int> alloc = (allocSize * Integers.NumBytes <= MaxStackAlloc) + ? stackalloc int[allocSize] + : new int[allocSize]; Span<int> t = stackalloc int[4]; Span<int> D = alloc[..len30]; alloc = alloc[len30..]; @@ -284,11 +275,11 @@ namespace Org.BouncyCastle.Math.Raw Encode30(bits, m, M); M.CopyTo(F); - int clzG = Integers.NumberOfLeadingZeros(G[len30 - 1] | 1) - (len30 * 30 + 2 - bits); - int eta = -1 - clzG; + int clz = System.Math.Max(0, bits - 1 - Nat.GetBitLength(len32, x)); + int eta = -1 - clz; int lenDE = len30, lenFG = len30; int m0Inv32 = (int)Inverse32((uint)M[0]); - int maxDivsteps = GetMaximumDivsteps(bits); + int maxDivsteps = GetMaximumDivsteps(bits) - clz; int divsteps = 0; while (!EqualToZeroVar_Unlikely(lenFG, G)) @@ -301,20 +292,7 @@ namespace Org.BouncyCastle.Math.Raw eta = Divsteps30Var(eta, F[0], G[0], t); UpdateDE30(lenDE, D, E, t, m0Inv32, M); UpdateFG30(lenFG, F, G, t); - - int fn = F[lenFG - 1]; - int gn = G[lenFG - 1]; - - int cond = (lenFG - 2) >> 31; - cond |= fn ^ (fn >> 31); - cond |= gn ^ (gn >> 31); - - if (cond == 0) - { - F[lenFG - 2] |= fn << 30; - G[lenFG - 2] |= gn << 30; - --lenFG; - } + lenFG = TrimFG30Var(lenFG, F, G); } int signF = F[lenFG - 1] >> 31; @@ -392,9 +370,10 @@ namespace Org.BouncyCastle.Math.Raw m |= m >> 8; m |= m >> 16; - Span<byte> bytes = len <= 256 - ? stackalloc byte[len << 2] - : new byte[len << 2]; + int allocSize = len * Integers.NumBytes; + Span<byte> bytes = allocSize <= MaxStackAlloc + ? stackalloc byte[allocSize] + : new byte[allocSize]; do { @@ -784,6 +763,33 @@ namespace Org.BouncyCastle.Math.Raw } #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static int TrimFG30Var(int len30, Span<int> F, Span<int> G) +#else + private static int TrimFG30Var(int len30, int[] F, int[] G) +#endif + { + Debug.Assert(len30 > 0); + Debug.Assert(F.Length >= len30); + Debug.Assert(G.Length >= len30); + + int fn = F[len30 - 1]; + int gn = G[len30 - 1]; + + int cond = (len30 - 2) >> 31; + cond |= fn ^ (fn >> 31); + cond |= gn ^ (gn >> 31); + + if (cond == 0) + { + F[len30 - 2] |= fn << 30; + G[len30 - 2] |= gn << 30; + --len30; + } + + return len30; + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER private static void UpdateDE30(int len30, Span<int> D, Span<int> E, ReadOnlySpan<int> t, int m0Inv32, ReadOnlySpan<int> M) #else diff --git a/crypto/src/math/raw/Nat.cs b/crypto/src/math/raw/Nat.cs index 0f53b1a8b..80ea6d7ce 100644 --- a/crypto/src/math/raw/Nat.cs +++ b/crypto/src/math/raw/Nat.cs @@ -6,6 +6,7 @@ using System.Runtime.InteropServices; #endif using Org.BouncyCastle.Crypto.Utilities; +using Org.BouncyCastle.Utilities; namespace Org.BouncyCastle.Math.Raw { @@ -954,6 +955,32 @@ namespace Org.BouncyCastle.Math.Raw } #endif +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static int GetBitLength(int len, ReadOnlySpan<uint> x) +#else + public static int GetBitLength(int len, uint[] x) +#endif + { + for (int i = len - 1; i >= 0; --i) + { + uint x_i = x[i]; + if (x_i != 0) + return i * 32 + 32 - Integers.NumberOfLeadingZeros((int)x_i); + } + return 0; + } + + public static int GetBitLength(int len, uint[] x, int xOff) + { + for (int i = len - 1; i >= 0; --i) + { + uint x_i = x[xOff + i]; + if (x_i != 0) + return i * 32 + 32 - Integers.NumberOfLeadingZeros((int)x_i); + } + return 0; + } + public static int GetLengthForBits(int bits) { if (bits < 1) diff --git a/crypto/src/util/BigIntegers.cs b/crypto/src/util/BigIntegers.cs index 9c5477e6a..d1b15f869 100644 --- a/crypto/src/util/BigIntegers.cs +++ b/crypto/src/util/BigIntegers.cs @@ -187,7 +187,7 @@ namespace Org.BouncyCastle.Utilities public static BigInteger ModOddInverse(BigInteger M, BigInteger X) { if (!M.TestBit(0)) - throw new ArgumentException("must be odd", "M"); + 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) @@ -226,7 +226,7 @@ namespace Org.BouncyCastle.Utilities public static BigInteger ModOddInverseVar(BigInteger M, BigInteger X) { if (!M.TestBit(0)) - throw new ArgumentException("must be odd", "M"); + throw new ArgumentException("must be odd", nameof(M)); if (M.SignValue != 1) throw new ArithmeticException("BigInteger: modulus not positive"); if (M.Equals(One)) |