diff options
| -rw-r--r-- | crypto/src/math/ec/LongArray.cs | 4 | ||||
| -rw-r--r-- | crypto/src/math/ec/multiplier/FixedPointCombMultiplier.cs | 15 | ||||
| -rw-r--r-- | crypto/src/math/raw/Interleave.cs | 45 | ||||
| -rw-r--r-- | crypto/src/math/raw/Mod.cs | 20 | ||||
| -rw-r--r-- | crypto/src/math/raw/Nat.cs | 1080 | ||||
| -rw-r--r-- | crypto/src/util/BigIntegers.cs | 64 |
6 files changed, 1105 insertions, 123 deletions
diff --git a/crypto/src/math/ec/LongArray.cs b/crypto/src/math/ec/LongArray.cs index 0cf32fd15..90ca49c77 100644 --- a/crypto/src/math/ec/LongArray.cs +++ b/crypto/src/math/ec/LongArray.cs @@ -1018,10 +1018,10 @@ namespace Org.BouncyCastle.Math.EC while (--n >= 0) { - Raw.Interleave.Expand64To128(r, 0, len); + Raw.Interleave.Expand64To128(r, 0, len, r, 0); len = ReduceInPlace(r, 0, r.Length, m, ks); } - + return new LongArray(r, 0, len); } diff --git a/crypto/src/math/ec/multiplier/FixedPointCombMultiplier.cs b/crypto/src/math/ec/multiplier/FixedPointCombMultiplier.cs index 37e5b5c29..6449e1d8b 100644 --- a/crypto/src/math/ec/multiplier/FixedPointCombMultiplier.cs +++ b/crypto/src/math/ec/multiplier/FixedPointCombMultiplier.cs @@ -28,18 +28,25 @@ namespace Org.BouncyCastle.Math.EC.Multiplier int width = info.Width; int d = (size + width - 1) / width; + int fullComb = d * width; ECPoint R = c.Infinity; - int fullComb = d * width; +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + int KLen = Nat.GetLengthForBits(fullComb); + Span<uint> K = KLen <= 32 + ? stackalloc uint[KLen] + : new uint[KLen]; + Nat.FromBigInteger(fullComb, k, K); +#else uint[] K = Nat.FromBigInteger(fullComb, k); +#endif - int top = fullComb - 1; - for (int i = 0; i < d; ++i) + for (int i = 1; i <= d; ++i) { uint secretIndex = 0; - for (int j = top - i; j >= 0; j -= d) + for (int j = fullComb - i; j >= 0; j -= d) { uint secretBit = K[j >> 5] >> (j & 0x1F); secretIndex ^= secretBit >> 1; diff --git a/crypto/src/math/raw/Interleave.cs b/crypto/src/math/raw/Interleave.cs index 9ff85c572..c7c8eb4da 100644 --- a/crypto/src/math/raw/Interleave.cs +++ b/crypto/src/math/raw/Interleave.cs @@ -1,4 +1,5 @@ using System; +using System.Diagnostics; #if NETCOREAPP3_0_OR_GREATER using System.Runtime.Intrinsics.X86; #endif @@ -71,25 +72,53 @@ namespace Org.BouncyCastle.Math.Raw z[zOff + 1] = (x >> 1) & M64; } - internal static void Expand64To128(ulong[] zs, int zsOff, int zsLen) +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + internal static void Expand64To128(ulong x, Span<ulong> z) { - int i = zsLen, zsPos = zsOff + zsLen << 1; - while (--i >= 0) +#if NETCOREAPP3_0_OR_GREATER + if (Bmi2.X64.IsSupported) { - zsPos -= 2; - Expand64To128(zs[zsOff + i], zs, zsPos); + z[0] = Bmi2.X64.ParallelBitDeposit(x , 0x5555555555555555UL); + z[1] = Bmi2.X64.ParallelBitDeposit(x >> 32, 0x5555555555555555UL); + return; } +#endif + + // "shuffle" low half to even bits and high half to odd bits + x = Bits.BitPermuteStep(x, 0x00000000FFFF0000UL, 16); + x = Bits.BitPermuteStep(x, 0x0000FF000000FF00UL, 8); + x = Bits.BitPermuteStep(x, 0x00F000F000F000F0UL, 4); + x = Bits.BitPermuteStep(x, 0x0C0C0C0C0C0C0C0CUL, 2); + x = Bits.BitPermuteStep(x, 0x2222222222222222UL, 1); + + z[0] = (x ) & M64; + z[1] = (x >> 1) & M64; } +#endif internal static void Expand64To128(ulong[] xs, int xsOff, int xsLen, ulong[] zs, int zsOff) { - for (int i = 0; i < xsLen; ++i) + int xsPos = xsLen, zsPos = zsOff + xsLen << 1; + while (--xsPos >= 0) { - Expand64To128(xs[xsOff + i], zs, zsOff); - zsOff += 2; + zsPos -= 2; + Expand64To128(xs[xsOff + xsPos], zs, zsPos); } } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + internal static void Expand64To128(ReadOnlySpan<ulong> xs, Span<ulong> zs) + { + int xsPos = xs.Length, zsPos = xs.Length << 1; + Debug.Assert(!zs[xsPos..zsPos].Overlaps(xs)); + while (--xsPos >= 0) + { + zsPos -= 2; + Expand64To128(xs[xsPos], zs[zsPos..]); + } + } +#endif + internal static ulong Expand64To128Rev(ulong x, out ulong low) { #if NETCOREAPP3_0_OR_GREATER diff --git a/crypto/src/math/raw/Mod.cs b/crypto/src/math/raw/Mod.cs index a46a7cdfa..ea61bdd83 100644 --- a/crypto/src/math/raw/Mod.cs +++ b/crypto/src/math/raw/Mod.cs @@ -19,33 +19,25 @@ namespace Org.BouncyCastle.Math.Raw private const int M30 = 0x3FFFFFFF; private const ulong M32UL = 0xFFFFFFFFUL; - public static void CheckedModOddInverse(uint[] m, uint[] x, uint[] z) - { - if (0 == ModOddInverse(m, x, z)) - throw new ArithmeticException("Inverse does not exist."); - } - #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER public static void CheckedModOddInverse(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x, Span<uint> z) - { - if (0 == ModOddInverse(m, x, z)) - throw new ArithmeticException("Inverse does not exist."); - } +#else + public static void CheckedModOddInverse(uint[] m, uint[] x, uint[] z) #endif - - public static void CheckedModOddInverseVar(uint[] m, uint[] x, uint[] z) { - if (!ModOddInverseVar(m, x, z)) + if (0 == ModOddInverse(m, x, z)) throw new ArithmeticException("Inverse does not exist."); } #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER public static void CheckedModOddInverseVar(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x, Span<uint> z) +#else + public static void CheckedModOddInverseVar(uint[] m, uint[] x, uint[] z) +#endif { if (!ModOddInverseVar(m, x, z)) throw new ArithmeticException("Inverse does not exist."); } -#endif public static uint Inverse32(uint d) { diff --git a/crypto/src/math/raw/Nat.cs b/crypto/src/math/raw/Nat.cs index 4065c82c2..09c263f4d 100644 --- a/crypto/src/math/raw/Nat.cs +++ b/crypto/src/math/raw/Nat.cs @@ -21,6 +21,20 @@ namespace Org.BouncyCastle.Math.Raw return (uint)c; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint Add(int len, ReadOnlySpan<uint> x, ReadOnlySpan<uint> y, Span<uint> z) + { + ulong c = 0; + for (int i = 0; i < len; ++i) + { + c += (ulong)x[i] + y[i]; + z[i] = (uint)c; + c >>= 32; + } + return (uint)c; + } +#endif + public static uint Add33At(int len, uint x, uint[] z, int zPos) { Debug.Assert(zPos <= (len - 2)); @@ -45,6 +59,20 @@ namespace Org.BouncyCastle.Math.Raw return c == 0 ? 0 : IncAt(len, z, zOff, zPos + 2); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint Add33At(int len, uint x, Span<uint> z, int zPos) + { + Debug.Assert(zPos <= (len - 2)); + ulong c = (ulong)z[zPos + 0] + x; + z[zPos + 0] = (uint)c; + c >>= 32; + c += (ulong)z[zPos + 1] + 1; + z[zPos + 1] = (uint)c; + c >>= 32; + return c == 0 ? 0 : IncAt(len, z, zPos + 2); + } +#endif + public static uint Add33To(int len, uint x, uint[] z) { ulong c = (ulong)z[0] + x; @@ -67,6 +95,19 @@ namespace Org.BouncyCastle.Math.Raw return c == 0 ? 0 : IncAt(len, z, zOff, 2); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint Add33To(int len, uint x, Span<uint> z) + { + ulong c = (ulong)z[0] + x; + z[0] = (uint)c; + c >>= 32; + c += (ulong)z[1] + 1; + z[1] = (uint)c; + c >>= 32; + return c == 0 ? 0 : IncAt(len, z, 2); + } +#endif + public static uint AddBothTo(int len, uint[] x, uint[] y, uint[] z) { ulong c = 0; @@ -91,13 +132,27 @@ namespace Org.BouncyCastle.Math.Raw return (uint)c; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint AddBothTo(int len, ReadOnlySpan<uint> x, ReadOnlySpan<uint> y, Span<uint> z) + { + ulong c = 0; + for (int i = 0; i < len; ++i) + { + c += (ulong)x[i] + y[i] + z[i]; + z[i] = (uint)c; + c >>= 32; + } + return (uint)c; + } +#endif + public static uint AddDWordAt(int len, ulong x, uint[] z, int zPos) { Debug.Assert(zPos <= (len - 2)); - ulong c = (ulong)z[zPos + 0] + (x & M); + ulong c = z[zPos + 0] + (x & M); z[zPos + 0] = (uint)c; c >>= 32; - c += (ulong)z[zPos + 1] + (x >> 32); + c += z[zPos + 1] + (x >> 32); z[zPos + 1] = (uint)c; c >>= 32; return c == 0 ? 0 : IncAt(len, z, zPos + 2); @@ -106,15 +161,29 @@ namespace Org.BouncyCastle.Math.Raw public static uint AddDWordAt(int len, ulong x, uint[] z, int zOff, int zPos) { Debug.Assert(zPos <= (len - 2)); - ulong c = (ulong)z[zOff + zPos] + (x & M); + ulong c = z[zOff + zPos] + (x & M); z[zOff + zPos] = (uint)c; c >>= 32; - c += (ulong)z[zOff + zPos + 1] + (x >> 32); + c += z[zOff + zPos + 1] + (x >> 32); z[zOff + zPos + 1] = (uint)c; c >>= 32; return c == 0 ? 0 : IncAt(len, z, zOff, zPos + 2); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint AddDWordAt(int len, ulong x, Span<uint> z, int zPos) + { + Debug.Assert(zPos <= (len - 2)); + ulong c = z[zPos + 0] + (x & M); + z[zPos + 0] = (uint)c; + c >>= 32; + c += z[zPos + 1] + (x >> 32); + z[zPos + 1] = (uint)c; + c >>= 32; + return c == 0 ? 0 : IncAt(len, z, zPos + 2); + } +#endif + public static uint AddDWordTo(int len, ulong x, uint[] z) { ulong c = (ulong)z[0] + (x & M); @@ -137,6 +206,19 @@ namespace Org.BouncyCastle.Math.Raw return c == 0 ? 0 : IncAt(len, z, zOff, 2); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint AddDWordTo(int len, ulong x, Span<uint> z) + { + ulong c = z[0] + (x & M); + z[0] = (uint)c; + c >>= 32; + c += z[1] + (x >> 32); + z[1] = (uint)c; + c >>= 32; + return c == 0 ? 0 : IncAt(len, z, 2); + } +#endif + public static uint AddTo(int len, uint[] x, uint[] z) { ulong c = 0; @@ -161,6 +243,20 @@ namespace Org.BouncyCastle.Math.Raw return (uint)c; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint AddTo(int len, ReadOnlySpan<uint> x, Span<uint> z) + { + ulong c = 0; + for (int i = 0; i < len; ++i) + { + c += (ulong)x[i] + z[i]; + z[i] = (uint)c; + c >>= 32; + } + return (uint)c; + } +#endif + public static uint AddTo(int len, uint[] x, int xOff, uint[] z, int zOff, uint cIn) { ulong c = cIn; @@ -173,6 +269,20 @@ namespace Org.BouncyCastle.Math.Raw return (uint)c; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint AddTo(int len, ReadOnlySpan<uint> x, Span<uint> z, uint cIn) + { + ulong c = cIn; + for (int i = 0; i < len; ++i) + { + c += (ulong)x[i] + z[i]; + z[i] = (uint)c; + c >>= 32; + } + return (uint)c; + } +#endif + public static uint AddToEachOther(int len, uint[] u, int uOff, uint[] v, int vOff) { ulong c = 0; @@ -186,6 +296,21 @@ namespace Org.BouncyCastle.Math.Raw return (uint)c; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint AddToEachOther(int len, Span<uint> u, Span<uint> v) + { + ulong c = 0; + for (int i = 0; i < len; ++i) + { + c += (ulong)u[i] + v[i]; + u[i] = (uint)c; + v[i] = (uint)c; + c >>= 32; + } + return (uint)c; + } +#endif + public static uint AddWordAt(int len, uint x, uint[] z, int zPos) { Debug.Assert(zPos <= (len - 1)); @@ -204,6 +329,17 @@ namespace Org.BouncyCastle.Math.Raw return c == 0 ? 0 : IncAt(len, z, zOff, zPos + 1); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint AddWordAt(int len, uint x, Span<uint> z, int zPos) + { + Debug.Assert(zPos <= (len - 1)); + ulong c = (ulong)x + z[zPos]; + z[zPos] = (uint)c; + c >>= 32; + return c == 0 ? 0 : IncAt(len, z, zPos + 1); + } +#endif + public static uint AddWordTo(int len, uint x, uint[] z) { ulong c = (ulong)x + z[0]; @@ -220,6 +356,16 @@ namespace Org.BouncyCastle.Math.Raw return c == 0 ? 0 : IncAt(len, z, zOff, 1); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint AddWordTo(int len, uint x, Span<uint> z) + { + ulong c = (ulong)x + z[0]; + z[0] = (uint)c; + c >>= 32; + return c == 0 ? 0 : IncAt(len, z, 1); + } +#endif + public static uint CAdd(int len, int mask, uint[] x, uint[] y, uint[] z) { uint MASK = (uint)-(mask & 1); @@ -257,7 +403,7 @@ namespace Org.BouncyCastle.Math.Raw for (int i = 0; i < len; ++i) { uint z_i = z[zOff + i], diff = z_i ^ x[xOff + i]; - z_i ^= (diff & MASK); + z_i ^= diff & MASK; z[zOff + i] = z_i; } @@ -272,27 +418,29 @@ namespace Org.BouncyCastle.Math.Raw //} } - public static void CMov(int len, int mask, int[] x, int xOff, int[] z, int zOff) +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void CMov(int len, int mask, ReadOnlySpan<uint> x, Span<uint> z) { - mask = -(mask & 1); + uint MASK = (uint)-(mask & 1); for (int i = 0; i < len; ++i) { - int z_i = z[zOff + i], diff = z_i ^ x[xOff + i]; - z_i ^= (diff & mask); - z[zOff + i] = z_i; + uint z_i = z[i], diff = z_i ^ x[i]; + z_i ^= diff & MASK; + z[i] = z_i; } - //int half = 0x55555555, rest = half << (-mask); + //uint half = 0x55555555U, rest = half << (-(int)MASK); //for (int i = 0; i < len; ++i) //{ - // int z_i = z[zOff + i], diff = z_i ^ x[xOff + i]; + // uint z_i = z[i], diff = z_i ^ x[i]; // z_i ^= (diff & half); // z_i ^= (diff & rest); - // z[zOff + i] = z_i; + // z[i] = z_i; //} } +#endif public static int Compare(int len, uint[] x, uint[] y) { @@ -322,10 +470,21 @@ namespace Org.BouncyCastle.Math.Raw return 0; } - public static void Copy(int len, uint[] x, uint[] z) +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static int Compare(int len, ReadOnlySpan<uint> x, ReadOnlySpan<uint> y) { - Array.Copy(x, 0, z, 0, len); + for (int i = len - 1; i >= 0; --i) + { + uint x_i = x[i]; + uint y_i = y[i]; + if (x_i < y_i) + return -1; + if (x_i > y_i) + return 1; + } + return 0; } +#endif public static uint[] Copy(int len, uint[] x) { @@ -334,11 +493,23 @@ namespace Org.BouncyCastle.Math.Raw return z; } + public static void Copy(int len, uint[] x, uint[] z) + { + Array.Copy(x, 0, z, 0, len); + } + public static void Copy(int len, uint[] x, int xOff, uint[] z, int zOff) { Array.Copy(x, xOff, z, zOff, len); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Copy(int len, ReadOnlySpan<uint> x, Span<uint> z) + { + x[..len].CopyTo(z); + } +#endif + public static ulong[] Copy64(int len, ulong[] x) { ulong[] z = new ulong[len]; @@ -356,6 +527,13 @@ namespace Org.BouncyCastle.Math.Raw Array.Copy(x, xOff, z, zOff, len); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Copy64(int len, ReadOnlySpan<ulong> x, Span<ulong> z) + { + x[..len].CopyTo(z); + } +#endif + public static uint[] Create(int len) { return new uint[len]; @@ -372,7 +550,7 @@ namespace Org.BouncyCastle.Math.Raw long c = 0; for (int i = 0; i < len; ++i) { - c += (long)x[i] - (y[i] & MASK); + c += x[i] - (y[i] & MASK); z[i] = (uint)c; c >>= 32; } @@ -385,26 +563,73 @@ namespace Org.BouncyCastle.Math.Raw long c = 0; for (int i = 0; i < len; ++i) { - c += (long)x[xOff + i] - (y[yOff + i] & MASK); + c += x[xOff + i] - (y[yOff + i] & MASK); z[zOff + i] = (uint)c; c >>= 32; } return (int)c; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static int CSub(int len, int mask, ReadOnlySpan<uint> x, ReadOnlySpan<uint> y, Span<uint> z) + { + long MASK = (uint)-(mask & 1); + long c = 0; + for (int i = 0; i < len; ++i) + { + c += x[i] - (y[i] & MASK); + z[i] = (uint)c; + c >>= 32; + } + return (int)c; + } +#endif + public static int Dec(int len, uint[] z) { for (int i = 0; i < len; ++i) { if (--z[i] != uint.MaxValue) + return 0; + } + return -1; + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static int Dec(int len, Span<uint> z) + { + for (int i = 0; i < len; ++i) + { + if (--z[i] != uint.MaxValue) + return 0; + } + return -1; + } +#endif + + public static int Dec(int len, uint[] x, uint[] z) + { + int i = 0; + while (i < len) + { + uint c = x[i] - 1; + z[i] = c; + ++i; + if (c != uint.MaxValue) { + while (i < len) + { + z[i] = x[i]; + ++i; + } return 0; } } return -1; } - public static int Dec(int len, uint[] x, uint[] z) +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static int Dec(int len, ReadOnlySpan<uint> x, Span<uint> z) { int i = 0; while (i < len) @@ -424,6 +649,7 @@ namespace Org.BouncyCastle.Math.Raw } return -1; } +#endif public static int DecAt(int len, uint[] z, int zPos) { @@ -431,9 +657,7 @@ namespace Org.BouncyCastle.Math.Raw for (int i = zPos; i < len; ++i) { if (--z[i] != uint.MaxValue) - { return 0; - } } return -1; } @@ -444,25 +668,46 @@ namespace Org.BouncyCastle.Math.Raw for (int i = zPos; i < len; ++i) { if (--z[zOff + i] != uint.MaxValue) - { return 0; - } } return -1; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static int DecAt(int len, Span<uint> z, int zPos) + { + Debug.Assert(zPos <= len); + for (int i = zPos; i < len; ++i) + { + if (--z[i] != uint.MaxValue) + return 0; + } + return -1; + } +#endif + public static bool Eq(int len, uint[] x, uint[] y) { for (int i = len - 1; i >= 0; --i) { if (x[i] != y[i]) - { return false; - } } return true; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static bool Eq(int len, ReadOnlySpan<uint> x, ReadOnlySpan<uint> y) + { + for (int i = len - 1; i >= 0; --i) + { + if (x[i] != y[i]) + return false; + } + return true; + } +#endif + public static uint EqualTo(int len, uint[] x, uint y) { uint d = x[0] ^ y; @@ -485,6 +730,19 @@ namespace Org.BouncyCastle.Math.Raw return (uint)(((int)d - 1) >> 31); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint EqualTo(int len, ReadOnlySpan<uint> x, uint y) + { + uint d = x[0] ^ y; + for (int i = 1; i < len; ++i) + { + d |= x[i]; + } + d = (d >> 1) | (d & 1); + return (uint)(((int)d - 1) >> 31); + } +#endif + public static uint EqualTo(int len, uint[] x, uint[] y) { uint d = 0; @@ -507,6 +765,19 @@ namespace Org.BouncyCastle.Math.Raw return (uint)(((int)d - 1) >> 31); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint EqualTo(int len, ReadOnlySpan<uint> x, ReadOnlySpan<uint> y) + { + uint d = 0; + for (int i = 0; i < len; ++i) + { + d |= x[i] ^ y[i]; + } + d = (d >> 1) | (d & 1); + return (uint)(((int)d - 1) >> 31); + } +#endif + public static uint EqualToZero(int len, uint[] x) { uint d = 0; @@ -529,15 +800,26 @@ namespace Org.BouncyCastle.Math.Raw return (uint)(((int)d - 1) >> 31); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint EqualToZero(int len, ReadOnlySpan<uint> x) + { + uint d = 0; + for (int i = 0; i < len; ++i) + { + d |= x[i]; + } + d = (d >> 1) | (d & 1); + return (uint)(((int)d - 1) >> 31); + } +#endif + public static uint[] FromBigInteger(int bits, BigInteger x) { - if (bits < 1) - throw new ArgumentException(); + int len = GetLengthForBits(bits); + if (x.SignValue < 0 || x.BitLength > bits) throw new ArgumentException(); - int len = (bits + 31) >> 5; - Debug.Assert(len > 0); uint[] z = Create(len); // NOTE: Use a fixed number of loop iterations @@ -550,15 +832,33 @@ namespace Org.BouncyCastle.Math.Raw return z; } - public static ulong[] FromBigInteger64(int bits, BigInteger x) +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void FromBigInteger(int bits, BigInteger x, Span<uint> z) { - if (bits < 1) + int len = GetLengthForBits(bits); + + if (x.SignValue < 0 || x.BitLength > bits) + throw new ArgumentException(); + if (z.Length < len) throw new ArgumentException(); + + // NOTE: Use a fixed number of loop iterations + z[0] = (uint)x.IntValue; + for (int i = 1; i < len; ++i) + { + x = x.ShiftRight(32); + z[i] = (uint)x.IntValue; + } + } +#endif + + public static ulong[] FromBigInteger64(int bits, BigInteger x) + { + int len = GetLengthForBits64(bits); + if (x.SignValue < 0 || x.BitLength > bits) throw new ArgumentException(); - int len = (bits + 63) >> 6; - Debug.Assert(len > 0); ulong[] z = Create64(len); // NOTE: Use a fixed number of loop iterations @@ -571,21 +871,70 @@ namespace Org.BouncyCastle.Math.Raw return z; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void FromBigInteger64(int bits, BigInteger x, Span<ulong> z) + { + int len = GetLengthForBits64(bits); + + if (x.SignValue < 0 || x.BitLength > bits) + throw new ArgumentException(); + if (z.Length < len) + throw new ArgumentException(); + + // NOTE: Use a fixed number of loop iterations + z[0] = (ulong)x.LongValue; + for (int i = 1; i < len; ++i) + { + x = x.ShiftRight(64); + z[i] = (ulong)x.LongValue; + } + } +#endif + public static uint GetBit(uint[] x, int bit) { if (bit == 0) - { return x[0] & 1; - } + int w = bit >> 5; if (w < 0 || w >= x.Length) - { return 0; - } + int b = bit & 31; return (x[w] >> b) & 1; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint GetBit(ReadOnlySpan<uint> x, int bit) + { + if (bit == 0) + return x[0] & 1; + + int w = bit >> 5; + if (w < 0 || w >= x.Length) + return 0; + + int b = bit & 31; + return (x[w] >> b) & 1; + } +#endif + + public static int GetLengthForBits(int bits) + { + if (bits < 1) + throw new ArgumentException(); + + return (int)(((uint)bits + 31) >> 5); + } + + public static int GetLengthForBits64(int bits) + { + if (bits < 1) + throw new ArgumentException(); + + return (int)(((uint)bits + 63) >> 6); + } + public static bool Gte(int len, uint[] x, uint[] y) { for (int i = len - 1; i >= 0; --i) @@ -619,14 +968,46 @@ namespace Org.BouncyCastle.Math.Raw for (int i = 0; i < len; ++i) { if (++z[i] != uint.MinValue) + return 0; + } + return 1; + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint Inc(int len, Span<uint> z) + { + for (int i = 0; i < len; ++i) + { + if (++z[i] != uint.MinValue) + return 0; + } + return 1; + } +#endif + + public static uint Inc(int len, uint[] x, uint[] z) + { + int i = 0; + while (i < len) + { + uint c = x[i] + 1; + z[i] = c; + ++i; + if (c != 0) { + while (i < len) + { + z[i] = x[i]; + ++i; + } return 0; } } return 1; } - public static uint Inc(int len, uint[] x, uint[] z) +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint Inc(int len, ReadOnlySpan<uint> x, Span<uint> z) { int i = 0; while (i < len) @@ -646,6 +1027,7 @@ namespace Org.BouncyCastle.Math.Raw } return 1; } +#endif public static uint IncAt(int len, uint[] z, int zPos) { @@ -653,9 +1035,7 @@ namespace Org.BouncyCastle.Math.Raw for (int i = zPos; i < len; ++i) { if (++z[i] != uint.MinValue) - { return 0; - } } return 1; } @@ -666,44 +1046,79 @@ namespace Org.BouncyCastle.Math.Raw for (int i = zPos; i < len; ++i) { if (++z[zOff + i] != uint.MinValue) - { return 0; - } } return 1; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint IncAt(int len, Span<uint> z, int zPos) + { + Debug.Assert(zPos <= len); + for (int i = zPos; i < len; ++i) + { + if (++z[i] != uint.MinValue) + return 0; + } + return 1; + } +#endif + public static bool IsOne(int len, uint[] x) { if (x[0] != 1) - { return false; + + for (int i = 1; i < len; ++i) + { + if (x[i] != 0) + return false; } + return true; + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static bool IsOne(int len, ReadOnlySpan<uint> x) + { + if (x[0] != 1) + return false; + for (int i = 1; i < len; ++i) { if (x[i] != 0) - { return false; - } } return true; } +#endif public static bool IsZero(int len, uint[] x) { if (x[0] != 0) - { return false; + + for (int i = 1; i < len; ++i) + { + if (x[i] != 0) + return false; } + return true; + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static bool IsZero(int len, ReadOnlySpan<uint> x) + { + if (x[0] != 0) + return false; + for (int i = 1; i < len; ++i) { if (x[i] != 0) - { return false; - } } return true; } +#endif public static int LessThan(int len, uint[] x, uint[] y) { @@ -763,6 +1178,18 @@ namespace Org.BouncyCastle.Math.Raw } } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Mul(int len, ReadOnlySpan<uint> x, ReadOnlySpan<uint> y, Span<uint> zz) + { + zz[len] = MulWord(len, x[0], y, zz); + + for (int i = 1; i < len; ++i) + { + zz[i + len] = MulWordAddTo(len, x[i], y, zz[i..]); + } + } +#endif + public static void Mul(uint[] x, int xOff, int xLen, uint[] y, int yOff, int yLen, uint[] zz, int zzOff) { zz[zzOff + yLen] = MulWord(yLen, x[xOff], y, yOff, zz, zzOff); @@ -773,6 +1200,19 @@ namespace Org.BouncyCastle.Math.Raw } } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Mul(ReadOnlySpan<uint> x, ReadOnlySpan<uint> y, Span<uint> zz) + { + int xLen = x.Length, yLen = y.Length; + zz[yLen] = MulWord(yLen, x[0], y, zz); + + for (int i = 1; i < xLen; ++i) + { + zz[i + yLen] = MulWordAddTo(yLen, x[i], y, zz[i..]); + } + } +#endif + public static uint MulAddTo(int len, uint[] x, uint[] y, uint[] zz) { ulong zc = 0; @@ -800,9 +1240,24 @@ namespace Org.BouncyCastle.Math.Raw return (uint)zc; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint MulAddTo(int len, ReadOnlySpan<uint> x, ReadOnlySpan<uint> y, Span<uint> zz) + { + ulong zc = 0; + for (int i = 0; i < len; ++i) + { + zc += MulWordAddTo(len, x[i], y, zz[i..]) & M; + zc += zz[i + len] & M; + zz[i + len] = (uint)zc; + zc >>= 32; + } + return (uint)zc; + } +#endif + public static uint Mul31BothAdd(int len, uint a, uint[] x, uint b, uint[] y, uint[] z, int zOff) { - ulong c = 0, aVal = (ulong)a, bVal = (ulong)b; + ulong c = 0, aVal = a, bVal = b; int i = 0; do { @@ -814,9 +1269,26 @@ namespace Org.BouncyCastle.Math.Raw return (uint)c; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint Mul31BothAdd(int len, uint a, ReadOnlySpan<uint> x, uint b, ReadOnlySpan<uint> y, + Span<uint> z) + { + ulong c = 0, aVal = a, bVal = b; + int i = 0; + do + { + c += aVal * x[i] + bVal * y[i] + z[i]; + z[i] = (uint)c; + c >>= 32; + } + while (++i < len); + return (uint)c; + } +#endif + public static uint MulWord(int len, uint x, uint[] y, uint[] z) { - ulong c = 0, xVal = (ulong)x; + ulong c = 0, xVal = x; int i = 0; do { @@ -830,7 +1302,7 @@ namespace Org.BouncyCastle.Math.Raw public static uint MulWord(int len, uint x, uint[] y, int yOff, uint[] z, int zOff) { - ulong c = 0, xVal = (ulong)x; + ulong c = 0, xVal = x; int i = 0; do { @@ -842,9 +1314,25 @@ namespace Org.BouncyCastle.Math.Raw return (uint)c; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint MulWord(int len, uint x, ReadOnlySpan<uint> y, Span<uint> z) + { + ulong c = 0, xVal = x; + int i = 0; + do + { + c += xVal * y[i]; + z[i] = (uint)c; + c >>= 32; + } + while (++i < len); + return (uint)c; + } +#endif + public static uint MulWordAddTo(int len, uint x, uint[] y, int yOff, uint[] z, int zOff) { - ulong c = 0, xVal = (ulong)x; + ulong c = 0, xVal = x; int i = 0; do { @@ -856,22 +1344,56 @@ namespace Org.BouncyCastle.Math.Raw return (uint)c; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint MulWordAddTo(int len, uint x, ReadOnlySpan<uint> y, Span<uint> z) + { + ulong c = 0, xVal = x; + int i = 0; + do + { + c += xVal * y[i] + z[i]; + z[i] = (uint)c; + c >>= 32; + } + while (++i < len); + return (uint)c; + } +#endif + public static uint MulWordDwordAddAt(int len, uint x, ulong y, uint[] z, int zPos) { Debug.Assert(zPos <= (len - 3)); - ulong c = 0, xVal = (ulong)x; + ulong c = 0, xVal = x; c += xVal * (uint)y + z[zPos + 0]; z[zPos + 0] = (uint)c; c >>= 32; c += xVal * (y >> 32) + z[zPos + 1]; z[zPos + 1] = (uint)c; c >>= 32; - c += (ulong)z[zPos + 2]; + c += z[zPos + 2]; z[zPos + 2] = (uint)c; c >>= 32; return c == 0 ? 0 : IncAt(len, z, zPos + 3); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint MulWordDwordAddAt(int len, uint x, ulong y, Span<uint> z, int zPos) + { + Debug.Assert(zPos <= (len - 3)); + ulong c = 0, xVal = x; + c += xVal * (uint)y + z[zPos + 0]; + z[zPos + 0] = (uint)c; + c >>= 32; + c += xVal * (y >> 32) + z[zPos + 1]; + z[zPos + 1] = (uint)c; + c >>= 32; + c += z[zPos + 2]; + z[zPos + 2] = (uint)c; + c >>= 32; + return c == 0 ? 0 : IncAt(len, z, zPos + 3); + } +#endif + public static uint ShiftDownBit(int len, uint[] z, uint c) { int i = len; @@ -884,31 +1406,31 @@ namespace Org.BouncyCastle.Math.Raw return c << 31; } -#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER - public static uint ShiftDownBit(int len, Span<uint> z, uint c) + public static uint ShiftDownBit(int len, uint[] z, int zOff, uint c) { int i = len; while (--i >= 0) { - uint next = z[i]; - z[i] = (next >> 1) | (c << 31); + uint next = z[zOff + i]; + z[zOff + i] = (next >> 1) | (c << 31); c = next; } return c << 31; } -#endif - public static uint ShiftDownBit(int len, uint[] z, int zOff, uint c) +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint ShiftDownBit(int len, Span<uint> z, uint c) { int i = len; while (--i >= 0) { - uint next = z[zOff + i]; - z[zOff + i] = (next >> 1) | (c << 31); + uint next = z[i]; + z[i] = (next >> 1) | (c << 31); c = next; } return c << 31; } +#endif public static uint ShiftDownBit(int len, uint[] x, uint c, uint[] z) { @@ -934,6 +1456,20 @@ namespace Org.BouncyCastle.Math.Raw return c << 31; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint ShiftDownBit(int len, ReadOnlySpan<uint> x, uint c, Span<uint> z) + { + int i = len; + while (--i >= 0) + { + uint next = x[i]; + z[i] = (next >> 1) | (c << 31); + c = next; + } + return c << 31; + } +#endif + public static uint ShiftDownBits(int len, uint[] z, int bits, uint c) { Debug.Assert(bits > 0 && bits < 32); @@ -960,6 +1496,21 @@ namespace Org.BouncyCastle.Math.Raw return c << -bits; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint ShiftDownBits(int len, Span<uint> z, int bits, uint c) + { + Debug.Assert(bits > 0 && bits < 32); + int i = len; + while (--i >= 0) + { + uint next = z[i]; + z[i] = (next >> bits) | (c << -bits); + c = next; + } + return c << -bits; + } +#endif + public static uint ShiftDownBits(int len, uint[] x, int bits, uint c, uint[] z) { Debug.Assert(bits > 0 && bits < 32); @@ -986,6 +1537,21 @@ namespace Org.BouncyCastle.Math.Raw return c << -bits; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint ShiftDownBits(int len, ReadOnlySpan<uint> x, int bits, uint c, Span<uint> z) + { + Debug.Assert(bits > 0 && bits < 32); + int i = len; + while (--i >= 0) + { + uint next = x[i]; + z[i] = (next >> bits) | (c << -bits); + c = next; + } + return c << -bits; + } +#endif + public static uint ShiftDownWord(int len, uint[] z, uint c) { int i = len; @@ -998,6 +1564,20 @@ namespace Org.BouncyCastle.Math.Raw return c; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint ShiftDownWord(int len, Span<uint> z, uint c) + { + int i = len; + while (--i >= 0) + { + uint next = z[i]; + z[i] = c; + c = next; + } + return c; + } +#endif + public static uint ShiftUpBit(int len, uint[] z, uint c) { for (int i = 0; i < len; ++i) @@ -1020,6 +1600,19 @@ namespace Org.BouncyCastle.Math.Raw return c >> 31; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint ShiftUpBit(int len, Span<uint> z, uint c) + { + for (int i = 0; i < len; ++i) + { + uint next = z[i]; + z[i] = (next << 1) | (c >> 31); + c = next; + } + return c >> 31; + } +#endif + public static uint ShiftUpBit(int len, uint[] x, uint c, uint[] z) { for (int i = 0; i < len; ++i) @@ -1042,6 +1635,30 @@ namespace Org.BouncyCastle.Math.Raw return c >> 31; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint ShiftUpBit(int len, ReadOnlySpan<uint> x, uint c, Span<uint> z) + { + for (int i = 0; i < len; ++i) + { + uint next = x[i]; + z[i] = (next << 1) | (c >> 31); + c = next; + } + return c >> 31; + } +#endif + + public static ulong ShiftUpBit64(int len, ulong[] x, ulong c, ulong[] z) + { + for (int i = 0; i < len; ++i) + { + ulong next = x[i]; + z[i] = (next << 1) | (c >> 63); + c = next; + } + return c >> 63; + } + public static ulong ShiftUpBit64(int len, ulong[] x, int xOff, ulong c, ulong[] z, int zOff) { for (int i = 0; i < len; ++i) @@ -1053,6 +1670,19 @@ namespace Org.BouncyCastle.Math.Raw return c >> 63; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static ulong ShiftUpBit64(int len, ReadOnlySpan<ulong> x, ulong c, Span<ulong> z) + { + for (int i = 0; i < len; ++i) + { + ulong next = x[i]; + z[i] = (next << 1) | (c >> 63); + c = next; + } + return c >> 63; + } +#endif + public static uint ShiftUpBits(int len, uint[] z, int bits, uint c) { Debug.Assert(bits > 0 && bits < 32); @@ -1077,17 +1707,19 @@ namespace Org.BouncyCastle.Math.Raw return c >> -bits; } - public static ulong ShiftUpBits64(int len, ulong[] z, int zOff, int bits, ulong c) +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint ShiftUpBits(int len, Span<uint> z, int bits, uint c) { - Debug.Assert(bits > 0 && bits < 64); + Debug.Assert(bits > 0 && bits < 32); for (int i = 0; i < len; ++i) { - ulong next = z[zOff + i]; - z[zOff + i] = (next << bits) | (c >> -bits); + uint next = z[i]; + z[i] = (next << bits) | (c >> -bits); c = next; } return c >> -bits; } +#endif public static uint ShiftUpBits(int len, uint[] x, int bits, uint c, uint[] z) { @@ -1113,6 +1745,70 @@ namespace Org.BouncyCastle.Math.Raw return c >> -bits; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint ShiftUpBits(int len, ReadOnlySpan<uint> x, int bits, uint c, Span<uint> z) + { + Debug.Assert(bits > 0 && bits < 32); + for (int i = 0; i < len; ++i) + { + uint next = x[i]; + z[i] = (next << bits) | (c >> -bits); + c = next; + } + return c >> -bits; + } +#endif + + public static ulong ShiftUpBits64(int len, ulong[] z, int bits, ulong c) + { + Debug.Assert(bits > 0 && bits < 64); + for (int i = 0; i < len; ++i) + { + ulong next = z[i]; + z[i] = (next << bits) | (c >> -bits); + c = next; + } + return c >> -bits; + } + + public static ulong ShiftUpBits64(int len, ulong[] z, int zOff, int bits, ulong c) + { + Debug.Assert(bits > 0 && bits < 64); + for (int i = 0; i < len; ++i) + { + ulong next = z[zOff + i]; + z[zOff + i] = (next << bits) | (c >> -bits); + c = next; + } + return c >> -bits; + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static ulong ShiftUpBits64(int len, Span<ulong> z, int bits, ulong c) + { + Debug.Assert(bits > 0 && bits < 64); + for (int i = 0; i < len; ++i) + { + ulong next = z[i]; + z[i] = (next << bits) | (c >> -bits); + c = next; + } + return c >> -bits; + } +#endif + + public static ulong ShiftUpBits64(int len, ulong[] x, int bits, ulong c, ulong[] z) + { + Debug.Assert(bits > 0 && bits < 64); + for (int i = 0; i < len; ++i) + { + ulong next = x[i]; + z[i] = (next << bits) | (c >> -bits); + c = next; + } + return c >> -bits; + } + public static ulong ShiftUpBits64(int len, ulong[] x, int xOff, int bits, ulong c, ulong[] z, int zOff) { Debug.Assert(bits > 0 && bits < 64); @@ -1125,6 +1821,20 @@ namespace Org.BouncyCastle.Math.Raw return c >> -bits; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static ulong ShiftUpBits64(int len, ReadOnlySpan<ulong> x, int bits, ulong c, Span<ulong> z) + { + Debug.Assert(bits > 0 && bits < 64); + for (int i = 0; i < len; ++i) + { + ulong next = x[i]; + z[i] = (next << bits) | (c >> -bits); + c = next; + } + return c >> -bits; + } +#endif + public static void Square(int len, uint[] x, uint[] zz) { int extLen = len << 1; @@ -1187,6 +1897,39 @@ namespace Org.BouncyCastle.Math.Raw ShiftUpBit(extLen, zz, zzOff, x[xOff] << 31); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Square(int len, ReadOnlySpan<uint> x, Span<uint> zz) + { + int extLen = len << 1; + uint c = 0; + int j = len, k = extLen; + do + { + ulong xVal = (ulong)x[--j]; + ulong p = xVal * xVal; + zz[--k] = (c << 31) | (uint)(p >> 33); + zz[--k] = (uint)(p >> 1); + c = (uint)p; + } + while (j > 0); + + ulong d = 0UL; + int zzPos = 2; + + for (int i = 1; i < len; ++i) + { + d += SquareWordAddTo(x, i, zz); + d += zz[zzPos]; + zz[zzPos++] = (uint)d; d >>= 32; + d += zz[zzPos]; + zz[zzPos++] = (uint)d; d >>= 32; + } + Debug.Assert(0UL == d); + + ShiftUpBit(extLen, zz, x[0] << 31); + } +#endif + public static uint SquareWordAddTo(uint[] x, int xPos, uint[] z) { ulong c = 0, xVal = (ulong)x[xPos]; @@ -1216,6 +1959,22 @@ namespace Org.BouncyCastle.Math.Raw return (uint)c; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint SquareWordAddTo(ReadOnlySpan<uint> x, int xPos, Span<uint> z) + { + ulong c = 0, xVal = x[xPos]; + int i = 0; + do + { + c += xVal * x[i] + z[xPos + i]; + z[xPos + i] = (uint)c; + c >>= 32; + } + while (++i < xPos); + return (uint)c; + } +#endif + public static int Sub(int len, uint[] x, uint[] y, uint[] z) { long c = 0; @@ -1239,6 +1998,21 @@ namespace Org.BouncyCastle.Math.Raw } return (int)c; } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static int Sub(int len, ReadOnlySpan<uint> x, ReadOnlySpan<uint> y, Span<uint> z) + { + long c = 0; + for (int i = 0; i < len; ++i) + { + c += (long)x[i] - y[i]; + z[i] = (uint)c; + c >>= 32; + } + return (int)c; + } +#endif + public static int Sub33At(int len, uint x, uint[] z, int zPos) { Debug.Assert(zPos <= (len - 2)); @@ -1263,6 +2037,20 @@ namespace Org.BouncyCastle.Math.Raw return c == 0 ? 0 : DecAt(len, z, zOff, zPos + 2); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static int Sub33At(int len, uint x, Span<uint> z, int zPos) + { + Debug.Assert(zPos <= (len - 2)); + long c = (long)z[zPos + 0] - x; + z[zPos + 0] = (uint)c; + c >>= 32; + c += (long)z[zPos + 1] - 1; + z[zPos + 1] = (uint)c; + c >>= 32; + return c == 0 ? 0 : DecAt(len, z, zPos + 2); + } +#endif + public static int Sub33From(int len, uint x, uint[] z) { long c = (long)z[0] - x; @@ -1285,6 +2073,19 @@ namespace Org.BouncyCastle.Math.Raw return c == 0 ? 0 : DecAt(len, z, zOff, 2); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static int Sub33From(int len, uint x, Span<uint> z) + { + long c = (long)z[0] - x; + z[0] = (uint)c; + c >>= 32; + c += (long)z[1] - 1; + z[1] = (uint)c; + c >>= 32; + return c == 0 ? 0 : DecAt(len, z, 2); + } +#endif + public static int SubBothFrom(int len, uint[] x, uint[] y, uint[] z) { long c = 0; @@ -1309,13 +2110,27 @@ namespace Org.BouncyCastle.Math.Raw return (int)c; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static int SubBothFrom(int len, ReadOnlySpan<uint> x, ReadOnlySpan<uint> y, Span<uint> z) + { + long c = 0; + for (int i = 0; i < len; ++i) + { + c += (long)z[i] - x[i] - y[i]; + z[i] = (uint)c; + c >>= 32; + } + return (int)c; + } +#endif + public static int SubDWordAt(int len, ulong x, uint[] z, int zPos) { Debug.Assert(zPos <= (len - 2)); - long c = (long)z[zPos + 0] - (long)(x & M); + long c = z[zPos + 0] - (long)(x & M); z[zPos + 0] = (uint)c; c >>= 32; - c += (long)z[zPos + 1] - (long)(x >> 32); + c += z[zPos + 1] - (long)(x >> 32); z[zPos + 1] = (uint)c; c >>= 32; return c == 0 ? 0 : DecAt(len, z, zPos + 2); @@ -1324,21 +2139,35 @@ namespace Org.BouncyCastle.Math.Raw public static int SubDWordAt(int len, ulong x, uint[] z, int zOff, int zPos) { Debug.Assert(zPos <= (len - 2)); - long c = (long)z[zOff + zPos] - (long)(x & M); + long c = z[zOff + zPos] - (long)(x & M); z[zOff + zPos] = (uint)c; c >>= 32; - c += (long)z[zOff + zPos + 1] - (long)(x >> 32); + c += z[zOff + zPos + 1] - (long)(x >> 32); z[zOff + zPos + 1] = (uint)c; c >>= 32; - return c == 0 ? 0 : DecAt(len, z, zOff, zPos + 2); + return c == 0 ? 0 : DecAt(len, z, zOff, zPos + 2); + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static int SubDWordAt(int len, ulong x, Span<uint> z, int zPos) + { + Debug.Assert(zPos <= (len - 2)); + long c = z[zPos + 0] - (long)(x & M); + z[zPos + 0] = (uint)c; + c >>= 32; + c += z[zPos + 1] - (long)(x >> 32); + z[zPos + 1] = (uint)c; + c >>= 32; + return c == 0 ? 0 : DecAt(len, z, zPos + 2); } +#endif public static int SubDWordFrom(int len, ulong x, uint[] z) { - long c = (long)z[0] - (long)(x & M); + long c = z[0] - (long)(x & M); z[0] = (uint)c; c >>= 32; - c += (long)z[1] - (long)(x >> 32); + c += z[1] - (long)(x >> 32); z[1] = (uint)c; c >>= 32; return c == 0 ? 0 : DecAt(len, z, 2); @@ -1346,15 +2175,28 @@ namespace Org.BouncyCastle.Math.Raw public static int SubDWordFrom(int len, ulong x, uint[] z, int zOff) { - long c = (long)z[zOff + 0] - (long)(x & M); + long c = z[zOff + 0] - (long)(x & M); z[zOff + 0] = (uint)c; c >>= 32; - c += (long)z[zOff + 1] - (long)(x >> 32); + c += z[zOff + 1] - (long)(x >> 32); z[zOff + 1] = (uint)c; c >>= 32; return c == 0 ? 0 : DecAt(len, z, zOff, 2); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static int SubDWordFrom(int len, ulong x, Span<uint> z) + { + long c = z[0] - (long)(x & M); + z[0] = (uint)c; + c >>= 32; + c += z[1] - (long)(x >> 32); + z[1] = (uint)c; + c >>= 32; + return c == 0 ? 0 : DecAt(len, z, 2); + } +#endif + public static int SubFrom(int len, uint[] x, uint[] z) { long c = 0; @@ -1379,6 +2221,20 @@ namespace Org.BouncyCastle.Math.Raw return (int)c; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static int SubFrom(int len, ReadOnlySpan<uint> x, Span<uint> z) + { + long c = 0; + for (int i = 0; i < len; ++i) + { + c += (long)z[i] - x[i]; + z[i] = (uint)c; + c >>= 32; + } + return (int)c; + } +#endif + public static int SubWordAt(int len, uint x, uint[] z, int zPos) { Debug.Assert(zPos <= (len - 1)); @@ -1397,6 +2253,17 @@ namespace Org.BouncyCastle.Math.Raw return c == 0 ? 0 : DecAt(len, z, zOff, zPos + 1); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static int SubWordAt(int len, uint x, Span<uint> z, int zPos) + { + Debug.Assert(zPos <= (len - 1)); + long c = (long)z[zPos] - x; + z[zPos] = (uint)c; + c >>= 32; + return c == 0 ? 0 : DecAt(len, z, zPos + 1); + } +#endif + public static int SubWordFrom(int len, uint x, uint[] z) { long c = (long)z[0] - x; @@ -1413,28 +2280,69 @@ namespace Org.BouncyCastle.Math.Raw return c == 0 ? 0 : DecAt(len, z, zOff, 1); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static int SubWordFrom(int len, uint x, Span<uint> z) + { + long c = (long)z[0] - x; + z[0] = (uint)c; + c >>= 32; + return c == 0 ? 0 : DecAt(len, z, 1); + } +#endif + public static BigInteger ToBigInteger(int len, uint[] x) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + return ToBigInteger(len, x.AsSpan()); +#else byte[] bs = new byte[len << 2]; - for (int i = 0; i < len; ++i) + int xPos = len, bsPos = 0; + while (--xPos >= 0) { - uint x_i = x[i]; - if (x_i != 0) - { - Pack.UInt32_To_BE(x_i, bs, (len - 1 - i) << 2); - } + Pack.UInt32_To_BE(x[xPos], bs, bsPos); + bsPos += 4; + } + return new BigInteger(1, bs); +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static BigInteger ToBigInteger(int len, ReadOnlySpan<uint> x) + { + int bsLen = len << 2; + Span<byte> bs = bsLen <= 512 + ? stackalloc byte[bsLen] + : new byte[bsLen]; + + int xPos = len; + Span<byte> t = bs; + while (--xPos >= 0) + { + Pack.UInt32_To_BE(x[xPos], t); + t = t[4..]; } return new BigInteger(1, bs); } +#endif public static void Zero(int len, uint[] z) { for (int i = 0; i < len; ++i) { - z[i] = 0; + z[i] = 0U; } } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Zero(int len, Span<uint> z) + { + for (int i = 0; i < len; ++i) + { + z[i] = 0U; + } + } +#endif + public static void Zero64(int len, ulong[] z) { for (int i = 0; i < len; ++i) @@ -1442,5 +2350,15 @@ namespace Org.BouncyCastle.Math.Raw z[i] = 0UL; } } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Zero64(int len, Span<ulong> z) + { + for (int i = 0; i < len; ++i) + { + z[i] = 0UL; + } + } +#endif } } diff --git a/crypto/src/util/BigIntegers.cs b/crypto/src/util/BigIntegers.cs index 44c9e32a7..93dc8e8eb 100644 --- a/crypto/src/util/BigIntegers.cs +++ b/crypto/src/util/BigIntegers.cs @@ -168,13 +168,31 @@ namespace Org.BouncyCastle.Utilities } int bits = M.BitLength; - uint[] m = Nat.FromBigInteger(bits, M); - uint[] x = Nat.FromBigInteger(bits, X); - int len = m.Length; - uint[] z = Nat.Create(len); - if (0 == Mod.ModOddInverse(m, x, z)) - throw new ArithmeticException("BigInteger not invertible"); - return Nat.ToBigInteger(len, z); + +#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]; + Span<uint> z = stackalloc uint[len]; + Nat.FromBigInteger(bits, M, m); + Nat.FromBigInteger(bits, X, x); + if (0 == Mod.ModOddInverse(m, x, z)) + throw new ArithmeticException("BigInteger not invertible"); + return Nat.ToBigInteger(len, z); + } + else +#endif + { + uint[] m = Nat.FromBigInteger(bits, M); + uint[] x = Nat.FromBigInteger(bits, X); + int len = m.Length; + uint[] z = Nat.Create(len); + if (0 == Mod.ModOddInverse(m, x, z)) + throw new ArithmeticException("BigInteger not invertible"); + return Nat.ToBigInteger(len, z); + } } public static BigInteger ModOddInverseVar(BigInteger M, BigInteger X) @@ -193,13 +211,31 @@ namespace Org.BouncyCastle.Utilities return One; int bits = M.BitLength; - uint[] m = Nat.FromBigInteger(bits, M); - uint[] x = Nat.FromBigInteger(bits, X); - int len = m.Length; - uint[] z = Nat.Create(len); - if (!Mod.ModOddInverseVar(m, x, z)) - throw new ArithmeticException("BigInteger not invertible"); - return Nat.ToBigInteger(len, z); + +#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]; + Span<uint> z = stackalloc uint[len]; + Nat.FromBigInteger(bits, M, m); + Nat.FromBigInteger(bits, X, x); + if (!Mod.ModOddInverseVar(m, x, z)) + throw new ArithmeticException("BigInteger not invertible"); + return Nat.ToBigInteger(len, z); + } + else +#endif + { + uint[] m = Nat.FromBigInteger(bits, M); + uint[] x = Nat.FromBigInteger(bits, X); + int len = m.Length; + uint[] z = Nat.Create(len); + if (!Mod.ModOddInverseVar(m, x, z)) + throw new ArithmeticException("BigInteger not invertible"); + return Nat.ToBigInteger(len, z); + } } public static int GetByteLength(BigInteger n) |