diff options
Diffstat (limited to 'crypto/src/math')
40 files changed, 4546 insertions, 381 deletions
diff --git a/crypto/src/math/BigInteger.cs b/crypto/src/math/BigInteger.cs index d6c43cdc0..caf78843e 100644 --- a/crypto/src/math/BigInteger.cs +++ b/crypto/src/math/BigInteger.cs @@ -7,14 +7,14 @@ using System.Runtime.Intrinsics.X86; #endif using System.Runtime.Serialization; using System.Text; - +using Org.BouncyCastle.Crypto.Prng; using Org.BouncyCastle.Security; using Org.BouncyCastle.Utilities; namespace Org.BouncyCastle.Math { [Serializable] - public class BigInteger + public sealed class BigInteger { // The first few odd primes /* @@ -163,8 +163,6 @@ namespace Org.BouncyCastle.Math private const int chunk2 = 1, chunk8 = 1, chunk10 = 19, chunk16 = 16; private static readonly BigInteger radix2, radix2E, radix8, radix8E, radix10, radix10E, radix16, radix16E; - private static readonly SecureRandom RandomSource = new SecureRandom(); - /* * These are the threshold bit-lengths (of an exponent) where we increase the window size. * They are calculated according to the expected savings in multiplications. @@ -237,15 +235,14 @@ namespace Org.BouncyCastle.Math this.mQuote = 0; } - private static int GetByteLength( - int nBits) + private static int GetByteLength(int nBits) { return (nBits + BitsPerByte - 1) / BitsPerByte; } public static BigInteger Arbitrary(int sizeInBits) { - return new BigInteger(sizeInBits, RandomSource); + return new BigInteger(sizeInBits, SecureRandom.ArbitraryRandom); } private BigInteger( @@ -510,7 +507,14 @@ namespace Org.BouncyCastle.Math else { int numBytes = end - iBval; + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + Span<byte> inverse = numBytes <= 512 + ? stackalloc byte[numBytes] + : new byte[numBytes]; +#else byte[] inverse = new byte[numBytes]; +#endif int index = 0; while (index < numBytes) @@ -527,7 +531,7 @@ namespace Org.BouncyCastle.Math inverse[index]++; - this.magnitude = MakeMagnitude(inverse, 0, inverse.Length); + this.magnitude = MakeMagnitude(inverse); } } else @@ -538,24 +542,26 @@ namespace Org.BouncyCastle.Math } } - private static int[] MakeMagnitude( - byte[] bytes, - int offset, - int length) + private static int[] MakeMagnitude(byte[] bytes) + { + return MakeMagnitude(bytes, 0, bytes.Length); + } + + private static int[] MakeMagnitude(byte[] bytes, int offset, int length) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + return MakeMagnitude(bytes.AsSpan(offset, length)); +#else int end = offset + length; // strip leading zeros int firstSignificant; - for (firstSignificant = offset; firstSignificant < end - && bytes[firstSignificant] == 0; firstSignificant++) + for (firstSignificant = offset; firstSignificant < end && bytes[firstSignificant] == 0; firstSignificant++) { } if (firstSignificant >= end) - { return ZeroMagnitude; - } int nInts = (end - firstSignificant + 3) / BytesPerInt; int bCount = (end - firstSignificant) % BytesPerInt; @@ -565,10 +571,59 @@ namespace Org.BouncyCastle.Math } if (nInts < 1) + return ZeroMagnitude; + + int[] mag = new int[nInts]; + + int v = 0; + int magnitudeIndex = 0; + for (int i = firstSignificant; i < end; ++i) + { + v <<= 8; + v |= bytes[i] & 0xff; + bCount--; + if (bCount <= 0) + { + mag[magnitudeIndex] = v; + magnitudeIndex++; + bCount = BytesPerInt; + v = 0; + } + } + + if (magnitudeIndex < mag.Length) { + mag[magnitudeIndex] = v; + } + + return mag; +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static int[] MakeMagnitude(ReadOnlySpan<byte> bytes) + { + int end = bytes.Length; + + // strip leading zeros + int firstSignificant; + for (firstSignificant = 0; firstSignificant < end && bytes[firstSignificant] == 0; firstSignificant++) + { + } + + if (firstSignificant >= end) return ZeroMagnitude; + + int nInts = (end - firstSignificant + 3) / BytesPerInt; + int bCount = (end - firstSignificant) % BytesPerInt; + if (bCount == 0) + { + bCount = BytesPerInt; } + if (nInts < 1) + return ZeroMagnitude; + int[] mag = new int[nInts]; int v = 0; @@ -594,19 +649,14 @@ namespace Org.BouncyCastle.Math return mag; } +#endif - public BigInteger( - int sign, - byte[] bytes) + public BigInteger(int sign, byte[] bytes) : this(sign, bytes, 0, bytes.Length) { } - public BigInteger( - int sign, - byte[] bytes, - int offset, - int length) + public BigInteger(int sign, byte[] bytes, int offset, int length) { if (sign < -1 || sign > 1) throw new FormatException("Invalid sign value"); @@ -624,6 +674,26 @@ namespace Org.BouncyCastle.Math } } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public BigInteger(int sign, ReadOnlySpan<byte> bytes) + { + if (sign < -1 || sign > 1) + throw new FormatException("Invalid sign value"); + + if (sign == 0) + { + this.sign = 0; + this.magnitude = ZeroMagnitude; + } + else + { + // copy bytes + this.magnitude = MakeMagnitude(bytes); + this.sign = this.magnitude.Length < 1 ? 0 : sign; + } + } +#endif + public BigInteger( int sizeInBits, Random random) @@ -642,14 +712,21 @@ namespace Org.BouncyCastle.Math } int nBytes = GetByteLength(sizeInBits); + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + Span<byte> b = nBytes <= 512 + ? stackalloc byte[nBytes] + : new byte[nBytes]; +#else byte[] b = new byte[nBytes]; +#endif random.NextBytes(b); // strip off any excess bits in the MSB int xBits = BitsPerByte * nBytes - sizeInBits; b[0] &= (byte)(255U >> xBits); - this.magnitude = MakeMagnitude(b, 0, b.Length); + this.magnitude = MakeMagnitude(b); this.sign = this.magnitude.Length < 1 ? 0 : 1; } @@ -673,7 +750,14 @@ namespace Org.BouncyCastle.Math } int nBytes = GetByteLength(bitLength); + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + Span<byte> b = nBytes <= 512 + ? stackalloc byte[nBytes] + : new byte[nBytes]; +#else byte[] b = new byte[nBytes]; +#endif int xBits = BitsPerByte * nBytes - bitLength; byte mask = (byte)(255U >> xBits); @@ -692,7 +776,7 @@ namespace Org.BouncyCastle.Math // ensure the trailing bit is 1 (i.e. must be odd) b[nBytes - 1] |= 1; - this.magnitude = MakeMagnitude(b, 0, b.Length); + this.magnitude = MakeMagnitude(b); this.nBits = -1; this.mQuote = 0; @@ -1374,7 +1458,7 @@ namespace Org.BouncyCastle.Math if (n.Equals(One)) return false; - return n.CheckProbablePrime(certainty, RandomSource, randomlySelected); + return n.CheckProbablePrime(certainty, SecureRandom.ArbitraryRandom, randomlySelected); } private bool CheckProbablePrime(int certainty, Random random, bool randomlySelected) @@ -2547,7 +2631,7 @@ namespace Org.BouncyCastle.Math BigInteger n = Inc().SetBit(0); - while (!n.CheckProbablePrime(100, RandomSource, false)) + while (!n.CheckProbablePrime(100, SecureRandom.ArbitraryRandom, false)) { n = n.Add(Two); } @@ -3108,18 +3192,41 @@ namespace Org.BouncyCastle.Math return Subtract(0, res, 0, lilMag); } + public int GetLengthofByteArray() + { + return GetByteLength(BitLength + 1); + } + + public int GetLengthofByteArrayUnsigned() + { + return GetByteLength(sign < 0 ? BitLength + 1 : BitLength); + } + public byte[] ToByteArray() { return ToByteArray(false); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public void ToByteArray(Span<byte> output) + { + ToByteArray(false, output); + } +#endif + public byte[] ToByteArrayUnsigned() { return ToByteArray(true); } - private byte[] ToByteArray( - bool unsigned) +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public void ToByteArrayUnsigned(Span<byte> output) + { + ToByteArray(true, output); + } +#endif + + private byte[] ToByteArray(bool unsigned) { if (sign == 0) return unsigned ? ZeroEncoding : new byte[1]; @@ -3198,6 +3305,90 @@ namespace Org.BouncyCastle.Math return bytes; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private void ToByteArray(bool unsigned, Span<byte> output) + { + if (sign == 0) + { + if (!unsigned) + { + output[0] = 0; + } + return; + } + + int nBits = (unsigned && sign > 0) ? BitLength : BitLength + 1; + + int nBytes = GetByteLength(nBits); + if (nBytes > output.Length) + throw new ArgumentException("insufficient space", nameof(output)); + + int magIndex = magnitude.Length; + int bytesIndex = nBytes; + + if (sign > 0) + { + 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); + } + + uint lastMag = (uint)magnitude[0]; + while (lastMag > byte.MaxValue) + { + output[--bytesIndex] = (byte)lastMag; + lastMag >>= 8; + } + + output[--bytesIndex] = (byte)lastMag; + } + else // sign < 0 + { + bool carry = true; + + while (magIndex > 1) + { + uint mag = ~((uint)magnitude[--magIndex]); + + if (carry) + { + carry = (++mag == uint.MinValue); + } + + output[--bytesIndex] = (byte) mag; + output[--bytesIndex] = (byte)(mag >> 8); + output[--bytesIndex] = (byte)(mag >> 16); + output[--bytesIndex] = (byte)(mag >> 24); + } + + uint lastMag = (uint)magnitude[0]; + + if (carry) + { + // Never wraps because magnitude[0] != 0 + --lastMag; + } + + while (lastMag > byte.MaxValue) + { + output[--bytesIndex] = (byte)~lastMag; + lastMag >>= 8; + } + + output[--bytesIndex] = (byte)~lastMag; + + if (bytesIndex > 0) + { + output[--bytesIndex] = byte.MaxValue; + } + } + } +#endif + public override string ToString() { return ToString(10); diff --git a/crypto/src/math/ec/ECAlgorithms.cs b/crypto/src/math/ec/ECAlgorithms.cs index 64e68fccc..3059ca3b3 100644 --- a/crypto/src/math/ec/ECAlgorithms.cs +++ b/crypto/src/math/ec/ECAlgorithms.cs @@ -213,9 +213,18 @@ namespace Org.BouncyCastle.Math.EC { ECCurve cp = p.Curve; if (!c.Equals(cp)) - throw new ArgumentException("Point must be on the same curve", "p"); - + throw new ArgumentException("Point must be on the same curve", nameof(p)); + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + int encodedLength = p.GetEncodedLength(false); + Span<byte> encoding = encodedLength <= 512 + ? stackalloc byte[encodedLength] + : new byte[encodedLength]; + p.EncodeTo(false, encoding); + return c.DecodePoint(encoding); +#else return c.DecodePoint(p.GetEncoded(false)); +#endif } internal static ECPoint ImplCheckResult(ECPoint p) diff --git a/crypto/src/math/ec/ECCurve.cs b/crypto/src/math/ec/ECCurve.cs index 38e05991e..b37d62721 100644 --- a/crypto/src/math/ec/ECCurve.cs +++ b/crypto/src/math/ec/ECCurve.cs @@ -436,67 +436,143 @@ namespace Org.BouncyCastle.Math.EC */ public virtual ECPoint DecodePoint(byte[] encoded) { - ECPoint p = null; +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + return DecodePoint(encoded.AsSpan()); +#else + ECPoint p; int expectedLength = (FieldSize + 7) / 8; byte type = encoded[0]; switch (type) { - case 0x00: // infinity - { - if (encoded.Length != 1) - throw new ArgumentException("Incorrect length for infinity encoding", "encoded"); + case 0x00: // infinity + { + if (encoded.Length != 1) + throw new ArgumentException("Incorrect length for infinity encoding", "encoded"); - p = Infinity; - break; - } + p = Infinity; + break; + } - case 0x02: // compressed - case 0x03: // compressed - { - if (encoded.Length != (expectedLength + 1)) - throw new ArgumentException("Incorrect length for compressed encoding", "encoded"); + case 0x02: // compressed + case 0x03: // compressed + { + if (encoded.Length != (expectedLength + 1)) + throw new ArgumentException("Incorrect length for compressed encoding", "encoded"); - int yTilde = type & 1; - BigInteger X = new BigInteger(1, encoded, 1, expectedLength); + int yTilde = type & 1; + BigInteger X = new BigInteger(1, encoded, 1, expectedLength); - p = DecompressPoint(yTilde, X); - if (!p.ImplIsValid(true, true)) - throw new ArgumentException("Invalid point"); + p = DecompressPoint(yTilde, X); + if (!p.ImplIsValid(true, true)) + throw new ArgumentException("Invalid point"); - break; - } + break; + } - case 0x04: // uncompressed - { - if (encoded.Length != (2 * expectedLength + 1)) - throw new ArgumentException("Incorrect length for uncompressed encoding", "encoded"); + case 0x04: // uncompressed + { + if (encoded.Length != (2 * expectedLength + 1)) + throw new ArgumentException("Incorrect length for uncompressed encoding", "encoded"); - BigInteger X = new BigInteger(1, encoded, 1, expectedLength); - BigInteger Y = new BigInteger(1, encoded, 1 + expectedLength, expectedLength); + BigInteger X = new BigInteger(1, encoded, 1, expectedLength); + BigInteger Y = new BigInteger(1, encoded, 1 + expectedLength, expectedLength); - p = ValidatePoint(X, Y); - break; - } + p = ValidatePoint(X, Y); + break; + } - case 0x06: // hybrid - case 0x07: // hybrid - { - if (encoded.Length != (2 * expectedLength + 1)) - throw new ArgumentException("Incorrect length for hybrid encoding", "encoded"); + case 0x06: // hybrid + case 0x07: // hybrid + { + if (encoded.Length != (2 * expectedLength + 1)) + throw new ArgumentException("Incorrect length for hybrid encoding", "encoded"); - BigInteger X = new BigInteger(1, encoded, 1, expectedLength); - BigInteger Y = new BigInteger(1, encoded, 1 + expectedLength, expectedLength); + BigInteger X = new BigInteger(1, encoded, 1, expectedLength); + BigInteger Y = new BigInteger(1, encoded, 1 + expectedLength, expectedLength); - if (Y.TestBit(0) != (type == 0x07)) - throw new ArgumentException("Inconsistent Y coordinate in hybrid encoding", "encoded"); + if (Y.TestBit(0) != (type == 0x07)) + throw new ArgumentException("Inconsistent Y coordinate in hybrid encoding", "encoded"); - p = ValidatePoint(X, Y); - break; - } + p = ValidatePoint(X, Y); + break; + } - default: - throw new FormatException("Invalid point encoding " + type); + default: + throw new FormatException("Invalid point encoding " + type); + } + + if (type != 0x00 && p.IsInfinity) + throw new ArgumentException("Invalid infinity encoding", "encoded"); + + return p; +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public virtual ECPoint DecodePoint(ReadOnlySpan<byte> encoded) + { + ECPoint p; + int expectedLength = (FieldSize + 7) / 8; + + byte type = encoded[0]; + switch (type) + { + case 0x00: // infinity + { + if (encoded.Length != 1) + throw new ArgumentException("Incorrect length for infinity encoding", "encoded"); + + p = Infinity; + break; + } + + case 0x02: // compressed + case 0x03: // compressed + { + if (encoded.Length != (expectedLength + 1)) + throw new ArgumentException("Incorrect length for compressed encoding", "encoded"); + + int yTilde = type & 1; + BigInteger X = new BigInteger(1, encoded[1..]); + + p = DecompressPoint(yTilde, X); + if (!p.ImplIsValid(true, true)) + throw new ArgumentException("Invalid point"); + + break; + } + + case 0x04: // uncompressed + { + if (encoded.Length != (2 * expectedLength + 1)) + throw new ArgumentException("Incorrect length for uncompressed encoding", "encoded"); + + BigInteger X = new BigInteger(1, encoded[1..(1 + expectedLength)]); + BigInteger Y = new BigInteger(1, encoded[(1 + expectedLength)..]); + + p = ValidatePoint(X, Y); + break; + } + + case 0x06: // hybrid + case 0x07: // hybrid + { + if (encoded.Length != (2 * expectedLength + 1)) + throw new ArgumentException("Incorrect length for hybrid encoding", "encoded"); + + BigInteger X = new BigInteger(1, encoded[1..(1 + expectedLength)]); + BigInteger Y = new BigInteger(1, encoded[(1 + expectedLength)..]); + + if (Y.TestBit(0) != (type == 0x07)) + throw new ArgumentException("Inconsistent Y coordinate in hybrid encoding", "encoded"); + + p = ValidatePoint(X, Y); + break; + } + + default: + throw new FormatException("Invalid point encoding " + type); } if (type != 0x00 && p.IsInfinity) @@ -504,6 +580,7 @@ namespace Org.BouncyCastle.Math.EC return p; } +#endif private class DefaultLookupTable : AbstractECLookupTable @@ -660,7 +737,6 @@ namespace Org.BouncyCastle.Math.EC private const int FP_DEFAULT_COORDS = COORD_JACOBIAN_MODIFIED; private static readonly HashSet<BigInteger> KnownQs = new HashSet<BigInteger>(); - private static readonly SecureRandom random = new SecureRandom(); protected readonly BigInteger m_q, m_r; protected readonly FpPoint m_infinity; @@ -694,7 +770,8 @@ namespace Org.BouncyCastle.Math.EC throw new ArgumentException("Fp q value out of range"); if (Primes.HasAnySmallFactors(q) || - !Primes.IsMRProbablePrime(q, random, GetNumberOfIterations(qBitLength, certainty))) + !Primes.IsMRProbablePrime(q, SecureRandom.ArbitraryRandom, + GetNumberOfIterations(qBitLength, certainty))) { throw new ArgumentException("Fp q value not prime"); } diff --git a/crypto/src/math/ec/ECFieldElement.cs b/crypto/src/math/ec/ECFieldElement.cs index a96556482..3afc843cd 100644 --- a/crypto/src/math/ec/ECFieldElement.cs +++ b/crypto/src/math/ec/ECFieldElement.cs @@ -96,8 +96,25 @@ namespace Org.BouncyCastle.Math.EC public virtual byte[] GetEncoded() { - return BigIntegers.AsUnsignedByteArray((FieldSize + 7) / 8, ToBigInteger()); + return BigIntegers.AsUnsignedByteArray(GetEncodedLength(), ToBigInteger()); } + + public virtual int GetEncodedLength() + { + return (FieldSize + 7) / 8; + } + + public virtual void EncodeTo(byte[] buf, int off) + { + BigIntegers.AsUnsignedByteArray(ToBigInteger(), buf, off, GetEncodedLength()); + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public virtual void EncodeTo(Span<byte> buf) + { + BigIntegers.AsUnsignedByteArray(ToBigInteger(), buf[..GetEncodedLength()]); + } +#endif } public abstract class AbstractFpFieldElement @@ -768,9 +785,9 @@ namespace Org.BouncyCastle.Math.EC LongArray ab = ax.Multiply(bx, m, ks); LongArray xy = xx.Multiply(yx, m, ks); - if (ab == ax || ab == bx) + if (LongArray.AreAliased(ref ab, ref ax) || LongArray.AreAliased(ref ab, ref bx)) { - ab = (LongArray)ab.Copy(); + ab = ab.Copy(); } ab.AddShiftedByWords(xy, 0); @@ -810,9 +827,9 @@ namespace Org.BouncyCastle.Math.EC LongArray aa = ax.Square(m, ks); LongArray xy = xx.Multiply(yx, m, ks); - if (aa == ax) + if (LongArray.AreAliased(ref aa, ref ax)) { - aa = (LongArray)aa.Copy(); + aa = aa.Copy(); } aa.AddShiftedByWords(xy, 0); diff --git a/crypto/src/math/ec/ECPoint.cs b/crypto/src/math/ec/ECPoint.cs index dcda5abfc..ee7cf9a92 100644 --- a/crypto/src/math/ec/ECPoint.cs +++ b/crypto/src/math/ec/ECPoint.cs @@ -12,8 +12,6 @@ namespace Org.BouncyCastle.Math.EC */ public abstract class ECPoint { - private static readonly SecureRandom Random = new SecureRandom(); - protected static ECFieldElement[] EMPTY_ZS = new ECFieldElement[0]; protected static ECFieldElement[] GetInitialZCoords(ECCurve curve) @@ -246,10 +244,7 @@ namespace Org.BouncyCastle.Math.EC * Any side-channel in the implementation of 'inverse' now only leaks information about * the value (z * b), and no longer reveals information about 'z' itself. */ - // TODO Add CryptoServicesRegistrar class and use here - //SecureRandom r = CryptoServicesRegistrar.GetSecureRandom(); - SecureRandom r = Random; - ECFieldElement b = m_curve.RandomFieldElementMult(r); + ECFieldElement b = m_curve.RandomFieldElementMult(SecureRandom.ArbitraryRandom); ECFieldElement zInv = z.Multiply(b).Invert().Multiply(b); return Normalize(zInv); } @@ -437,6 +432,14 @@ namespace Org.BouncyCastle.Math.EC public abstract byte[] GetEncoded(bool compressed); + public abstract int GetEncodedLength(bool compressed); + + public abstract void EncodeTo(bool compressed, byte[] buf, int off); + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public abstract void EncodeTo(bool compressed, Span<byte> buf); +#endif + protected internal abstract bool CompressionYTilde { get; } public abstract ECPoint Add(ECPoint b); @@ -560,6 +563,69 @@ namespace Org.BouncyCastle.Math.EC } } + public override int GetEncodedLength(bool compressed) + { + if (IsInfinity) + return 1; + + if (compressed) + return 1 + XCoord.GetEncodedLength(); + + return 1 + XCoord.GetEncodedLength() + YCoord.GetEncodedLength(); + } + + public override void EncodeTo(bool compressed, byte[] buf, int off) + { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + EncodeTo(compressed, buf.AsSpan(off)); +#else + if (IsInfinity) + { + buf[off] = 0x00; + return; + } + + ECPoint normed = Normalize(); + ECFieldElement X = normed.XCoord, Y = normed.YCoord; + + if (compressed) + { + buf[off] = (byte)(normed.CompressionYTilde ? 0x03 : 0x02); + X.EncodeTo(buf, off + 1); + return; + } + + buf[off] = 0x04; + X.EncodeTo(buf, off + 1); + Y.EncodeTo(buf, off + 1 + X.GetEncodedLength()); +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public override void EncodeTo(bool compressed, Span<byte> buf) + { + if (IsInfinity) + { + buf[0] = 0x00; + return; + } + + ECPoint normed = Normalize(); + ECFieldElement X = normed.XCoord, Y = normed.YCoord; + + if (compressed) + { + buf[0] = (byte)(normed.CompressionYTilde ? 0x03 : 0x02); + X.EncodeTo(buf[1..]); + return; + } + + buf[0] = 0x04; + X.EncodeTo(buf[1..]); + Y.EncodeTo(buf[(1 + X.GetEncodedLength())..]); + } +#endif + /** * Multiplies this <code>ECPoint</code> by the given number. * @param k The multiplicator. diff --git a/crypto/src/math/ec/LongArray.cs b/crypto/src/math/ec/LongArray.cs index 0cf32fd15..aa36de215 100644 --- a/crypto/src/math/ec/LongArray.cs +++ b/crypto/src/math/ec/LongArray.cs @@ -1,27 +1,32 @@ using System; using System.Text; - +using Org.BouncyCastle.Math.Raw; using Org.BouncyCastle.Utilities; namespace Org.BouncyCastle.Math.EC { - internal sealed class LongArray + internal struct LongArray { + internal static bool AreAliased(ref LongArray a, ref LongArray b) + { + return a.m_data == b.m_data; + } + // TODO make m fixed for the LongArray, and hence compute T once and for all private ulong[] m_data; - public LongArray(int intLen) + internal LongArray(int intLen) { m_data = new ulong[intLen]; } - public LongArray(ulong[] data) + internal LongArray(ulong[] data) { m_data = data; } - public LongArray(ulong[] data, int off, int len) + internal LongArray(ulong[] data, int off, int len) { if (off == 0 && len == data.Length) { @@ -34,16 +39,14 @@ namespace Org.BouncyCastle.Math.EC } } - public LongArray(BigInteger bigInt) + internal LongArray(BigInteger bigInt) { if (bigInt == null || bigInt.SignValue < 0) - { - throw new ArgumentException("invalid F2m field value", "bigInt"); - } + throw new ArgumentException("invalid F2m field value", nameof(bigInt)); if (bigInt.SignValue == 0) { - m_data = new ulong[]{ 0UL }; + m_data = new ulong[1]{ 0UL }; return; } @@ -93,51 +96,44 @@ namespace Org.BouncyCastle.Math.EC Array.Copy(m_data, 0, z, zOff, m_data.Length); } - public bool IsOne() + internal bool IsOne() { ulong[] a = m_data; int aLen = a.Length; if (aLen < 1 || a[0] != 1UL) - { return false; - } + for (int i = 1; i < aLen; ++i) { if (a[i] != 0UL) - { return false; - } } return true; } - public bool IsZero() + internal bool IsZero() { ulong[] a = m_data; for (int i = 0; i < a.Length; ++i) { if (a[i] != 0UL) - { return false; - } } return true; } - public int GetUsedLength() + internal int GetUsedLength() { return GetUsedLengthFrom(m_data.Length); } - public int GetUsedLengthFrom(int from) + internal int GetUsedLengthFrom(int from) { ulong[] a = m_data; from = System.Math.Min(from, a.Length); if (from < 1) - { return 0; - } // Check if first element will act as sentinel if (a[0] != 0UL) @@ -160,16 +156,15 @@ namespace Org.BouncyCastle.Math.EC return 0; } - public int Degree() + internal int Degree() { int i = m_data.Length; ulong w; do { if (i == 0) - { return 0; - } + w = m_data[--i]; } while (w == 0UL); @@ -184,9 +179,8 @@ namespace Org.BouncyCastle.Math.EC do { if (i == 0) - { return 0; - } + w = m_data[--i]; } while (w == 0); @@ -206,13 +200,11 @@ namespace Org.BouncyCastle.Math.EC return newInts; } - public BigInteger ToBigInteger() + internal BigInteger ToBigInteger() { int usedLen = GetUsedLength(); if (usedLen == 0) - { return BigInteger.Zero; - } ulong highestInt = m_data[usedLen - 1]; byte[] temp = new byte[8]; @@ -273,12 +265,10 @@ namespace Org.BouncyCastle.Math.EC return prev; } - public LongArray AddOne() + internal LongArray AddOne() { if (m_data.Length == 0) - { - return new LongArray(new ulong[]{ 1UL }); - } + return new LongArray(new ulong[1]{ 1UL }); int resultLen = System.Math.Max(1, GetUsedLength()); ulong[] data = ResizedData(resultLen); @@ -333,13 +323,11 @@ namespace Org.BouncyCastle.Math.EC return prev; } - public void AddShiftedByWords(LongArray other, int words) + internal void AddShiftedByWords(LongArray other, int words) { int otherUsedLen = other.GetUsedLength(); if (otherUsedLen == 0) - { return; - } int minLen = otherUsedLen + words; if (minLen > m_data.Length) @@ -352,18 +340,12 @@ namespace Org.BouncyCastle.Math.EC private static void Add(ulong[] x, int xOff, ulong[] y, int yOff, int count) { - for (int i = 0; i < count; ++i) - { - x[xOff + i] ^= y[yOff + i]; - } + Nat.XorTo64(count, y, yOff, x, xOff); } private static void Add(ulong[] x, int xOff, ulong[] y, int yOff, ulong[] z, int zOff, int count) { - for (int i = 0; i < count; ++i) - { - z[zOff + i] = x[xOff + i] ^ y[yOff + i]; - } + Nat.Xor64(count, x, xOff, y, yOff, z, zOff); } private static void AddBoth(ulong[] x, int xOff, ulong[] y1, int y1Off, ulong[] y2, int y2Off, int count) @@ -393,7 +375,7 @@ namespace Org.BouncyCastle.Math.EC } } - public bool TestBitZero() + internal bool TestBitZero() { return m_data.Length > 0 && (m_data[0] & 1UL) != 0; } @@ -439,21 +421,18 @@ namespace Org.BouncyCastle.Math.EC } } - public LongArray ModMultiplyLD(LongArray other, int m, int[] ks) + internal LongArray ModMultiplyLD(LongArray other, int m, int[] ks) { /* * Find out the degree of each argument and handle the zero cases */ int aDeg = Degree(); if (aDeg == 0) - { return this; - } + int bDeg = other.Degree(); if (bDeg == 0) - { return other; - } /* * Swap if necessary so that A is the smaller argument @@ -476,9 +455,7 @@ namespace Org.BouncyCastle.Math.EC { ulong a0 = A.m_data[0]; if (a0 == 1UL) - { return B; - } /* * Fast path for small A, with performance dependent only on the number of set bits @@ -571,21 +548,18 @@ namespace Org.BouncyCastle.Math.EC return ReduceResult(c, 0, cLen, m, ks); } - public LongArray ModMultiply(LongArray other, int m, int[] ks) + internal LongArray ModMultiply(LongArray other, int m, int[] ks) { /* * Find out the degree of each argument and handle the zero cases */ int aDeg = Degree(); if (aDeg == 0) - { return this; - } + int bDeg = other.Degree(); if (bDeg == 0) - { return other; - } /* * Swap if necessary so that A is the smaller argument @@ -608,9 +582,7 @@ namespace Org.BouncyCastle.Math.EC { ulong a0 = A.m_data[0]; if (a0 == 1UL) - { return B; - } /* * Fast path for small A, with performance dependent only on the number of set bits @@ -681,9 +653,8 @@ namespace Org.BouncyCastle.Math.EC uint v = (uint)aVal & MASK; aVal >>= 4; AddBoth(c, cOff, T0, ti[u], T1, ti[v], bMax); if (aVal == 0UL) - { break; - } + cOff += cLen; } } @@ -702,28 +673,25 @@ namespace Org.BouncyCastle.Math.EC return ReduceResult(c, 0, cLen, m, ks); } - //public LongArray ModReduce(int m, int[] ks) + //internal LongArray ModReduce(int m, int[] ks) //{ // ulong[] buf = Arrays.Clone(m_data); // int rLen = ReduceInPlace(buf, 0, buf.Length, m, ks); // return new LongArray(buf, 0, rLen); //} - public LongArray Multiply(LongArray other, int m, int[] ks) + internal LongArray Multiply(LongArray other, int m, int[] ks) { /* * Find out the degree of each argument and handle the zero cases */ int aDeg = Degree(); if (aDeg == 0) - { return this; - } + int bDeg = other.Degree(); if (bDeg == 0) - { return other; - } /* * Swap if necessary so that A is the smaller argument @@ -746,9 +714,7 @@ namespace Org.BouncyCastle.Math.EC { ulong a0 = A.m_data[0]; if (a0 == 1UL) - { return B; - } /* * Fast path for small A, with performance dependent only on the number of set bits @@ -820,9 +786,8 @@ namespace Org.BouncyCastle.Math.EC uint v = (uint)aVal & MASK; aVal >>= 4; AddBoth(c, cOff, T0, ti[u], T1, ti[v], bMax); if (aVal == 0UL) - { break; - } + cOff += cLen; } } @@ -842,7 +807,7 @@ namespace Org.BouncyCastle.Math.EC return new LongArray(c, 0, cLen); } - public void Reduce(int m, int[] ks) + internal void Reduce(int m, int[] ks) { ulong[] buf = m_data; int rLen = ReduceInPlace(buf, 0, buf.Length, m, ks); @@ -863,9 +828,7 @@ namespace Org.BouncyCastle.Math.EC { int mLen = (m + 63) >> 6; if (len < mLen) - { return len; - } int numBits = System.Math.Min(len << 6, (m << 1) - 1); // TODO use actual degree? int excessBits = (len << 6) - numBits; @@ -994,19 +957,19 @@ namespace Org.BouncyCastle.Math.EC } } - public LongArray ModSquare(int m, int[] ks) + internal LongArray ModSquare(int m, int[] ks) { int len = GetUsedLength(); if (len == 0) return this; ulong[] r = new ulong[len << 1]; - Raw.Interleave.Expand64To128(m_data, 0, len, r, 0); + Interleave.Expand64To128(m_data, 0, len, r, 0); return new LongArray(r, 0, ReduceInPlace(r, 0, r.Length, m, ks)); } - public LongArray ModSquareN(int n, int m, int[] ks) + internal LongArray ModSquareN(int n, int m, int[] ks) { int len = GetUsedLength(); if (len == 0) @@ -1018,21 +981,21 @@ namespace Org.BouncyCastle.Math.EC while (--n >= 0) { - Raw.Interleave.Expand64To128(r, 0, len); + Interleave.Expand64To128(r, 0, len, r, 0); len = ReduceInPlace(r, 0, r.Length, m, ks); } - + return new LongArray(r, 0, len); } - public LongArray Square(int m, int[] ks) + internal LongArray Square(int m, int[] ks) { int len = GetUsedLength(); if (len == 0) return this; ulong[] r = new ulong[len << 1]; - Raw.Interleave.Expand64To128(m_data, 0, len, r, 0); + Interleave.Expand64To128(m_data, 0, len, r, 0); return new LongArray(r, 0, r.Length); } @@ -1147,7 +1110,7 @@ namespace Org.BouncyCastle.Math.EC // return t4.ModMultiply(t1, m, ks); // } - public LongArray ModInverse(int m, int[] ks) + internal LongArray ModInverse(int m, int[] ks) { /* * Fermat's Little Theorem @@ -1188,16 +1151,13 @@ namespace Org.BouncyCastle.Math.EC */ int uzDegree = Degree(); if (uzDegree == 0) - { throw new InvalidOperationException(); - } + if (uzDegree == 1) - { return this; - } // u(z) := a(z) - LongArray uz = (LongArray)Copy(); + LongArray uz = Copy(); int t = (m + 63) >> 6; @@ -1237,9 +1197,7 @@ namespace Org.BouncyCastle.Math.EC int duv2 = uv[b].DegreeFrom(duv1); if (duv2 == 0) - { return gg[1 - b]; - } { int dgg2 = ggDeg[1 - b]; @@ -1263,26 +1221,25 @@ namespace Org.BouncyCastle.Math.EC public override bool Equals(object obj) { - return Equals(obj as LongArray); + if (obj is LongArray longArray) + return Equals(ref longArray); + + return false; } - public bool Equals(LongArray other) + internal bool Equals(ref LongArray other) { - if (this == other) + if (AreAliased(ref this, ref other)) return true; - if (null == other) - return false; + int usedLen = GetUsedLength(); if (other.GetUsedLength() != usedLen) - { return false; - } + for (int i = 0; i < usedLen; i++) { if (m_data[i] != other.m_data[i]) - { return false; - } } return true; } @@ -1311,9 +1268,7 @@ namespace Org.BouncyCastle.Math.EC { int i = GetUsedLength(); if (i == 0) - { return "0"; - } StringBuilder sb = new StringBuilder(i * 64); sb.Append(Convert.ToString((long)m_data[--i], 2)); diff --git a/crypto/src/math/ec/custom/gm/SM2P256V1FieldElement.cs b/crypto/src/math/ec/custom/gm/SM2P256V1FieldElement.cs index 25cb24932..e3de6c594 100644 --- a/crypto/src/math/ec/custom/gm/SM2P256V1FieldElement.cs +++ b/crypto/src/math/ec/custom/gm/SM2P256V1FieldElement.cs @@ -115,7 +115,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.GM public override ECFieldElement Invert() { - //return new SM2P256V1FieldElement(ToBigInteger().ModInverse(Q)); uint[] z = Nat256.Create(); SM2P256V1Field.Inv(x, z); return new SM2P256V1FieldElement(z); diff --git a/crypto/src/math/ec/custom/sec/SecP128R1FieldElement.cs b/crypto/src/math/ec/custom/sec/SecP128R1FieldElement.cs index e9235c2f3..1db449442 100644 --- a/crypto/src/math/ec/custom/sec/SecP128R1FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecP128R1FieldElement.cs @@ -115,7 +115,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public override ECFieldElement Invert() { - // return new SecP128R1FieldElement(toBigInteger().modInverse(Q)); uint[] z = Nat128.Create(); SecP128R1Field.Inv(x, z); return new SecP128R1FieldElement(z); diff --git a/crypto/src/math/ec/custom/sec/SecP160R1FieldElement.cs b/crypto/src/math/ec/custom/sec/SecP160R1FieldElement.cs index 4876fafa9..a4307cbaf 100644 --- a/crypto/src/math/ec/custom/sec/SecP160R1FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecP160R1FieldElement.cs @@ -115,7 +115,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public override ECFieldElement Invert() { - // return new SecP160R1FieldElement(ToBigInteger().modInverse(Q)); uint[] z = Nat160.Create(); SecP160R1Field.Inv(x, z); return new SecP160R1FieldElement(z); diff --git a/crypto/src/math/ec/custom/sec/SecP160R2FieldElement.cs b/crypto/src/math/ec/custom/sec/SecP160R2FieldElement.cs index 795fe3b2e..9237c0778 100644 --- a/crypto/src/math/ec/custom/sec/SecP160R2FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecP160R2FieldElement.cs @@ -115,7 +115,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public override ECFieldElement Invert() { - // return new SecP160R2FieldElement(ToBigInteger().modInverse(Q)); uint[] z = Nat160.Create(); SecP160R2Field.Inv(x, z); return new SecP160R2FieldElement(z); diff --git a/crypto/src/math/ec/custom/sec/SecP192K1FieldElement.cs b/crypto/src/math/ec/custom/sec/SecP192K1FieldElement.cs index c933ffc8d..a37bc1539 100644 --- a/crypto/src/math/ec/custom/sec/SecP192K1FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecP192K1FieldElement.cs @@ -116,7 +116,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public override ECFieldElement Invert() { - //return new SecP192K1FieldElement(ToBigInteger().ModInverse(Q)); uint[] z = Nat192.Create(); SecP192K1Field.Inv(x, z); return new SecP192K1FieldElement(z); diff --git a/crypto/src/math/ec/custom/sec/SecP192R1FieldElement.cs b/crypto/src/math/ec/custom/sec/SecP192R1FieldElement.cs index e61c2251b..a8c7ae83c 100644 --- a/crypto/src/math/ec/custom/sec/SecP192R1FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecP192R1FieldElement.cs @@ -115,7 +115,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public override ECFieldElement Invert() { - //return new SecP192R1FieldElement(ToBigInteger().ModInverse(Q)); uint[] z = Nat192.Create(); SecP192R1Field.Inv(x, z); return new SecP192R1FieldElement(z); diff --git a/crypto/src/math/ec/custom/sec/SecP224K1FieldElement.cs b/crypto/src/math/ec/custom/sec/SecP224K1FieldElement.cs index eb740419f..24de7112a 100644 --- a/crypto/src/math/ec/custom/sec/SecP224K1FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecP224K1FieldElement.cs @@ -120,7 +120,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public override ECFieldElement Invert() { - //return new SecP224K1FieldElement(ToBigInteger().ModInverse(Q)); uint[] z = Nat224.Create(); SecP224K1Field.Inv(x, z); return new SecP224K1FieldElement(z); diff --git a/crypto/src/math/ec/custom/sec/SecP224R1FieldElement.cs b/crypto/src/math/ec/custom/sec/SecP224R1FieldElement.cs index bb60edaf6..e53f44164 100644 --- a/crypto/src/math/ec/custom/sec/SecP224R1FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecP224R1FieldElement.cs @@ -1,6 +1,7 @@ using System; using Org.BouncyCastle.Math.Raw; +using Org.BouncyCastle.Security; using Org.BouncyCastle.Utilities; using Org.BouncyCastle.Utilities.Encoders; @@ -115,7 +116,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public override ECFieldElement Invert() { - //return new SecP224R1FieldElement(ToBigInteger().ModInverse(Q)); uint[] z = Nat224.Create(); SecP224R1Field.Inv(x, z); return new SecP224R1FieldElement(z); @@ -134,7 +134,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec uint[] nc = Nat224.Create(); SecP224R1Field.Negate(c, nc); - uint[] r = Mod.Random(SecP224R1Field.P); + uint[] r = Mod.Random(SecureRandom.ArbitraryRandom, SecP224R1Field.P); uint[] t = Nat224.Create(); if (!IsSquare(c)) diff --git a/crypto/src/math/ec/custom/sec/SecP256K1FieldElement.cs b/crypto/src/math/ec/custom/sec/SecP256K1FieldElement.cs index 2bb83d5e9..055df0d06 100644 --- a/crypto/src/math/ec/custom/sec/SecP256K1FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecP256K1FieldElement.cs @@ -115,7 +115,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public override ECFieldElement Invert() { - //return new SecP256K1FieldElement(ToBigInteger().ModInverse(Q)); uint[] z = Nat256.Create(); SecP256K1Field.Inv(x, z); return new SecP256K1FieldElement(z); diff --git a/crypto/src/math/ec/custom/sec/SecP256R1FieldElement.cs b/crypto/src/math/ec/custom/sec/SecP256R1FieldElement.cs index 928461ec6..e09cd8c8d 100644 --- a/crypto/src/math/ec/custom/sec/SecP256R1FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecP256R1FieldElement.cs @@ -115,7 +115,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public override ECFieldElement Invert() { - //return new SecP256R1FieldElement(ToBigInteger().ModInverse(Q)); uint[] z = Nat256.Create(); SecP256R1Field.Inv(x, z); return new SecP256R1FieldElement(z); diff --git a/crypto/src/math/ec/custom/sec/SecP384R1FieldElement.cs b/crypto/src/math/ec/custom/sec/SecP384R1FieldElement.cs index d190c4ae9..33f251b76 100644 --- a/crypto/src/math/ec/custom/sec/SecP384R1FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecP384R1FieldElement.cs @@ -115,7 +115,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public override ECFieldElement Invert() { - //return new SecP384R1FieldElement(ToBigInteger().ModInverse(Q)); uint[] z = Nat.Create(12); SecP384R1Field.Inv(x, z); return new SecP384R1FieldElement(z); diff --git a/crypto/src/math/ec/custom/sec/SecP521R1FieldElement.cs b/crypto/src/math/ec/custom/sec/SecP521R1FieldElement.cs index 409352586..1169d41a9 100644 --- a/crypto/src/math/ec/custom/sec/SecP521R1FieldElement.cs +++ b/crypto/src/math/ec/custom/sec/SecP521R1FieldElement.cs @@ -115,7 +115,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public override ECFieldElement Invert() { - //return new SecP521R1FieldElement(ToBigInteger().ModInverse(Q)); uint[] z = Nat.Create(17); SecP521R1Field.Inv(x, z); return new SecP521R1FieldElement(z); diff --git a/crypto/src/math/ec/custom/sec/SecT113Field.cs b/crypto/src/math/ec/custom/sec/SecT113Field.cs index c41d9f7d7..65249562a 100644 --- a/crypto/src/math/ec/custom/sec/SecT113Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT113Field.cs @@ -1,5 +1,9 @@ using System; using System.Diagnostics; +#if NETCOREAPP3_0_OR_GREATER +using System.Runtime.Intrinsics; +using System.Runtime.Intrinsics.X86; +#endif using Org.BouncyCastle.Math.Raw; @@ -166,6 +170,25 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec protected static void ImplMultiply(ulong[] x, ulong[] y, ulong[] zz) { +#if NETCOREAPP3_0_OR_GREATER + if (Pclmulqdq.IsSupported) + { + var X01 = Vector128.Create(x[0], x[1]); + var Y01 = Vector128.Create(y[0], y[1]); + + var Z01 = Pclmulqdq.CarrylessMultiply(X01, Y01, 0x00); + var Z12 = Sse2.Xor(Pclmulqdq.CarrylessMultiply(X01, Y01, 0x01), + Pclmulqdq.CarrylessMultiply(X01, Y01, 0x10)); + var Z23 = Pclmulqdq.CarrylessMultiply(X01, Y01, 0x11); + + zz[0] = Z01.GetElement(0); + zz[1] = Z01.GetElement(1) ^ Z12.GetElement(0); + zz[2] = Z23.GetElement(0) ^ Z12.GetElement(1); + zz[3] = Z23.GetElement(1); + return; + } +#endif + /* * "Three-way recursion" as described in "Batch binary Edwards", Daniel J. Bernstein. */ diff --git a/crypto/src/math/ec/custom/sec/SecT131Field.cs b/crypto/src/math/ec/custom/sec/SecT131Field.cs index 4ff5999a4..6088b264c 100644 --- a/crypto/src/math/ec/custom/sec/SecT131Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT131Field.cs @@ -1,5 +1,9 @@ using System; using System.Diagnostics; +#if NETCOREAPP3_0_OR_GREATER +using System.Runtime.Intrinsics; +using System.Runtime.Intrinsics.X86; +#endif using Org.BouncyCastle.Math.Raw; @@ -194,6 +198,33 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec protected static void ImplMultiply(ulong[] x, ulong[] y, ulong[] zz) { +#if NETCOREAPP3_0_OR_GREATER + if (Pclmulqdq.IsSupported) + { + var X01 = Vector128.Create(x[0], x[1]); + var X2_ = Vector128.CreateScalar(x[2]); + var Y01 = Vector128.Create(y[0], y[1]); + var Y2_ = Vector128.CreateScalar(y[2]); + + var Z01 = Pclmulqdq.CarrylessMultiply(X01, Y01, 0x00); + var Z12 = Sse2.Xor(Pclmulqdq.CarrylessMultiply(X01, Y01, 0x01), + Pclmulqdq.CarrylessMultiply(X01, Y01, 0x10)); + var Z23 = Sse2.Xor(Pclmulqdq.CarrylessMultiply(X01, Y2_, 0x00), + Sse2.Xor(Pclmulqdq.CarrylessMultiply(X01, Y01, 0x11), + Pclmulqdq.CarrylessMultiply(X2_, Y01, 0x00))); + var Z34 = Sse2.Xor(Pclmulqdq.CarrylessMultiply(X01, Y2_, 0x01), + Pclmulqdq.CarrylessMultiply(X2_, Y01, 0x10)); + var Z4_ = Pclmulqdq.CarrylessMultiply(X2_, Y2_, 0x00); + + zz[0] = Z01.GetElement(0); + zz[1] = Z01.GetElement(1) ^ Z12.GetElement(0); + zz[2] = Z23.GetElement(0) ^ Z12.GetElement(1); + zz[3] = Z23.GetElement(1) ^ Z34.GetElement(0); + zz[4] = Z4_.GetElement(0) ^ Z34.GetElement(1); + return; + } +#endif + /* * "Five-way recursion" as described in "Batch binary Edwards", Daniel J. Bernstein. */ diff --git a/crypto/src/math/ec/custom/sec/SecT163Field.cs b/crypto/src/math/ec/custom/sec/SecT163Field.cs index 44105039d..0c616600a 100644 --- a/crypto/src/math/ec/custom/sec/SecT163Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT163Field.cs @@ -1,5 +1,9 @@ using System; using System.Diagnostics; +#if NETCOREAPP3_0_OR_GREATER +using System.Runtime.Intrinsics; +using System.Runtime.Intrinsics.X86; +#endif using Org.BouncyCastle.Math.Raw; @@ -205,6 +209,34 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec protected static void ImplMultiply(ulong[] x, ulong[] y, ulong[] zz) { +#if NETCOREAPP3_0_OR_GREATER + if (Pclmulqdq.IsSupported) + { + var X01 = Vector128.Create(x[0], x[1]); + var X2_ = Vector128.CreateScalar(x[2]); + var Y01 = Vector128.Create(y[0], y[1]); + var Y2_ = Vector128.CreateScalar(y[2]); + + var Z01 = Pclmulqdq.CarrylessMultiply(X01, Y01, 0x00); + var Z12 = Sse2.Xor(Pclmulqdq.CarrylessMultiply(X01, Y01, 0x01), + Pclmulqdq.CarrylessMultiply(X01, Y01, 0x10)); + var Z23 = Sse2.Xor(Pclmulqdq.CarrylessMultiply(X01, Y2_, 0x00), + Sse2.Xor(Pclmulqdq.CarrylessMultiply(X01, Y01, 0x11), + Pclmulqdq.CarrylessMultiply(X2_, Y01, 0x00))); + var Z34 = Sse2.Xor(Pclmulqdq.CarrylessMultiply(X01, Y2_, 0x01), + Pclmulqdq.CarrylessMultiply(X2_, Y01, 0x10)); + var Z45 = Pclmulqdq.CarrylessMultiply(X2_, Y2_, 0x00); + + zz[0] = Z01.GetElement(0); + zz[1] = Z01.GetElement(1) ^ Z12.GetElement(0); + zz[2] = Z23.GetElement(0) ^ Z12.GetElement(1); + zz[3] = Z23.GetElement(1) ^ Z34.GetElement(0); + zz[4] = Z45.GetElement(0) ^ Z34.GetElement(1); + zz[5] = Z45.GetElement(1); + return; + } +#endif + /* * "Five-way recursion" as described in "Batch binary Edwards", Daniel J. Bernstein. */ diff --git a/crypto/src/math/ec/custom/sec/SecT193Field.cs b/crypto/src/math/ec/custom/sec/SecT193Field.cs index 59da8b000..4aa3ad5c2 100644 --- a/crypto/src/math/ec/custom/sec/SecT193Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT193Field.cs @@ -1,5 +1,9 @@ using System; using System.Diagnostics; +#if NETCOREAPP3_0_OR_GREATER +using System.Runtime.Intrinsics; +using System.Runtime.Intrinsics.X86; +#endif using Org.BouncyCastle.Math.Raw; @@ -226,6 +230,38 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec protected static void ImplMultiply(ulong[] x, ulong[] y, ulong[] zz) { +#if NETCOREAPP3_0_OR_GREATER + if (Pclmulqdq.IsSupported) + { + var X01 = Vector128.Create(x[0], x[1]); + var X2_ = Vector128.CreateScalar(x[2]); + var Y01 = Vector128.Create(y[0], y[1]); + var Y2_ = Vector128.CreateScalar(y[2]); + + var Z01 = Pclmulqdq.CarrylessMultiply(X01, Y01, 0x00); + var Z12 = Sse2.Xor(Pclmulqdq.CarrylessMultiply(X01, Y01, 0x01), + Pclmulqdq.CarrylessMultiply(X01, Y01, 0x10)); + var Z23 = Sse2.Xor(Pclmulqdq.CarrylessMultiply(X01, Y2_, 0x00), + Sse2.Xor(Pclmulqdq.CarrylessMultiply(X01, Y01, 0x11), + Pclmulqdq.CarrylessMultiply(X2_, Y01, 0x00))); + var Z34 = Sse2.Xor(Pclmulqdq.CarrylessMultiply(X01, Y2_, 0x01), + Pclmulqdq.CarrylessMultiply(X2_, Y01, 0x10)); + var Z45 = Pclmulqdq.CarrylessMultiply(X2_, Y2_, 0x00); + + ulong X3M = 0UL - x[3]; + ulong Y3M = 0UL - y[3]; + + zz[0] = Z01.GetElement(0); + zz[1] = Z01.GetElement(1) ^ Z12.GetElement(0); + zz[2] = Z23.GetElement(0) ^ Z12.GetElement(1); + zz[3] = Z23.GetElement(1) ^ Z34.GetElement(0) ^ (X3M & y[0]) ^ (x[0] & Y3M); + zz[4] = Z45.GetElement(0) ^ Z34.GetElement(1) ^ (X3M & y[1]) ^ (x[1] & Y3M); + zz[5] = Z45.GetElement(1) ^ (X3M & y[2]) ^ (x[2] & Y3M); + zz[6] = X3M & y[3]; + return; + } +#endif + /* * "Two-level seven-way recursion" as described in "Batch binary Edwards", Daniel J. Bernstein. */ diff --git a/crypto/src/math/ec/custom/sec/SecT233Field.cs b/crypto/src/math/ec/custom/sec/SecT233Field.cs index c16a3d612..e4e291154 100644 --- a/crypto/src/math/ec/custom/sec/SecT233Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT233Field.cs @@ -1,5 +1,9 @@ using System; using System.Diagnostics; +#if NETCOREAPP3_0_OR_GREATER +using System.Runtime.Intrinsics; +using System.Runtime.Intrinsics.X86; +#endif using Org.BouncyCastle.Math.Raw; @@ -237,6 +241,54 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec protected static void ImplMultiply(ulong[] x, ulong[] y, ulong[] zz) { +#if NETCOREAPP3_0_OR_GREATER + if (Pclmulqdq.IsSupported) + { + var X01 = Vector128.Create(x[0], x[1]); + var X23 = Vector128.Create(x[2], x[3]); + var Y01 = Vector128.Create(y[0], y[1]); + var Y23 = Vector128.Create(y[2], y[3]); + var X03 = Sse2.Xor(X01, X23); + var Y03 = Sse2.Xor(Y01, Y23); + + var Z01 = Pclmulqdq.CarrylessMultiply(X01, Y01, 0x00); + var Z12 = Sse2.Xor(Pclmulqdq.CarrylessMultiply(X01, Y01, 0x01), + Pclmulqdq.CarrylessMultiply(X01, Y01, 0x10)); + var Z23 = Pclmulqdq.CarrylessMultiply(X01, Y01, 0x11); + + var Z45 = Pclmulqdq.CarrylessMultiply(X23, Y23, 0x00); + var Z56 = Sse2.Xor(Pclmulqdq.CarrylessMultiply(X23, Y23, 0x01), + Pclmulqdq.CarrylessMultiply(X23, Y23, 0x10)); + var Z67 = Pclmulqdq.CarrylessMultiply(X23, Y23, 0x11); + + var K01 = Pclmulqdq.CarrylessMultiply(X03, Y03, 0x00); + var K12 = Sse2.Xor(Pclmulqdq.CarrylessMultiply(X03, Y03, 0x01), + Pclmulqdq.CarrylessMultiply(X03, Y03, 0x10)); + var K23 = Pclmulqdq.CarrylessMultiply(X03, Y03, 0x11); + + K01 = Sse2.Xor(K01, Z01); + K12 = Sse2.Xor(K12, Z12); + K23 = Sse2.Xor(K23, Z23); + + K01 = Sse2.Xor(K01, Z45); + K12 = Sse2.Xor(K12, Z56); + K23 = Sse2.Xor(K23, Z67); + + Z23 = Sse2.Xor(Z23, K01); + Z45 = Sse2.Xor(Z45, K23); + + zz[0] = Z01.GetElement(0); + zz[1] = Z01.GetElement(1) ^ Z12.GetElement(0); + zz[2] = Z23.GetElement(0) ^ Z12.GetElement(1); + zz[3] = Z23.GetElement(1) ^ K12.GetElement(0); + zz[4] = Z45.GetElement(0) ^ K12.GetElement(1); + zz[5] = Z45.GetElement(1) ^ Z56.GetElement(0); + zz[6] = Z67.GetElement(0) ^ Z56.GetElement(1); + zz[7] = Z67.GetElement(1); + return; + } +#endif + /* * "Two-level seven-way recursion" as described in "Batch binary Edwards", Daniel J. Bernstein. */ diff --git a/crypto/src/math/ec/custom/sec/SecT239Field.cs b/crypto/src/math/ec/custom/sec/SecT239Field.cs index de87b18a2..a3851de16 100644 --- a/crypto/src/math/ec/custom/sec/SecT239Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT239Field.cs @@ -1,5 +1,9 @@ using System; using System.Diagnostics; +#if NETCOREAPP3_0_OR_GREATER +using System.Runtime.Intrinsics; +using System.Runtime.Intrinsics.X86; +#endif using Org.BouncyCastle.Math.Raw; @@ -246,6 +250,54 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec protected static void ImplMultiply(ulong[] x, ulong[] y, ulong[] zz) { +#if NETCOREAPP3_0_OR_GREATER + if (Pclmulqdq.IsSupported) + { + var X01 = Vector128.Create(x[0], x[1]); + var X23 = Vector128.Create(x[2], x[3]); + var Y01 = Vector128.Create(y[0], y[1]); + var Y23 = Vector128.Create(y[2], y[3]); + var X03 = Sse2.Xor(X01, X23); + var Y03 = Sse2.Xor(Y01, Y23); + + var Z01 = Pclmulqdq.CarrylessMultiply(X01, Y01, 0x00); + var Z12 = Sse2.Xor(Pclmulqdq.CarrylessMultiply(X01, Y01, 0x01), + Pclmulqdq.CarrylessMultiply(X01, Y01, 0x10)); + var Z23 = Pclmulqdq.CarrylessMultiply(X01, Y01, 0x11); + + var Z45 = Pclmulqdq.CarrylessMultiply(X23, Y23, 0x00); + var Z56 = Sse2.Xor(Pclmulqdq.CarrylessMultiply(X23, Y23, 0x01), + Pclmulqdq.CarrylessMultiply(X23, Y23, 0x10)); + var Z67 = Pclmulqdq.CarrylessMultiply(X23, Y23, 0x11); + + var K01 = Pclmulqdq.CarrylessMultiply(X03, Y03, 0x00); + var K12 = Sse2.Xor(Pclmulqdq.CarrylessMultiply(X03, Y03, 0x01), + Pclmulqdq.CarrylessMultiply(X03, Y03, 0x10)); + var K23 = Pclmulqdq.CarrylessMultiply(X03, Y03, 0x11); + + K01 = Sse2.Xor(K01, Z01); + K12 = Sse2.Xor(K12, Z12); + K23 = Sse2.Xor(K23, Z23); + + K01 = Sse2.Xor(K01, Z45); + K12 = Sse2.Xor(K12, Z56); + K23 = Sse2.Xor(K23, Z67); + + Z23 = Sse2.Xor(Z23, K01); + Z45 = Sse2.Xor(Z45, K23); + + zz[0] = Z01.GetElement(0); + zz[1] = Z01.GetElement(1) ^ Z12.GetElement(0); + zz[2] = Z23.GetElement(0) ^ Z12.GetElement(1); + zz[3] = Z23.GetElement(1) ^ K12.GetElement(0); + zz[4] = Z45.GetElement(0) ^ K12.GetElement(1); + zz[5] = Z45.GetElement(1) ^ Z56.GetElement(0); + zz[6] = Z67.GetElement(0) ^ Z56.GetElement(1); + zz[7] = Z67.GetElement(1); + return; + } +#endif + /* * "Two-level seven-way recursion" as described in "Batch binary Edwards", Daniel J. Bernstein. */ diff --git a/crypto/src/math/ec/custom/sec/SecT283Field.cs b/crypto/src/math/ec/custom/sec/SecT283Field.cs index ee5ad89c5..334986452 100644 --- a/crypto/src/math/ec/custom/sec/SecT283Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT283Field.cs @@ -1,5 +1,9 @@ using System; using System.Diagnostics; +#if NETCOREAPP3_0_OR_GREATER +using System.Runtime.Intrinsics; +using System.Runtime.Intrinsics.X86; +#endif using Org.BouncyCastle.Math.Raw; @@ -245,6 +249,56 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec protected static void ImplMultiply(ulong[] x, ulong[] y, ulong[] zz) { +#if NETCOREAPP3_0_OR_GREATER + if (Pclmulqdq.IsSupported) + { + var X01 = Vector128.Create(x[0], x[1]); + var X23 = Vector128.Create(x[2], x[3]); + var X4_ = Vector128.CreateScalar(x[4]); + var Y01 = Vector128.Create(y[0], y[1]); + var Y23 = Vector128.Create(y[2], y[3]); + var Y4_ = Vector128.CreateScalar(y[4]); + + var Z01 = Pclmulqdq.CarrylessMultiply(X01, Y01, 0x00); + var Z12 = Sse2.Xor(Pclmulqdq.CarrylessMultiply(X01, Y01, 0x01), + Pclmulqdq.CarrylessMultiply(X01, Y01, 0x10)); + var Z23 = Sse2.Xor(Pclmulqdq.CarrylessMultiply(X01, Y23, 0x00), + Sse2.Xor(Pclmulqdq.CarrylessMultiply(X01, Y01, 0x11), + Pclmulqdq.CarrylessMultiply(X23, Y01, 0x00))); + var Z34 = Sse2.Xor(Pclmulqdq.CarrylessMultiply(X01, Y23, 0x01), + Sse2.Xor(Pclmulqdq.CarrylessMultiply(X01, Y23, 0x10), + Sse2.Xor(Pclmulqdq.CarrylessMultiply(X23, Y01, 0x01), + Pclmulqdq.CarrylessMultiply(X23, Y01, 0x10)))); + var Z45 = Sse2.Xor(Pclmulqdq.CarrylessMultiply(X01, Y4_, 0x00), + Sse2.Xor(Pclmulqdq.CarrylessMultiply(X01, Y23, 0x11), + Sse2.Xor(Pclmulqdq.CarrylessMultiply(X23, Y23, 0x00), + Sse2.Xor(Pclmulqdq.CarrylessMultiply(X23, Y01, 0x11), + Pclmulqdq.CarrylessMultiply(X4_, Y01, 0x00))))); + var Z56 = Sse2.Xor(Pclmulqdq.CarrylessMultiply(X01, Y4_, 0x01), + Sse2.Xor(Pclmulqdq.CarrylessMultiply(X23, Y23, 0x01), + Sse2.Xor(Pclmulqdq.CarrylessMultiply(X23, Y23, 0x10), + Pclmulqdq.CarrylessMultiply(X4_, Y01, 0x10)))); + var Z67 = Sse2.Xor(Pclmulqdq.CarrylessMultiply(X23, Y4_, 0x00), + Sse2.Xor(Pclmulqdq.CarrylessMultiply(X23, Y23, 0x11), + Pclmulqdq.CarrylessMultiply(X4_, Y23, 0x00))); + var Z78 = Sse2.Xor(Pclmulqdq.CarrylessMultiply(X23, Y4_, 0x01), + Pclmulqdq.CarrylessMultiply(X4_, Y23, 0x10)); + var Z89 = Pclmulqdq.CarrylessMultiply(X4_, Y4_, 0x00); + + zz[0] = Z01.GetElement(0); + zz[1] = Z01.GetElement(1) ^ Z12.GetElement(0); + zz[2] = Z23.GetElement(0) ^ Z12.GetElement(1); + zz[3] = Z23.GetElement(1) ^ Z34.GetElement(0); + zz[4] = Z45.GetElement(0) ^ Z34.GetElement(1); + zz[5] = Z45.GetElement(1) ^ Z56.GetElement(0); + zz[6] = Z67.GetElement(0) ^ Z56.GetElement(1); + zz[7] = Z67.GetElement(1) ^ Z78.GetElement(0); + zz[8] = Z89.GetElement(0) ^ Z78.GetElement(1); + zz[9] = Z89.GetElement(1); + return; + } +#endif + /* * Formula (17) from "Some New Results on Binary Polynomial Multiplication", * Murat Cenk and M. Anwar Hasan. diff --git a/crypto/src/math/ec/custom/sec/SecT409Field.cs b/crypto/src/math/ec/custom/sec/SecT409Field.cs index 0fb7377f6..414a094a8 100644 --- a/crypto/src/math/ec/custom/sec/SecT409Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT409Field.cs @@ -1,5 +1,9 @@ using System; using System.Diagnostics; +#if NETCOREAPP3_0_OR_GREATER +using System.Runtime.Intrinsics; +using System.Runtime.Intrinsics.X86; +#endif using Org.BouncyCastle.Math.Raw; @@ -344,6 +348,20 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec Debug.Assert(x >> 59 == 0); Debug.Assert(y >> 59 == 0); +#if NETCOREAPP3_0_OR_GREATER + if (Pclmulqdq.IsSupported) + { + var X = Vector128.CreateScalar(x); + var Y = Vector128.CreateScalar(y); + var Z = Pclmulqdq.CarrylessMultiply(X, Y, 0x00); + ulong z0 = Z.GetElement(0); + ulong z1 = Z.GetElement(1); + z[zOff ] ^= z0 & M59; + z[zOff + 1] ^= (z0 >> 59) ^ (z1 << 5); + return; + } +#endif + //u[0] = 0; u[1] = y; u[2] = u[1] << 1; diff --git a/crypto/src/math/ec/custom/sec/SecT571Field.cs b/crypto/src/math/ec/custom/sec/SecT571Field.cs index 91a3fde9d..49eaae2d4 100644 --- a/crypto/src/math/ec/custom/sec/SecT571Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT571Field.cs @@ -19,18 +19,12 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public static void Add(ulong[] x, ulong[] y, ulong[] z) { - for (int i = 0; i < 9; ++i) - { - z[i] = x[i] ^ y[i]; - } + Nat.Xor64(9, x, y, z); } private static void Add(ulong[] x, int xOff, ulong[] y, int yOff, ulong[] z, int zOff) { - for (int i = 0; i < 9; ++i) - { - z[zOff + i] = x[xOff + i] ^ y[yOff + i]; - } + Nat.Xor64(9, x, xOff, y, yOff, z, zOff); } public static void AddBothTo(ulong[] x, ulong[] y, ulong[] z) @@ -51,10 +45,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public static void AddExt(ulong[] xx, ulong[] yy, ulong[] zz) { - for (int i = 0; i < 18; ++i) - { - zz[i] = xx[i] ^ yy[i]; - } + Nat.Xor64(18, xx, yy, zz); } public static void AddOne(ulong[] x, ulong[] z) @@ -68,10 +59,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec private static void AddTo(ulong[] x, ulong[] z) { - for (int i = 0; i < 9; ++i) - { - z[i] ^= x[i]; - } + Nat.XorTo64(9, x, z); } public static ulong[] FromBigInteger(BigInteger x) @@ -175,6 +163,11 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec public static ulong[] PrecompMultiplicand(ulong[] x) { +#if NETCOREAPP3_0_OR_GREATER + ulong[] z = Nat576.Create64(); + Nat576.Copy64(x, z); + return z; +#else /* * Precompute table of all 4-bit products of x (first section) */ @@ -197,6 +190,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec Nat.ShiftUpBits64(len, t, 0, 4, 0UL, t, len); return t; +#endif } public static void Reduce(ulong[] xx, ulong[] z) @@ -367,6 +361,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec protected static void ImplMultiplyPrecomp(ulong[] x, ulong[] precomp, ulong[] zz) { +#if NETCOREAPP3_0_OR_GREATER + ImplMultiply(x, precomp, zz); +#else uint MASK = 0xF; /* @@ -399,6 +396,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec Nat.ShiftUpBits64(18, zz, 0, 8, 0UL); } } +#endif } protected static void ImplMulwAcc(ulong[] u, ulong x, ulong y, ulong[] z, int zOff) 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/ec/rfc7748/X25519.cs b/crypto/src/math/ec/rfc7748/X25519.cs index 217ef8785..ffddd4376 100644 --- a/crypto/src/math/ec/rfc7748/X25519.cs +++ b/crypto/src/math/ec/rfc7748/X25519.cs @@ -26,6 +26,36 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 return !Arrays.AreAllZeroes(r, rOff, PointSize); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static bool CalculateAgreement(ReadOnlySpan<byte> k, ReadOnlySpan<byte> u, Span<byte> r) + { + ScalarMult(k, u, r); + return !Arrays.AreAllZeroes(r[..PointSize]); + } +#endif + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static uint Decode32(ReadOnlySpan<byte> bs) + { + uint n = bs[0]; + n |= (uint)bs[1] << 8; + n |= (uint)bs[2] << 16; + n |= (uint)bs[3] << 24; + return n; + } + + private static void DecodeScalar(ReadOnlySpan<byte> k, Span<uint> n) + { + for (int i = 0; i < 8; ++i) + { + n[i] = Decode32(k[(i * 4)..]); + } + + n[0] &= 0xFFFFFFF8U; + n[7] &= 0x7FFFFFFFU; + n[7] |= 0x40000000U; + } +#else private static uint Decode32(byte[] bs, int off) { uint n = bs[off]; @@ -46,21 +76,46 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 n[7] &= 0x7FFFFFFFU; n[7] |= 0x40000000U; } +#endif public static void GeneratePrivateKey(SecureRandom random, byte[] k) { + if (k.Length != ScalarSize) + throw new ArgumentException(nameof(k)); + + random.NextBytes(k); + + k[0] &= 0xF8; + k[ScalarSize - 1] &= 0x7F; + k[ScalarSize - 1] |= 0x40; + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void GeneratePrivateKey(SecureRandom random, Span<byte> k) + { + if (k.Length != ScalarSize) + throw new ArgumentException(nameof(k)); + random.NextBytes(k); k[0] &= 0xF8; k[ScalarSize - 1] &= 0x7F; k[ScalarSize - 1] |= 0x40; } +#endif public static void GeneratePublicKey(byte[] k, int kOff, byte[] r, int rOff) { ScalarMultBase(k, kOff, r, rOff); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void GeneratePublicKey(ReadOnlySpan<byte> k, Span<byte> r) + { + ScalarMultBase(k, r); + } +#endif + private static void PointDouble(int[] x, int[] z) { int[] a = F.Create(); @@ -83,6 +138,9 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 public static void ScalarMult(byte[] k, int kOff, byte[] u, int uOff, byte[] r, int rOff) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + ScalarMult(k.AsSpan(kOff), u.AsSpan(uOff), r.AsSpan(rOff)); +#else uint[] n = new uint[8]; DecodeScalar(k, kOff, n); int[] x1 = F.Create(); F.Decode(u, uOff, x1); @@ -140,10 +198,77 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 F.Normalize(x2); F.Encode(x2, r, rOff); +#endif } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void ScalarMult(ReadOnlySpan<byte> k, ReadOnlySpan<byte> u, Span<byte> r) + { + uint[] n = new uint[8]; DecodeScalar(k, n); + + int[] x1 = F.Create(); F.Decode(u, x1); + int[] x2 = F.Create(); F.Copy(x1, 0, x2, 0); + int[] z2 = F.Create(); z2[0] = 1; + int[] x3 = F.Create(); x3[0] = 1; + int[] z3 = F.Create(); + + int[] t1 = F.Create(); + int[] t2 = F.Create(); + + Debug.Assert(n[7] >> 30 == 1U); + + int bit = 254, swap = 1; + do + { + F.Apm(x3, z3, t1, x3); + F.Apm(x2, z2, z3, x2); + F.Mul(t1, x2, t1); + F.Mul(x3, z3, x3); + F.Sqr(z3, z3); + F.Sqr(x2, x2); + + F.Sub(z3, x2, t2); + F.Mul(t2, C_A24, z2); + F.Add(z2, x2, z2); + F.Mul(z2, t2, z2); + F.Mul(x2, z3, x2); + + F.Apm(t1, x3, x3, z3); + F.Sqr(x3, x3); + F.Sqr(z3, z3); + F.Mul(z3, x1, z3); + + --bit; + + int word = bit >> 5, shift = bit & 0x1F; + int kt = (int)(n[word] >> shift) & 1; + swap ^= kt; + F.CSwap(swap, x2, x3); + F.CSwap(swap, z2, z3); + swap = kt; + } + while (bit >= 3); + + Debug.Assert(swap == 0); + + for (int i = 0; i < 3; ++i) + { + PointDouble(x2, z2); + } + + F.Inv(z2, z2); + F.Mul(x2, z2, x2); + + F.Normalize(x2); + F.Encode(x2, r); + } +#endif + public static void ScalarMultBase(byte[] k, int kOff, byte[] r, int rOff) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + ScalarMultBase(k.AsSpan(kOff), r.AsSpan(rOff)); +#else int[] y = F.Create(); int[] z = F.Create(); @@ -156,6 +281,25 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 F.Normalize(y); F.Encode(y, r, rOff); +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void ScalarMultBase(ReadOnlySpan<byte> k, Span<byte> r) + { + int[] y = F.Create(); + int[] z = F.Create(); + + Ed25519.ScalarMultBaseYZ(k, y, z); + + F.Apm(z, y, y, z); + + F.Inv(z, z); + F.Mul(y, z, y); + + F.Normalize(y); + F.Encode(y, r); } +#endif } } diff --git a/crypto/src/math/ec/rfc7748/X25519Field.cs b/crypto/src/math/ec/rfc7748/X25519Field.cs index e6d5687ec..5c9eadc6b 100644 --- a/crypto/src/math/ec/rfc7748/X25519Field.cs +++ b/crypto/src/math/ec/rfc7748/X25519Field.cs @@ -103,6 +103,20 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 } } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void CMov(int cond, ReadOnlySpan<int> x, Span<int> z) + { + Debug.Assert(0 == cond || -1 == cond); + + for (int i = 0; i < Size; ++i) + { + int z_i = z[i], diff = z_i ^ x[i]; + z_i ^= (diff & cond); + z[i] = z_i; + } + } +#endif + public static void CNegate(int negate, int[] z) { Debug.Assert(negate >> 1 == 0); @@ -122,6 +136,13 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 } } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Copy(ReadOnlySpan<int> x, Span<int> z) + { + x[..Size].CopyTo(z); + } +#endif + public static int[] Create() { return new int[Size]; @@ -155,6 +176,16 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 z[9] &= M24; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + [CLSCompliant(false)] + public static void Decode(ReadOnlySpan<uint> x, Span<int> z) + { + Decode128(x, z); + Decode128(x[4..], z[5..]); + z[9] &= M24; + } +#endif + public static void Decode(byte[] x, int xOff, int[] z) { Decode128(x, xOff, z, 0); @@ -162,6 +193,15 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 z[9] &= M24; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Decode(ReadOnlySpan<byte> x, Span<int> z) + { + Decode128(x, z); + Decode128(x[16..], z[5..]); + z[9] &= M24; + } +#endif + private static void Decode128(uint[] x, int xOff, int[] z, int zOff) { uint t0 = x[xOff + 0], t1 = x[xOff + 1], t2 = x[xOff + 2], t3 = x[xOff + 3]; @@ -173,6 +213,19 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 z[zOff + 4] = (int)(t3 >> 7); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void Decode128(ReadOnlySpan<uint> x, Span<int> z) + { + uint t0 = x[0], t1 = x[1], t2 = x[2], t3 = x[3]; + + z[0] = (int)t0 & M26; + z[1] = (int)((t1 << 6) | (t0 >> 26)) & M26; + z[2] = (int)((t2 << 12) | (t1 >> 20)) & M25; + z[3] = (int)((t3 << 19) | (t2 >> 13)) & M26; + z[4] = (int)(t3 >> 7); + } +#endif + private static void Decode128(byte[] bs, int off, int[] z, int zOff) { uint t0 = Decode32(bs, off + 0); @@ -181,12 +234,28 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 uint t3 = Decode32(bs, off + 12); z[zOff + 0] = (int)t0 & M26; - z[zOff + 1] = (int)((t1 << 6) | (t0 >> 26)) & M26; + z[zOff + 1] = (int)((t1 << 6) | (t0 >> 26)) & M26; z[zOff + 2] = (int)((t2 << 12) | (t1 >> 20)) & M25; z[zOff + 3] = (int)((t3 << 19) | (t2 >> 13)) & M26; z[zOff + 4] = (int)(t3 >> 7); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void Decode128(ReadOnlySpan<byte> bs, Span<int> z) + { + uint t0 = Decode32(bs); + uint t1 = Decode32(bs[4..]); + uint t2 = Decode32(bs[8..]); + uint t3 = Decode32(bs[12..]); + + z[0] = (int)t0 & M26; + z[1] = (int)((t1 << 6) | (t0 >> 26)) & M26; + z[2] = (int)((t2 << 12) | (t1 >> 20)) & M25; + z[3] = (int)((t3 << 19) | (t2 >> 13)) & M26; + z[4] = (int)(t3 >> 7); + } +#endif + private static uint Decode32(byte[] bs, int off) { uint n = bs[off]; @@ -196,6 +265,17 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 return n; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static uint Decode32(ReadOnlySpan<byte> bs) + { + uint n = bs[0]; + n |= (uint)bs[1] << 8; + n |= (uint)bs[2] << 16; + n |= (uint)bs[3] << 24; + return n; + } +#endif + [CLSCompliant(false)] public static void Encode(int[] x, uint[] z, int zOff) { @@ -203,12 +283,29 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 Encode128(x, 5, z, zOff + 4); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + [CLSCompliant(false)] + public static void Encode(ReadOnlySpan<int> x, Span<uint> z) + { + Encode128(x, z); + Encode128(x[5..], z[4..]); + } +#endif + public static void Encode(int[] x, byte[] z, int zOff) { Encode128(x, 0, z, zOff); Encode128(x, 5, z, zOff + 16); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Encode(ReadOnlySpan<int> x, Span<byte> z) + { + Encode128(x, z); + Encode128(x[5..], z[16..]); + } +#endif + private static void Encode128(int[] x, int xOff, uint[] z, int zOff) { uint x0 = (uint)x[xOff + 0], x1 = (uint)x[xOff + 1], x2 = (uint)x[xOff + 2], x3 = (uint)x[xOff + 3], @@ -220,6 +317,18 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 z[zOff + 3] = (x3 >> 19) | (x4 << 7); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void Encode128(ReadOnlySpan<int> x, Span<uint> z) + { + uint x0 = (uint)x[0], x1 = (uint)x[1], x2 = (uint)x[2], x3 = (uint)x[3], x4 = (uint)x[4]; + + z[0] = x0 | (x1 << 26); + z[1] = (x1 >> 6) | (x2 << 20); + z[2] = (x2 >> 12) | (x3 << 13); + z[3] = (x3 >> 19) | (x4 << 7); + } +#endif + private static void Encode128(int[] x, int xOff, byte[] bs, int off) { uint x0 = (uint)x[xOff + 0], x1 = (uint)x[xOff + 1], x2 = (uint)x[xOff + 2]; @@ -231,6 +340,19 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 uint t3 = (x3 >> 19) | (x4 << 7); Encode32(t3, bs, off + 12); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void Encode128(ReadOnlySpan<int> x, Span<byte> bs) + { + uint x0 = (uint)x[0], x1 = (uint)x[1], x2 = (uint)x[2]; + uint x3 = (uint)x[3], x4 = (uint)x[4]; + + uint t0 = x0 | (x1 << 26); Encode32(t0, bs); + uint t1 = (x1 >> 6) | (x2 << 20); Encode32(t1, bs[4..]); + uint t2 = (x2 >> 12) | (x3 << 13); Encode32(t2, bs[8..]); + uint t3 = (x3 >> 19) | (x4 << 7); Encode32(t3, bs[12..]); + } +#endif + private static void Encode32(uint n, byte[] bs, int off) { bs[ off] = (byte)(n ); @@ -239,8 +361,21 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 bs[++off] = (byte)(n >> 24); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void Encode32(uint n, Span<byte> bs) + { + bs[0] = (byte)(n ); + bs[1] = (byte)(n >> 8); + bs[2] = (byte)(n >> 16); + bs[3] = (byte)(n >> 24); + } +#endif + public static void Inv(int[] x, int[] z) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + Inv(x.AsSpan(), z.AsSpan()); +#else //int[] x2 = Create(); //int[] t = Create(); //PowPm5d8(x, x2, t); @@ -257,10 +392,30 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 Mod.ModOddInverse(P32, u, u); Decode(u, 0, z); +#endif } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Inv(ReadOnlySpan<int> x, Span<int> z) + { + Span<int> t = stackalloc int[Size]; + Span<uint> u = stackalloc uint[8]; + + Copy(x, t); + Normalize(t); + Encode(t, u); + + Mod.ModOddInverse(P32, u, u); + + Decode(u, z); + } +#endif + public static void InvVar(int[] x, int[] z) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + InvVar(x.AsSpan(), z.AsSpan()); +#else int[] t = Create(); uint[] u = new uint[8]; @@ -271,8 +426,25 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 Mod.ModOddInverseVar(P32, u, u); Decode(u, 0, z); +#endif } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void InvVar(ReadOnlySpan<int> x, Span<int> z) + { + Span<int> t = stackalloc int[Size]; + Span<uint> u = stackalloc uint[8]; + + Copy(x, t); + Normalize(t); + Encode(t, u); + + Mod.ModOddInverseVar(P32, u, u); + + Decode(u, z); + } +#endif + public static int IsOne(int[] x) { int d = x[0] ^ 1; @@ -507,6 +679,16 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 Debug.Assert(z[9] >> 24 == 0); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Normalize(Span<int> z) + { + int x = (z[9] >> 23) & 1; + Reduce(z, x); + Reduce(z, -x); + Debug.Assert(z[9] >> 24 == 0); + } +#endif + public static void One(int[] z) { z[0] = 1; @@ -556,6 +738,26 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 z[9] = z9 + (int)cc; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void Reduce(Span<int> z, int x) + { + int t = z[9], z9 = t & M24; + t = (t >> 24) + x; + + long cc = t * 19; + cc += z[0]; z[0] = (int)cc & M26; cc >>= 26; + cc += z[1]; z[1] = (int)cc & M26; cc >>= 26; + cc += z[2]; z[2] = (int)cc & M25; cc >>= 25; + cc += z[3]; z[3] = (int)cc & M26; cc >>= 26; + cc += z[4]; z[4] = (int)cc & M25; cc >>= 25; + cc += z[5]; z[5] = (int)cc & M26; cc >>= 26; + cc += z[6]; z[6] = (int)cc & M26; cc >>= 26; + cc += z[7]; z[7] = (int)cc & M25; cc >>= 25; + cc += z[8]; z[8] = (int)cc & M26; cc >>= 26; + z[9] = z9 + (int)cc; + } +#endif + public static void Sqr(int[] x, int[] z) { int x0 = x[0]; diff --git a/crypto/src/math/ec/rfc7748/X448.cs b/crypto/src/math/ec/rfc7748/X448.cs index 7de78ebdc..7e078c5c6 100644 --- a/crypto/src/math/ec/rfc7748/X448.cs +++ b/crypto/src/math/ec/rfc7748/X448.cs @@ -27,6 +27,35 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 return !Arrays.AreAllZeroes(r, rOff, PointSize); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static bool CalculateAgreement(ReadOnlySpan<byte> k, ReadOnlySpan<byte> u, Span<byte> r) + { + ScalarMult(k, u, r); + return !Arrays.AreAllZeroes(r[..PointSize]); + } +#endif + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static uint Decode32(ReadOnlySpan<byte> bs) + { + uint n = bs[0]; + n |= (uint)bs[1] << 8; + n |= (uint)bs[2] << 16; + n |= (uint)bs[3] << 24; + return n; + } + + private static void DecodeScalar(ReadOnlySpan<byte> k, uint[] n) + { + for (int i = 0; i < 14; ++i) + { + n[i] = Decode32(k[(i * 4)..]); + } + + n[ 0] &= 0xFFFFFFFCU; + n[13] |= 0x80000000U; + } +#else private static uint Decode32(byte[] bs, int off) { uint n = bs[off]; @@ -46,20 +75,44 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 n[ 0] &= 0xFFFFFFFCU; n[13] |= 0x80000000U; } +#endif public static void GeneratePrivateKey(SecureRandom random, byte[] k) { + if (k.Length != ScalarSize) + throw new ArgumentException(nameof(k)); + random.NextBytes(k); k[0] &= 0xFC; k[ScalarSize - 1] |= 0x80; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void GeneratePrivateKey(SecureRandom random, Span<byte> k) + { + if (k.Length != ScalarSize) + throw new ArgumentException(nameof(k)); + + random.NextBytes(k); + + k[0] &= 0xFC; + k[ScalarSize - 1] |= 0x80; + } +#endif + public static void GeneratePublicKey(byte[] k, int kOff, byte[] r, int rOff) { ScalarMultBase(k, kOff, r, rOff); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void GeneratePublicKey(ReadOnlySpan<byte> k, Span<byte> r) + { + ScalarMultBase(k, r); + } +#endif + private static void PointDouble(uint[] x, uint[] z) { uint[] a = F.Create(); @@ -84,6 +137,9 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 public static void ScalarMult(byte[] k, int kOff, byte[] u, int uOff, byte[] r, int rOff) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + ScalarMult(k.AsSpan(kOff), u.AsSpan(uOff), r.AsSpan(rOff)); +#else uint[] n = new uint[14]; DecodeScalar(k, kOff, n); uint[] x1 = F.Create(); F.Decode(u, uOff, x1); @@ -148,10 +204,84 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 F.Normalize(x2); F.Encode(x2, r, rOff); +#endif } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void ScalarMult(ReadOnlySpan<byte> k, ReadOnlySpan<byte> u, Span<byte> r) + { + uint[] n = new uint[14]; DecodeScalar(k, n); + + uint[] x1 = F.Create(); F.Decode(u, x1); + uint[] x2 = F.Create(); F.Copy(x1, 0, x2, 0); + uint[] z2 = F.Create(); z2[0] = 1; + uint[] x3 = F.Create(); x3[0] = 1; + uint[] z3 = F.Create(); + + uint[] t1 = F.Create(); + uint[] t2 = F.Create(); + + Debug.Assert(n[13] >> 31 == 1U); + + int bit = 447, swap = 1; + do + { + //F.Apm(x3, z3, t1, x3); + F.Add(x3, z3, t1); + F.Sub(x3, z3, x3); + //F.Apm(x2, z2, z3, x2); + F.Add(x2, z2, z3); + F.Sub(x2, z2, x2); + + F.Mul(t1, x2, t1); + F.Mul(x3, z3, x3); + F.Sqr(z3, z3); + F.Sqr(x2, x2); + + F.Sub(z3, x2, t2); + F.Mul(t2, C_A24, z2); + F.Add(z2, x2, z2); + F.Mul(z2, t2, z2); + F.Mul(x2, z3, x2); + + //F.Apm(t1, x3, x3, z3); + F.Sub(t1, x3, z3); + F.Add(t1, x3, x3); + F.Sqr(x3, x3); + F.Sqr(z3, z3); + F.Mul(z3, x1, z3); + + --bit; + + int word = bit >> 5, shift = bit & 0x1F; + int kt = (int)(n[word] >> shift) & 1; + swap ^= kt; + F.CSwap(swap, x2, x3); + F.CSwap(swap, z2, z3); + swap = kt; + } + while (bit >= 2); + + Debug.Assert(swap == 0); + + for (int i = 0; i < 2; ++i) + { + PointDouble(x2, z2); + } + + F.Inv(z2, z2); + F.Mul(x2, z2, x2); + + F.Normalize(x2); + F.Encode(x2, r); + } +#endif + public static void ScalarMultBase(byte[] k, int kOff, byte[] r, int rOff) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + ScalarMultBase(k.AsSpan(kOff), r.AsSpan(rOff)); +#else uint[] x = F.Create(); uint[] y = F.Create(); @@ -163,6 +293,24 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 F.Normalize(x); F.Encode(x, r, rOff); +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void ScalarMultBase(ReadOnlySpan<byte> k, Span<byte> r) + { + uint[] x = F.Create(); + uint[] y = F.Create(); + + Ed448.ScalarMultBaseXY(k, x, y); + + F.Inv(x, x); + F.Mul(x, y, x); + F.Sqr(x, x); + + F.Normalize(x); + F.Encode(x, r); } +#endif } } diff --git a/crypto/src/math/ec/rfc7748/X448Field.cs b/crypto/src/math/ec/rfc7748/X448Field.cs index 70273aea8..1e1d379fe 100644 --- a/crypto/src/math/ec/rfc7748/X448Field.cs +++ b/crypto/src/math/ec/rfc7748/X448Field.cs @@ -112,6 +112,22 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 } } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void CMov(int cond, ReadOnlySpan<uint> x, Span<uint> z) + { + Debug.Assert(0 == cond || -1 == cond); + + uint MASK = (uint)cond; + + for (int i = 0; i < Size; ++i) + { + uint z_i = z[i], diff = z_i ^ x[i]; + z_i ^= (diff & MASK); + z[i] = z_i; + } + } +#endif + public static void CNegate(int negate, uint[] z) { Debug.Assert(negate >> 1 == 0); @@ -130,6 +146,13 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 } } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Copy(ReadOnlySpan<uint> x, Span<uint> z) + { + x[..Size].CopyTo(z); + } +#endif + public static uint[] Create() { return new uint[Size]; @@ -161,6 +184,14 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 Decode224(x, xOff + 7, z, 8); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Decode(ReadOnlySpan<uint> x, Span<uint> z) + { + Decode224(x, z); + Decode224(x[7..], z[8..]); + } +#endif + public static void Decode(byte[] x, int xOff, uint[] z) { Decode56(x, xOff, z, 0); @@ -173,6 +204,20 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 Decode56(x, xOff + 49, z, 14); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Decode(ReadOnlySpan<byte> x, Span<uint> z) + { + Decode56(x, z); + Decode56(x[7..], z[2..]); + Decode56(x[14..], z[4..]); + Decode56(x[21..], z[6..]); + Decode56(x[28..], z[8..]); + Decode56(x[35..], z[10..]); + Decode56(x[42..], z[12..]); + Decode56(x[49..], z[14..]); + } +#endif + private static void Decode224(uint[] x, int xOff, uint[] z, int zOff) { uint x0 = x[xOff + 0], x1 = x[xOff + 1], x2 = x[xOff + 2], x3 = x[xOff + 3]; @@ -188,6 +233,23 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 z[zOff + 7] = x6 >> 4; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void Decode224(ReadOnlySpan<uint> x, Span<uint> z) + { + uint x0 = x[0], x1 = x[1], x2 = x[2], x3 = x[3]; + uint x4 = x[4], x5 = x[5], x6 = x[6]; + + z[0] = x0 & M28; + z[1] = (x0 >> 28 | x1 << 4) & M28; + z[2] = (x1 >> 24 | x2 << 8) & M28; + z[3] = (x2 >> 20 | x3 << 12) & M28; + z[4] = (x3 >> 16 | x4 << 16) & M28; + z[5] = (x4 >> 12 | x5 << 20) & M28; + z[6] = (x5 >> 8 | x6 << 24) & M28; + z[7] = x6 >> 4; + } +#endif + private static uint Decode24(byte[] bs, int off) { uint n = bs[off]; @@ -196,6 +258,16 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 return n; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static uint Decode24(ReadOnlySpan<byte> bs) + { + uint n = bs[0]; + n |= (uint)bs[1] << 8; + n |= (uint)bs[2] << 16; + return n; + } +#endif + private static uint Decode32(byte[] bs, int off) { uint n = bs[off]; @@ -205,6 +277,17 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 return n; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static uint Decode32(ReadOnlySpan<byte> bs) + { + uint n = bs[0]; + n |= (uint)bs[1] << 8; + n |= (uint)bs[2] << 16; + n |= (uint)bs[3] << 24; + return n; + } +#endif + private static void Decode56(byte[] bs, int off, uint[] z, int zOff) { uint lo = Decode32(bs, off); @@ -213,12 +296,30 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 z[zOff + 1] = (lo >> 28) | (hi << 4); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void Decode56(ReadOnlySpan<byte> bs, Span<uint> z) + { + uint lo = Decode32(bs); + uint hi = Decode24(bs[4..]); + z[0] = lo & M28; + z[1] = (lo >> 28) | (hi << 4); + } +#endif + public static void Encode(uint[] x, uint[] z, int zOff) { Encode224(x, 0, z, zOff); Encode224(x, 8, z, zOff + 7); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Encode(ReadOnlySpan<uint> x, Span<uint> z) + { + Encode224(x, z); + Encode224(x[8..], z[7..]); + } +#endif + public static void Encode(uint[] x, byte[] z, int zOff) { Encode56(x, 0, z, zOff); @@ -231,6 +332,20 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 Encode56(x, 14, z, zOff + 49); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Encode(ReadOnlySpan<uint> x, Span<byte> z) + { + Encode56(x, z); + Encode56(x[2..], z[7..]); + Encode56(x[4..], z[14..]); + Encode56(x[6..], z[21..]); + Encode56(x[8..], z[28..]); + Encode56(x[10..], z[35..]); + Encode56(x[12..], z[42..]); + Encode56(x[14..], z[49..]); + } +#endif + private static void Encode224(uint[] x, int xOff, uint[] z, int zOff) { uint x0 = x[xOff + 0], x1 = x[xOff + 1], x2 = x[xOff + 2], x3 = x[xOff + 3]; @@ -245,6 +360,22 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 z[zOff + 6] = (x6 >> 24) | (x7 << 4); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void Encode224(ReadOnlySpan<uint> x, Span<uint> z) + { + uint x0 = x[0], x1 = x[1], x2 = x[2], x3 = x[3]; + uint x4 = x[4], x5 = x[5], x6 = x[6], x7 = x[7]; + + z[0] = x0 | (x1 << 28); + z[1] = (x1 >> 4) | (x2 << 24); + z[2] = (x2 >> 8) | (x3 << 20); + z[3] = (x3 >> 12) | (x4 << 16); + z[4] = (x4 >> 16) | (x5 << 12); + z[5] = (x5 >> 20) | (x6 << 8); + z[6] = (x6 >> 24) | (x7 << 4); + } +#endif + private static void Encode24(uint n, byte[] bs, int off) { bs[ off] = (byte)(n ); @@ -252,6 +383,15 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 bs[++off] = (byte)(n >> 16); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void Encode24(uint n, Span<byte> bs) + { + bs[0] = (byte)(n ); + bs[1] = (byte)(n >> 8); + bs[2] = (byte)(n >> 16); + } +#endif + private static void Encode32(uint n, byte[] bs, int off) { bs[ off] = (byte)(n ); @@ -260,6 +400,16 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 bs[++off] = (byte)(n >> 24); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void Encode32(uint n, Span<byte> bs) + { + bs[0] = (byte)(n ); + bs[1] = (byte)(n >> 8); + bs[2] = (byte)(n >> 16); + bs[3] = (byte)(n >> 24); + } +#endif + private static void Encode56(uint[] x, int xOff, byte[] bs, int off) { uint lo = x[xOff], hi = x[xOff + 1]; @@ -267,8 +417,20 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 Encode24(hi >> 4, bs, off + 4); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void Encode56(ReadOnlySpan<uint> x, Span<byte> bs) + { + uint lo = x[0], hi = x[1]; + Encode32(lo | (hi << 28), bs); + Encode24(hi >> 4, bs[4..]); + } +#endif + public static void Inv(uint[] x, uint[] z) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + Inv(x.AsSpan(), z.AsSpan()); +#else //uint[] t = Create(); //PowPm3d4(x, t); //Sqr(t, 2, t); @@ -284,10 +446,30 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 Mod.ModOddInverse(P32, u, u); Decode(u, 0, z); +#endif } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Inv(ReadOnlySpan<uint> x, Span<uint> z) + { + Span<uint> t = stackalloc uint[Size]; + Span<uint> u = stackalloc uint[14]; + + Copy(x, t); + Normalize(t); + Encode(t, u); + + Mod.ModOddInverse(P32, u, u); + + Decode(u, z); + } +#endif + public static void InvVar(uint[] x, uint[] z) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + InvVar(x.AsSpan(), z.AsSpan()); +#else uint[] t = Create(); uint[] u = new uint[14]; @@ -298,8 +480,25 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 Mod.ModOddInverseVar(P32, u, u); Decode(u, 0, z); +#endif } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void InvVar(ReadOnlySpan<uint> x, Span<uint> z) + { + Span<uint> t = stackalloc uint[Size]; + Span<uint> u = stackalloc uint[14]; + + Copy(x, t); + Normalize(t); + Encode(t, u); + + Mod.ModOddInverseVar(P32, u, u); + + Decode(u, z); + } +#endif + public static int IsOne(uint[] x) { uint d = x[0] ^ 1; @@ -726,6 +925,16 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 Debug.Assert(z[15] >> 28 == 0U); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Normalize(Span<uint> z) + { + //int x = (z[15] >> (28 - 1)) & 1; + Reduce(z, 1); + Reduce(z, -1); + Debug.Assert(z[15] >> 28 == 0U); + } +#endif + public static void One(uint[] z) { z[0] = 1U; @@ -775,6 +984,26 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748 z[15] = z15 + (uint)cc; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void Reduce(Span<uint> z, int x) + { + uint u = z[15], z15 = u & M28; + int t = (int)(u >> 28) + x; + + long cc = t; + for (int i = 0; i < 8; ++i) + { + cc += z[i]; z[i] = (uint)cc & M28; cc >>= 28; + } + cc += t; + for (int i = 8; i < 15; ++i) + { + cc += z[i]; z[i] = (uint)cc & M28; cc >>= 28; + } + z[15] = z15 + (uint)cc; + } +#endif + public static void Sqr(uint[] x, uint[] z) { uint x0 = x[0]; diff --git a/crypto/src/math/ec/rfc8032/Ed25519.cs b/crypto/src/math/ec/rfc8032/Ed25519.cs index d88914c90..f3b63f3b3 100644 --- a/crypto/src/math/ec/rfc8032/Ed25519.cs +++ b/crypto/src/math/ec/rfc8032/Ed25519.cs @@ -92,12 +92,12 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 private static PointPrecomp[] PrecompBaseWnaf = null; private static int[] PrecompBaseComb = null; - private ref struct PointAccum + private struct PointAccum { internal int[] x, y, z, u, v; } - private ref struct PointAffine + private struct PointAffine { internal int[] x, y; } @@ -238,6 +238,17 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 return n; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static uint Decode32(ReadOnlySpan<byte> bs) + { + uint n = bs[0]; + n |= (uint)bs[1] << 8; + n |= (uint)bs[2] << 16; + n |= (uint)bs[3] << 24; + return n; + } +#endif + private static void Decode32(byte[] bs, int bsOff, uint[] n, int nOff, int nLen) { for (int i = 0; i < nLen; ++i) @@ -246,6 +257,16 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 } } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void Decode32(ReadOnlySpan<byte> bs, Span<uint> n) + { + for (int i = 0; i < n.Length; ++i) + { + n[i] = Decode32(bs[(i * 4)..]); + } + } +#endif + private static bool DecodePointVar(byte[] p, int pOff, bool negate, ref PointAffine r) { byte[] py = Copy(p, pOff, PointBytes); @@ -285,6 +306,13 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 Decode32(k, kOff, n, 0, ScalarUints); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void DecodeScalar(ReadOnlySpan<byte> k, Span<uint> n) + { + Decode32(k, n[..ScalarUints]); + } +#endif + private static void Dom2(IDigest d, byte phflag, byte[] ctx) { if (ctx != null) @@ -323,6 +351,9 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 private static int EncodePoint(ref PointAccum p, byte[] r, int rOff) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + return EncodePoint(ref p, r.AsSpan(rOff)); +#else int[] x = F.Create(); int[] y = F.Create(); @@ -338,15 +369,53 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 r[rOff + PointBytes - 1] |= (byte)((x[0] & 1) << 7); return result; +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static int EncodePoint(ref PointAccum p, Span<byte> r) + { + int[] x = F.Create(); + int[] y = F.Create(); + + F.Inv(p.z, y); + F.Mul(p.x, y, x); + F.Mul(p.y, y, y); + F.Normalize(x); + F.Normalize(y); + + int result = CheckPoint(x, y); + + F.Encode(y, r); + r[PointBytes - 1] |= (byte)((x[0] & 1) << 7); + + return result; } +#endif public static void GeneratePrivateKey(SecureRandom random, byte[] k) { + if (k.Length != SecretKeySize) + throw new ArgumentException(nameof(k)); + random.NextBytes(k); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void GeneratePrivateKey(SecureRandom random, Span<byte> k) + { + if (k.Length != SecretKeySize) + throw new ArgumentException(nameof(k)); + + random.NextBytes(k); + } +#endif + public static void GeneratePublicKey(byte[] sk, int skOff, byte[] pk, int pkOff) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + GeneratePublicKey(sk.AsSpan(skOff), pk.AsSpan(pkOff)); +#else IDigest d = CreateDigest(); byte[] h = new byte[d.GetDigestSize()]; @@ -357,9 +426,33 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 PruneScalar(h, 0, s); ScalarMultBaseEncoded(s, pk, pkOff); +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void GeneratePublicKey(ReadOnlySpan<byte> sk, Span<byte> pk) + { + IDigest d = CreateDigest(); + int digestSize = d.GetDigestSize(); + Span<byte> h = digestSize <= 128 + ? stackalloc byte[digestSize] + : new byte[digestSize]; + + d.BlockUpdate(sk[..SecretKeySize]); + d.DoFinal(h); + + Span<byte> s = stackalloc byte[ScalarBytes]; + PruneScalar(h, s); + + ScalarMultBaseEncoded(s, pk); } +#endif +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static uint GetWindow4(ReadOnlySpan<uint> x, int n) +#else private static uint GetWindow4(uint[] x, int n) +#endif { int w = (int)((uint)n >> 3), b = (n & 7) << 2; return (x[w] >> b) & 15U; @@ -496,7 +589,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 if (!CheckScalarVar(S, nS)) return false; - PointAffine pA; Init(out pA); + Init(out PointAffine pA); if (!DecodePointVar(pk, pkOff, true, ref pA)) return false; @@ -514,7 +607,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 uint[] nA = new uint[ScalarUints]; DecodeScalar(k, 0, nA); - PointAccum pR; Init(out pR); + Init(out PointAccum pR); ScalarMultStrausVar(nS, nA, ref pA, ref pR); byte[] check = new byte[PointBytes]; @@ -818,6 +911,32 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 } } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void PointLookupZ(ReadOnlySpan<uint> x, int n, ReadOnlySpan<int> table, ref PointPrecompZ r) + { + // TODO This method is currently hard-coded to 4-bit windows and 8 precomputed points + + uint w = GetWindow4(x, n); + + int sign = (int)(w >> (4 - 1)) ^ 1; + int abs = ((int)w ^ -sign) & 7; + + Debug.Assert(sign == 0 || sign == 1); + Debug.Assert(0 <= abs && abs < 8); + + for (int i = 0; i < 8; ++i) + { + int cond = ((i ^ abs) - 1) >> 31; + F.CMov(cond, table, r.ymx_h); table = table[F.Size..]; + F.CMov(cond, table, r.ypx_h); table = table[F.Size..]; + F.CMov(cond, table, r.xyd); table = table[F.Size..]; + F.CMov(cond, table, r.z); table = table[F.Size..]; + } + + F.CSwap(sign, r.ymx_h, r.ypx_h); + F.CNegate(sign, r.xyd); + } +#else private static void PointLookupZ(uint[] x, int n, int[] table, ref PointPrecompZ r) { // TODO This method is currently hard-coded to 4-bit windows and 8 precomputed points @@ -842,6 +961,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 F.CSwap(sign, r.ymx_h, r.ypx_h); F.CNegate(sign, r.xyd); } +#endif private static void PointPrecompute(ref PointAffine p, PointExtended[] points, int count, ref PointTemp t) { @@ -850,7 +970,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 Init(out points[0]); PointCopy(ref p, ref points[0]); - PointExtended d; Init(out d); + Init(out PointExtended d); PointAdd(ref points[0], ref points[0], ref d, ref t); for (int i = 1; i < count; ++i) @@ -864,13 +984,13 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 { Debug.Assert(count > 0); - PointExtended q; Init(out q); + Init(out PointExtended q); PointCopy(ref p, ref q); - PointExtended d; Init(out d); + Init(out PointExtended d); PointAdd(ref q, ref q, ref d, ref t); - PointPrecompZ r; Init(out r); + Init(out PointPrecompZ r); int[] table = F.CreateTable(count * 4); int off = 0; @@ -897,10 +1017,10 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 { Debug.Assert(count > 0); - PointExtended q; Init(out q); + Init(out PointExtended q); PointCopy(ref p, ref q); - PointExtended d; Init(out d); + Init(out PointExtended d); PointAdd(ref q, ref q, ref d, ref t); int i = 0; @@ -938,15 +1058,15 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 int totalPoints = wnafPoints + combPoints; PointExtended[] points = new PointExtended[totalPoints]; - PointTemp t; Init(out t); + Init(out PointTemp t); - PointAffine b; Init(out b); + Init(out PointAffine b); F.Copy(B_x, 0, b.x, 0); F.Copy(B_y, 0, b.y, 0); PointPrecompute(ref b, points, wnafPoints, ref t); - PointAccum p; Init(out p); + Init(out PointAccum p); F.Copy(B_x, 0, p.x, 0); F.Copy(B_y, 0, p.y, 0); F.One(p.z); @@ -959,7 +1079,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 { Init(out toothPowers[tooth]); } - PointExtended u; Init(out u); + Init(out PointExtended u); for (int block = 0; block < PrecompBlocks; ++block) { ref PointExtended sum = ref points[pointsIndex++]; @@ -1032,7 +1152,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 } PrecompBaseComb = F.CreateTable(combPoints * 3); - PointPrecomp s; Init(out s); + Init(out PointPrecomp s); int off = 0; for (int i = wnafPoints; i < totalPoints; ++i) { @@ -1070,6 +1190,17 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 r[ScalarBytes - 1] |= 0x40; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void PruneScalar(ReadOnlySpan<byte> n, Span<byte> r) + { + n[..ScalarBytes].CopyTo(r); + + r[0] &= 0xF8; + r[ScalarBytes - 1] &= 0x7F; + r[ScalarBytes - 1] |= 0x40; + } +#endif + private static byte[] ReduceScalar(byte[] n) { long x00 = Decode32(n, 0) & M32L; // x00:32/-- @@ -1208,6 +1339,9 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 private static void ScalarMult(byte[] k, ref PointAffine p, ref PointAccum r) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + ScalarMult(k.AsSpan(), ref p, ref r); +#else uint[] n = new uint[ScalarUints]; DecodeScalar(k, 0, n); @@ -1217,8 +1351,8 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 uint c2 = Nat.ShiftDownBit(ScalarUints, n, 1U); Debug.Assert(c2 == (1U << 31)); } - PointPrecompZ q; Init(out q); - PointTemp t; Init(out t); + Init(out PointPrecompZ q); + Init(out PointTemp t); int[] table = PointPrecomputeZ(ref p, 8, ref t); PointSetNeutral(ref r); @@ -1237,12 +1371,51 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 PointDouble(ref r); } } +#endif } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void ScalarMult(ReadOnlySpan<byte> k, ref PointAffine p, ref PointAccum r) + { + Span<uint> n = stackalloc uint[ScalarUints]; + DecodeScalar(k, n); + + // Recode the scalar into signed-digit form + { + uint c1 = Nat.CAdd(ScalarUints, ~(int)n[0] & 1, n, L, n); Debug.Assert(c1 == 0U); + uint c2 = Nat.ShiftDownBit(ScalarUints, n, 1U); Debug.Assert(c2 == (1U << 31)); + } + + Init(out PointPrecompZ q); + Init(out PointTemp t); + int[] table = PointPrecomputeZ(ref p, 8, ref t); + + PointSetNeutral(ref r); + + int w = 63; + for (;;) + { + PointLookupZ(n, w, table, ref q); + PointAdd(ref q, ref r, ref t); + + if (--w < 0) + break; + + for (int i = 0; i < 4; ++i) + { + PointDouble(ref r); + } + } + } +#endif + private static void ScalarMultBase(byte[] k, ref PointAccum r) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + ScalarMultBase(k.AsSpan(), ref r); +#else // Equivalent (but much slower) - //PointAffine p; Init(out p); + //Init(out PointAffine p); //F.Copy(B_x, 0, p.x, 0); //F.Copy(B_y, 0, p.y, 0); //ScalarMult(k, ref p, ref r); @@ -1267,8 +1440,8 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 } } - PointPrecomp p; Init(out p); - PointTemp t; Init(out t); + Init(out PointPrecomp p); + Init(out PointTemp t); PointSetNeutral(ref r); int resultSign = 0; @@ -1302,22 +1475,107 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 F.CNegate(resultSign, r.x); F.CNegate(resultSign, r.u); +#endif } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void ScalarMultBase(ReadOnlySpan<byte> k, ref PointAccum r) + { + // Equivalent (but much slower) + //Init(out PointAffine p); + //F.Copy(B_x, 0, p.x, 0); + //F.Copy(B_y, 0, p.y, 0); + //ScalarMult(k, ref p, ref r); + + Precompute(); + + Span<uint> n = stackalloc uint[ScalarUints]; + DecodeScalar(k, n); + + // Recode the scalar into signed-digit form, then group comb bits in each block + { + uint c1 = Nat.CAdd(ScalarUints, ~(int)n[0] & 1, n, L, n); Debug.Assert(c1 == 0U); + uint c2 = Nat.ShiftDownBit(ScalarUints, n, 1U); Debug.Assert(c2 == (1U << 31)); + + /* + * Because we are using 4 teeth and 8 spacing, each limb of n corresponds to one of the 8 blocks. + * Therefore we can efficiently group the bits for each comb position using a (double) shuffle. + */ + for (int i = 0; i < ScalarUints; ++i) + { + n[i] = Interleave.Shuffle2(n[i]); + } + } + + Init(out PointPrecomp p); + Init(out PointTemp t); + + PointSetNeutral(ref r); + int resultSign = 0; + + int cOff = (PrecompSpacing - 1) * PrecompTeeth; + for (;;) + { + for (int b = 0; b < PrecompBlocks; ++b) + { + uint w = n[b] >> cOff; + int sign = (int)(w >> (PrecompTeeth - 1)) & 1; + int abs = ((int)w ^ -sign) & PrecompMask; + + Debug.Assert(sign == 0 || sign == 1); + Debug.Assert(0 <= abs && abs < PrecompPoints); + + PointLookup(b, abs, ref p); + + F.CNegate(resultSign ^ sign, r.x); + F.CNegate(resultSign ^ sign, r.u); + resultSign = sign; + + PointAdd(ref p, ref r, ref t); + } + + if ((cOff -= PrecompTeeth) < 0) + break; + + PointDouble(ref r); + } + + F.CNegate(resultSign, r.x); + F.CNegate(resultSign, r.u); + } +#endif + private static void ScalarMultBaseEncoded(byte[] k, byte[] r, int rOff) { - PointAccum p; Init(out p); +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + ScalarMultBaseEncoded(k.AsSpan(), r.AsSpan(rOff)); +#else + Init(out PointAccum p); ScalarMultBase(k, ref p); if (0 == EncodePoint(ref p, r, rOff)) throw new InvalidOperationException(); +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void ScalarMultBaseEncoded(ReadOnlySpan<byte> k, Span<byte> r) + { + Init(out PointAccum p); + ScalarMultBase(k, ref p); + if (0 == EncodePoint(ref p, r)) + throw new InvalidOperationException(); } +#endif internal static void ScalarMultBaseYZ(byte[] k, int kOff, int[] y, int[] z) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + ScalarMultBaseYZ(k.AsSpan(kOff), y.AsSpan(), z.AsSpan()); +#else byte[] n = new byte[ScalarBytes]; PruneScalar(k, kOff, n); - PointAccum p; Init(out p); + Init(out PointAccum p); ScalarMultBase(n, ref p); if (0 == CheckPoint(p.x, p.y, p.z)) @@ -1325,7 +1583,25 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 F.Copy(p.y, 0, y, 0); F.Copy(p.z, 0, z, 0); +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + internal static void ScalarMultBaseYZ(ReadOnlySpan<byte> k, Span<int> y, Span<int> z) + { + Span<byte> n = stackalloc byte[ScalarBytes]; + PruneScalar(k, n); + + Init(out PointAccum p); + ScalarMultBase(n, ref p); + + if (0 == CheckPoint(p.x, p.y, p.z)) + throw new InvalidOperationException(); + + F.Copy(p.y, y); + F.Copy(p.z, z); } +#endif private static void ScalarMultOrderVar(ref PointAffine p, ref PointAccum r) { @@ -1333,7 +1609,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 int count = 1 << (WnafWidth - 2); PointPrecompZ[] tp = new PointPrecompZ[count]; - PointTemp t; Init(out t); + Init(out PointTemp t); PointPrecomputeZ(ref p, tp, count, ref t); PointSetNeutral(ref r); @@ -1365,7 +1641,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 int count = 1 << (WnafWidth - 2); PointPrecompZ[] tp = new PointPrecompZ[count]; - PointTemp t; Init(out t); + Init(out PointTemp t); PointPrecomputeZ(ref p, tp, count, ref t); PointSetNeutral(ref r); @@ -1465,7 +1741,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 public static bool ValidatePublicKeyFull(byte[] pk, int pkOff) { - PointAffine p; Init(out p); + Init(out PointAffine p); if (!DecodePointVar(pk, pkOff, false, ref p)) return false; @@ -1475,7 +1751,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 if (IsNeutralElementVar(p.x, p.y)) return false; - PointAccum r; Init(out r); + Init(out PointAccum r); ScalarMultOrderVar(ref p, ref r); F.Normalize(r.x); @@ -1487,7 +1763,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 public static bool ValidatePublicKeyPartial(byte[] pk, int pkOff) { - PointAffine p; Init(out p); + Init(out PointAffine p); return DecodePointVar(pk, pkOff, false, ref p); } diff --git a/crypto/src/math/ec/rfc8032/Ed448.cs b/crypto/src/math/ec/rfc8032/Ed448.cs index 55ec5f03b..b73aaa7f8 100644 --- a/crypto/src/math/ec/rfc8032/Ed448.cs +++ b/crypto/src/math/ec/rfc8032/Ed448.cs @@ -222,6 +222,17 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 return n; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static uint Decode32(ReadOnlySpan<byte> bs) + { + uint n = bs[0]; + n |= (uint)bs[1] << 8; + n |= (uint)bs[2] << 16; + n |= (uint)bs[3] << 24; + return n; + } +#endif + private static void Decode32(byte[] bs, int bsOff, uint[] n, int nOff, int nLen) { for (int i = 0; i < nLen; ++i) @@ -230,6 +241,16 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 } } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void Decode32(ReadOnlySpan<byte> bs, Span<uint> n) + { + for (int i = 0; i < n.Length; ++i) + { + n[i] = Decode32(bs[(i * 4)..]); + } + } +#endif + private static bool DecodePointVar(byte[] p, int pOff, bool negate, ref PointProjective r) { byte[] py = Copy(p, pOff, PointBytes); @@ -273,6 +294,15 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 Decode32(k, kOff, n, 0, ScalarUints); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void DecodeScalar(ReadOnlySpan<byte> k, Span<uint> n) + { + Debug.Assert(k[ScalarBytes - 1] == 0x00); + + Decode32(k, n[..ScalarUints]); + } +#endif + private static void Dom4(IXof d, byte phflag, byte[] ctx) { int n = Dom4Prefix.Length; @@ -325,26 +355,84 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 return result; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static int EncodePoint(ref PointProjective p, Span<byte> r) + { + uint[] x = F.Create(); + uint[] y = F.Create(); + + F.Inv(p.z, y); + F.Mul(p.x, y, x); + F.Mul(p.y, y, y); + F.Normalize(x); + F.Normalize(y); + + int result = CheckPoint(x, y); + + F.Encode(y, r); + r[PointBytes - 1] = (byte)((x[0] & 1) << 7); + + return result; + } +#endif + public static void GeneratePrivateKey(SecureRandom random, byte[] k) { + if (k.Length != SecretKeySize) + throw new ArgumentException(nameof(k)); + random.NextBytes(k); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void GeneratePrivateKey(SecureRandom random, Span<byte> k) + { + if (k.Length != SecretKeySize) + throw new ArgumentException(nameof(k)); + + random.NextBytes(k); + } +#endif + public static void GeneratePublicKey(byte[] sk, int skOff, byte[] pk, int pkOff) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + GeneratePublicKey(sk.AsSpan(skOff), pk.AsSpan(pkOff)); +#else IXof d = CreateXof(); byte[] h = new byte[ScalarBytes * 2]; d.BlockUpdate(sk, skOff, SecretKeySize); - d.DoFinal(h, 0, h.Length); + d.OutputFinal(h, 0, h.Length); byte[] s = new byte[ScalarBytes]; PruneScalar(h, 0, s); ScalarMultBaseEncoded(s, pk, pkOff); +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void GeneratePublicKey(ReadOnlySpan<byte> sk, Span<byte> pk) + { + IXof d = CreateXof(); + Span<byte> h = stackalloc byte[ScalarBytes * 2]; + + d.BlockUpdate(sk[..SecretKeySize]); + d.OutputFinal(h); + + Span<byte> s = stackalloc byte[ScalarBytes]; + PruneScalar(h, s); + + ScalarMultBaseEncoded(s, pk); } +#endif +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static uint GetWindow4(ReadOnlySpan<uint> x, int n) +#else private static uint GetWindow4(uint[] x, int n) +#endif { int w = (int)((uint)n >> 3), b = (n & 7) << 2; return (x[w] >> b) & 15U; @@ -407,7 +495,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 Dom4(d, phflag, ctx); d.BlockUpdate(h, ScalarBytes, ScalarBytes); d.BlockUpdate(m, mOff, mLen); - d.DoFinal(h, 0, h.Length); + d.OutputFinal(h, 0, h.Length); byte[] r = ReduceScalar(h); byte[] R = new byte[PointBytes]; @@ -417,7 +505,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 d.BlockUpdate(R, 0, PointBytes); d.BlockUpdate(pk, pkOff, PointBytes); d.BlockUpdate(m, mOff, mLen); - d.DoFinal(h, 0, h.Length); + d.OutputFinal(h, 0, h.Length); byte[] k = ReduceScalar(h); byte[] S = CalculateS(r, k, s); @@ -436,7 +524,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 byte[] h = new byte[ScalarBytes * 2]; d.BlockUpdate(sk, skOff, SecretKeySize); - d.DoFinal(h, 0, h.Length); + d.OutputFinal(h, 0, h.Length); byte[] s = new byte[ScalarBytes]; PruneScalar(h, 0, s); @@ -457,7 +545,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 byte[] h = new byte[ScalarBytes * 2]; d.BlockUpdate(sk, skOff, SecretKeySize); - d.DoFinal(h, 0, h.Length); + d.OutputFinal(h, 0, h.Length); byte[] s = new byte[ScalarBytes]; PruneScalar(h, 0, s); @@ -481,7 +569,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 if (!CheckScalarVar(S, nS)) return false; - PointProjective pA; Init(out pA); + Init(out PointProjective pA); if (!DecodePointVar(pk, pkOff, true, ref pA)) return false; @@ -492,14 +580,14 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 d.BlockUpdate(R, 0, PointBytes); d.BlockUpdate(pk, pkOff, PointBytes); d.BlockUpdate(m, mOff, mLen); - d.DoFinal(h, 0, h.Length); + d.OutputFinal(h, 0, h.Length); byte[] k = ReduceScalar(h); uint[] nA = new uint[ScalarUints]; DecodeScalar(k, 0, nA); - PointProjective pR; Init(out pR); + Init(out PointProjective pR); ScalarMultStrausVar(nS, nA, ref pA, ref pR); byte[] check = new byte[PointBytes]; @@ -763,6 +851,30 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 } } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void PointLookup(ReadOnlySpan<uint> x, int n, ReadOnlySpan<uint> table, ref PointProjective r) + { + // TODO This method is currently hardcoded to 4-bit windows and 8 precomputed points + + uint w = GetWindow4(x, n); + + int sign = (int)(w >> (4 - 1)) ^ 1; + int abs = ((int)w ^ -sign) & 7; + + Debug.Assert(sign == 0 || sign == 1); + Debug.Assert(0 <= abs && abs < 8); + + for (int i = 0; i < 8; ++i) + { + int cond = ((i ^ abs) - 1) >> 31; + F.CMov(cond, table, r.x); table = table[F.Size..]; + F.CMov(cond, table, r.y); table = table[F.Size..]; + F.CMov(cond, table, r.z); table = table[F.Size..]; + } + + F.CNegate(sign, r.x); + } +#else private static void PointLookup(uint[] x, int n, uint[] table, ref PointProjective r) { // TODO This method is currently hardcoded to 4-bit windows and 8 precomputed points @@ -785,6 +897,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 F.CNegate(sign, r.x); } +#endif private static void PointLookup15(uint[] table, ref PointProjective r) { @@ -799,10 +912,10 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 { Debug.Assert(count > 0); - PointProjective q; Init(out q); + Init(out PointProjective q); PointCopy(ref p, ref q); - PointProjective d; Init(out d); + Init(out PointProjective d); PointCopy(ref q, ref d); PointDouble(ref d); @@ -829,7 +942,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 { Debug.Assert(count > 0); - PointProjective d; Init(out d); + Init(out PointProjective d); PointCopy(ref p, ref d); PointDouble(ref d); @@ -866,7 +979,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 PointProjective[] points = new PointProjective[totalPoints]; - PointProjective p; Init(out p); + Init(out PointProjective p); F.Copy(B_x, 0, p.x, 0); F.Copy(B_y, 0, p.y, 0); F.One(p.z); @@ -960,6 +1073,17 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 r[ScalarBytes - 1] = 0x00; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void PruneScalar(ReadOnlySpan<byte> n, Span<byte> r) + { + n[..(ScalarBytes - 1)].CopyTo(r); + + r[0] &= 0xFC; + r[ScalarBytes - 2] |= 0x80; + r[ScalarBytes - 1] = 0x00; + } +#endif + private static byte[] ReduceScalar(byte[] n) { ulong x00 = Decode32(n, 0); // x00:32/-- @@ -1239,6 +1363,9 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 private static void ScalarMult(byte[] k, ref PointProjective p, ref PointProjective r) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + ScalarMult(k.AsSpan(), ref p, ref r); +#else uint[] n = new uint[ScalarUints]; DecodeScalar(k, 0, n); @@ -1251,7 +1378,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 } uint[] table = PointPrecompute(ref p, 8); - PointProjective q; Init(out q); + Init(out PointProjective q); // Replace first 4 doublings (2^4 * P) with 1 addition (P + 15 * P) PointLookup15(table, ref r); @@ -1271,12 +1398,54 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 PointDouble(ref r); } } +#endif } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void ScalarMult(ReadOnlySpan<byte> k, ref PointProjective p, ref PointProjective r) + { + Span<uint> n = stackalloc uint[ScalarUints]; + DecodeScalar(k, n); + + // Recode the scalar into signed-digit form + { + uint c1 = Nat.CAdd(ScalarUints, ~(int)n[0] & 1, n, L, n); + uint c2 = Nat.ShiftDownBit(ScalarUints, n, c1); Debug.Assert(c2 == (1U << 31)); + + // NOTE: Bit 448 is implicitly set after the signed-digit recoding + } + + uint[] table = PointPrecompute(ref p, 8); + Init(out PointProjective q); + + // Replace first 4 doublings (2^4 * P) with 1 addition (P + 15 * P) + PointLookup15(table, ref r); + PointAdd(ref p, ref r); + + int w = 111; + for (;;) + { + PointLookup(n, w, table, ref q); + PointAdd(ref q, ref r); + + if (--w < 0) + break; + + for (int i = 0; i < 4; ++i) + { + PointDouble(ref r); + } + } + } +#endif + private static void ScalarMultBase(byte[] k, ref PointProjective r) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + ScalarMultBase(k.AsSpan(), ref r); +#else // Equivalent (but much slower) - //PointProjective p; Init(out p); + //Init(out PointProjective p); //F.Copy(B_x, 0, p.x, 0); //F.Copy(B_y, 0, p.y, 0); //F.One(p.z); @@ -1295,7 +1464,71 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 Debug.Assert(c == (1U << 31)); } - PointAffine p; Init(out p); + Init(out PointAffine p); + + PointSetNeutral(ref r); + + int cOff = PrecompSpacing - 1; + for (;;) + { + int tPos = cOff; + + for (int b = 0; b < PrecompBlocks; ++b) + { + uint w = 0; + for (int t = 0; t < PrecompTeeth; ++t) + { + uint tBit = n[tPos >> 5] >> (tPos & 0x1F); + w &= ~(1U << t); + w ^= (tBit << t); + tPos += PrecompSpacing; + } + + int sign = (int)(w >> (PrecompTeeth - 1)) & 1; + int abs = ((int)w ^ -sign) & PrecompMask; + + Debug.Assert(sign == 0 || sign == 1); + Debug.Assert(0 <= abs && abs < PrecompPoints); + + PointLookup(b, abs, ref p); + + F.CNegate(sign, p.x); + + PointAdd(ref p, ref r); + } + + if (--cOff < 0) + break; + + PointDouble(ref r); + } +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void ScalarMultBase(ReadOnlySpan<byte> k, ref PointProjective r) + { + // Equivalent (but much slower) + //Init(out PointProjective p); + //F.Copy(B_x, 0, p.x, 0); + //F.Copy(B_y, 0, p.y, 0); + //F.One(p.z); + //ScalarMult(k, ref p, ref r); + + Precompute(); + + Span<uint> n = stackalloc uint[ScalarUints + 1]; + DecodeScalar(k, n); + + // Recode the scalar into signed-digit form + { + n[ScalarUints] = (1U << (PrecompRange - 448)) + + Nat.CAdd(ScalarUints, ~(int)n[0] & 1, n, L, n); + uint c = Nat.ShiftDownBit(n.Length, n, 0); + Debug.Assert(c == (1U << 31)); + } + + Init(out PointAffine p); PointSetNeutral(ref r); @@ -1334,21 +1567,39 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 PointDouble(ref r); } } +#endif private static void ScalarMultBaseEncoded(byte[] k, byte[] r, int rOff) { - PointProjective p; Init(out p); +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + ScalarMultBaseEncoded(k.AsSpan(), r.AsSpan(rOff)); +#else + Init(out PointProjective p); ScalarMultBase(k, ref p); if (0 == EncodePoint(ref p, r, rOff)) throw new InvalidOperationException(); +#endif } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void ScalarMultBaseEncoded(ReadOnlySpan<byte> k, Span<byte> r) + { + Init(out PointProjective p); + ScalarMultBase(k, ref p); + if (0 == EncodePoint(ref p, r)) + throw new InvalidOperationException(); + } +#endif + internal static void ScalarMultBaseXY(byte[] k, int kOff, uint[] x, uint[] y) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + ScalarMultBaseXY(k.AsSpan(kOff), x.AsSpan(), y.AsSpan()); +#else byte[] n = new byte[ScalarBytes]; PruneScalar(k, kOff, n); - PointProjective p; Init(out p); + Init(out PointProjective p); ScalarMultBase(n, ref p); if (0 == CheckPoint(p.x, p.y, p.z)) @@ -1356,7 +1607,25 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 F.Copy(p.x, 0, x, 0); F.Copy(p.y, 0, y, 0); +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + internal static void ScalarMultBaseXY(ReadOnlySpan<byte> k, Span<uint> x, Span<uint> y) + { + Span<byte> n = stackalloc byte[ScalarBytes]; + PruneScalar(k, n); + + Init(out PointProjective p); + ScalarMultBase(n, ref p); + + if (0 == CheckPoint(p.x, p.y, p.z)) + throw new InvalidOperationException(); + + F.Copy(p.x, x); + F.Copy(p.y, y); } +#endif private static void ScalarMultOrderVar(ref PointProjective p, ref PointProjective r) { @@ -1457,7 +1726,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 public static void SignPrehash(byte[] sk, int skOff, byte[] ctx, IXof ph, byte[] sig, int sigOff) { byte[] m = new byte[PrehashSize]; - if (PrehashSize != ph.DoFinal(m, 0, PrehashSize)) + if (PrehashSize != ph.OutputFinal(m, 0, PrehashSize)) throw new ArgumentException("ph"); byte phflag = 0x01; @@ -1468,7 +1737,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 public static void SignPrehash(byte[] sk, int skOff, byte[] pk, int pkOff, byte[] ctx, IXof ph, byte[] sig, int sigOff) { byte[] m = new byte[PrehashSize]; - if (PrehashSize != ph.DoFinal(m, 0, PrehashSize)) + if (PrehashSize != ph.OutputFinal(m, 0, PrehashSize)) throw new ArgumentException("ph"); byte phflag = 0x01; @@ -1478,7 +1747,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 public static bool ValidatePublicKeyFull(byte[] pk, int pkOff) { - PointProjective p; Init(out p); + Init(out PointProjective p); if (!DecodePointVar(pk, pkOff, false, ref p)) return false; @@ -1489,7 +1758,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 if (IsNeutralElementVar(p.x, p.y, p.z)) return false; - PointProjective r; Init(out r); + Init(out PointProjective r); ScalarMultOrderVar(ref p, ref r); F.Normalize(r.x); @@ -1501,7 +1770,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 public static bool ValidatePublicKeyPartial(byte[] pk, int pkOff) { - PointProjective p; Init(out p); + Init(out PointProjective p); return DecodePointVar(pk, pkOff, false, ref p); } @@ -1522,7 +1791,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 public static bool VerifyPrehash(byte[] sig, int sigOff, byte[] pk, int pkOff, byte[] ctx, IXof ph) { byte[] m = new byte[PrehashSize]; - if (PrehashSize != ph.DoFinal(m, 0, PrehashSize)) + if (PrehashSize != ph.OutputFinal(m, 0, PrehashSize)) throw new ArgumentException("ph"); byte phflag = 0x01; diff --git a/crypto/src/math/raw/Bits.cs b/crypto/src/math/raw/Bits.cs index d344e1672..423151651 100644 --- a/crypto/src/math/raw/Bits.cs +++ b/crypto/src/math/raw/Bits.cs @@ -1,28 +1,85 @@ -using System; +using System.Diagnostics; +#if NETSTANDARD1_0_OR_GREATER || NETCOREAPP1_0_OR_GREATER +using System.Runtime.CompilerServices; +#endif namespace Org.BouncyCastle.Math.Raw { - internal abstract class Bits + internal static class Bits { +#if NETSTANDARD1_0_OR_GREATER || NETCOREAPP1_0_OR_GREATER + [MethodImpl(MethodImplOptions.AggressiveInlining)] +#endif internal static uint BitPermuteStep(uint x, uint m, int s) { + Debug.Assert((m & (m << s)) == 0U); + Debug.Assert((m << s) >> s == m); + uint t = (x ^ (x >> s)) & m; - return (t ^ (t << s)) ^ x; + return t ^ (t << s) ^ x; } +#if NETSTANDARD1_0_OR_GREATER || NETCOREAPP1_0_OR_GREATER + [MethodImpl(MethodImplOptions.AggressiveInlining)] +#endif internal static ulong BitPermuteStep(ulong x, ulong m, int s) { + Debug.Assert((m & (m << s)) == 0UL); + Debug.Assert((m << s) >> s == m); + ulong t = (x ^ (x >> s)) & m; - return (t ^ (t << s)) ^ x; + return t ^ (t << s) ^ x; + } + +#if NETSTANDARD1_0_OR_GREATER || NETCOREAPP1_0_OR_GREATER + [MethodImpl(MethodImplOptions.AggressiveInlining)] +#endif + internal static void BitPermuteStep2(ref uint hi, ref uint lo, uint m, int s) + { +#if NETSTANDARD2_1_OR_GREATER || NETCOREAPP1_1_OR_GREATER + Debug.Assert(!Unsafe.AreSame(ref hi, ref lo) || (m & (m << s)) == 0U); +#endif + Debug.Assert((m << s) >> s == m); + + uint t = ((lo >> s) ^ hi) & m; + lo ^= t << s; + hi ^= t; } +#if NETSTANDARD1_0_OR_GREATER || NETCOREAPP1_0_OR_GREATER + [MethodImpl(MethodImplOptions.AggressiveInlining)] +#endif + internal static void BitPermuteStep2(ref ulong hi, ref ulong lo, ulong m, int s) + { +#if NETSTANDARD2_1_OR_GREATER || NETCOREAPP1_1_OR_GREATER + Debug.Assert(!Unsafe.AreSame(ref hi, ref lo) || (m & (m << s)) == 0UL); +#endif + Debug.Assert((m << s) >> s == m); + + ulong t = ((lo >> s) ^ hi) & m; + lo ^= t << s; + hi ^= t; + } + +#if NETSTANDARD1_0_OR_GREATER || NETCOREAPP1_0_OR_GREATER + [MethodImpl(MethodImplOptions.AggressiveInlining)] +#endif internal static uint BitPermuteStepSimple(uint x, uint m, int s) { + Debug.Assert((m & (m << s)) == 0U); + Debug.Assert((m << s) >> s == m); + return ((x & m) << s) | ((x >> s) & m); } +#if NETSTANDARD1_0_OR_GREATER || NETCOREAPP1_0_OR_GREATER + [MethodImpl(MethodImplOptions.AggressiveInlining)] +#endif internal static ulong BitPermuteStepSimple(ulong x, ulong m, int s) { + Debug.Assert((m & (m << s)) == 0UL); + Debug.Assert((m << s) >> s == m); + return ((x & m) << s) | ((x >> s) & m); } } diff --git a/crypto/src/math/raw/Interleave.cs b/crypto/src/math/raw/Interleave.cs index 9ff85c572..02aa79551 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 d4d1f716d..721134b0c 100644 --- a/crypto/src/math/raw/Mod.cs +++ b/crypto/src/math/raw/Mod.cs @@ -12,20 +12,26 @@ namespace Org.BouncyCastle.Math.Raw * computation and modular inversion" by Daniel J. Bernstein and Bo-Yin Yang. */ - internal abstract class Mod + internal static class Mod { - private static readonly SecureRandom RandomSource = new SecureRandom(); - private const int M30 = 0x3FFFFFFF; private const ulong M32UL = 0xFFFFFFFFUL; +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void CheckedModOddInverse(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x, Span<uint> z) +#else public static void CheckedModOddInverse(uint[] m, uint[] x, uint[] z) +#endif { 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."); @@ -33,7 +39,7 @@ namespace Org.BouncyCastle.Math.Raw public static uint Inverse32(uint d) { - Debug.Assert((d & 1) == 1); + Debug.Assert((d & 1U) == 1U); //int x = d + (((d + 1) & 4) << 1); // d.x == 1 mod 2**4 uint x = d; // d.x == 1 mod 2**3 @@ -41,12 +47,30 @@ namespace Org.BouncyCastle.Math.Raw x *= 2 - d * x; // d.x == 1 mod 2**12 x *= 2 - d * x; // d.x == 1 mod 2**24 x *= 2 - d * x; // d.x == 1 mod 2**48 - Debug.Assert(d * x == 1); + Debug.Assert(d * x == 1U); + return x; + } + + public static ulong Inverse64(ulong d) + { + Debug.Assert((d & 1UL) == 1UL); + + //ulong x = d + (((d + 1) & 4) << 1); // d.x == 1 mod 2**4 + ulong x = d; // d.x == 1 mod 2**3 + x *= 2 - d * x; // d.x == 1 mod 2**6 + x *= 2 - d * x; // d.x == 1 mod 2**12 + x *= 2 - d * x; // d.x == 1 mod 2**24 + x *= 2 - d * x; // d.x == 1 mod 2**48 + x *= 2 - d * x; // d.x == 1 mod 2**96 + Debug.Assert(d * x == 1UL); return x; } public static uint ModOddInverse(uint[] m, uint[] x, uint[] z) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + return ModOddInverse(m.AsSpan(), x.AsSpan(), z.AsSpan()); +#else int len32 = m.Length; Debug.Assert(len32 > 0); Debug.Assert((m[0] & 1) != 0); @@ -89,13 +113,72 @@ namespace Org.BouncyCastle.Math.Raw CNormalize30(len30, signF, D, M); Decode30(bits, D, 0, z, 0); - Debug.Assert(0 != Nat.LessThan(len32, z, m)); + Debug.Assert(0 != Nat.LessThan(m.Length, z, m)); return (uint)(EqualTo(len30, F, 1) & EqualToZero(len30, G)); +#endif } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint ModOddInverse(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x, Span<uint> z) + { + 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; + + Span<int> alloc = len30 <= 50 + ? stackalloc int[len30 * 5] + : new int[len30 * 5]; + + Span<int> t = stackalloc int[4]; + Span<int> D = alloc[..len30]; alloc = alloc[len30..]; + Span<int> E = alloc[..len30]; alloc = alloc[len30..]; + Span<int> F = alloc[..len30]; alloc = alloc[len30..]; + Span<int> G = alloc[..len30]; alloc = alloc[len30..]; + Span<int> M = alloc[..len30]; + + E[0] = 1; + Encode30(bits, x, G); + Encode30(bits, m, M); + M.CopyTo(F); + + int delta = 0; + int m0Inv32 = (int)Inverse32((uint)M[0]); + int maxDivsteps = GetMaximumDivsteps(bits); + + for (int divSteps = 0; divSteps < maxDivsteps; divSteps += 30) + { + delta = Divsteps30(delta, F[0], G[0], t); + UpdateDE30(len30, D, E, t, m0Inv32, M); + UpdateFG30(len30, F, G, t); + } + + int signF = F[len30 - 1] >> 31; + CNegate30(len30, signF, F); + + /* + * D is in the range (-2.M, M). First, conditionally add M if D is negative, to bring it + * into the range (-M, M). Then normalize by conditionally negating (according to signF) + * and/or then adding M, to bring it into the range [0, M). + */ + CNormalize30(len30, signF, D, M); + + Decode30(bits, D, z); + Debug.Assert(0 != Nat.LessThan(m.Length, z, m)); + + return (uint)(EqualTo(len30, F, 1) & EqualToZero(len30, G)); + } +#endif + public static bool ModOddInverseVar(uint[] m, uint[] x, uint[] z) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + return ModOddInverseVar(m.AsSpan(), x.AsSpan(), z.AsSpan()); +#else int len32 = m.Length; Debug.Assert(len32 > 0); Debug.Assert((m[0] & 1) != 0); @@ -178,12 +261,108 @@ namespace Org.BouncyCastle.Math.Raw Debug.Assert(0 == signD); Decode30(bits, D, 0, z, 0); - Debug.Assert(!Nat.Gte(len32, z, m)); + Debug.Assert(!Nat.Gte(m.Length, z, m)); + + return true; +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static bool ModOddInverseVar(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x, Span<uint> z) + { + 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; + + Span<int> alloc = len30 <= 50 + ? stackalloc int[len30 * 5] + : new int[len30 * 5]; + + Span<int> t = stackalloc int[4]; + Span<int> D = alloc[..len30]; alloc = alloc[len30..]; + Span<int> E = alloc[..len30]; alloc = alloc[len30..]; + Span<int> F = alloc[..len30]; alloc = alloc[len30..]; + Span<int> G = alloc[..len30]; alloc = alloc[len30..]; + Span<int> M = alloc[..len30]; + + E[0] = 1; + Encode30(bits, x, G); + Encode30(bits, m, M); + M.CopyTo(F); + + int clzG = Integers.NumberOfLeadingZeros(G[len30 - 1] | 1) - (len30 * 30 + 2 - bits); + int eta = -1 - clzG; + int lenDE = len30, lenFG = len30; + int m0Inv32 = (int)Inverse32((uint)M[0]); + int maxDivsteps = GetMaximumDivsteps(bits); + + int divsteps = 0; + while (!IsZero(lenFG, G)) + { + if (divsteps >= maxDivsteps) + return false; + + divsteps += 30; + + 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; + } + } + + int signF = F[lenFG - 1] >> 31; + + /* + * D is in the range (-2.M, M). First, conditionally add M if D is negative, to bring it + * into the range (-M, M). Then normalize by conditionally negating (according to signF) + * and/or then adding M, to bring it into the range [0, M). + */ + int signD = D[lenDE - 1] >> 31; + if (signD < 0) + { + signD = Add30(lenDE, D, M); + } + if (signF < 0) + { + signD = Negate30(lenDE, D); + signF = Negate30(lenFG, F); + } + Debug.Assert(0 == signF); + + if (!IsOne(lenFG, F)) + return false; + + if (signD < 0) + { + signD = Add30(lenDE, D, M); + } + Debug.Assert(0 == signD); + + Decode30(bits, D, z); + Debug.Assert(!Nat.Gte(m.Length, z, m)); return true; } +#endif - public static uint[] Random(uint[] p) + public static uint[] Random(SecureRandom random, uint[] p) { int len = p.Length; uint[] s = Nat.Create(len); @@ -195,10 +374,10 @@ namespace Org.BouncyCastle.Math.Raw m |= m >> 8; m |= m >> 16; + byte[] bytes = new byte[len << 2]; do { - byte[] bytes = new byte[len << 2]; - RandomSource.NextBytes(bytes); + random.NextBytes(bytes); Pack.BE_To_UInt32(bytes, 0, s); s[len - 1] &= m; } @@ -207,7 +386,41 @@ namespace Org.BouncyCastle.Math.Raw return s; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Random(SecureRandom random, ReadOnlySpan<uint> p, Span<uint> z) + { + int len = p.Length; + if (z.Length < len) + throw new ArgumentException("insufficient space", nameof(z)); + + var s = z[..len]; + + uint m = p[len - 1]; + m |= m >> 1; + m |= m >> 2; + m |= m >> 4; + m |= m >> 8; + m |= m >> 16; + + Span<byte> bytes = len <= 256 + ? stackalloc byte[len << 2] + : new byte[len << 2]; + + do + { + random.NextBytes(bytes); + Pack.BE_To_UInt32(bytes, s); + s[len - 1] &= m; + } + while (Nat.Gte(len, s, p)); + } +#endif + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static int Add30(int len30, Span<int> D, ReadOnlySpan<int> M) +#else private static int Add30(int len30, int[] D, int[] M) +#endif { Debug.Assert(len30 > 0); Debug.Assert(D.Length >= len30); @@ -224,7 +437,11 @@ namespace Org.BouncyCastle.Math.Raw return c; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void CNegate30(int len30, int cond, Span<int> D) +#else private static void CNegate30(int len30, int cond, int[] D) +#endif { Debug.Assert(len30 > 0); Debug.Assert(D.Length >= len30); @@ -239,7 +456,11 @@ namespace Org.BouncyCastle.Math.Raw D[last] = c; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void CNormalize30(int len30, int condNegate, Span<int> D, ReadOnlySpan<int> M) +#else private static void CNormalize30(int len30, int condNegate, int[] D, int[] M) +#endif { Debug.Assert(len30 > 0); Debug.Assert(D.Length >= len30); @@ -277,6 +498,29 @@ namespace Org.BouncyCastle.Math.Raw } } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void Decode30(int bits, ReadOnlySpan<int> x, Span<uint> z) + { + Debug.Assert(bits > 0); + + int avail = 0; + ulong data = 0L; + + int xOff = 0, zOff = 0; + while (bits > 0) + { + while (avail < System.Math.Min(32, bits)) + { + data |= (ulong)x[xOff++] << avail; + avail += 30; + } + + z[zOff++] = (uint)data; data >>= 32; + avail -= 32; + bits -= 32; + } + } +#else private static void Decode30(int bits, int[] x, int xOff, uint[] z, int zOff) { Debug.Assert(bits > 0); @@ -297,8 +541,13 @@ namespace Org.BouncyCastle.Math.Raw bits -= 32; } } +#endif +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static int Divsteps30(int delta, int f0, int g0, Span<int> t) +#else private static int Divsteps30(int delta, int f0, int g0, int[] t) +#endif { int u = 1 << 30, v = 0, q = 0, r = 1 << 30; int f = f0, g = g0; @@ -340,7 +589,11 @@ namespace Org.BouncyCastle.Math.Raw return delta; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static int Divsteps30Var(int eta, int f0, int g0, Span<int> t) +#else private static int Divsteps30Var(int eta, int f0, int g0, int[] t) +#endif { int u = 1, v = 0, q = 0, r = 1; int f = f0, g = g0, m, w, x, y, z; @@ -403,6 +656,29 @@ namespace Org.BouncyCastle.Math.Raw return eta; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void Encode30(int bits, ReadOnlySpan<uint> x, Span<int> z) + { + Debug.Assert(bits > 0); + + int avail = 0; + ulong data = 0UL; + + int xOff = 0, zOff = 0; + while (bits > 0) + { + if (avail < System.Math.Min(30, bits)) + { + data |= (x[xOff++] & M32UL) << avail; + avail += 32; + } + + z[zOff++] = (int)data & M30; data >>= 30; + avail -= 30; + bits -= 30; + } + } +#else private static void Encode30(int bits, uint[] x, int xOff, int[] z, int zOff) { Debug.Assert(bits > 0); @@ -423,8 +699,13 @@ namespace Org.BouncyCastle.Math.Raw bits -= 30; } } +#endif +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static int EqualTo(int len, ReadOnlySpan<int> x, int y) +#else private static int EqualTo(int len, int[] x, int y) +#endif { int d = x[0] ^ y; for (int i = 1; i < len; ++i) @@ -435,7 +716,11 @@ namespace Org.BouncyCastle.Math.Raw return (d - 1) >> 31; } +#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) @@ -451,7 +736,11 @@ namespace Org.BouncyCastle.Math.Raw return (49 * bits + (bits < 46 ? 80 : 47)) / 17; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static bool IsOne(int len, ReadOnlySpan<int> x) +#else private static bool IsOne(int len, int[] x) +#endif { if (x[0] != 1) { @@ -467,7 +756,11 @@ namespace Org.BouncyCastle.Math.Raw return true; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static bool IsZero(int len, ReadOnlySpan<int> x) +#else private static bool IsZero(int len, int[] x) +#endif { if (x[0] != 0) { @@ -483,7 +776,11 @@ namespace Org.BouncyCastle.Math.Raw return true; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static int Negate30(int len30, Span<int> D) +#else private static int Negate30(int len30, int[] D) +#endif { Debug.Assert(len30 > 0); Debug.Assert(D.Length >= len30); @@ -499,7 +796,12 @@ namespace Org.BouncyCastle.Math.Raw return c; } +#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 private static void UpdateDE30(int len30, int[] D, int[] E, int[] t, int m0Inv32, int[] M) +#endif { Debug.Assert(len30 > 0); Debug.Assert(D.Length >= len30); @@ -563,7 +865,11 @@ namespace Org.BouncyCastle.Math.Raw E[len30 - 1] = (int)ce; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void UpdateFG30(int len30, Span<int> F, Span<int> G, ReadOnlySpan<int> t) +#else private static void UpdateFG30(int len30, int[] F, int[] G, int[] t) +#endif { Debug.Assert(len30 > 0); Debug.Assert(F.Length >= len30); @@ -601,4 +907,4 @@ namespace Org.BouncyCastle.Math.Raw G[len30 - 1] = (int)cg; } } -} \ No newline at end of file +} diff --git a/crypto/src/math/raw/Nat.cs b/crypto/src/math/raw/Nat.cs index 8e5b7a04c..3bc983430 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); @@ -234,6 +380,22 @@ namespace Org.BouncyCastle.Math.Raw return (uint)c; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint CAdd(int len, int mask, ReadOnlySpan<uint> x, ReadOnlySpan<uint> y, Span<uint> z) + { + uint MASK = (uint)-(mask & 1); + + ulong c = 0; + for (int i = 0; i < len; ++i) + { + c += (ulong)x[i] + (y[i] & MASK); + z[i] = (uint)c; + c >>= 32; + } + return (uint)c; + } +#endif + public static void CMov(int len, int mask, uint[] x, int xOff, uint[] z, int zOff) { uint MASK = (uint)-(mask & 1); @@ -241,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; } @@ -256,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) { @@ -306,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) { @@ -318,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]; @@ -340,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]; @@ -356,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; } @@ -369,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) @@ -408,6 +649,7 @@ namespace Org.BouncyCastle.Math.Raw } return -1; } +#endif public static int DecAt(int len, uint[] z, int zPos) { @@ -415,9 +657,7 @@ namespace Org.BouncyCastle.Math.Raw for (int i = zPos; i < len; ++i) { if (--z[i] != uint.MaxValue) - { return 0; - } } return -1; } @@ -428,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; @@ -469,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; @@ -491,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; @@ -513,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 @@ -534,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 @@ -555,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) @@ -583,19 +948,66 @@ namespace Org.BouncyCastle.Math.Raw return true; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static bool Gte(int len, ReadOnlySpan<uint> x, ReadOnlySpan<uint> y) + { + for (int i = len - 1; i >= 0; --i) + { + uint x_i = x[i], y_i = y[i]; + if (x_i < y_i) + return false; + if (x_i > y_i) + return true; + } + return true; + } +#endif + public static uint Inc(int len, uint[] z) { 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) @@ -615,6 +1027,7 @@ namespace Org.BouncyCastle.Math.Raw } return 1; } +#endif public static uint IncAt(int len, uint[] z, int zPos) { @@ -622,9 +1035,7 @@ namespace Org.BouncyCastle.Math.Raw for (int i = zPos; i < len; ++i) { if (++z[i] != uint.MinValue) - { return 0; - } } return 1; } @@ -635,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) { @@ -698,6 +1144,20 @@ namespace Org.BouncyCastle.Math.Raw return (int)c; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static int LessThan(int len, ReadOnlySpan<uint> x, ReadOnlySpan<uint> y) + { + long c = 0; + for (int i = 0; i < len; ++i) + { + c += (long)x[i] - y[i]; + c >>= 32; + } + Debug.Assert(c == 0L || c == -1L); + return (int)c; + } +#endif + public static void Mul(int len, uint[] x, uint[] y, uint[] zz) { zz[len] = MulWord(len, x[0], y, zz); @@ -718,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); @@ -728,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; @@ -755,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 { @@ -769,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 { @@ -785,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 { @@ -797,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 { @@ -811,21 +1344,55 @@ 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 += 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 += (ulong)z[zPos + 2]; + 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) { @@ -851,6 +1418,20 @@ 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) + { + int i = len; + while (--i >= 0) + { + 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) { int i = len; @@ -875,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); @@ -901,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); @@ -927,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; @@ -939,133 +1564,648 @@ 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) +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + return ShiftUpBit(len, z.AsSpan(0, len), c); +#else + int i = 0, limit4 = len - 4; + while (i <= limit4) + { + uint next0 = z[i + 0]; + uint next1 = z[i + 1]; + uint next2 = z[i + 2]; + uint next3 = z[i + 3]; + z[i + 0] = (next0 << 1) | (c >> 31); + z[i + 1] = (next1 << 1) | (next0 >> 31); + z[i + 2] = (next2 << 1) | (next1 >> 31); + z[i + 3] = (next3 << 1) | (next2 >> 31); + c = next3; + i += 4; + } + while (i < len) { uint next = z[i]; z[i] = (next << 1) | (c >> 31); c = next; + ++i; } return c >> 31; +#endif } public static uint ShiftUpBit(int len, uint[] z, int zOff, uint c) { - for (int i = 0; i < len; ++i) +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + return ShiftUpBit(len, z.AsSpan(zOff, len), c); +#else + int i = 0, limit4 = len - 4; + while (i <= limit4) + { + uint next0 = z[zOff + i + 0]; + uint next1 = z[zOff + i + 1]; + uint next2 = z[zOff + i + 2]; + uint next3 = z[zOff + i + 3]; + z[zOff + i + 0] = (next0 << 1) | (c >> 31); + z[zOff + i + 1] = (next1 << 1) | (next0 >> 31); + z[zOff + i + 2] = (next2 << 1) | (next1 >> 31); + z[zOff + i + 3] = (next3 << 1) | (next2 >> 31); + c = next3; + i += 4; + } + while (i < len) { uint next = z[zOff + i]; z[zOff + i] = (next << 1) | (c >> 31); c = next; + ++i; + } + return c >> 31; +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint ShiftUpBit(int len, Span<uint> z, uint c) + { + int i = 0, limit4 = len - 4; + while (i <= limit4) + { + uint next0 = z[i + 0]; + uint next1 = z[i + 1]; + uint next2 = z[i + 2]; + uint next3 = z[i + 3]; + z[i + 0] = (next0 << 1) | (c >> 31); + z[i + 1] = (next1 << 1) | (next0 >> 31); + z[i + 2] = (next2 << 1) | (next1 >> 31); + z[i + 3] = (next3 << 1) | (next2 >> 31); + c = next3; + i += 4; + } + while (i < len) + { + uint next = z[i]; + z[i] = (next << 1) | (c >> 31); + c = next; + ++i; } return c >> 31; } +#endif public static uint ShiftUpBit(int len, uint[] x, uint c, uint[] z) { - for (int i = 0; i < len; ++i) +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + return ShiftUpBit(len, x.AsSpan(0, len), c, z.AsSpan(0, len)); +#else + int i = 0, limit4 = len - 4; + while (i <= limit4) + { + uint next0 = x[i + 0]; + uint next1 = x[i + 1]; + uint next2 = x[i + 2]; + uint next3 = x[i + 3]; + z[i + 0] = (next0 << 1) | (c >> 31); + z[i + 1] = (next1 << 1) | (next0 >> 31); + z[i + 2] = (next2 << 1) | (next1 >> 31); + z[i + 3] = (next3 << 1) | (next2 >> 31); + c = next3; + i += 4; + } + while (i < len) { uint next = x[i]; z[i] = (next << 1) | (c >> 31); c = next; + ++i; } return c >> 31; +#endif } public static uint ShiftUpBit(int len, uint[] x, int xOff, uint c, uint[] z, int zOff) { - for (int i = 0; i < len; ++i) +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + return ShiftUpBit(len, x.AsSpan(xOff, len), c, z.AsSpan(zOff, len)); +#else + int i = 0, limit4 = len - 4; + while (i <= limit4) + { + uint next0 = x[xOff + i + 0]; + uint next1 = x[xOff + i + 1]; + uint next2 = x[xOff + i + 2]; + uint next3 = x[xOff + i + 3]; + z[zOff + i + 0] = (next0 << 1) | (c >> 31); + z[zOff + i + 1] = (next1 << 1) | (next0 >> 31); + z[zOff + i + 2] = (next2 << 1) | (next1 >> 31); + z[zOff + i + 3] = (next3 << 1) | (next2 >> 31); + c = next3; + i += 4; + } + while (i < len) { uint next = x[xOff + i]; z[zOff + i] = (next << 1) | (c >> 31); c = next; + ++i; } return c >> 31; +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint ShiftUpBit(int len, ReadOnlySpan<uint> x, uint c, Span<uint> z) + { + int i = 0, limit4 = len - 4; + while (i <= limit4) + { + uint next0 = x[i + 0]; + uint next1 = x[i + 1]; + uint next2 = x[i + 2]; + uint next3 = x[i + 3]; + z[i + 0] = (next0 << 1) | (c >> 31); + z[i + 1] = (next1 << 1) | (next0 >> 31); + z[i + 2] = (next2 << 1) | (next1 >> 31); + z[i + 3] = (next3 << 1) | (next2 >> 31); + c = next3; + i += 4; + } + while (i < len) + { + uint next = x[i]; + z[i] = (next << 1) | (c >> 31); + c = next; + ++i; + } + return c >> 31; + } +#endif + + public static ulong ShiftUpBit64(int len, ulong[] x, ulong c, ulong[] z) + { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + return ShiftUpBit64(len, x.AsSpan(0, len), c, z.AsSpan(0, len)); +#else + int i = 0, limit4 = len - 4; + while (i <= limit4) + { + ulong next0 = x[i + 0]; + ulong next1 = x[i + 1]; + ulong next2 = x[i + 2]; + ulong next3 = x[i + 3]; + z[i + 0] = (next0 << 1) | (c >> 63); + z[i + 1] = (next1 << 1) | (next0 >> 63); + z[i + 2] = (next2 << 1) | (next1 >> 63); + z[i + 3] = (next3 << 1) | (next2 >> 63); + c = next3; + i += 4; + } + while (i < len) + { + ulong next = x[i]; + z[i] = (next << 1) | (c >> 63); + c = next; + ++i; + } + return c >> 63; +#endif } public static ulong ShiftUpBit64(int len, ulong[] x, int xOff, ulong c, ulong[] z, int zOff) { - for (int i = 0; i < len; ++i) +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + return ShiftUpBit64(len, x.AsSpan(xOff, len), c, z.AsSpan(zOff, len)); +#else + int i = 0, limit4 = len - 4; + while (i <= limit4) + { + ulong next0 = x[xOff + i + 0]; + ulong next1 = x[xOff + i + 1]; + ulong next2 = x[xOff + i + 2]; + ulong next3 = x[xOff + i + 3]; + z[zOff + i + 0] = (next0 << 1) | (c >> 63); + z[zOff + i + 1] = (next1 << 1) | (next0 >> 63); + z[zOff + i + 2] = (next2 << 1) | (next1 >> 63); + z[zOff + i + 3] = (next3 << 1) | (next2 >> 63); + c = next3; + i += 4; + } + while (i < len) { ulong next = x[xOff + i]; z[zOff + i] = (next << 1) | (c >> 63); c = next; + ++i; } return c >> 63; +#endif } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static ulong ShiftUpBit64(int len, ReadOnlySpan<ulong> x, ulong c, Span<ulong> z) + { + int i = 0, limit4 = len - 4; + while (i <= limit4) + { + ulong next0 = x[i + 0]; + ulong next1 = x[i + 1]; + ulong next2 = x[i + 2]; + ulong next3 = x[i + 3]; + z[i + 0] = (next0 << 1) | (c >> 63); + z[i + 1] = (next1 << 1) | (next0 >> 63); + z[i + 2] = (next2 << 1) | (next1 >> 63); + z[i + 3] = (next3 << 1) | (next2 >> 63); + c = next3; + i += 4; + } + while (i < len) + { + ulong next = x[i]; + z[i] = (next << 1) | (c >> 63); + c = next; + ++i; + } + return c >> 63; + } +#endif + public static uint ShiftUpBits(int len, uint[] z, int bits, uint c) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + return ShiftUpBits(len, z.AsSpan(0, len), bits, c); +#else Debug.Assert(bits > 0 && bits < 32); - for (int i = 0; i < len; ++i) + int i = 0, limit4 = len - 4; + while (i <= limit4) + { + uint next0 = z[i + 0]; + uint next1 = z[i + 1]; + uint next2 = z[i + 2]; + uint next3 = z[i + 3]; + z[i + 0] = (next0 << bits) | (c >> -bits); + z[i + 1] = (next1 << bits) | (next0 >> -bits); + z[i + 2] = (next2 << bits) | (next1 >> -bits); + z[i + 3] = (next3 << bits) | (next2 >> -bits); + c = next3; + i += 4; + } + while (i < len) { uint next = z[i]; z[i] = (next << bits) | (c >> -bits); c = next; + ++i; } return c >> -bits; +#endif } public static uint ShiftUpBits(int len, uint[] z, int zOff, int bits, uint c) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + return ShiftUpBits(len, z.AsSpan(zOff, len), bits, c); +#else Debug.Assert(bits > 0 && bits < 32); - for (int i = 0; i < len; ++i) + int i = 0, limit4 = len - 4; + while (i <= limit4) + { + uint next0 = z[zOff + i + 0]; + uint next1 = z[zOff + i + 1]; + uint next2 = z[zOff + i + 2]; + uint next3 = z[zOff + i + 3]; + z[zOff + i + 0] = (next0 << bits) | (c >> -bits); + z[zOff + i + 1] = (next1 << bits) | (next0 >> -bits); + z[zOff + i + 2] = (next2 << bits) | (next1 >> -bits); + z[zOff + i + 3] = (next3 << bits) | (next2 >> -bits); + c = next3; + i += 4; + } + while (i < len) { uint next = z[zOff + i]; z[zOff + i] = (next << bits) | (c >> -bits); c = next; + ++i; } return c >> -bits; +#endif } - 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); - for (int i = 0; i < len; ++i) + Debug.Assert(bits > 0 && bits < 32); + int i = 0, limit4 = len - 4; + while (i <= limit4) + { + uint next0 = z[i + 0]; + uint next1 = z[i + 1]; + uint next2 = z[i + 2]; + uint next3 = z[i + 3]; + z[i + 0] = (next0 << bits) | (c >> -bits); + z[i + 1] = (next1 << bits) | (next0 >> -bits); + z[i + 2] = (next2 << bits) | (next1 >> -bits); + z[i + 3] = (next3 << bits) | (next2 >> -bits); + c = next3; + i += 4; + } + while (i < len) { - ulong next = z[zOff + i]; - z[zOff + i] = (next << bits) | (c >> -bits); + uint next = z[i]; + z[i] = (next << bits) | (c >> -bits); c = next; + ++i; } return c >> -bits; } +#endif public static uint ShiftUpBits(int len, uint[] x, int bits, uint c, uint[] z) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + return ShiftUpBits(len, x.AsSpan(0, len), bits, c, z.AsSpan(0, len)); +#else Debug.Assert(bits > 0 && bits < 32); - for (int i = 0; i < len; ++i) + int i = 0, limit4 = len - 4; + while (i <= limit4) + { + uint next0 = x[i + 0]; + uint next1 = x[i + 1]; + uint next2 = x[i + 2]; + uint next3 = x[i + 3]; + z[i + 0] = (next0 << bits) | (c >> -bits); + z[i + 1] = (next1 << bits) | (next0 >> -bits); + z[i + 2] = (next2 << bits) | (next1 >> -bits); + z[i + 3] = (next3 << bits) | (next2 >> -bits); + c = next3; + i += 4; + } + while (i < len) { uint next = x[i]; z[i] = (next << bits) | (c >> -bits); c = next; + ++i; } return c >> -bits; +#endif } public static uint ShiftUpBits(int len, uint[] x, int xOff, int bits, uint c, uint[] z, int zOff) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + return ShiftUpBits(len, x.AsSpan(xOff, len), bits, c, z.AsSpan(zOff, len)); +#else Debug.Assert(bits > 0 && bits < 32); - for (int i = 0; i < len; ++i) + int i = 0, limit4 = len - 4; + while (i <= limit4) + { + uint next0 = x[xOff + i + 0]; + uint next1 = x[xOff + i + 1]; + uint next2 = x[xOff + i + 2]; + uint next3 = x[xOff + i + 3]; + z[zOff + i + 0] = (next0 << bits) | (c >> -bits); + z[zOff + i + 1] = (next1 << bits) | (next0 >> -bits); + z[zOff + i + 2] = (next2 << bits) | (next1 >> -bits); + z[zOff + i + 3] = (next3 << bits) | (next2 >> -bits); + c = next3; + i += 4; + } + while (i < len) { uint next = x[xOff + i]; z[zOff + i] = (next << bits) | (c >> -bits); c = next; + ++i; } return c >> -bits; +#endif + } + +#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); + int i = 0, limit4 = len - 4; + while (i <= limit4) + { + uint next0 = x[i + 0]; + uint next1 = x[i + 1]; + uint next2 = x[i + 2]; + uint next3 = x[i + 3]; + z[i + 0] = (next0 << bits) | (c >> -bits); + z[i + 1] = (next1 << bits) | (next0 >> -bits); + z[i + 2] = (next2 << bits) | (next1 >> -bits); + z[i + 3] = (next3 << bits) | (next2 >> -bits); + c = next3; + i += 4; + } + while (i < len) + { + uint next = x[i]; + z[i] = (next << bits) | (c >> -bits); + c = next; + ++i; + } + return c >> -bits; + } +#endif + + public static ulong ShiftUpBits64(int len, ulong[] z, int bits, ulong c) + { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + return ShiftUpBits64(len, z.AsSpan(0, len), bits, c); +#else + Debug.Assert(bits > 0 && bits < 64); + int i = 0, limit4 = len - 4; + while (i <= limit4) + { + ulong next0 = z[i + 0]; + ulong next1 = z[i + 1]; + ulong next2 = z[i + 2]; + ulong next3 = z[i + 3]; + z[i + 0] = (next0 << bits) | (c >> -bits); + z[i + 1] = (next1 << bits) | (next0 >> -bits); + z[i + 2] = (next2 << bits) | (next1 >> -bits); + z[i + 3] = (next3 << bits) | (next2 >> -bits); + c = next3; + i += 4; + } + while (i < len) + { + ulong next = z[i]; + z[i] = (next << bits) | (c >> -bits); + c = next; + ++i; + } + return c >> -bits; +#endif + } + + public static ulong ShiftUpBits64(int len, ulong[] z, int zOff, int bits, ulong c) + { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + return ShiftUpBits64(len, z.AsSpan(zOff, len), bits, c); +#else + Debug.Assert(bits > 0 && bits < 64); + int i = 0, limit4 = len - 4; + while (i <= limit4) + { + ulong next0 = z[zOff + i + 0]; + ulong next1 = z[zOff + i + 1]; + ulong next2 = z[zOff + i + 2]; + ulong next3 = z[zOff + i + 3]; + z[zOff + i + 0] = (next0 << bits) | (c >> -bits); + z[zOff + i + 1] = (next1 << bits) | (next0 >> -bits); + z[zOff + i + 2] = (next2 << bits) | (next1 >> -bits); + z[zOff + i + 3] = (next3 << bits) | (next2 >> -bits); + c = next3; + i += 4; + } + while (i < len) + { + ulong next = z[zOff + i]; + z[zOff + i] = (next << bits) | (c >> -bits); + c = next; + ++i; + } + return c >> -bits; +#endif + } + +#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); + int i = 0, limit4 = len - 4; + while (i <= limit4) + { + ulong next0 = z[i + 0]; + ulong next1 = z[i + 1]; + ulong next2 = z[i + 2]; + ulong next3 = z[i + 3]; + z[i + 0] = (next0 << bits) | (c >> -bits); + z[i + 1] = (next1 << bits) | (next0 >> -bits); + z[i + 2] = (next2 << bits) | (next1 >> -bits); + z[i + 3] = (next3 << bits) | (next2 >> -bits); + c = next3; + i += 4; + } + while (i < len) + { + ulong next = z[i]; + z[i] = (next << bits) | (c >> -bits); + c = next; + ++i; + } + return c >> -bits; + } +#endif + + public static ulong ShiftUpBits64(int len, ulong[] x, int bits, ulong c, ulong[] z) + { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + return ShiftUpBits64(len, x.AsSpan(0, len), bits, c, z.AsSpan(0, len)); +#else + Debug.Assert(bits > 0 && bits < 64); + int i = 0, limit4 = len - 4; + while (i <= limit4) + { + ulong next0 = x[i + 0]; + ulong next1 = x[i + 1]; + ulong next2 = x[i + 2]; + ulong next3 = x[i + 3]; + z[i + 0] = (next0 << bits) | (c >> -bits); + z[i + 1] = (next1 << bits) | (next0 >> -bits); + z[i + 2] = (next2 << bits) | (next1 >> -bits); + z[i + 3] = (next3 << bits) | (next2 >> -bits); + c = next3; + i += 4; + } + while (i < len) + { + ulong next = x[i]; + z[i] = (next << bits) | (c >> -bits); + c = next; + ++i; + } + return c >> -bits; +#endif } public static ulong ShiftUpBits64(int len, ulong[] x, int xOff, int bits, ulong c, ulong[] z, int zOff) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + return ShiftUpBits64(len, x.AsSpan(xOff, len), bits, c, z.AsSpan(zOff, len)); +#else Debug.Assert(bits > 0 && bits < 64); - for (int i = 0; i < len; ++i) + int i = 0, limit4 = len - 4; + while (i <= limit4) + { + ulong next0 = x[xOff + i + 0]; + ulong next1 = x[xOff + i + 1]; + ulong next2 = x[xOff + i + 2]; + ulong next3 = x[xOff + i + 3]; + z[zOff + i + 0] = (next0 << bits) | (c >> -bits); + z[zOff + i + 1] = (next1 << bits) | (next0 >> -bits); + z[zOff + i + 2] = (next2 << bits) | (next1 >> -bits); + z[zOff + i + 3] = (next3 << bits) | (next2 >> -bits); + c = next3; + i += 4; + } + while (i < len) { ulong next = x[xOff + i]; z[zOff + i] = (next << bits) | (c >> -bits); c = next; + ++i; } return c >> -bits; +#endif } +#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); + int i = 0, limit4 = len - 4; + while (i <= limit4) + { + ulong next0 = x[i + 0]; + ulong next1 = x[i + 1]; + ulong next2 = x[i + 2]; + ulong next3 = x[i + 3]; + z[i + 0] = (next0 << bits) | (c >> -bits); + z[i + 1] = (next1 << bits) | (next0 >> -bits); + z[i + 2] = (next2 << bits) | (next1 >> -bits); + z[i + 3] = (next3 << bits) | (next2 >> -bits); + c = next3; + i += 4; + } + while (i < len) + { + ulong next = x[i]; + z[i] = (next << bits) | (c >> -bits); + c = next; + ++i; + } + return c >> -bits; + } +#endif + public static void Square(int len, uint[] x, uint[] zz) { int extLen = len << 1; @@ -1128,6 +2268,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]; @@ -1157,6 +2330,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; @@ -1180,6 +2369,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)); @@ -1204,6 +2408,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; @@ -1226,6 +2444,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; @@ -1250,13 +2481,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); @@ -1265,21 +2510,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); @@ -1287,15 +2546,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; @@ -1320,6 +2592,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)); @@ -1338,6 +2624,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; @@ -1354,34 +2651,251 @@ 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 Xor(int len, uint[] x, uint[] y, uint[] z) + { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + Xor(len, x.AsSpan(0, len), y.AsSpan(0, len), z.AsSpan(0, len)); +#else + for (int i = 0; i < len; ++i) + { + z[i] = x[i] ^ y[i]; + } +#endif + } + + public static void Xor(int len, uint[] x, int xOff, uint[] y, int yOff, uint[] z, int zOff) + { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + Xor(len, x.AsSpan(xOff, len), y.AsSpan(yOff, len), z.AsSpan(zOff, len)); +#else + for (int i = 0; i < len; ++i) + { + z[zOff + i] = x[xOff + i] ^ y[yOff + i]; + } +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Xor(int len, ReadOnlySpan<uint> x, ReadOnlySpan<uint> y, Span<uint> z) + { + int i = 0, limit16 = len - 16; + while (i <= limit16) + { + Nat512.Xor(x[i..], y[i..], z[i..]); + i += 16; + } + while (i < len) + { + z[i] = x[i] ^ y[i]; + ++i; + } + } +#endif + + public static void Xor64(int len, ulong[] x, ulong[] y, ulong[] z) + { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + Xor64(len, x.AsSpan(0, len), y.AsSpan(0, len), z.AsSpan(0, len)); +#else + for (int i = 0; i < len; ++i) + { + z[i] = x[i] ^ y[i]; + } +#endif + } + + public static void Xor64(int len, ulong[] x, int xOff, ulong[] y, int yOff, ulong[] z, int zOff) + { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + Xor64(len, x.AsSpan(xOff, len), y.AsSpan(yOff, len), z.AsSpan(zOff, len)); +#else + for (int i = 0; i < len; ++i) + { + z[zOff + i] = x[xOff + i] ^ y[yOff + i]; + } +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Xor64(int len, ReadOnlySpan<ulong> x, ReadOnlySpan<ulong> y, Span<ulong> z) + { + int i = 0, limit8 = len - 8; + while (i <= limit8) + { + Nat512.Xor64(x[i..], y[i..], z[i..]); + i += 8; + } + while (i < len) + { + z[i] = x[i] ^ y[i]; + ++i; + } + } +#endif + + public static void XorTo(int len, uint[] x, uint[] z) + { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + XorTo(len, x.AsSpan(0, len), z.AsSpan(0, len)); +#else + for (int i = 0; i < len; ++i) + { + z[i] ^= x[i]; + } +#endif + } + + public static void XorTo(int len, uint[] x, int xOff, uint[] z, int zOff) + { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + XorTo(len, x.AsSpan(xOff, len), z.AsSpan(zOff, len)); +#else + for (int i = 0; i < len; ++i) + { + z[zOff + i] ^= x[xOff + i]; + } +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void XorTo(int len, ReadOnlySpan<uint> x, Span<uint> z) + { + int i = 0, limit16 = len - 16; + while (i <= limit16) + { + Nat512.XorTo(x[i..], z[i..]); + i += 16; + } + while (i < len) + { + z[i] ^= x[i]; + ++i; + } + } +#endif + + public static void XorTo64(int len, ulong[] x, ulong[] z) + { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + XorTo64(len, x.AsSpan(0, len), z.AsSpan(0, len)); +#else + for (int i = 0; i < len; ++i) + { + z[i] ^= x[i]; + } +#endif + } + + public static void XorTo64(int len, ulong[] x, int xOff, ulong[] z, int zOff) + { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + XorTo64(len, x.AsSpan(xOff, len), z.AsSpan(zOff, len)); +#else + for (int i = 0; i < len; ++i) + { + z[zOff + i] ^= x[xOff + i]; + } +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void XorTo64(int len, ReadOnlySpan<ulong> x, Span<ulong> z) + { + int i = 0, limit8 = len - 8; + while (i <= limit8) + { + Nat512.XorTo64(x[i..], z[i..]); + i += 8; + } + while (i < len) + { + z[i] ^= x[i]; + ++i; + } + } +#endif + public static void Zero(int len, uint[] z) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + z.AsSpan(0, len).Fill(0U); +#else for (int i = 0; i < len; ++i) { - z[i] = 0; + z[i] = 0U; } +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Zero(int len, Span<uint> z) + { + z[..len].Fill(0U); } +#endif public static void Zero64(int len, ulong[] z) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + z.AsSpan(0, len).Fill(0UL); +#else for (int i = 0; i < len; ++i) { z[i] = 0UL; } +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Zero64(int len, Span<ulong> z) + { + z[..len].Fill(0UL); } +#endif } } diff --git a/crypto/src/math/raw/Nat256.cs b/crypto/src/math/raw/Nat256.cs index 710060bee..47e0644f6 100644 --- a/crypto/src/math/raw/Nat256.cs +++ b/crypto/src/math/raw/Nat256.cs @@ -1,5 +1,11 @@ using System; using System.Diagnostics; +#if NETCOREAPP3_0_OR_GREATER +using System.Runtime.CompilerServices; +using System.Runtime.InteropServices; +using System.Runtime.Intrinsics; +using System.Runtime.Intrinsics.X86; +#endif using Org.BouncyCastle.Crypto.Utilities; @@ -1364,6 +1370,71 @@ namespace Org.BouncyCastle.Math.Raw return new BigInteger(1, bs); } + public static void Xor(uint[] x, int xOff, uint[] y, int yOff, uint[] z, int zOff) + { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + Xor(x.AsSpan(xOff), y.AsSpan(yOff), z.AsSpan(zOff)); +#else + for (int i = 0; i < 8; i += 4) + { + z[zOff + i + 0] = x[xOff + i + 0] ^ y[yOff + i + 0]; + z[zOff + i + 1] = x[xOff + i + 1] ^ y[yOff + i + 1]; + z[zOff + i + 2] = x[xOff + i + 2] ^ y[yOff + i + 2]; + z[zOff + i + 3] = x[xOff + i + 3] ^ y[yOff + i + 3]; + } +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Xor(ReadOnlySpan<uint> x, ReadOnlySpan<uint> y, Span<uint> z) + { +#if NETCOREAPP3_0_OR_GREATER + if (Avx2.IsSupported && Unsafe.SizeOf<Vector256<byte>>() == 32) + { + var X = MemoryMarshal.AsBytes(x[..8]); + var Y = MemoryMarshal.AsBytes(y[..8]); + var Z = MemoryMarshal.AsBytes(z[..8]); + + var X0 = MemoryMarshal.Read<Vector256<byte>>(X[0x00..0x20]); + var Y0 = MemoryMarshal.Read<Vector256<byte>>(Y[0x00..0x20]); + + var Z0 = Avx2.Xor(X0, Y0); + + MemoryMarshal.Write(Z[0x00..0x20], ref Z0); + return; + } + + if (Sse2.IsSupported && Unsafe.SizeOf<Vector128<byte>>() == 16) + { + var X = MemoryMarshal.AsBytes(x[..8]); + var Y = MemoryMarshal.AsBytes(y[..8]); + var Z = MemoryMarshal.AsBytes(z[..8]); + + var X0 = MemoryMarshal.Read<Vector128<byte>>(X[0x00..0x10]); + var X1 = MemoryMarshal.Read<Vector128<byte>>(X[0x10..0x20]); + + var Y0 = MemoryMarshal.Read<Vector128<byte>>(Y[0x00..0x10]); + var Y1 = MemoryMarshal.Read<Vector128<byte>>(Y[0x10..0x20]); + + var Z0 = Sse2.Xor(X0, Y0); + var Z1 = Sse2.Xor(X1, Y1); + + MemoryMarshal.Write(Z[0x00..0x10], ref Z0); + MemoryMarshal.Write(Z[0x10..0x20], ref Z1); + return; + } +#endif + + for (int i = 0; i < 8; i += 4) + { + z[i + 0] = x[i + 0] ^ y[i + 0]; + z[i + 1] = x[i + 1] ^ y[i + 1]; + z[i + 2] = x[i + 2] ^ y[i + 2]; + z[i + 3] = x[i + 3] ^ y[i + 3]; + } + } +#endif + public static void Zero(uint[] z) { z[0] = 0; diff --git a/crypto/src/math/raw/Nat512.cs b/crypto/src/math/raw/Nat512.cs index a9ef2b3b6..2312e1cf2 100644 --- a/crypto/src/math/raw/Nat512.cs +++ b/crypto/src/math/raw/Nat512.cs @@ -1,5 +1,10 @@ using System; -using System.Diagnostics; +#if NETCOREAPP3_0_OR_GREATER +using System.Runtime.CompilerServices; +using System.Runtime.InteropServices; +using System.Runtime.Intrinsics; +using System.Runtime.Intrinsics.X86; +#endif namespace Org.BouncyCastle.Math.Raw { @@ -42,5 +47,313 @@ namespace Org.BouncyCastle.Math.Raw c24 += (uint)Nat.SubFrom(16, m, 0, zz, 8); Nat.AddWordAt(32, c24, zz, 24); } + + public static void Xor(uint[] x, int xOff, uint[] y, int yOff, uint[] z, int zOff) + { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + Xor(x.AsSpan(xOff), y.AsSpan(yOff), z.AsSpan(zOff)); +#else + for (int i = 0; i < 16; i += 4) + { + z[zOff + i + 0] = x[xOff + i + 0] ^ y[yOff + i + 0]; + z[zOff + i + 1] = x[xOff + i + 1] ^ y[yOff + i + 1]; + z[zOff + i + 2] = x[xOff + i + 2] ^ y[yOff + i + 2]; + z[zOff + i + 3] = x[xOff + i + 3] ^ y[yOff + i + 3]; + } +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Xor(ReadOnlySpan<uint> x, ReadOnlySpan<uint> y, Span<uint> z) + { +#if NETCOREAPP3_0_OR_GREATER + if (Avx2.IsSupported && Unsafe.SizeOf<Vector256<byte>>() == 32) + { + var X = MemoryMarshal.AsBytes(x[..16]); + var Y = MemoryMarshal.AsBytes(y[..16]); + var Z = MemoryMarshal.AsBytes(z[..16]); + + var X0 = MemoryMarshal.Read<Vector256<byte>>(X[0x00..0x20]); + var X1 = MemoryMarshal.Read<Vector256<byte>>(X[0x20..0x40]); + + var Y0 = MemoryMarshal.Read<Vector256<byte>>(Y[0x00..0x20]); + var Y1 = MemoryMarshal.Read<Vector256<byte>>(Y[0x20..0x40]); + + var Z0 = Avx2.Xor(X0, Y0); + var Z1 = Avx2.Xor(X1, Y1); + + MemoryMarshal.Write(Z[0x00..0x20], ref Z0); + MemoryMarshal.Write(Z[0x20..0x40], ref Z1); + return; + } + + if (Sse2.IsSupported && Unsafe.SizeOf<Vector128<byte>>() == 16) + { + var X = MemoryMarshal.AsBytes(x[..16]); + var Y = MemoryMarshal.AsBytes(y[..16]); + var Z = MemoryMarshal.AsBytes(z[..16]); + + var X0 = MemoryMarshal.Read<Vector128<byte>>(X[0x00..0x10]); + var X1 = MemoryMarshal.Read<Vector128<byte>>(X[0x10..0x20]); + var X2 = MemoryMarshal.Read<Vector128<byte>>(X[0x20..0x30]); + var X3 = MemoryMarshal.Read<Vector128<byte>>(X[0x30..0x40]); + + var Y0 = MemoryMarshal.Read<Vector128<byte>>(Y[0x00..0x10]); + var Y1 = MemoryMarshal.Read<Vector128<byte>>(Y[0x10..0x20]); + var Y2 = MemoryMarshal.Read<Vector128<byte>>(Y[0x20..0x30]); + var Y3 = MemoryMarshal.Read<Vector128<byte>>(Y[0x30..0x40]); + + var Z0 = Sse2.Xor(X0, Y0); + var Z1 = Sse2.Xor(X1, Y1); + var Z2 = Sse2.Xor(X2, Y2); + var Z3 = Sse2.Xor(X3, Y3); + + MemoryMarshal.Write(Z[0x00..0x10], ref Z0); + MemoryMarshal.Write(Z[0x10..0x20], ref Z1); + MemoryMarshal.Write(Z[0x20..0x30], ref Z2); + MemoryMarshal.Write(Z[0x30..0x40], ref Z3); + return; + } +#endif + + for (int i = 0; i < 16; i += 4) + { + z[i + 0] = x[i + 0] ^ y[i + 0]; + z[i + 1] = x[i + 1] ^ y[i + 1]; + z[i + 2] = x[i + 2] ^ y[i + 2]; + z[i + 3] = x[i + 3] ^ y[i + 3]; + } + } +#endif + + public static void XorTo(uint[] x, int xOff, uint[] z, int zOff) + { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + XorTo(x.AsSpan(xOff), z.AsSpan(zOff)); +#else + for (int i = 0; i < 16; i += 4) + { + z[zOff + i + 0] ^= x[xOff + i + 0]; + z[zOff + i + 1] ^= x[xOff + i + 1]; + z[zOff + i + 2] ^= x[xOff + i + 2]; + z[zOff + i + 3] ^= x[xOff + i + 3]; + } +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void XorTo(ReadOnlySpan<uint> x, Span<uint> z) + { +#if NETCOREAPP3_0_OR_GREATER + if (Avx2.IsSupported && Unsafe.SizeOf<Vector256<byte>>() == 32) + { + var X = MemoryMarshal.AsBytes(x[..16]); + var Z = MemoryMarshal.AsBytes(z[..16]); + + var X0 = MemoryMarshal.Read<Vector256<byte>>(X[0x00..0x20]); + var X1 = MemoryMarshal.Read<Vector256<byte>>(X[0x20..0x40]); + + var Y0 = MemoryMarshal.Read<Vector256<byte>>(Z[0x00..0x20]); + var Y1 = MemoryMarshal.Read<Vector256<byte>>(Z[0x20..0x40]); + + var Z0 = Avx2.Xor(X0, Y0); + var Z1 = Avx2.Xor(X1, Y1); + + MemoryMarshal.Write(Z[0x00..0x20], ref Z0); + MemoryMarshal.Write(Z[0x20..0x40], ref Z1); + return; + } + + if (Sse2.IsSupported && Unsafe.SizeOf<Vector128<byte>>() == 16) + { + var X = MemoryMarshal.AsBytes(x[..16]); + var Z = MemoryMarshal.AsBytes(z[..16]); + + var X0 = MemoryMarshal.Read<Vector128<byte>>(X[0x00..0x10]); + var X1 = MemoryMarshal.Read<Vector128<byte>>(X[0x10..0x20]); + var X2 = MemoryMarshal.Read<Vector128<byte>>(X[0x20..0x30]); + var X3 = MemoryMarshal.Read<Vector128<byte>>(X[0x30..0x40]); + + var Y0 = MemoryMarshal.Read<Vector128<byte>>(Z[0x00..0x10]); + var Y1 = MemoryMarshal.Read<Vector128<byte>>(Z[0x10..0x20]); + var Y2 = MemoryMarshal.Read<Vector128<byte>>(Z[0x20..0x30]); + var Y3 = MemoryMarshal.Read<Vector128<byte>>(Z[0x30..0x40]); + + var Z0 = Sse2.Xor(X0, Y0); + var Z1 = Sse2.Xor(X1, Y1); + var Z2 = Sse2.Xor(X2, Y2); + var Z3 = Sse2.Xor(X3, Y3); + + MemoryMarshal.Write(Z[0x00..0x10], ref Z0); + MemoryMarshal.Write(Z[0x10..0x20], ref Z1); + MemoryMarshal.Write(Z[0x20..0x30], ref Z2); + MemoryMarshal.Write(Z[0x30..0x40], ref Z3); + return; + } +#endif + + for (int i = 0; i < 16; i += 4) + { + z[i + 0] ^= x[i + 0]; + z[i + 1] ^= x[i + 1]; + z[i + 2] ^= x[i + 2]; + z[i + 3] ^= x[i + 3]; + } + } +#endif + + public static void Xor64(ulong[] x, int xOff, ulong[] y, int yOff, ulong[] z, int zOff) + { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + Xor64(x.AsSpan(xOff), y.AsSpan(yOff), z.AsSpan(zOff)); +#else + for (int i = 0; i < 8; i += 4) + { + z[zOff + i + 0] = x[xOff + i + 0] ^ y[yOff + i + 0]; + z[zOff + i + 1] = x[xOff + i + 1] ^ y[yOff + i + 1]; + z[zOff + i + 2] = x[xOff + i + 2] ^ y[yOff + i + 2]; + z[zOff + i + 3] = x[xOff + i + 3] ^ y[yOff + i + 3]; + } +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Xor64(ReadOnlySpan<ulong> x, ReadOnlySpan<ulong> y, Span<ulong> z) + { +#if NETCOREAPP3_0_OR_GREATER + if (Avx2.IsSupported && Unsafe.SizeOf<Vector256<byte>>() == 32) + { + var X = MemoryMarshal.AsBytes(x[..8]); + var Y = MemoryMarshal.AsBytes(y[..8]); + var Z = MemoryMarshal.AsBytes(z[..8]); + + var X0 = MemoryMarshal.Read<Vector256<byte>>(X[0x00..0x20]); + var X1 = MemoryMarshal.Read<Vector256<byte>>(X[0x20..0x40]); + + var Y0 = MemoryMarshal.Read<Vector256<byte>>(Y[0x00..0x20]); + var Y1 = MemoryMarshal.Read<Vector256<byte>>(Y[0x20..0x40]); + + var Z0 = Avx2.Xor(X0, Y0); + var Z1 = Avx2.Xor(X1, Y1); + + MemoryMarshal.Write(Z[0x00..0x20], ref Z0); + MemoryMarshal.Write(Z[0x20..0x40], ref Z1); + return; + } + + if (Sse2.IsSupported && Unsafe.SizeOf<Vector128<byte>>() == 16) + { + var X = MemoryMarshal.AsBytes(x[..8]); + var Y = MemoryMarshal.AsBytes(y[..8]); + var Z = MemoryMarshal.AsBytes(z[..8]); + + var X0 = MemoryMarshal.Read<Vector128<byte>>(X[0x00..0x10]); + var X1 = MemoryMarshal.Read<Vector128<byte>>(X[0x10..0x20]); + var X2 = MemoryMarshal.Read<Vector128<byte>>(X[0x20..0x30]); + var X3 = MemoryMarshal.Read<Vector128<byte>>(X[0x30..0x40]); + + var Y0 = MemoryMarshal.Read<Vector128<byte>>(Y[0x00..0x10]); + var Y1 = MemoryMarshal.Read<Vector128<byte>>(Y[0x10..0x20]); + var Y2 = MemoryMarshal.Read<Vector128<byte>>(Y[0x20..0x30]); + var Y3 = MemoryMarshal.Read<Vector128<byte>>(Y[0x30..0x40]); + + var Z0 = Sse2.Xor(X0, Y0); + var Z1 = Sse2.Xor(X1, Y1); + var Z2 = Sse2.Xor(X2, Y2); + var Z3 = Sse2.Xor(X3, Y3); + + MemoryMarshal.Write(Z[0x00..0x10], ref Z0); + MemoryMarshal.Write(Z[0x10..0x20], ref Z1); + MemoryMarshal.Write(Z[0x20..0x30], ref Z2); + MemoryMarshal.Write(Z[0x30..0x40], ref Z3); + return; + } +#endif + + for (int i = 0; i < 8; i += 4) + { + z[i + 0] = x[i + 0] ^ y[i + 0]; + z[i + 1] = x[i + 1] ^ y[i + 1]; + z[i + 2] = x[i + 2] ^ y[i + 2]; + z[i + 3] = x[i + 3] ^ y[i + 3]; + } + } +#endif + + public static void XorTo64(ulong[] x, int xOff, ulong[] z, int zOff) + { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + XorTo64(x.AsSpan(xOff), z.AsSpan(zOff)); +#else + for (int i = 0; i < 8; i += 4) + { + z[zOff + i + 0] ^= x[xOff + i + 0]; + z[zOff + i + 1] ^= x[xOff + i + 1]; + z[zOff + i + 2] ^= x[xOff + i + 2]; + z[zOff + i + 3] ^= x[xOff + i + 3]; + } +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void XorTo64(ReadOnlySpan<ulong> x, Span<ulong> z) + { +#if NETCOREAPP3_0_OR_GREATER + if (Avx2.IsSupported && Unsafe.SizeOf<Vector256<byte>>() == 32) + { + var X = MemoryMarshal.AsBytes(x[..8]); + var Z = MemoryMarshal.AsBytes(z[..8]); + + var X0 = MemoryMarshal.Read<Vector256<byte>>(X[0x00..0x20]); + var X1 = MemoryMarshal.Read<Vector256<byte>>(X[0x20..0x40]); + + var Y0 = MemoryMarshal.Read<Vector256<byte>>(Z[0x00..0x20]); + var Y1 = MemoryMarshal.Read<Vector256<byte>>(Z[0x20..0x40]); + + var Z0 = Avx2.Xor(X0, Y0); + var Z1 = Avx2.Xor(X1, Y1); + + MemoryMarshal.Write(Z[0x00..0x20], ref Z0); + MemoryMarshal.Write(Z[0x20..0x40], ref Z1); + return; + } + + if (Sse2.IsSupported && Unsafe.SizeOf<Vector128<byte>>() == 16) + { + var X = MemoryMarshal.AsBytes(x[..8]); + var Z = MemoryMarshal.AsBytes(z[..8]); + + var X0 = MemoryMarshal.Read<Vector128<byte>>(X[0x00..0x10]); + var X1 = MemoryMarshal.Read<Vector128<byte>>(X[0x10..0x20]); + var X2 = MemoryMarshal.Read<Vector128<byte>>(X[0x20..0x30]); + var X3 = MemoryMarshal.Read<Vector128<byte>>(X[0x30..0x40]); + + var Y0 = MemoryMarshal.Read<Vector128<byte>>(Z[0x00..0x10]); + var Y1 = MemoryMarshal.Read<Vector128<byte>>(Z[0x10..0x20]); + var Y2 = MemoryMarshal.Read<Vector128<byte>>(Z[0x20..0x30]); + var Y3 = MemoryMarshal.Read<Vector128<byte>>(Z[0x30..0x40]); + + var Z0 = Sse2.Xor(X0, Y0); + var Z1 = Sse2.Xor(X1, Y1); + var Z2 = Sse2.Xor(X2, Y2); + var Z3 = Sse2.Xor(X3, Y3); + + MemoryMarshal.Write(Z[0x00..0x10], ref Z0); + MemoryMarshal.Write(Z[0x10..0x20], ref Z1); + MemoryMarshal.Write(Z[0x20..0x30], ref Z2); + MemoryMarshal.Write(Z[0x30..0x40], ref Z3); + return; + } +#endif + + for (int i = 0; i < 8; i += 4) + { + z[i + 0] ^= x[i + 0]; + z[i + 1] ^= x[i + 1]; + z[i + 2] ^= x[i + 2]; + z[i + 3] ^= x[i + 3]; + } + } +#endif } } |