EdDSA improvements

- better guards on context values
- add Verify method to public keys
- reduced allocation during verification

1 files changed, 320 insertions, 21 deletions

diff --git a/crypto/src/math/ec/rfc8032/Ed25519.cs b/crypto/src/math/ec/rfc8032/Ed25519.cs
index f3b63f3b3..82e46aa1f 100644
--- a/crypto/src/math/ec/rfc8032/Ed25519.cs
+++ b/crypto/src/math/ec/rfc8032/Ed25519.cs
@@ -1,4 +1,7 @@
 using System;
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+using System.Buffers.Binary;
+#endif
 using System.Diagnostics;
 
 using Org.BouncyCastle.Crypto;
@@ -190,12 +193,35 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             return F.IsZero(t);
         }
 
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+        private static bool CheckPointVar(ReadOnlySpan<byte> p)
+        {
+            if ((Decode32(p[28..]) & 0x7FFFFFFFU) < P[7])
+                return true;
+            for (int i = CoordUints - 2; i >= 0; --i)
+            {
+                if (Decode32(p[(i * 4)..]) < P[i])
+                    return true;
+            }
+            return false;
+        }
+
+        private static bool CheckScalarVar(ReadOnlySpan<byte> s, Span<uint> n)
+        {
+            DecodeScalar(s, n);
+            return !Nat.Gte(ScalarUints, n, L);
+        }
+#else
         private static bool CheckPointVar(byte[] p)
         {
-            uint[] t = new uint[CoordUints];
-            Decode32(p, 0, t, 0, CoordUints);
-            t[CoordUints - 1] &= 0x7FFFFFFFU;
-            return !Nat256.Gte(t, P);
+            if ((Decode32(p, 28) & 0x7FFFFFFFU) < P[7])
+                return true;
+            for (int i = CoordUints - 2; i >= 0; --i)
+            {
+                if (Decode32(p, i * 4) < P[i])
+                    return true;
+            }
+            return false;
         }
 
         private static bool CheckScalarVar(byte[] s, uint[] n)
@@ -203,6 +229,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             DecodeScalar(s, 0, n);
             return !Nat256.Gte(n, L);
         }
+#endif
 
         private static byte[] Copy(byte[] buf, int off, int len)
         {
@@ -213,7 +240,10 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
 
         private static IDigest CreateDigest()
         {
-            return new Sha512Digest();
+            var d = new Sha512Digest();
+            if (d.GetDigestSize() != 64)
+                throw new InvalidOperationException();
+            return d;
         }
 
         public static IDigest CreatePrehash()
@@ -229,23 +259,33 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             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)
         {
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+            return BinaryPrimitives.ReadUInt32LittleEndian(bs.AsSpan(off));
+#else
             uint n = bs[off];
             n |= (uint)bs[++off] << 8;
             n |= (uint)bs[++off] << 16;
             n |= (uint)bs[++off] << 24;
             return n;
+#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;
+            return BinaryPrimitives.ReadUInt32LittleEndian(bs);
         }
 #endif
 
@@ -335,20 +375,48 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             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);
-            bs[++off] = (byte)(n >> 8);
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+            BinaryPrimitives.WriteUInt32LittleEndian(bs.AsSpan(off), n);
+#else
+            bs[  off] = (byte)(n      );
+            bs[++off] = (byte)(n >>  8);
             bs[++off] = (byte)(n >> 16);
             bs[++off] = (byte)(n >> 24);
+#endif
         }
 
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+        private static void Encode32(uint n, Span<byte> bs)
+        {
+            BinaryPrimitives.WriteUInt32LittleEndian(bs, n);
+        }
+#endif
+
         private static void Encode56(ulong n, byte[] bs, int off)
         {
             Encode32((uint)n, bs, off);
             Encode24((uint)(n >> 32), bs, off + 4);
         }
 
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+        private static void Encode56(ulong n, Span<byte> bs)
+        {
+            Encode32((uint)n, bs);
+            Encode24((uint)(n >> 32), bs[4..]);
+        }
+#endif
+
         private static int EncodePoint(ref PointAccum p, byte[] r, int rOff)
         {
 #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
@@ -417,7 +485,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             GeneratePublicKey(sk.AsSpan(skOff), pk.AsSpan(pkOff));
 #else
             IDigest d = CreateDigest();
-            byte[] h = new byte[d.GetDigestSize()];
+            byte[] h = new byte[64];
 
             d.BlockUpdate(sk, skOff, SecretKeySize);
             d.DoFinal(h, 0);
@@ -433,10 +501,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
         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];
+            Span<byte> h = stackalloc byte[64];
 
             d.BlockUpdate(sk[..SecretKeySize]);
             d.DoFinal(h);
@@ -458,7 +523,11 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             return (x[w] >> b) & 15U;
         }
 
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+        private static sbyte[] GetWnafVar(ReadOnlySpan<uint> n, int width)
+#else
         private static sbyte[] GetWnafVar(uint[] n, int width)
+#endif
         {
             Debug.Assert(n[ScalarUints - 1] <= L[ScalarUints - 1]);
             Debug.Assert(2 <= width && width <= 8);
@@ -541,7 +610,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
                 throw new ArgumentException("ctx");
 
             IDigest d = CreateDigest();
-            byte[] h = new byte[d.GetDigestSize()];
+            byte[] h = new byte[64];
 
             d.BlockUpdate(sk, skOff, SecretKeySize);
             d.DoFinal(h, 0);
@@ -562,7 +631,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
                 throw new ArgumentException("ctx");
 
             IDigest d = CreateDigest();
-            byte[] h = new byte[d.GetDigestSize()];
+            byte[] h = new byte[64];
 
             d.BlockUpdate(sk, skOff, SecretKeySize);
             d.DoFinal(h, 0);
@@ -579,6 +648,45 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             if (!CheckContextVar(ctx, phflag))
                 throw new ArgumentException("ctx");
 
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+            Span<byte> RS = stackalloc byte[PointBytes + ScalarBytes];
+            RS.CopyFrom(sig.AsSpan(sigOff, PointBytes + ScalarBytes));
+
+            var R = RS[..PointBytes];
+            var S = RS[PointBytes..];
+
+            if (!CheckPointVar(R))
+                return false;
+
+            Span<uint> nS = stackalloc uint[ScalarUints];
+            if (!CheckScalarVar(S, nS))
+                return false;
+
+            Init(out PointAffine pA);
+            if (!DecodePointVar(pk, pkOff, true, ref pA))
+                return false;
+
+            IDigest d = CreateDigest();
+            Span<byte> h = stackalloc byte[64];
+
+            Dom2(d, phflag, ctx);
+            d.BlockUpdate(R);
+            d.BlockUpdate(pk.AsSpan(pkOff, PointBytes));
+            d.BlockUpdate(m.AsSpan(mOff, mLen));
+            d.DoFinal(h);
+
+            Span<byte> k = stackalloc byte[ScalarBytes];
+            ReduceScalar(h, k);
+
+            Span<uint> nA = stackalloc uint[ScalarUints];
+            DecodeScalar(k, nA);
+
+            Init(out PointAccum pR);
+            ScalarMultStrausVar(nS, nA, ref pA, ref pR);
+
+            Span<byte> check = stackalloc byte[PointBytes];
+            return 0 != EncodePoint(ref pR, check) && check.SequenceEqual(R);
+#else
             byte[] R = Copy(sig, sigOff, PointBytes);
             byte[] S = Copy(sig, sigOff + PointBytes, ScalarBytes);
 
@@ -594,7 +702,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
                 return false;
 
             IDigest d = CreateDigest();
-            byte[] h = new byte[d.GetDigestSize()];
+            byte[] h = new byte[64];
 
             Dom2(d, phflag, ctx);
             d.BlockUpdate(R, 0, PointBytes);
@@ -612,6 +720,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
 
             byte[] check = new byte[PointBytes];
             return 0 != EncodePoint(ref pR, check, 0) && Arrays.AreEqual(check, R);
+#endif
         }
 
         private static void Init(out PointAccum r)
@@ -1203,6 +1312,11 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
 
         private static byte[] ReduceScalar(byte[] n)
         {
+            byte[] r = new byte[ScalarBytes];
+
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+            ReduceScalar(n, r);
+#else
             long x00 = Decode32(n,  0) & M32L;          // x00:32/--
             long x01 = (Decode24(n, 4) << 4) & M32L;    // x01:28/--
             long x02 = Decode32(n,  7) & M32L;          // x02:32/--
@@ -1328,15 +1442,152 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             x07 += (x06 >> 28); x06 &= M28L;
             x08 += (x07 >> 28); x07 &= M28L;
 
-            byte[] r = new byte[ScalarBytes];
             Encode56((ulong)(x00 | (x01 << 28)), r, 0);
             Encode56((ulong)(x02 | (x03 << 28)), r, 7);
             Encode56((ulong)(x04 | (x05 << 28)), r, 14);
             Encode56((ulong)(x06 | (x07 << 28)), r, 21);
             Encode32((uint)x08, r, 28);
+#endif
+
             return r;
         }
 
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+        private static void ReduceScalar(ReadOnlySpan<byte> n, Span<byte> r)
+        {
+            long x00 = Decode32(n[0..]) & M32L;         // x00:32/--
+            long x01 = (Decode24(n[4..]) << 4) & M32L;  // x01:28/--
+            long x02 = Decode32(n[7..]) & M32L;         // x02:32/--
+            long x03 = (Decode24(n[11..]) << 4) & M32L; // x03:28/--
+            long x04 = Decode32(n[14..]) & M32L;        // x04:32/--
+            long x05 = (Decode24(n[18..]) << 4) & M32L; // x05:28/--
+            long x06 = Decode32(n[21..]) & M32L;        // x06:32/--
+            long x07 = (Decode24(n[25..]) << 4) & M32L; // x07:28/--
+            long x08 = Decode32(n[28..]) & M32L;        // x08:32/--
+            long x09 = (Decode24(n[32..]) << 4) & M32L; // x09:28/--
+            long x10 = Decode32(n[35..]) & M32L;        // x10:32/--
+            long x11 = (Decode24(n[39..]) << 4) & M32L; // x11:28/--
+            long x12 = Decode32(n[42..]) & M32L;        // x12:32/--
+            long x13 = (Decode24(n[46..]) << 4) & M32L; // x13:28/--
+            long x14 = Decode32(n[49..]) & M32L;        // x14:32/--
+            long x15 = (Decode24(n[53..]) << 4) & M32L; // x15:28/--
+            long x16 = Decode32(n[56..]) & M32L;        // x16:32/--
+            long x17 = (Decode24(n[60..]) << 4) & M32L; // x17:28/--
+            long x18 = n[63]                  & M08L;   // x18:08/--
+            long t;
+
+            //x18 += (x17 >> 28); x17 &= M28L;
+            x09 -= x18 * L0;                            // x09:34/28
+            x10 -= x18 * L1;                            // x10:33/30
+            x11 -= x18 * L2;                            // x11:35/28
+            x12 -= x18 * L3;                            // x12:32/31
+            x13 -= x18 * L4;                            // x13:28/21
+
+            x17 += (x16 >> 28); x16 &= M28L;            // x17:28/--, x16:28/--
+            x08 -= x17 * L0;                            // x08:54/32
+            x09 -= x17 * L1;                            // x09:52/51
+            x10 -= x17 * L2;                            // x10:55/34
+            x11 -= x17 * L3;                            // x11:51/36
+            x12 -= x17 * L4;                            // x12:41/--
+
+            //x16 += (x15 >> 28); x15 &= M28L;
+            x07 -= x16 * L0;                            // x07:54/28
+            x08 -= x16 * L1;                            // x08:54/53
+            x09 -= x16 * L2;                            // x09:55/53
+            x10 -= x16 * L3;                            // x10:55/52
+            x11 -= x16 * L4;                            // x11:51/41
+
+            x15 += (x14 >> 28); x14 &= M28L;            // x15:28/--, x14:28/--
+            x06 -= x15 * L0;                            // x06:54/32
+            x07 -= x15 * L1;                            // x07:54/53
+            x08 -= x15 * L2;                            // x08:56/--
+            x09 -= x15 * L3;                            // x09:55/54
+            x10 -= x15 * L4;                            // x10:55/53
+
+            //x14 += (x13 >> 28); x13 &= M28L;
+            x05 -= x14 * L0;                            // x05:54/28
+            x06 -= x14 * L1;                            // x06:54/53
+            x07 -= x14 * L2;                            // x07:56/--
+            x08 -= x14 * L3;                            // x08:56/51
+            x09 -= x14 * L4;                            // x09:56/--
+
+            x13 += (x12 >> 28); x12 &= M28L;            // x13:28/22, x12:28/--
+            x04 -= x13 * L0;                            // x04:54/49
+            x05 -= x13 * L1;                            // x05:54/53
+            x06 -= x13 * L2;                            // x06:56/--
+            x07 -= x13 * L3;                            // x07:56/52
+            x08 -= x13 * L4;                            // x08:56/52
+
+            x12 += (x11 >> 28); x11 &= M28L;            // x12:28/24, x11:28/--
+            x03 -= x12 * L0;                            // x03:54/49
+            x04 -= x12 * L1;                            // x04:54/51
+            x05 -= x12 * L2;                            // x05:56/--
+            x06 -= x12 * L3;                            // x06:56/52
+            x07 -= x12 * L4;                            // x07:56/53
+
+            x11 += (x10 >> 28); x10 &= M28L;            // x11:29/--, x10:28/--
+            x02 -= x11 * L0;                            // x02:55/32
+            x03 -= x11 * L1;                            // x03:55/--
+            x04 -= x11 * L2;                            // x04:56/55
+            x05 -= x11 * L3;                            // x05:56/52
+            x06 -= x11 * L4;                            // x06:56/53
+
+            x10 += (x09 >> 28); x09 &= M28L;            // x10:29/--, x09:28/--
+            x01 -= x10 * L0;                            // x01:55/28
+            x02 -= x10 * L1;                            // x02:55/54
+            x03 -= x10 * L2;                            // x03:56/55
+            x04 -= x10 * L3;                            // x04:57/--
+            x05 -= x10 * L4;                            // x05:56/53
+
+            x08 += (x07 >> 28); x07 &= M28L;            // x08:56/53, x07:28/--
+            x09 += (x08 >> 28); x08 &= M28L;            // x09:29/25, x08:28/--
+
+            t    = (x08 >> 27) & 1L;
+            x09 += t;                                   // x09:29/26
+
+            x00 -= x09 * L0;                            // x00:55/53
+            x01 -= x09 * L1;                            // x01:55/54
+            x02 -= x09 * L2;                            // x02:57/--
+            x03 -= x09 * L3;                            // x03:57/--
+            x04 -= x09 * L4;                            // x04:57/42
+
+            x01 += (x00 >> 28); x00 &= M28L;
+            x02 += (x01 >> 28); x01 &= M28L;
+            x03 += (x02 >> 28); x02 &= M28L;
+            x04 += (x03 >> 28); x03 &= M28L;
+            x05 += (x04 >> 28); x04 &= M28L;
+            x06 += (x05 >> 28); x05 &= M28L;
+            x07 += (x06 >> 28); x06 &= M28L;
+            x08 += (x07 >> 28); x07 &= M28L;
+            x09  = (x08 >> 28); x08 &= M28L;
+
+            x09 -= t;
+
+            Debug.Assert(x09 == 0L || x09 == -1L);
+
+            x00 += x09 & L0;
+            x01 += x09 & L1;
+            x02 += x09 & L2;
+            x03 += x09 & L3;
+            x04 += x09 & L4;
+
+            x01 += (x00 >> 28); x00 &= M28L;
+            x02 += (x01 >> 28); x01 &= M28L;
+            x03 += (x02 >> 28); x02 &= M28L;
+            x04 += (x03 >> 28); x03 &= M28L;
+            x05 += (x04 >> 28); x04 &= M28L;
+            x06 += (x05 >> 28); x05 &= M28L;
+            x07 += (x06 >> 28); x06 &= M28L;
+            x08 += (x07 >> 28); x07 &= M28L;
+
+            Encode56((ulong)(x00 | (x01 << 28)), r);
+            Encode56((ulong)(x02 | (x03 << 28)), r[7..]);
+            Encode56((ulong)(x04 | (x05 << 28)), r[14..]);
+            Encode56((ulong)(x06 | (x07 << 28)), r[21..]);
+            Encode32((uint)x08, r[28..]);
+        }
+#endif
+
         private static void ScalarMult(byte[] k, ref PointAffine p, ref PointAccum r)
         {
 #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
@@ -1634,6 +1885,9 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
 
         private static void ScalarMultStrausVar(uint[] nb, uint[] np, ref PointAffine p, ref PointAccum r)
         {
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+            ScalarMultStrausVar(nb.AsSpan(), np.AsSpan(), ref p, ref r);
+#else
             Precompute();
 
             sbyte[] ws_b = GetWnafVar(nb, WnafWidthBase);
@@ -1671,7 +1925,52 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
 
                 PointDouble(ref r);
             }
+#endif
+        }
+
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+        private static void ScalarMultStrausVar(ReadOnlySpan<uint> nb, ReadOnlySpan<uint> np, ref PointAffine p,
+            ref PointAccum r)
+        {
+            Precompute();
+
+            sbyte[] ws_b = GetWnafVar(nb, WnafWidthBase);
+            sbyte[] ws_p = GetWnafVar(np, WnafWidth);
+
+            int count = 1 << (WnafWidth - 2);
+            PointPrecompZ[] tp = new PointPrecompZ[count];
+            Init(out PointTemp t);
+            PointPrecomputeZ(ref p, tp, count, ref t);
+
+            PointSetNeutral(ref r);
+
+            for (int bit = 252; ;)
+            {
+                int wb = ws_b[bit];
+                if (wb != 0)
+                {
+                    int sign = wb >> 31;
+                    int index = (wb ^ sign) >> 1;
+
+                    PointAddVar(sign != 0, ref PrecompBaseWnaf[index], ref r, ref t);
+                }
+
+                int wp = ws_p[bit];
+                if (wp != 0)
+                {
+                    int sign = wp >> 31;
+                    int index = (wp ^ sign) >> 1;
+
+                    PointAddVar(sign != 0, ref tp[index], ref r, ref t);
+                }
+
+                if (--bit < 0)
+                    break;
+
+                PointDouble(ref r);
+            }
         }
+#endif
 
         public static void Sign(byte[] sk, int skOff, byte[] m, int mOff, int mLen, byte[] sig, int sigOff)
         {