Factor Wnaf out of EdDSA

1 files changed, 26 insertions, 104 deletions

diff --git a/crypto/src/math/ec/rfc8032/Ed448.cs b/crypto/src/math/ec/rfc8032/Ed448.cs
index 4e1744d53..6d0bc5c7d 100644
--- a/crypto/src/math/ec/rfc8032/Ed448.cs
+++ b/crypto/src/math/ec/rfc8032/Ed448.cs
@@ -535,61 +535,6 @@ 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);
-
-            uint[] t = new uint[ScalarUints * 2];
-            {
-                uint c = 0;
-                int tPos = t.Length, i = ScalarUints;
-                while (--i >= 0)
-                {
-                    uint next = n[i];
-                    t[--tPos] = (next >> 16) | (c << 16);
-                    t[--tPos] = c = next;
-                }
-            }
-
-            sbyte[] ws = new sbyte[447];
-
-            int lead = 32 - width;
-
-            uint carry = 0U;
-            int j = 0;
-            for (int i = 0; i < t.Length; ++i, j -= 16)
-            {
-                uint word = t[i];
-                while (j < 16)
-                {
-                    uint word16 = word >> j;
-                    uint bit = word16 & 1U;
-
-                    if (bit == carry)
-                    {
-                        ++j;
-                        continue;
-                    }
-
-                    uint digit = (word16 | 1U) << lead;
-                    carry = digit >> 31;
-
-                    ws[(i << 4) + j] = (sbyte)((int)digit >> lead);
-
-                    j += width;
-                }
-            }
-
-            Debug.Assert(carry == 0);
-
-            return ws;
-        }
-
         private static void ImplSign(IXof d, byte[] h, byte[] s, byte[] pk, int pkOff, byte[] ctx, byte phflag,
             byte[] m, int mOff, int mLen, byte[] sig, int sigOff)
         {
@@ -2072,41 +2017,12 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
 
         private static void ScalarMultOrderVar(ref PointProjective p, ref PointProjective r)
         {
-            sbyte[] ws_p = GetWnafVar(L, WnafWidth);
-
-            int count = 1 << (WnafWidth - 2);
-            PointProjective[] tp = new PointProjective[count];
-            PointPrecomputeVar(ref p, tp, 0, count);
-
-            PointSetNeutral(ref r);
-
-            for (int bit = 446;;)
-            {
-                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);
-                }
-
-                if (--bit < 0)
-                    break;
-
-                PointDouble(ref r);
-            }
-        }
-
-        private static void ScalarMultStrausVar(uint[] nb, uint[] np, ref PointProjective p, ref PointProjective r)
-        {
 #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
-            ScalarMultStrausVar(nb.AsSpan(), np.AsSpan(), ref p, ref r);
+            Span<sbyte> ws_p = stackalloc sbyte[447];
 #else
-            Precompute();
-
-            sbyte[] ws_b = GetWnafVar(nb, WnafWidthBase);
-            sbyte[] ws_p = GetWnafVar(np, WnafWidth);
+            sbyte[] ws_p = new sbyte[447];
+#endif
+            Wnaf.GetSignedVar(L, WnafWidth, ws_p);
 
             int count = 1 << (WnafWidth - 2);
             PointProjective[] tp = new PointProjective[count];
@@ -2116,20 +2032,11 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
 
             for (int bit = 446;;)
             {
-                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);
-                }
-
                 int wp = ws_p[bit];
                 if (wp != 0)
                 {
                     int sign = wp >> 31;
-                    int index = (wp ^ sign) >> 1;
+                    int index = (wp >> 1) ^ sign;
 
                     PointAddVar(sign != 0, ref tp[index], ref r);
                 }
@@ -2139,17 +2046,33 @@ 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 PointProjective p,
             ref PointProjective r)
+#else
+        private static void ScalarMultStrausVar(uint[] nb, uint[] np, ref PointProjective p, ref PointProjective r)
+#endif
         {
+            Debug.Assert(nb.Length == ScalarUints);
+            Debug.Assert(nb[ScalarUints - 1] <= L[ScalarUints - 1]);
+
+            Debug.Assert(np.Length == ScalarUints);
+            Debug.Assert(np[ScalarUints - 1] <= L[ScalarUints - 1]);
+
             Precompute();
 
-            sbyte[] ws_b = GetWnafVar(nb, WnafWidthBase);
-            sbyte[] ws_p = GetWnafVar(np, WnafWidth);
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+            Span<sbyte> ws_b = stackalloc sbyte[447];
+            Span<sbyte> ws_p = stackalloc sbyte[447];
+#else
+            sbyte[] ws_b = new sbyte[447];
+            sbyte[] ws_p = new sbyte[447];
+#endif
+
+            Wnaf.GetSignedVar(nb, WnafWidthBase, ws_b);
+            Wnaf.GetSignedVar(np, WnafWidth, ws_p);
 
             int count = 1 << (WnafWidth - 2);
             PointProjective[] tp = new PointProjective[count];
@@ -2163,7 +2086,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
                 if (wb != 0)
                 {
                     int sign = wb >> 31;
-                    int index = (wb ^ sign) >> 1;
+                    int index = (wb >> 1) ^ sign;
 
                     PointAddVar(sign != 0, ref PrecompBaseWnaf[index], ref r);
                 }
@@ -2172,7 +2095,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
                 if (wp != 0)
                 {
                     int sign = wp >> 31;
-                    int index = (wp ^ sign) >> 1;
+                    int index = (wp >> 1) ^ sign;
 
                     PointAddVar(sign != 0, ref tp[index], ref r);
                 }
@@ -2183,7 +2106,6 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032
                 PointDouble(ref r);
             }
         }
-#endif
 
         public static void Sign(byte[] sk, int skOff, byte[] ctx, byte[] m, int mOff, int mLen, byte[] sig, int sigOff)
         {