From 7703a5bf539150be76f2cf330080c5ef0c597707 Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Sun, 13 Nov 2022 18:15:26 +0700 Subject: BigInteger direct conversion to Span --- .../src/crypto/parameters/DHPublicKeyParameters.cs | 16 +- crypto/src/math/BigInteger.cs | 177 +++++++++++++++++++-- crypto/src/math/ec/ECAlgorithms.cs | 19 ++- .../math/ec/multiplier/FixedPointCombMultiplier.cs | 13 +- crypto/src/math/raw/Nat.cs | 31 ++-- 5 files changed, 217 insertions(+), 39 deletions(-) diff --git a/crypto/src/crypto/parameters/DHPublicKeyParameters.cs b/crypto/src/crypto/parameters/DHPublicKeyParameters.cs index 19e732b89..a72f247a5 100644 --- a/crypto/src/crypto/parameters/DHPublicKeyParameters.cs +++ b/crypto/src/crypto/parameters/DHPublicKeyParameters.cs @@ -122,12 +122,24 @@ namespace Org.BouncyCastle.Crypto.Parameters //return BigInteger.One.Equals(b) ? (1 - (r & 2)) : 0; int bitLength = b.BitLength; + int len = Nat.GetLengthForBits(bitLength); + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + Span A = len <= 64 + ? stackalloc uint[len] + : new uint[len]; + Nat.FromBigInteger(bitLength, a, A); + Span B = len <= 64 + ? stackalloc uint[len] + : new uint[len]; + Nat.FromBigInteger(bitLength, b, B); +#else uint[] A = Nat.FromBigInteger(bitLength, a); uint[] B = Nat.FromBigInteger(bitLength, b); +#endif int r = 0; - int len = B.Length; for (;;) { while (A[0] == 0) @@ -150,7 +162,7 @@ namespace Org.BouncyCastle.Crypto.Parameters if (cmp < 0) { r ^= (int)(A[0] & B[0]); - uint[] t = A; A = B; B = t; + var t = A; A = B; B = t; } while (A[len - 1] == 0) diff --git a/crypto/src/math/BigInteger.cs b/crypto/src/math/BigInteger.cs index 53537f0c8..44d6ee20a 100644 --- a/crypto/src/math/BigInteger.cs +++ b/crypto/src/math/BigInteger.cs @@ -7,6 +7,7 @@ using System.Numerics; #endif using System.Runtime.Serialization; using System.Text; + using Org.BouncyCastle.Crypto.Utilities; using Org.BouncyCastle.Security; using Org.BouncyCastle.Utilities; @@ -235,11 +236,18 @@ namespace Org.BouncyCastle.Math this.nBitLength = -1; } - private static int GetByteLength(int nBits) + private static int GetBytesLength(int nBits) { return (nBits + BitsPerByte - 1) / BitsPerByte; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static int GetIntsLength(int nBits) + { + return (nBits + BitsPerInt - 1) / BitsPerInt; + } +#endif + public static BigInteger Arbitrary(int sizeInBits) { return new BigInteger(sizeInBits, SecureRandom.ArbitraryRandom); @@ -711,7 +719,7 @@ namespace Org.BouncyCastle.Math return; } - int nBytes = GetByteLength(sizeInBits); + int nBytes = GetBytesLength(sizeInBits); #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER Span b = nBytes <= 512 @@ -749,7 +757,7 @@ namespace Org.BouncyCastle.Math return; } - int nBytes = GetByteLength(bitLength); + int nBytes = GetBytesLength(bitLength); #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER Span b = nBytes <= 512 @@ -3175,14 +3183,26 @@ namespace Org.BouncyCastle.Math public int GetLengthofByteArray() { - return GetByteLength(BitLength + 1); + return GetBytesLength(BitLength + 1); } public int GetLengthofByteArrayUnsigned() { - return GetByteLength(sign < 0 ? BitLength + 1 : BitLength); + return GetBytesLength(sign < 0 ? BitLength + 1 : BitLength); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public int GetLengthofUInt32Array() + { + return GetIntsLength(BitLength + 1); + } + + public int GetLengthofUInt32ArrayUnsigned() + { + return GetIntsLength(sign < 0 ? BitLength + 1 : BitLength); + } +#endif + public byte[] ToByteArray() { return ToByteArray(false); @@ -3193,6 +3213,18 @@ namespace Org.BouncyCastle.Math { ToByteArray(false, output); } + + [CLSCompliant(false)] + public void ToUInt32ArrayBigEndian(Span output) + { + ToUInt32ArrayBigEndian(false, output); + } + + [CLSCompliant(false)] + public void ToUInt32ArrayLittleEndian(Span output) + { + ToUInt32ArrayLittleEndian(false, output); + } #endif public byte[] ToByteArrayUnsigned() @@ -3205,6 +3237,18 @@ namespace Org.BouncyCastle.Math { ToByteArray(true, output); } + + [CLSCompliant(false)] + public void ToUInt32ArrayBigEndianUnsigned(Span output) + { + ToUInt32ArrayBigEndian(true, output); + } + + [CLSCompliant(false)] + public void ToUInt32ArrayLittleEndianUnsigned(Span output) + { + ToUInt32ArrayLittleEndian(true, output); + } #endif private byte[] ToByteArray(bool unsigned) @@ -3216,7 +3260,7 @@ namespace Org.BouncyCastle.Math ? BitLength : BitLength + 1; - int nBytes = GetByteLength(nBits); + int nBytes = GetBytesLength(nBits); byte[] bytes = new byte[nBytes]; int magIndex = magnitude.Length; @@ -3239,6 +3283,11 @@ namespace Org.BouncyCastle.Math } bytes[--bytesIndex] = (byte) lastMag; + Debug.Assert((bytesIndex & 1) == bytesIndex); + //if (bytesIndex != 0) + //{ + // bytes[0] = 0; + //} } else // sign < 0 { @@ -3272,8 +3321,8 @@ namespace Org.BouncyCastle.Math } bytes[--bytesIndex] = (byte) ~lastMag; - - if (bytesIndex > 0) + Debug.Assert((bytesIndex & 1) == bytesIndex); + if (bytesIndex != 0) { bytes[--bytesIndex] = byte.MaxValue; } @@ -3296,7 +3345,7 @@ namespace Org.BouncyCastle.Math int nBits = (unsigned && sign > 0) ? BitLength : BitLength + 1; - int nBytes = GetByteLength(nBits); + int nBytes = GetBytesLength(nBits); if (nBytes > output.Length) throw new ArgumentException("insufficient space", nameof(output)); @@ -3320,6 +3369,11 @@ namespace Org.BouncyCastle.Math } output[--bytesIndex] = (byte)lastMag; + Debug.Assert((bytesIndex & 1) == bytesIndex); + if (bytesIndex != 0) + { + output[0] = 0; + } } else // sign < 0 { @@ -3353,13 +3407,114 @@ namespace Org.BouncyCastle.Math } output[--bytesIndex] = (byte)~lastMag; - - if (bytesIndex > 0) + Debug.Assert((bytesIndex & 1) == bytesIndex); + if (bytesIndex != 0) { output[--bytesIndex] = byte.MaxValue; } } } + + private void ToUInt32ArrayBigEndian(bool unsigned, Span output) + { + if (sign == 0) + { + if (!unsigned) + { + output[0] = uint.MinValue; + } + return; + } + + int nBits = (unsigned && sign > 0) ? BitLength : BitLength + 1; + + int nInts = GetIntsLength(nBits); + if (nInts > output.Length) + throw new ArgumentException("insufficient space", nameof(output)); + + int magIndex = magnitude.Length; + int intsIndex = nInts; + + if (sign > 0) + { + while (magIndex > 0) + { + output[--intsIndex] = (uint)magnitude[--magIndex]; + } + + Debug.Assert((intsIndex & 1) == intsIndex); + if (intsIndex != 0) + { + output[0] = uint.MinValue; + } + } + else // sign < 0 + { + ulong cc = 1UL; + while (magIndex > 0) + { + cc += ~(uint)magnitude[--magIndex]; + output[--intsIndex] = (uint)cc; cc >>= 32; + } + Debug.Assert(cc == 0UL); + + Debug.Assert((intsIndex & 1) == intsIndex); + if (intsIndex != 0) + { + output[--intsIndex] = uint.MaxValue; + } + } + } + + private void ToUInt32ArrayLittleEndian(bool unsigned, Span output) + { + if (sign == 0) + { + if (!unsigned) + { + output[0] = uint.MinValue; + } + return; + } + + int nBits = (unsigned && sign > 0) ? BitLength : BitLength + 1; + + int nInts = GetIntsLength(nBits); + if (nInts > output.Length) + throw new ArgumentException("insufficient space", nameof(output)); + + int magIndex = magnitude.Length; + + if (sign > 0) + { + for (int intsIndex = 0; intsIndex < magnitude.Length; ++intsIndex) + { + output[intsIndex] = (uint)magnitude[--magIndex]; + } + + if (nInts > magnitude.Length) + { + Debug.Assert(nInts == magnitude.Length + 1); + output[magnitude.Length] = uint.MinValue; + } + } + else // sign < 0 + { + ulong cc = 1UL; + for (int intsIndex = 0; intsIndex < magnitude.Length; ++intsIndex) + { + cc += ~(uint)magnitude[--magIndex]; + output[intsIndex] = (uint)cc; cc >>= 32; + } + Debug.Assert(cc == 0UL); + + if (nInts > magnitude.Length) + { + Debug.Assert(nInts == magnitude.Length + 1); + output[magnitude.Length] = uint.MaxValue; + } + } + } #endif public override string ToString() diff --git a/crypto/src/math/ec/ECAlgorithms.cs b/crypto/src/math/ec/ECAlgorithms.cs index 3059ca3b3..15204e4ed 100644 --- a/crypto/src/math/ec/ECAlgorithms.cs +++ b/crypto/src/math/ec/ECAlgorithms.cs @@ -569,14 +569,25 @@ namespace Org.BouncyCastle.Math.EC } int width = widthP; - int d = (combSize + width - 1) / width; - - ECPoint R = c.Infinity; - int fullComb = d * width; + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + int len = Nat.GetLengthForBits(fullComb); + Span K = len <= 64 + ? stackalloc uint[len] + : new uint[len]; + Nat.FromBigInteger(fullComb, k, K); + Span L = len <= 64 + ? stackalloc uint[len] + : new uint[len]; + Nat.FromBigInteger(fullComb, l, L); +#else uint[] K = Nat.FromBigInteger(fullComb, k); uint[] L = Nat.FromBigInteger(fullComb, l); +#endif + + ECPoint R = c.Infinity; int top = fullComb - 1; for (int i = 0; i < d; ++i) diff --git a/crypto/src/math/ec/multiplier/FixedPointCombMultiplier.cs b/crypto/src/math/ec/multiplier/FixedPointCombMultiplier.cs index 6449e1d8b..049c36f11 100644 --- a/crypto/src/math/ec/multiplier/FixedPointCombMultiplier.cs +++ b/crypto/src/math/ec/multiplier/FixedPointCombMultiplier.cs @@ -26,22 +26,21 @@ namespace Org.BouncyCastle.Math.EC.Multiplier FixedPointPreCompInfo info = FixedPointUtilities.Precompute(p); ECLookupTable lookupTable = info.LookupTable; int width = info.Width; - int d = (size + width - 1) / width; int fullComb = d * width; - ECPoint R = c.Infinity; - #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER - int KLen = Nat.GetLengthForBits(fullComb); - Span K = KLen <= 32 - ? stackalloc uint[KLen] - : new uint[KLen]; + int len = Nat.GetLengthForBits(fullComb); + Span K = len <= 64 + ? stackalloc uint[len] + : new uint[len]; Nat.FromBigInteger(fullComb, k, K); #else uint[] K = Nat.FromBigInteger(fullComb, k); #endif + ECPoint R = c.Infinity; + for (int i = 1; i <= d; ++i) { uint secretIndex = 0; diff --git a/crypto/src/math/raw/Nat.cs b/crypto/src/math/raw/Nat.cs index b3b670954..4600f247f 100644 --- a/crypto/src/math/raw/Nat.cs +++ b/crypto/src/math/raw/Nat.cs @@ -818,13 +818,17 @@ namespace Org.BouncyCastle.Math.Raw public static uint[] FromBigInteger(int bits, BigInteger x) { - int len = GetLengthForBits(bits); - if (x.SignValue < 0 || x.BitLength > bits) throw new ArgumentException(); + int len = GetLengthForBits(bits); uint[] z = Create(len); +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + int xLen = x.GetLengthofUInt32ArrayUnsigned(); + x.ToUInt32ArrayLittleEndianUnsigned(z.AsSpan(0, xLen)); + //z.AsSpan(xLen).Fill(0x00); +#else // NOTE: Use a fixed number of loop iterations z[0] = (uint)x.IntValue; for (int i = 1; i < len; ++i) @@ -832,36 +836,33 @@ namespace Org.BouncyCastle.Math.Raw x = x.ShiftRight(32); z[i] = (uint)x.IntValue; } +#endif + return z; } #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER public static void FromBigInteger(int bits, BigInteger x, Span z) { - int len = GetLengthForBits(bits); - if (x.SignValue < 0 || x.BitLength > bits) throw new ArgumentException(); + + int len = GetLengthForBits(bits); 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; - } + int xLen = x.GetLengthofUInt32ArrayUnsigned(); + x.ToUInt32ArrayLittleEndianUnsigned(z[..xLen]); + z[xLen..].Fill(0x00); } #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 = GetLengthForBits64(bits); ulong[] z = Create64(len); // NOTE: Use a fixed number of loop iterations @@ -877,10 +878,10 @@ namespace Org.BouncyCastle.Math.Raw #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER public static void FromBigInteger64(int bits, BigInteger x, Span z) { - int len = GetLengthForBits64(bits); - if (x.SignValue < 0 || x.BitLength > bits) throw new ArgumentException(); + + int len = GetLengthForBits64(bits); if (z.Length < len) throw new ArgumentException(); -- cgit 1.4.1