Use Edwards internals for X25519/X448 public key calculations

4 files changed, 49 insertions, 249 deletions

diff --git a/crypto/src/math/ec/rfc7748/X25519.cs b/crypto/src/math/ec/rfc7748/X25519.cs
index 5c408ae42..1d581bb85 100644
--- a/crypto/src/math/ec/rfc7748/X25519.cs
+++ b/crypto/src/math/ec/rfc7748/X25519.cs
@@ -1,6 +1,7 @@
 using System;
 using System.Diagnostics;
 
+using Org.BouncyCastle.Math.EC.Rfc8032;
 using Org.BouncyCastle.Security;
 using Org.BouncyCastle.Utilities;
 
@@ -14,15 +15,8 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
         private const int C_A = 486662;
         private const int C_A24 = (C_A + 2)/4;
 
-        // 0x1
-        //private static readonly int[] S_x = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
-
-        // 0x215132111D8354CB52385F46DCA2B71D440F6A51EB4D1207816B1E0137D48290
-        private static readonly int[] PsubS_x = { 0x03D48290, 0x02C7804D, 0x01207816, 0x028F5A68, 0x00881ED4, 0x00A2B71D,
-            0x0217D1B7, 0x014CB523, 0x0088EC1A, 0x0042A264 };
-
-        private static readonly object precompLock = new object();
-        private static int[] precompBase = null;
+        //private static readonly int[] SqrtNeg486664 = { 0x03457E06, 0x03812ABF, 0x01A82CC6, 0x028A5BE8, 0x018B43A7,
+        //    0x03FC4F7E, 0x02C23700, 0x006BBD27, 0x03A30500, 0x001E4DDB };
 
         public static bool CalculateAgreement(byte[] k, int kOff, byte[] u, int uOff, byte[] r, int rOff)
         {
@@ -82,64 +76,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
 
         public static void Precompute()
         {
-            lock (precompLock)
-            {
-                if (precompBase != null)
-                    return;
-
-                precompBase = new int[X25519Field.Size * 252];
-
-                int[] xs = precompBase;
-                int[] zs = new int[X25519Field.Size * 251];
-
-                int[] x = X25519Field.Create(); x[0] = 9;
-                int[] z = X25519Field.Create(); z[0] = 1;
-
-                int[] n = X25519Field.Create();
-                int[] d = X25519Field.Create();
-
-                X25519Field.Apm(x, z, n, d);
-
-                int[] c = X25519Field.Create(); X25519Field.Copy(d, 0, c, 0);
-
-                int off = 0;
-                for (; ; )
-                {
-                    X25519Field.Copy(n, 0, xs, off);
-
-                    if (off == (X25519Field.Size * 251))
-                        break;
-
-                    PointDouble(x, z);
-
-                    X25519Field.Apm(x, z, n, d);
-                    X25519Field.Mul(n, c, n);
-                    X25519Field.Mul(c, d, c);
-
-                    X25519Field.Copy(d, 0, zs, off);
-
-                    off += X25519Field.Size;
-                }
-
-                int[] u = X25519Field.Create();
-                X25519Field.Inv(c, u);
-
-                for (; ; )
-                {
-                    X25519Field.Copy(xs, off, x, 0);
-
-                    X25519Field.Mul(x, u, x);
-                    //X25519Field.Normalize(x);
-                    X25519Field.Copy(x, 0, precompBase, off);
-
-                    if (off == 0)
-                        break;
-
-                    off -= X25519Field.Size;
-                    X25519Field.Copy(zs, off, z, 0);
-                    X25519Field.Mul(u, z, u);
-                }
-            }
+            Ed25519.Precompute();
         }
 
         public static void ScalarMult(byte[] k, int kOff, byte[] u, int uOff, byte[] r, int rOff)
@@ -205,61 +142,18 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
 
         public static void ScalarMultBase(byte[] k, int kOff, byte[] r, int rOff)
         {
-            Precompute();
-
-            uint[] n = new uint[8];     DecodeScalar(k, kOff, n);
-
-            int[] x0 = X25519Field.Create();
-            //int[] x1 = X25519Field.Create();        X25519Field.Copy(S_x, 0, x1, 0);
-            int[] x1 = X25519Field.Create();        x1[0] = 1;
-            int[] z1 = X25519Field.Create();        z1[0] = 1;        
-            int[] x2 = X25519Field.Create();        X25519Field.Copy(PsubS_x, 0, x2, 0);
-            int[] z2 = X25519Field.Create();        z2[0] = 1;        
-
-            int[] A = x1;
-            int[] B = z1;
-            int[] C = x0;
-            int[] D = A;
-            int[] E = B;
-
-            Debug.Assert(n[7] >> 30 == 1U);
-
-            int off = 0, bit = 3, swap = 1;
-            do
-            {
-                X25519Field.Copy(precompBase, off, x0, 0);
-                off += X25519Field.Size;
+            int[] y = X25519Field.Create();
+            int[] z = X25519Field.Create();
 
-                int word = bit >> 5, shift = bit & 0x1F;
-                int kt = (int)(n[word] >> shift) & 1;
-                swap ^= kt;
-                X25519Field.CSwap(swap, x1, x2);
-                X25519Field.CSwap(swap, z1, z2);
-                swap = kt;
-
-                X25519Field.Apm(x1, z1, A, B);
-                X25519Field.Mul(x0, B, C);
-                X25519Field.Carry(A);
-                X25519Field.Apm(A, C, D, E);
-                X25519Field.Sqr(D, D);
-                X25519Field.Sqr(E, E);
-                X25519Field.Mul(z2, D, x1);
-                X25519Field.Mul(x2, E, z1);
-            }
-            while (++bit < 255);
-
-            Debug.Assert(swap == 1);
+            Ed25519.ScalarMultBaseYZ(k, kOff, y, z);
 
-            for (int i = 0; i < 3; ++i)
-            {
-                PointDouble(x1, z1);
-            }
+            X25519Field.Apm(z, y, y, z);
 
-            X25519Field.Inv(z1, z1);
-            X25519Field.Mul(x1, z1, x1);
+            X25519Field.Inv(z, z);
+            X25519Field.Mul(y, z, y);
 
-            X25519Field.Normalize(x1);
-            X25519Field.Encode(x1, r, rOff);
+            X25519Field.Normalize(y);
+            X25519Field.Encode(y, r, rOff);
         }
     }
 }
diff --git a/crypto/src/math/ec/rfc7748/X448.cs b/crypto/src/math/ec/rfc7748/X448.cs
index 7ee0bdbd4..4f139f23d 100644
--- a/crypto/src/math/ec/rfc7748/X448.cs
+++ b/crypto/src/math/ec/rfc7748/X448.cs
@@ -1,6 +1,7 @@
 using System;
 using System.Diagnostics;
 
+using Org.BouncyCastle.Math.EC.Rfc8032;
 using Org.BouncyCastle.Security;
 using Org.BouncyCastle.Utilities;
 
@@ -14,18 +15,9 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
         private const uint C_A = 156326;
         private const uint C_A24 = (C_A + 2)/4;
 
-        // 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE
-        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 = { 0x099D2720U, 0x0B1197DCU, 0x09BAF8ACU, 0x033FF1C6U, 0x0B5123ACU,
-            0x0643ACE1U, 0x03F1BD65U, 0x084C1F82U, 0x0954459DU, 0x081B9672U, 0x0DD1031CU, 0x0EB7BDACU, 0x03881AFFU, 0x0423ACF0U,
-            0x05013244U, 0x0F0FAB72U };
-
-        private static readonly object precompLock = new object();
-        private static uint[] precompBase = null;
+        //private static readonly uint[] Sqrt156324 = { 0x0551B193U, 0x07A21E17U, 0x0E635AD3U, 0x00812ABBU, 0x025B3F99U, 0x01605224U,
+        //    0x0AF8CB32U, 0x0D2E7D68U, 0x06BA50FDU, 0x08E55693U, 0x0CB08EB4U, 0x02ABEBC1U, 0x051BA0BBU, 0x02F8812EU, 0x0829B611U,
+        //    0x0BA4D3A0U };
 
         public static bool CalculateAgreement(byte[] k, int kOff, byte[] u, int uOff, byte[] r, int rOff)
         {
@@ -85,68 +77,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
 
         public static void Precompute()
         {
-            lock (precompLock)
-            {
-                if (precompBase != null)
-                    return;
-
-                precompBase = new uint[X448Field.Size * 446];
-
-                uint[] xs = precompBase;
-                uint[] zs = new uint[X448Field.Size * 445];
-
-                uint[] x = X448Field.Create();     x[0] = 5;          
-                uint[] z = X448Field.Create();     z[0] = 1;
-
-                uint[] n = X448Field.Create();
-                uint[] d = X448Field.Create();
-
-                //X448Field.Apm(x, z, n, d);
-                X448Field.Add(x, z, n);
-                X448Field.Sub(x, z, d);
-
-                uint[] c = X448Field.Create();     X448Field.Copy(d, 0, c, 0);
-
-                int off = 0;
-                for (;;)
-                {
-                    X448Field.Copy(n, 0, xs, off);
-
-                    if (off == (X448Field.Size * 445))
-                        break;
-
-                    PointDouble(x, z);
-
-                    //X448Field.Apm(x, z, n, d);
-                    X448Field.Add(x, z, n);
-                    X448Field.Sub(x, z, d);
-                    X448Field.Mul(n, c, n);
-                    X448Field.Mul(c, d, c);
-
-                    X448Field.Copy(d, 0, zs, off);
-
-                    off += X448Field.Size;
-                }
-
-                uint[] u = X448Field.Create();
-                X448Field.Inv(c, u);
-
-                for (;;)
-                {
-                    X448Field.Copy(xs, off, x, 0);
-
-                    X448Field.Mul(x, u, x);
-                    //X448Field.Normalize(x);
-                    X448Field.Copy(x, 0, precompBase, off);
-
-                    if (off == 0)
-                        break;
-
-                    off -= X448Field.Size;
-                    X448Field.Copy(zs, off, z, 0);
-                    X448Field.Mul(u, z, u);
-                }
-            }
+            Ed448.Precompute();
         }
 
         public static void ScalarMult(byte[] k, int kOff, byte[] u, int uOff, byte[] r, int rOff)
@@ -219,64 +150,17 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
 
         public static void ScalarMultBase(byte[] k, int kOff, byte[] r, int rOff)
         {
-            Precompute();
+            uint[] x = X448Field.Create();
+            uint[] y = X448Field.Create();
 
-            uint[] n = new uint[14];    DecodeScalar(k, kOff, n);
-
-            uint[] x0 = X448Field.Create();
-            uint[] x1 = X448Field.Create();     X448Field.Copy(S_x, 0, x1, 0);
-            uint[] z1 = X448Field.Create();     z1[0] = 1;        
-            uint[] x2 = X448Field.Create();     X448Field.Copy(PsubS_x, 0, x2, 0);
-            uint[] z2 = X448Field.Create();     z2[0] = 1;
-
-            uint[] A = X448Field.Create();
-            uint[] B = z1;
-            uint[] C = x0;
-            uint[] D = x1;
-            uint[] E = B;
-
-            Debug.Assert(n[13] >> 31 == 1U);
-
-            int off = 0, bit = 2, swap = 1;
-            do
-            {
-                X448Field.Copy(precompBase, off, x0, 0);
-                off += X448Field.Size;
-
-                int word = bit >> 5, shift = bit & 0x1F;
-                int kt = (int)(n[word] >> shift) & 1;
-                swap ^= kt;
-                X448Field.CSwap(swap, x1, x2);
-                X448Field.CSwap(swap, z1, z2);
-                swap = kt;
-
-                //X448Field.Apm(x1, z1, A, B);
-                X448Field.Add(x1, z1, A);
-                X448Field.Sub(x1, z1, B);
-                X448Field.Mul(x0, B, C);
-                X448Field.Carry(A);
-                //X448Field.Apm(A, C, D, E);
-                X448Field.Add(A, C, D);
-                X448Field.Sub(A, C, E);
-                X448Field.Sqr(D, D);
-                X448Field.Sqr(E, E);
-                X448Field.Mul(z2, D, x1);
-                X448Field.Mul(x2, E, z1);
-            }
-            while (++bit < 448);
-
-            Debug.Assert(swap == 1);
-
-            for (int i = 0; i < 2; ++i)
-            {
-                PointDouble(x1, z1);
-            }
+            Ed448.ScalarMultBaseXY(k, kOff, x, y);
 
-            X448Field.Inv(z1, z1);
-            X448Field.Mul(x1, z1, x1);
+            X448Field.Inv(x, x);
+            X448Field.Mul(x, y, x);
+            X448Field.Sqr(x, x);
 
-            X448Field.Normalize(x1);
-            X448Field.Encode(x1, r, rOff);
+            X448Field.Normalize(x);
+            X448Field.Encode(x, r, rOff);
         }
     }
 }
diff --git a/crypto/src/math/ec/rfc8032/Ed25519.cs b/crypto/src/math/ec/rfc8032/Ed25519.cs
index b77853f30..6dc52a865 100644
--- a/crypto/src/math/ec/rfc8032/Ed25519.cs
+++ b/crypto/src/math/ec/rfc8032/Ed25519.cs
@@ -934,6 +934,17 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             EncodePoint(p, r, rOff);
         }
 
+        internal static void ScalarMultBaseYZ(byte[] k, int kOff, int[] y, int[] z)
+        {
+            byte[] n = new byte[ScalarBytes];
+            PruneScalar(k, kOff, n);
+
+            PointAccum p = new PointAccum();
+            ScalarMultBase(n, p);
+            X25519Field.Copy(p.y, 0, y, 0);
+            X25519Field.Copy(p.z, 0, z, 0);
+        }
+
         private static void ScalarMultStraussVar(uint[] nb, uint[] np, PointExt p, PointAccum r)
         {
             Precompute();
diff --git a/crypto/src/math/ec/rfc8032/Ed448.cs b/crypto/src/math/ec/rfc8032/Ed448.cs
index 38bdee83e..774052082 100644
--- a/crypto/src/math/ec/rfc8032/Ed448.cs
+++ b/crypto/src/math/ec/rfc8032/Ed448.cs
@@ -676,11 +676,11 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
 
         private static void PruneScalar(byte[] n, int nOff, byte[] r)
         {
-            Array.Copy(n, nOff, r, 0, ScalarBytes);
+            Array.Copy(n, nOff, r, 0, ScalarBytes - 1);
 
             r[0] &= 0xFC;
             r[ScalarBytes - 2] |= 0x80;
-            r[ScalarBytes - 1] &= 0x00;
+            r[ScalarBytes - 1]  = 0x00;
         }
 
         private static byte[] ReduceScalar(byte[] n)
@@ -1021,6 +1021,17 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
             EncodePoint(p, r, rOff);
         }
 
+        internal static void ScalarMultBaseXY(byte[] k, int kOff, uint[] x, uint[] y)
+        {
+            byte[] n = new byte[ScalarBytes];
+            PruneScalar(k, kOff, n);
+
+            PointExt p = new PointExt();
+            ScalarMultBase(n, p);
+            X448Field.Copy(p.x, 0, x, 0);
+            X448Field.Copy(p.y, 0, y, 0);
+        }
+
         private static void ScalarMultStraussVar(uint[] nb, uint[] np, PointExt p, PointExt r)
         {
             Precompute();