From 63aad6ee7166ab55decdbc9d3e3110e7b10ce216 Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Sun, 20 Nov 2022 01:53:05 +0700 Subject: Factor Wnaf out of EdDSA --- crypto/src/math/ec/rfc8032/Ed25519.cs | 133 +++++++--------------------------- crypto/src/math/ec/rfc8032/Ed448.cs | 130 +++++++-------------------------- crypto/src/math/ec/rfc8032/Wnaf.cs | 65 +++++++++++++++++ 3 files changed, 118 insertions(+), 210 deletions(-) create mode 100644 crypto/src/math/ec/rfc8032/Wnaf.cs diff --git a/crypto/src/math/ec/rfc8032/Ed25519.cs b/crypto/src/math/ec/rfc8032/Ed25519.cs index 2f2ea507d..502d5ed9c 100644 --- a/crypto/src/math/ec/rfc8032/Ed25519.cs +++ b/crypto/src/math/ec/rfc8032/Ed25519.cs @@ -530,61 +530,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 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[253]; - - 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(IDigest d, byte[] h, byte[] s, byte[] pk, int pkOff, byte[] ctx, byte phflag, byte[] m, int mOff, int mLen, byte[] sig, int sigOff) { @@ -1893,42 +1838,12 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 private static void ScalarMultOrderVar(ref PointAffine p, ref PointAccum r) { - sbyte[] ws_p = GetWnafVar(L, WnafWidth); - - int count = 1 << (WnafWidth - 2); - PointPrecompZ[] tp = new PointPrecompZ[count]; - Init(out PointTemp t); - PointPrecomputeZ(ref p, tp, count, ref t); - - PointSetNeutral(ref r); - - for (int bit = 252;;) - { - 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, ref t); - } - - if (--bit < 0) - break; - - PointDouble(ref r); - } - } - - private static void ScalarMultStrausVar(uint[] nb, uint[] np, ref PointAffine p, ref PointAccum r) - { #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER - ScalarMultStrausVar(nb.AsSpan(), np.AsSpan(), ref p, ref r); + Span ws_p = stackalloc sbyte[253]; #else - Precompute(); - - sbyte[] ws_b = GetWnafVar(nb, WnafWidthBase); - sbyte[] ws_p = GetWnafVar(np, WnafWidth); + sbyte[] ws_p = new sbyte[253]; +#endif + Wnaf.GetSignedVar(L, WnafWidth, ws_p); int count = 1 << (WnafWidth - 2); PointPrecompZ[] tp = new PointPrecompZ[count]; @@ -1939,20 +1854,11 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 for (int bit = 252;;) { - 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, ref t); - } - 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, ref t); } @@ -1962,17 +1868,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 nb, ReadOnlySpan np, ref PointAffine p, ref PointAccum r) +#else + private static void ScalarMultStrausVar(uint[] nb, uint[] np, ref PointAffine p, ref PointAccum 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 ws_b = stackalloc sbyte[253]; + Span ws_p = stackalloc sbyte[253]; +#else + sbyte[] ws_b = new sbyte[253]; + sbyte[] ws_p = new sbyte[253]; +#endif + + Wnaf.GetSignedVar(nb, WnafWidthBase, ws_b); + Wnaf.GetSignedVar(np, WnafWidth, ws_p); int count = 1 << (WnafWidth - 2); PointPrecompZ[] tp = new PointPrecompZ[count]; @@ -1981,13 +1903,13 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 PointSetNeutral(ref r); - for (int bit = 252; ;) + for (int bit = 252;;) { int wb = ws_b[bit]; 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, ref t); } @@ -1996,7 +1918,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, ref t); } @@ -2007,7 +1929,6 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 PointDouble(ref r); } } -#endif public static void Sign(byte[] sk, int skOff, byte[] m, int mOff, int mLen, byte[] sig, int sigOff) { 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 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 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 nb, ReadOnlySpan 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 ws_b = stackalloc sbyte[447]; + Span 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) { diff --git a/crypto/src/math/ec/rfc8032/Wnaf.cs b/crypto/src/math/ec/rfc8032/Wnaf.cs new file mode 100644 index 000000000..cc6e3704f --- /dev/null +++ b/crypto/src/math/ec/rfc8032/Wnaf.cs @@ -0,0 +1,65 @@ +using System; +using System.Diagnostics; + +using Org.BouncyCastle.Utilities; + +namespace Org.BouncyCastle.Math.EC.Rfc8032 +{ + internal static class Wnaf + { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + internal static void GetSignedVar(ReadOnlySpan n, int width, Span ws) +#else + internal static void GetSignedVar(uint[] n, int width, sbyte[] ws) +#endif + { + Debug.Assert(2 <= width && width <= 8); + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + Span t = n.Length <= 64 + ? stackalloc uint[n.Length * 2] + : new uint[n.Length * 2]; +#else + uint[] t = new uint[n.Length * 2]; +#endif + { + uint c = 0U - (n[n.Length - 1] >> 31); + int tPos = t.Length, i = n.Length; + while (--i >= 0) + { + uint next = n[i]; + t[--tPos] = (next >> 16) | (c << 16); + t[--tPos] = c = next; + } + } + + uint sign = 0U; + int j = 0, lead = 32 - width; + + for (int i = 0; i < t.Length; ++i, j -= 16) + { + uint word = t[i]; + while (j < 16) + { + uint word16 = word >> j; + + int skip = Integers.NumberOfTrailingZeros((int)((sign ^ word16) | 0xFFFF0000U)); + if (skip > 0) + { + j += skip; + continue; + } + + int digit = ((int)word16 | 1) << lead; + sign = (uint)(digit >> 31); + + ws[(i << 4) + j] = (sbyte)(digit >> lead); + + j += width; + } + } + + Debug.Assert(sign == n[n.Length - 1] >> 31); + } + } +} -- cgit 1.4.1