diff options
Diffstat (limited to 'crypto/src/math/ec')
33 files changed, 1927 insertions, 243 deletions
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; |