Add Ed25519 and Ed448 from RFC 8032

1 files changed, 133 insertions, 14 deletions

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;
+            }
+        }
     }
 }