Add Ed25519 and Ed448 from RFC 8032

4 files changed, 249 insertions, 33 deletions

diff --git a/crypto/src/math/ec/rfc7748/X25519.cs b/crypto/src/math/ec/rfc7748/X25519.cs
index 16f680d90..a10d53da5 100644
--- a/crypto/src/math/ec/rfc7748/X25519.cs
+++ b/crypto/src/math/ec/rfc7748/X25519.cs
@@ -10,10 +10,10 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
         private const int C_A24 = (C_A + 2)/4;
 
         // 0x1
-        //private static readonly int[] S_x = new int[] { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
+        //private static readonly int[] S_x = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
 
         // 0x215132111D8354CB52385F46DCA2B71D440F6A51EB4D1207816B1E0137D48290
-        private static readonly int[] PsubS_x = new int[]{ 0x03D48290, 0x02C7804D, 0x01207816, 0x028F5A68, 0x00881ED4, 0x00A2B71D,
+        private static readonly int[] PsubS_x = { 0x03D48290, 0x02C7804D, 0x01207816, 0x028F5A68, 0x00881ED4, 0x00A2B71D,
             0x0217D1B7, 0x014CB523, 0x0088EC1A, 0x0042A264 };
 
         private static int[] precompBase = null;
diff --git a/crypto/src/math/ec/rfc7748/X25519Field.cs b/crypto/src/math/ec/rfc7748/X25519Field.cs
index 282f41628..fd5599657 100644
--- a/crypto/src/math/ec/rfc7748/X25519Field.cs
+++ b/crypto/src/math/ec/rfc7748/X25519Field.cs
@@ -11,6 +11,9 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
         private const int M25 = 0x01FFFFFF;
         private const int M26 = 0x03FFFFFF;
 
+        private static readonly int[] RootNegOne = { 0x020EA0B0, 0x0386C9D2, 0x00478C4E, 0x0035697F, 0x005E8630,
+            0x01FBD7A7, 0x0340264F, 0x01F0B2B4, 0x00027E0E, 0x00570649 };
+
         private X25519Field() {}
 
         public static void Add(int[] x, int[] y, int[] z)
@@ -21,6 +24,16 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
             }
         }
 
+        public static void AddOne(int[] z)
+        {
+            z[0] += 1;
+        }
+
+        public static void AddOne(int[] z, int zOff)
+        {
+            z[zOff] += 1;
+        }
+
         public static void Apm(int[] x, int[] y, int[] zp, int[] zm)
         {
             for (int i = 0; i < Size; ++i)
@@ -54,6 +67,17 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
             z[5] = z5; z[6] = z6; z[7] = z7; z[8] = z8; z[9] = z9;
         }
 
+        public static void CNegate(int negate, int[] z)
+        {
+            Debug.Assert(negate >> 1 == 0);
+
+            int mask = 0 - negate;
+            for (int i = 0; i < Size; ++i)
+            {
+                z[i] = (z[i] ^ mask) - mask;
+            }
+        }
+
         public static void Copy(int[] x, int xOff, int[] z, int zOff)
         {
             for (int i = 0; i < Size; ++i)
@@ -67,6 +91,11 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
             return new int[Size];
         }
 
+        public static int[] CreateTable(int n)
+        {
+            return new int[Size * n];
+        }
+
         public static void CSwap(int swap, int[] a, int[] b)
         {
             Debug.Assert(swap >> 1 == 0);
@@ -143,24 +172,23 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
             // (250 1s) (1 0s) (1 1s) (1 0s) (2 1s)
             // Addition chain: [1] [2] 3 5 10 15 25 50 75 125 [250]
 
-            int[] x2 = Create();    Sqr(x, x2);             Mul(x, x2, x2);
-            int[] x3 = Create();    Sqr(x2, x3);            Mul(x, x3, x3);
-            int[] x5 = x3;          Sqr(x3, 2, x5);         Mul(x2, x5, x5);
-            int[] x10 = Create();   Sqr(x5, 5, x10);        Mul(x5, x10, x10);
-            int[] x15 = Create();   Sqr(x10, 5, x15);       Mul(x5, x15, x15);
-            int[] x25 = x5;         Sqr(x15, 10, x25);      Mul(x10, x25, x25);
-            int[] x50 = x10;        Sqr(x25, 25, x50);      Mul(x25, x50, x50);
-            int[] x75 = x15;        Sqr(x50, 25, x75);      Mul(x25, x75, x75);
-            int[] x125 = x25;       Sqr(x75, 50, x125);     Mul(x50, x125, x125);
-            int[] x250 = x50;       Sqr(x125, 125, x250);   Mul(x125, x250, x250);
-
-            int[] t = x125;
-            Sqr(x250, 2, t);
-            Mul(t, x, t);
+            int[] x2 = Create();
+            int[] t = Create();
+            PowPm5d8(x, x2, t);
             Sqr(t, 3, t);
             Mul(t, x2, z);
         }
 
+        public static bool IsZeroVar(int[] x)
+        {
+            int d = 0;
+            for (int i = 0; i < Size; ++i)
+            {
+                d |= x[i];
+            }
+            return d == 0;
+        }
+
         public static void Mul(int[] x, int y, int[] z)
         {
             int x0 = x[0], x1 = x[1], x2 = x[2], x3 = x[3], x4 = x[4];
@@ -345,6 +373,14 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
             z[9]     = z9 + (int)t;
         }
 
+        public static void Negate(int[] x, int[] z)
+        {
+            for (int i = 0; i < Size; ++i)
+            {
+                z[i] = -x[i];
+            }
+        }
+
         public static void Normalize(int[] z)
         {
             int x = (z[9] >> 23) & 1;
@@ -353,6 +389,37 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
             Debug.Assert(z[9] >> 24 == 0);
         }
 
+        public static void One(int[] z)
+        {
+            z[0] = 1;
+            for (int i = 1; i < Size; ++i)
+            {
+                z[i] = 0;
+            }
+        }
+
+        private static void PowPm5d8(int[] x, int[] rx2, int[] rz)
+        {
+            // z = x^((p-5)/8) = x^FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD
+            // (250 1s) (1 0s) (1 1s)
+            // Addition chain: [1] 2 3 5 10 15 25 50 75 125 [250]
+
+            int[] x2 = rx2;         Sqr(x, x2);             Mul(x, x2, x2);
+            int[] x3 = Create();    Sqr(x2, x3);            Mul(x, x3, x3);
+            int[] x5 = x3;          Sqr(x3, 2, x5);         Mul(x2, x5, x5);
+            int[] x10 = Create();   Sqr(x5, 5, x10);        Mul(x5, x10, x10);
+            int[] x15 = Create();   Sqr(x10, 5, x15);       Mul(x5, x15, x15);
+            int[] x25 = x5;         Sqr(x15, 10, x25);      Mul(x10, x25, x25);
+            int[] x50 = x10;        Sqr(x25, 25, x50);      Mul(x25, x50, x50);
+            int[] x75 = x15;        Sqr(x50, 25, x75);      Mul(x25, x75, x75);
+            int[] x125 = x25;       Sqr(x75, 50, x125);     Mul(x50, x125, x125);
+            int[] x250 = x50;       Sqr(x125, 125, x250);   Mul(x125, x250, x250);
+
+            int[] t = x125;
+            Sqr(x250, 2, t);
+            Mul(t, x, rz);
+        }
+
         private static void Reduce(int[] z, int c)
         {
             int z9 = z[9], t = z9;
@@ -509,6 +576,45 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
             }
         }
 
+        public static bool SqrtRatioVar(int[] u, int[] v, int[] z)
+        {
+            int[] uv3 = Create();
+            int[] uv7 = Create();
+
+            Mul(u, v, uv3);
+            Sqr(v, uv7);
+            Mul(uv3, uv7, uv3);
+            Sqr(uv7, uv7);
+            Mul(uv7, uv3, uv7);
+
+            int[] t = Create();
+            int[] x = Create();
+            PowPm5d8(uv7, t, x);
+            Mul(x, uv3, x);
+
+            int[] vx2 = Create();
+            Sqr(x, vx2);
+            Mul(vx2, v, vx2);
+
+            Sub(vx2, u, t);
+            Normalize(t);
+            if (IsZeroVar(t))
+            {
+                Copy(x, 0, z, 0);
+                return true;
+            }
+
+            Add(vx2, u, t);
+            Normalize(t);
+            if (IsZeroVar(t))
+            {
+                Mul(x, RootNegOne, z);
+                return true;
+            }
+
+            return false;
+        }
+
         public static void Sub(int[] x, int[] y, int[] z)
         {
             for (int i = 0; i < Size; ++i)
@@ -516,5 +622,18 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
                 z[i] = x[i] - y[i];
             }
         }
+
+        public static void SubOne(int[] z)
+        {
+            z[0] -= 1;
+        }
+
+        public static void Zero(int[] z)
+        {
+            for (int i = 0; i < Size; ++i)
+            {
+                z[i] = 0;
+            }
+        }
     }
 }
diff --git a/crypto/src/math/ec/rfc7748/X448.cs b/crypto/src/math/ec/rfc7748/X448.cs
index 32a4a9e2a..88e8a5d76 100644
--- a/crypto/src/math/ec/rfc7748/X448.cs
+++ b/crypto/src/math/ec/rfc7748/X448.cs
@@ -10,14 +10,14 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
         private const uint C_A24 = (C_A + 2)/4;
 
         // 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE
-        private static readonly uint[] S_x = new uint[]{ 0x0FFFFFFEU, 0x0FFFFFFFU, 0x0FFFFFFFU, 0x0FFFFFFFU, 0x0FFFFFFFU, 0x0FFFFFFFU,
+        private static readonly uint[] S_x = { 0x0FFFFFFEU, 0x0FFFFFFFU, 0x0FFFFFFFU, 0x0FFFFFFFU, 0x0FFFFFFFU, 0x0FFFFFFFU,
             0x0FFFFFFFU, 0x0FFFFFFFU, 0x0FFFFFFEU, 0x0FFFFFFFU, 0x0FFFFFFFU, 0x0FFFFFFFU, 0x0FFFFFFFU, 0x0FFFFFFFU, 0x0FFFFFFFU,
             0x0FFFFFFFU };
 
         // 0xF0FAB725013244423ACF03881AFFEB7BDACDD1031C81B9672954459D84C1F823F1BD65643ACE1B5123AC33FF1C69BAF8ACB1197DC99D2720
-        private static readonly uint[] PsubS_x = new uint[]{ 0x099d2720U, 0x0b1197dcU, 0x09baf8acU, 0x033ff1c6U, 0x0b5123acU,
-            0x0643ace1U, 0x03f1bd65U, 0x084c1f82U, 0x0954459dU, 0x081b9672U, 0x0dd1031cU, 0x0eb7bdacU, 0x03881affU, 0x0423acf0U,
-            0x05013244U, 0x0f0fab72U };
+        private static readonly uint[] PsubS_x = { 0x099D2720U, 0x0B1197DCU, 0x09BAF8ACU, 0x033FF1C6U, 0x0B5123ACU,
+            0x0643ACE1U, 0x03F1BD65U, 0x084C1F82U, 0x0954459DU, 0x081B9672U, 0x0DD1031CU, 0x0EB7BDACU, 0x03881AFFU, 0x0423ACF0U,
+            0x05013244U, 0x0F0FAB72U };
 
         private static uint[] precompBase = null;
 
diff --git a/crypto/src/math/ec/rfc7748/X448Field.cs b/crypto/src/math/ec/rfc7748/X448Field.cs
index 0c44f1eb5..5a682714d 100644
--- a/crypto/src/math/ec/rfc7748/X448Field.cs
+++ b/crypto/src/math/ec/rfc7748/X448Field.cs
@@ -1,6 +1,8 @@
 using System;
 using System.Diagnostics;
 
+using Org.BouncyCastle.Math.Raw;
+
 namespace Org.BouncyCastle.Math.EC.Rfc7748
 {
     [CLSCompliantAttribute(false)]
@@ -20,6 +22,16 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
             }
         }
 
+        public static void AddOne(uint[] z)
+        {
+            z[0] += 1;
+        }
+
+        public static void AddOne(uint[] z, int zOff)
+        {
+            z[zOff] += 1;
+        }
+
         //public static void Apm(int[] x, int[] y, int[] zp, int[] zm)
         //{
         //    for (int i = 0; i < Size; ++i)
@@ -62,6 +74,16 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
             z[8] = z8; z[9] = z9; z[10] = z10; z[11] = z11; z[12] = z12; z[13] = z13; z[14] = z14; z[15] = z15;
         }
 
+        public static void CNegate(int negate, uint[] z)
+        {
+            Debug.Assert(negate >> 1 == 0);
+
+            uint[] t = Create();
+            Sub(t, z, t);
+
+            Nat.CMov(Size, negate, t, 0, z, 0);
+        }
+
         public static void Copy(uint[] x, int xOff, uint[] z, int zOff)
         {
             for (int i = 0; i < Size; ++i)
@@ -166,25 +188,23 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
             // z = x^(p-2) = x^(2^448 - 2^224 - 3)
             // (223 1s) (1 0s) (222 1s) (1 0s) (1 1s)
             // Addition chain: [1] 2 3 6 9 18 19 37 74 111 [222] [223]
-            uint[] x2 = Create();    Sqr(x, x2);             Mul(x, x2, x2);
-            uint[] x3 = Create();    Sqr(x2, x3);            Mul(x, x3, x3);
-            uint[] x6 = Create();    Sqr(x3, 3, x6);         Mul(x3, x6, x6);
-            uint[] x9 = Create();    Sqr(x6, 3, x9);         Mul(x3, x9, x9);
-            uint[] x18 = Create();   Sqr(x9, 9, x18);        Mul(x9, x18, x18);
-            uint[] x19 = Create();   Sqr(x18, x19);          Mul(x, x19, x19);
-            uint[] x37 = Create();   Sqr(x19, 18, x37);      Mul(x18, x37, x37);
-            uint[] x74 = Create();   Sqr(x37, 37, x74);      Mul(x37, x74, x74);
-            uint[] x111 = Create();  Sqr(x74, 37, x111);     Mul(x37, x111, x111);
-            uint[] x222 = Create();  Sqr(x111, 111, x222);   Mul(x111, x222, x222);
-            uint[] x223 = Create();  Sqr(x222, x223);        Mul(x, x223, x223);
 
             uint[] t = Create();
-            Sqr(x223, 223, t);
-            Mul(t, x222, t);
+            PowPm3d4(x, t);
             Sqr(t, 2, t);
             Mul(t, x, z);
         }
 
+        public static bool IsZeroVar(uint[] x)
+        {
+            uint d = 0;
+            for (int i = 0; i < Size; ++i)
+            {
+                d |= x[i];
+            }
+            return d == 0U;
+        }
+
         public static void Mul(uint[] x, uint y, uint[] z)
         {
             uint x0 = x[0], x1 = x[1], x2 = x[2], x3 = x[3], x4 = x[4], x5 = x[5], x6 = x[6], x7 = x[7];
@@ -563,6 +583,12 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
             z[15] = z15;
         }
 
+        public static void Negate(uint[] x, uint[] z)
+        {
+            uint[] zero = Create();
+            Sub(zero, x, z);
+        }
+
         public static void Normalize(uint[] z)
         {
             //int x = (z[15] >> (28 - 1)) & 1;
@@ -571,6 +597,37 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
             Debug.Assert(z[15] >> 28 == 0U);
         }
 
+        public static void One(uint[] z)
+        {
+            z[0] = 1U;
+            for (int i = 1; i < Size; ++i)
+            {
+                z[i] = 0;
+            }
+        }
+
+        private static void PowPm3d4(uint[] x, uint[] z)
+        {
+            // z = x^((p-3)/4) = x^(2^446 - 2^222 - 1)
+            // (223 1s) (1 0s) (222 1s)
+            // Addition chain: 1 2 3 6 9 18 19 37 74 111 [222] [223]
+            uint[] x2 = Create();   Sqr(x, x2);             Mul(x, x2, x2);
+            uint[] x3 = Create();   Sqr(x2, x3);            Mul(x, x3, x3);
+            uint[] x6 = Create();   Sqr(x3, 3, x6);         Mul(x3, x6, x6);
+            uint[] x9 = Create();   Sqr(x6, 3, x9);         Mul(x3, x9, x9);
+            uint[] x18 = Create();  Sqr(x9, 9, x18);        Mul(x9, x18, x18);
+            uint[] x19 = Create();  Sqr(x18, x19);          Mul(x, x19, x19);
+            uint[] x37 = Create();  Sqr(x19, 18, x37);      Mul(x18, x37, x37);
+            uint[] x74 = Create();  Sqr(x37, 37, x74);      Mul(x37, x74, x74);
+            uint[] x111 = Create(); Sqr(x74, 37, x111);     Mul(x37, x111, x111);
+            uint[] x222 = Create(); Sqr(x111, 111, x222);   Mul(x111, x222, x222);
+            uint[] x223 = Create(); Sqr(x222, x223);        Mul(x, x223, x223);
+
+            uint[] t = Create();
+            Sqr(x223, 223, t);
+            Mul(t, x222, z);
+        }
+
         private static void Reduce(uint[] z, int c)
         {
             uint z15 = z[15];
@@ -836,6 +893,38 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
             }
         }
 
+        public static bool SqrtRatioVar(uint[] u, uint[] v, uint[] z)
+        {
+            uint[] u3v = Create();
+            uint[] u5v3 = Create();
+
+            Sqr(u, u3v);
+            Mul(u3v, v, u3v);
+            Sqr(u3v, u5v3);
+            Mul(u3v, u, u3v);
+            Mul(u5v3, u, u5v3);
+            Mul(u5v3, v, u5v3);
+
+            uint[] x = Create();
+            PowPm3d4(u5v3, x);
+            Mul(x, u3v, x);
+
+            uint[] t = Create();
+            Sqr(x, t);
+            Mul(t, v, t);
+
+            Sub(u, t, t);
+            Normalize(t);
+
+            if (IsZeroVar(t))
+            {
+                Copy(x, 0, z, 0);
+                return true;
+            }
+
+            return false;
+        }
+
         public static void Sub(uint[] x, uint[] y, uint[] z)
         {
             uint x0 = x[0], x1 = x[1], x2 = x[2], x3 = x[3], x4 = x[4], x5 = x[5], x6 = x[6], x7 = x[7];
@@ -900,5 +989,13 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
             z[14] = z14;
             z[15] = z15;
         }
+
+        public static void Zero(uint[] z)
+        {
+            for (int i = 0; i < Size; ++i)
+            {
+                z[i] = 0;
+            }
+        }
     }
 }