EdDSA public key validation

- per NIST SP 800-186

4 files changed, 217 insertions, 6 deletions

diff --git a/crypto/src/math/ec/rfc7748/X25519Field.cs b/crypto/src/math/ec/rfc7748/X25519Field.cs
index ffede563b..d0b835226 100644
--- a/crypto/src/math/ec/rfc7748/X25519Field.cs
+++ b/crypto/src/math/ec/rfc7748/X25519Field.cs
@@ -48,6 +48,23 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
             }
         }
 
+        public static int AreEqual(int[] x, int[] y)
+        {
+            int d = 0;
+            for (int i = 0; i < Size; ++i)
+            {
+                d |= x[i] ^ y[i];
+            }
+            d |= d >> 16;
+            d &= 0xFFFF;
+            return (d - 1) >> 31;
+        }
+
+        public static bool AreEqualVar(int[] x, int[] y)
+        {
+            return 0 != AreEqual(x, y);
+        }
+
         public static void Carry(int[] z)
         {
             int z0 = z[0], z1 = z[1], z2 = z[2], z3 = z[3], z4 = z[4];
@@ -258,6 +275,23 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
             Decode(u, 0, z);
         }
 
+        public static int IsOne(int[] x)
+        {
+            int d = x[0] ^ 1;
+            for (int i = 1; i < Size; ++i)
+            {
+                d |= x[i];
+            }
+            d |= d >> 16;
+            d &= 0xFFFF;
+            return (d - 1) >> 31;
+        }
+
+        public static bool IsOneVar(int[] x)
+        {
+            return 0 != IsOne(x);
+        }
+
         public static int IsZero(int[] x)
         {
             int d = 0;
diff --git a/crypto/src/math/ec/rfc7748/X448Field.cs b/crypto/src/math/ec/rfc7748/X448Field.cs
index ef4fd4627..6d8c60e78 100644
--- a/crypto/src/math/ec/rfc7748/X448Field.cs
+++ b/crypto/src/math/ec/rfc7748/X448Field.cs
@@ -46,6 +46,23 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
         //    }
         //}
 
+        public static int AreEqual(uint[] x, uint[] y)
+        {
+            uint d = 0;
+            for (int i = 0; i < Size; ++i)
+            {
+                d |= x[i] ^ y[i];
+            }
+            d |= d >> 16;
+            d &= 0xFFFF;
+            return ((int)d - 1) >> 31;
+        }
+
+        public static bool AreEqualVar(uint[] x, uint[] y)
+        {
+            return 0 != AreEqual(x, y);
+        }
+
         public static void Carry(uint[] z)
         {
             uint z0 = z[0], z1 = z[1], z2 = z[2], z3 = z[3], z4 = z[4], z5 = z[5], z6 = z[6], z7 = z[7];
@@ -285,6 +302,23 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
             Decode(u, 0, z);
         }
 
+        public static int IsOne(uint[] x)
+        {
+            uint d = x[0] ^ 1;
+            for (int i = 1; i < Size; ++i)
+            {
+                d |= x[i];
+            }
+            d |= d >> 16;
+            d &= 0xFFFF;
+            return ((int)d - 1) >> 31;
+        }
+
+        public static bool IsOneVar(uint[] x)
+        {
+            return 0 != IsOne(x);
+        }
+
         public static int IsZero(uint[] x)
         {
             uint d = 0;
diff --git a/crypto/src/math/ec/rfc8032/Ed25519.cs b/crypto/src/math/ec/rfc8032/Ed25519.cs
index bdbe47e50..cc351bc45 100644
--- a/crypto/src/math/ec/rfc8032/Ed25519.cs
+++ b/crypto/src/math/ec/rfc8032/Ed25519.cs
@@ -183,6 +183,13 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             return !Nat256.Gte(n, L);
         }
 
+        private static byte[] Copy(byte[] buf, int off, int len)
+        {
+            byte[] result = new byte[len];
+            Array.Copy(buf, off, result, 0, len);
+            return result;
+        }
+
         private static IDigest CreateDigest()
         {
             return new Sha512Digest();
@@ -220,7 +227,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
 
         private static bool DecodePointVar(byte[] p, int pOff, bool negate, PointAffine r)
         {
-            byte[] py = Arrays.CopyOfRange(p, pOff, pOff + PointBytes);
+            byte[] py = Copy(p, pOff, PointBytes);
             if (!CheckPointVar(py))
                 return false;
 
@@ -461,8 +468,8 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             if (!CheckContextVar(ctx, phflag))
                 throw new ArgumentException("ctx");
 
-            byte[] R = Arrays.CopyOfRange(sig, sigOff, sigOff + PointBytes);
-            byte[] S = Arrays.CopyOfRange(sig, sigOff + PointBytes, sigOff + SignatureSize);
+            byte[] R = Copy(sig, sigOff, PointBytes);
+            byte[] S = Copy(sig, sigOff + PointBytes, ScalarBytes);
 
             if (!CheckPointVar(R))
                 return false;
@@ -498,6 +505,16 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             return 0 != EncodePoint(pR, check, 0) && Arrays.AreEqual(check, R);
         }
 
+        private static bool IsNeutralElementVar(int[] x, int[] y)
+        {
+            return F.IsZeroVar(x) && F.IsOneVar(y);
+        }
+
+        private static bool IsNeutralElementVar(int[] x, int[] y, int[] z)
+        {
+            return F.IsZeroVar(x) && F.AreEqualVar(y, z);
+        }
+
         private static void PointAdd(PointExt p, PointAccum r)
         {
             int[] a = F.Create();
@@ -1234,6 +1251,36 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             F.Copy(p.z, 0, z, 0);
         }
 
+        private static void ScalarMultOrder(PointAffine p, PointAccum r)
+        {
+            uint[] n = new uint[ScalarUints];
+            Nat.ShiftDownBit(ScalarUints, L, 0, n);
+            n[ScalarUints - 1] |= 1U << 28;
+
+            int[] table = PointPrecompute(p, 8);
+            PointExt q = new PointExt();
+
+            // Replace first 4 doublings (2^4 * P) with 1 addition (P + 15 * P)
+            PointCopy(p, r);
+            PointLookup(table, 7, q);
+            PointAdd(q, r);
+
+            int w = 62;
+            for (;;)
+            {
+                PointLookup(n, w, table, q);
+                PointAdd(q, r);
+
+                if (--w < 0)
+                    break;
+
+                for (int i = 0; i < 4; ++i)
+                {
+                    PointDouble(r);
+                }
+            }
+        }
+
         private static void ScalarMultStrausVar(uint[] nb, uint[] np, PointAffine p, PointAccum r)
         {
             Precompute();
@@ -1340,6 +1387,34 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             ImplSign(sk, skOff, pk, pkOff, ctx, phflag, m, 0, m.Length, sig, sigOff);
         }
 
+        public static bool ValidatePublicKeyFull(byte[] pk, int pkOff)
+        {
+            PointAffine p = new PointAffine();
+            if (!DecodePointVar(pk, pkOff, false, p))
+                return false;
+
+            F.Normalize(p.x);
+            F.Normalize(p.y);
+
+            if (IsNeutralElementVar(p.x, p.y))
+                return false;
+
+            PointAccum r = new PointAccum();
+            ScalarMultOrder(p, r);
+
+            F.Normalize(r.x);
+            F.Normalize(r.y);
+            F.Normalize(r.z);
+
+            return IsNeutralElementVar(r.x, r.y, r.z);
+        }
+
+        public static bool ValidatePublicKeyPartial(byte[] pk, int pkOff)
+        {
+            PointAffine p = new PointAffine();
+            return DecodePointVar(pk, pkOff, false, p);
+        }
+
         public static bool Verify(byte[] sig, int sigOff, byte[] pk, int pkOff, byte[] m, int mOff, int mLen)
         {
             byte[] ctx = null;
diff --git a/crypto/src/math/ec/rfc8032/Ed448.cs b/crypto/src/math/ec/rfc8032/Ed448.cs
index bbe1bb444..28ee546d1 100644
--- a/crypto/src/math/ec/rfc8032/Ed448.cs
+++ b/crypto/src/math/ec/rfc8032/Ed448.cs
@@ -173,6 +173,13 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             return !Nat.Gte(ScalarUints, n, L);
         }
 
+        private static byte[] Copy(byte[] buf, int off, int len)
+        {
+            byte[] result = new byte[len];
+            Array.Copy(buf, off, result, 0, len);
+            return result;
+        }
+
         public static IXof CreatePrehash()
         {
             return CreateXof();
@@ -217,7 +224,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
 
         private static bool DecodePointVar(byte[] p, int pOff, bool negate, PointExt r)
         {
-            byte[] py = Arrays.CopyOfRange(p, pOff, pOff + PointBytes);
+            byte[] py = Copy(p, pOff, PointBytes);
             if (!CheckPointVar(py))
                 return false;
 
@@ -459,8 +466,8 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             if (!CheckContextVar(ctx))
                 throw new ArgumentException("ctx");
 
-            byte[] R = Arrays.CopyOfRange(sig, sigOff, sigOff + PointBytes);
-            byte[] S = Arrays.CopyOfRange(sig, sigOff + PointBytes, sigOff + SignatureSize);
+            byte[] R = Copy(sig, sigOff, PointBytes);
+            byte[] S = Copy(sig, sigOff + PointBytes, ScalarBytes);
 
             if (!CheckPointVar(R))
                 return false;
@@ -496,6 +503,16 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             return 0 != EncodePoint(pR, check, 0) && Arrays.AreEqual(check, R);
         }
 
+        private static bool IsNeutralElementVar(uint[] x, uint[] y)
+        {
+            return F.IsZeroVar(x) && F.IsOneVar(y);
+        }
+
+        private static bool IsNeutralElementVar(uint[] x, uint[] y, uint[] z)
+        {
+            return F.IsZeroVar(x) && F.AreEqualVar(y, z);
+        }
+
         private static void PointAdd(PointExt p, PointExt r)
         {
             uint[] a = F.Create();
@@ -1255,6 +1272,28 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             F.Copy(p.y, 0, y, 0);
         }
 
+        private static void ScalarMultOrder(PointExt p, PointExt r)
+        {
+            uint[] n = new uint[ScalarUints];
+            Nat.ShiftDownBit(ScalarUints, L, 1, n);
+
+            uint[] table = PointPrecompute(p, 8);
+            PointExt q = new PointExt();
+
+            PointLookup(n, 111, table, r);
+
+            for (int w = 110; w >= 0; --w)
+            {
+                for (int i = 0; i < 4; ++i)
+                {
+                    PointDouble(r);
+                }
+
+                PointLookup(n, w, table, q);
+                PointAdd(q, r);
+            }
+        }
+
         private static void ScalarMultStrausVar(uint[] nb, uint[] np, PointExt p, PointExt r)
         {
             Precompute();
@@ -1345,6 +1384,35 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             ImplSign(sk, skOff, pk, pkOff, ctx, phflag, m, 0, m.Length, sig, sigOff);
         }
 
+        public static bool ValidatePublicKeyFull(byte[] pk, int pkOff)
+        {
+            PointExt p = new PointExt();
+            if (!DecodePointVar(pk, pkOff, false, p))
+                return false;
+
+            F.Normalize(p.x);
+            F.Normalize(p.y);
+            F.Normalize(p.z);
+
+            if (IsNeutralElementVar(p.x, p.y, p.z))
+                return false;
+
+            PointExt r = new PointExt();
+            ScalarMultOrder(p, r);
+
+            F.Normalize(r.x);
+            F.Normalize(r.y);
+            F.Normalize(r.z);
+
+            return IsNeutralElementVar(r.x, r.y, r.z);
+        }
+
+        public static bool ValidatePublicKeyPartial(byte[] pk, int pkOff)
+        {
+            PointExt p = new PointExt();
+            return DecodePointVar(pk, pkOff, false, p);
+        }
+
         public static bool Verify(byte[] sig, int sigOff, byte[] pk, int pkOff, byte[] ctx, byte[] m, int mOff, int mLen)
         {
             byte phflag = 0x00;