diff options
| -rw-r--r-- | crypto/src/math/BigInteger.cs | 160 |
1 files changed, 68 insertions, 92 deletions
diff --git a/crypto/src/math/BigInteger.cs b/crypto/src/math/BigInteger.cs index caf78843e..53537f0c8 100644 --- a/crypto/src/math/BigInteger.cs +++ b/crypto/src/math/BigInteger.cs @@ -3,11 +3,11 @@ using System.Collections.Generic; using System.Diagnostics; using System.Globalization; #if NETCOREAPP3_0_OR_GREATER -using System.Runtime.Intrinsics.X86; +using System.Numerics; #endif using System.Runtime.Serialization; using System.Text; -using Org.BouncyCastle.Crypto.Prng; +using Org.BouncyCastle.Crypto.Utilities; using Org.BouncyCastle.Security; using Org.BouncyCastle.Utilities; @@ -15,6 +15,7 @@ namespace Org.BouncyCastle.Math { [Serializable] public sealed class BigInteger + : IComparable<BigInteger>, IEquatable<BigInteger> { // The first few odd primes /* @@ -139,6 +140,7 @@ namespace Org.BouncyCastle.Math public static readonly BigInteger Four; public static readonly BigInteger Ten; +#if !NETCOREAPP3_0_OR_GREATER private readonly static byte[] BitLengthTable = { 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, @@ -158,6 +160,7 @@ namespace Org.BouncyCastle.Math 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 }; +#endif // TODO Parse radix-2 64 bits at a time and radix-8 63 bits at a time private const int chunk2 = 1, chunk8 = 1, chunk10 = 19, chunk16 = 16; @@ -224,15 +227,12 @@ namespace Org.BouncyCastle.Math private int nBits = -1; // cache BitCount() value [NonSerialized] private int nBitLength = -1; // cache BitLength() value - [NonSerialized] - private int mQuote = 0; // -m^(-1) mod b, b = 2^32 (see Montgomery mult.), 0 when uninitialised [OnDeserialized] private void OnDeserialized(StreamingContext context) { this.nBits = -1; this.nBitLength = -1; - this.mQuote = 0; } private static int GetByteLength(int nBits) @@ -778,7 +778,6 @@ namespace Org.BouncyCastle.Math this.magnitude = MakeMagnitude(b); this.nBits = -1; - this.mQuote = 0; if (certainty < 1) break; @@ -979,12 +978,8 @@ namespace Org.BouncyCastle.Math public static int BitCnt(int i) { #if NETCOREAPP3_0_OR_GREATER - if (Popcnt.IsSupported) - { - return (int)Popcnt.PopCount((uint)i); - } -#endif - + return BitOperations.PopCount((uint)i); +#else uint u = (uint)i; u = u - ((u >> 1) & 0x55555555); u = (u & 0x33333333) + ((u >> 2) & 0x33333333); @@ -993,6 +988,7 @@ namespace Org.BouncyCastle.Math u += (u >> 16); u &= 0x3f; return (int)u; +#endif } private static int CalcBitLength(int sign, int indx, int[] mag) @@ -1047,18 +1043,20 @@ namespace Org.BouncyCastle.Math } } - // - // BitLen(value) is the number of bits in value. - // - private static int BitLen(int w) + private static int BitLen(byte b) { #if NETCOREAPP3_0_OR_GREATER - if (Lzcnt.IsSupported) - { - return 32 - (int)Lzcnt.LeadingZeroCount((uint)w); - } + return 32 - BitOperations.LeadingZeroCount((uint)b); +#else + return BitLengthTable[b]; #endif + } + private static int BitLen(int w) + { +#if NETCOREAPP3_0_OR_GREATER + return 32 - BitOperations.LeadingZeroCount((uint)w); +#else uint v = (uint)w; uint t = v >> 24; if (t != 0) @@ -1070,6 +1068,7 @@ namespace Org.BouncyCastle.Math if (t != 0) return 8 + BitLengthTable[t]; return BitLengthTable[v]; +#endif } private bool QuickPow2Check() @@ -1077,10 +1076,18 @@ namespace Org.BouncyCastle.Math return sign > 0 && nBits == 1; } - public int CompareTo( - object obj) + public int CompareTo(BigInteger other) { - return CompareTo((BigInteger)obj); + if (other == null) + return 1; + + return sign < other.sign + ? -1 + : sign > other.sign + ? 1 + : sign == 0 + ? 0 + : sign * CompareNoLeadingZeroes(0, magnitude, 0, other.magnitude); } /** @@ -1133,15 +1140,6 @@ namespace Org.BouncyCastle.Math return 0; } - public int CompareTo( - BigInteger value) - { - return sign < value.sign ? -1 - : sign > value.sign ? 1 - : sign == 0 ? 0 - : sign * CompareNoLeadingZeroes(0, magnitude, 0, value.magnitude); - } - /** * return z = x / y - done in place (z value preserved, x contains the * remainder) @@ -1332,19 +1330,26 @@ namespace Org.BouncyCastle.Math return biggies; } - public override bool Equals( - object obj) + public override bool Equals(object obj) { if (obj == this) return true; - - BigInteger biggie = obj as BigInteger; - if (biggie == null) + if (!(obj is BigInteger biggie)) return false; return sign == biggie.sign && IsEqualMagnitude(biggie); } + public bool Equals(BigInteger other) + { + if (other == this) + return true; + if (other == null) + return false; + + return sign == other.sign && IsEqualMagnitude(other); + } + private bool IsEqualMagnitude(BigInteger x) { int[] xMag = x.magnitude; @@ -1754,7 +1759,7 @@ namespace Org.BouncyCastle.Math // if (F.Equals(One)) // { // BigInteger half = m.Add(One).ShiftRight(1); -// BigInteger halfK = half.ModPow(BigInteger.ValueOf(k), m); +// BigInteger halfK = half.ModPow(ValueOf(k), m); // return B.Multiply(halfK).Mod(m); // } // @@ -1801,13 +1806,13 @@ namespace Org.BouncyCastle.Math int pow = m.BitLength - 1; - long inv64 = ModInverse64(LongValue); + long inv64 = (long)Raw.Mod.Inverse64((ulong)LongValue); if (pow < 64) { inv64 &= ((1L << pow) - 1); } - BigInteger x = BigInteger.ValueOf(inv64); + BigInteger x = ValueOf(inv64); if (pow > 64) { @@ -1831,33 +1836,6 @@ namespace Org.BouncyCastle.Math return x; } - private static int ModInverse32(int d) - { - // Newton's method with initial estimate "correct to 4 bits" - Debug.Assert((d & 1) != 0); - int x = d + (((d + 1) & 4) << 1); // d.x == 1 mod 2**4 - Debug.Assert(((d * x) & 15) == 1); - x *= 2 - d * x; // d.x == 1 mod 2**8 - x *= 2 - d * x; // d.x == 1 mod 2**16 - x *= 2 - d * x; // d.x == 1 mod 2**32 - Debug.Assert(d * x == 1); - return x; - } - - private static long ModInverse64(long d) - { - // Newton's method with initial estimate "correct to 4 bits" - Debug.Assert((d & 1L) != 0); - long x = d + (((d + 1L) & 4L) << 1); // d.x == 1 mod 2**4 - Debug.Assert(((d * x) & 15L) == 1L); - x *= 2 - d * x; // d.x == 1 mod 2**8 - x *= 2 - d * x; // d.x == 1 mod 2**16 - x *= 2 - d * x; // d.x == 1 mod 2**32 - x *= 2 - d * x; // d.x == 1 mod 2**64 - Debug.Assert(d * x == 1L); - return x; - } - /** * Calculate the numbers u1, u2, and u3 such that: * @@ -1991,7 +1969,7 @@ namespace Org.BouncyCastle.Math { mult = window & 0xFF; - int bits = lastZeroes + BitLengthTable[mult]; + int bits = lastZeroes + BitLen((byte)mult); for (int j = 0; j < bits; ++j) { y = ReduceBarrett(y.Square(), m, mr, yu); @@ -2116,7 +2094,7 @@ namespace Org.BouncyCastle.Math { mult = window & 0xFF; - int bits = lastZeroes + BitLengthTable[mult]; + int bits = lastZeroes + BitLen((byte)mult); for (int j = 0; j < bits; ++j) { SquareMonty(yAccum, yVal, m.magnitude, mDash, smallMontyModulus); @@ -2201,11 +2179,19 @@ namespace Org.BouncyCastle.Math private static int CreateWindowEntry(int mult, int zeroes) { + Debug.Assert(mult > 0); + +#if NETCOREAPP3_0_OR_GREATER + int tz = BitOperations.TrailingZeroCount(mult); + mult >>= tz; + zeroes += tz; +#else while ((mult & 1) == 0) { mult >>= 1; ++zeroes; } +#endif return mult | (zeroes << 8); } @@ -2324,18 +2310,13 @@ namespace Org.BouncyCastle.Math */ private int GetMQuote() { - if (mQuote != 0) - { - return mQuote; // already calculated - } - Debug.Assert(this.sign > 0); int d = -magnitude[magnitude.Length - 1]; Debug.Assert((d & 1) != 0); - return mQuote = ModInverse32(d); + return (int)Raw.Mod.Inverse32((uint)d); } private static void MontgomeryReduce(int[] x, int[] m, uint mDash) // mDash = -m^(-1) mod b @@ -3246,10 +3227,8 @@ namespace Org.BouncyCastle.Math while (magIndex > 1) { uint mag = (uint) magnitude[--magIndex]; - bytes[--bytesIndex] = (byte) mag; - bytes[--bytesIndex] = (byte)(mag >> 8); - bytes[--bytesIndex] = (byte)(mag >> 16); - bytes[--bytesIndex] = (byte)(mag >> 24); + bytesIndex -= 4; + Pack.UInt32_To_BE(mag, bytes, bytesIndex); } uint lastMag = (uint) magnitude[0]; @@ -3274,10 +3253,8 @@ namespace Org.BouncyCastle.Math carry = (++mag == uint.MinValue); } - bytes[--bytesIndex] = (byte) mag; - bytes[--bytesIndex] = (byte)(mag >> 8); - bytes[--bytesIndex] = (byte)(mag >> 16); - bytes[--bytesIndex] = (byte)(mag >> 24); + bytesIndex -= 4; + Pack.UInt32_To_BE(mag, bytes, bytesIndex); } uint lastMag = (uint) magnitude[0]; @@ -3331,10 +3308,8 @@ namespace Org.BouncyCastle.Math while (magIndex > 1) { uint mag = (uint) magnitude[--magIndex]; - output[--bytesIndex] = (byte) mag; - output[--bytesIndex] = (byte)(mag >> 8); - output[--bytesIndex] = (byte)(mag >> 16); - output[--bytesIndex] = (byte)(mag >> 24); + bytesIndex -= 4; + Pack.UInt32_To_BE(mag, output[bytesIndex..]); } uint lastMag = (uint)magnitude[0]; @@ -3359,10 +3334,8 @@ namespace Org.BouncyCastle.Math carry = (++mag == uint.MinValue); } - output[--bytesIndex] = (byte) mag; - output[--bytesIndex] = (byte)(mag >> 8); - output[--bytesIndex] = (byte)(mag >> 16); - output[--bytesIndex] = (byte)(mag >> 24); + bytesIndex -= 4; + Pack.UInt32_To_BE(mag, output[bytesIndex..]); } uint lastMag = (uint)magnitude[0]; @@ -3613,6 +3586,9 @@ namespace Org.BouncyCastle.Math offset += 32; } +#if NETCOREAPP3_0_OR_GREATER + offset += BitOperations.TrailingZeroCount(word); +#else while ((word & 0xFF) == 0) { word >>= 8; @@ -3625,6 +3601,7 @@ namespace Org.BouncyCastle.Math ++offset; } +#endif return offset; } @@ -3816,7 +3793,6 @@ namespace Org.BouncyCastle.Math int[] mag = (int[]) this.magnitude.Clone(); mag[mag.Length - 1 - (n >> 5)] ^= (1 << (n & 31)); // Flip bit - //mag[mag.Length - 1 - (n / 32)] ^= (1 << (n % 32)); return new BigInteger(this.sign, mag, false); } } |