diff options
Diffstat (limited to 'crypto/src/math/ec')
| -rw-r--r-- | crypto/src/math/ec/ECCurve.cs | 18 | ||||
| -rw-r--r-- | crypto/src/math/ec/rfc8032/Scalar25519.cs | 26 | ||||
| -rw-r--r-- | crypto/src/math/ec/rfc8032/Scalar448.cs | 26 | ||||
| -rw-r--r-- | crypto/src/math/ec/rfc8032/ScalarUtilities.cs | 216 |
4 files changed, 217 insertions, 69 deletions
diff --git a/crypto/src/math/ec/ECCurve.cs b/crypto/src/math/ec/ECCurve.cs index 245ca1941..ae0d5d69e 100644 --- a/crypto/src/math/ec/ECCurve.cs +++ b/crypto/src/math/ec/ECCurve.cs @@ -607,6 +607,13 @@ namespace Org.BouncyCastle.Math.EC } #endif + internal static int ImplGetInteger(string envVariable, int defaultValue) + { + string property = Platform.GetEnvironmentVariable(envVariable); + + return int.TryParse(property, out int value) ? value : defaultValue; + } + private class DefaultLookupTable : AbstractECLookupTable { @@ -757,13 +764,6 @@ namespace Org.BouncyCastle.Math.EC throw new ArgumentException("Fp q value not prime"); } - private static int ImplGetInteger(string envVariable, int defaultValue) - { - string property = Platform.GetEnvironmentVariable(envVariable); - - return int.TryParse(property, out int value) ? value : defaultValue; - } - private static int ImplGetIterations(int bits, int certainty) { /* @@ -966,6 +966,10 @@ namespace Org.BouncyCastle.Math.EC private static IFiniteField BuildField(int m, int k1, int k2, int k3) { + int maxM = ImplGetInteger("Org.BouncyCastle.EC.F2m_MaxSize", 1142); // 2 * 571 + if (m > maxM) + throw new ArgumentException("F2m m value out of range"); + int[] exponents = (k2 | k3) == 0 ? new int[]{ 0, k1, m } : new int[]{ 0, k1, k2, k3, m }; diff --git a/crypto/src/math/ec/rfc8032/Scalar25519.cs b/crypto/src/math/ec/rfc8032/Scalar25519.cs index 67eee6155..08ab80607 100644 --- a/crypto/src/math/ec/rfc8032/Scalar25519.cs +++ b/crypto/src/math/ec/rfc8032/Scalar25519.cs @@ -595,7 +595,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 #endif #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER - internal static void ReduceBasisVar(ReadOnlySpan<uint> k, Span<uint> z0, Span<uint> z1) + internal static bool ReduceBasisVar(ReadOnlySpan<uint> k, Span<uint> z0, Span<uint> z1) { /* * Split scalar k into two half-size scalars z0 and z1, such that z1 * k == z0 mod L. @@ -606,28 +606,34 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 Span<uint> Nu = stackalloc uint[16]; LSq.CopyTo(Nu); Span<uint> Nv = stackalloc uint[16]; Nat256.Square(k, Nv); ++Nv[0]; Span<uint> p = stackalloc uint[16]; Nat256.Mul(L, k, p); + Span<uint> t = stackalloc uint[16]; Span<uint> u0 = stackalloc uint[4]; u0.CopyFrom(L); Span<uint> u1 = stackalloc uint[4]; Span<uint> v0 = stackalloc uint[4]; v0.CopyFrom(k); Span<uint> v1 = stackalloc uint[4]; v1[0] = 1U; + // Conservative upper bound on the number of loop iterations needed + int iterations = TargetLength * 4; int last = 15; int len_Nv = ScalarUtilities.GetBitLengthPositive(last, Nv); while (len_Nv > TargetLength) { + if (--iterations < 0) + return false; + int len_p = ScalarUtilities.GetBitLength(last, p); int s = len_p - len_Nv; s &= ~(s >> 31); if ((int)p[last] < 0) { - ScalarUtilities.AddShifted_NP(last, s, Nu, Nv, p); + ScalarUtilities.AddShifted_NP(last, s, Nu, Nv, p, t); ScalarUtilities.AddShifted_UV(last: 3, s, u0, u1, v0, v1); } else { - ScalarUtilities.SubShifted_NP(last, s, Nu, Nv, p); + ScalarUtilities.SubShifted_NP(last, s, Nu, Nv, p, t); ScalarUtilities.SubShifted_UV(last: 3, s, u0, u1, v0, v1); } @@ -645,9 +651,10 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 // v1 * k == v0 mod L v0.CopyTo(z0); v1.CopyTo(z1); + return true; } #else - internal static void ReduceBasisVar(uint[] k, uint[] z0, uint[] z1) + internal static bool ReduceBasisVar(uint[] k, uint[] z0, uint[] z1) { /* * Split scalar k into two half-size scalars z0 and z1, such that z1 * k == z0 mod L. @@ -658,28 +665,34 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 uint[] Nu = new uint[16]; Array.Copy(LSq, Nu, 16); uint[] Nv = new uint[16]; Nat256.Square(k, Nv); ++Nv[0]; uint[] p = new uint[16]; Nat256.Mul(L, k, p); + uint[] t = new uint[16]; uint[] u0 = new uint[4]; Array.Copy(L, u0, 4); uint[] u1 = new uint[4]; uint[] v0 = new uint[4]; Array.Copy(k, v0, 4); uint[] v1 = new uint[4]; v1[0] = 1U; + // Conservative upper bound on the number of loop iterations needed + int iterations = TargetLength * 4; int last = 15; int len_Nv = ScalarUtilities.GetBitLengthPositive(last, Nv); while (len_Nv > TargetLength) { + if (--iterations < 0) + return false; + int len_p = ScalarUtilities.GetBitLength(last, p); int s = len_p - len_Nv; s &= ~(s >> 31); if ((int)p[last] < 0) { - ScalarUtilities.AddShifted_NP(last, s, Nu, Nv, p); + ScalarUtilities.AddShifted_NP(last, s, Nu, Nv, p, t); ScalarUtilities.AddShifted_UV(last: 3, s, u0, u1, v0, v1); } else { - ScalarUtilities.SubShifted_NP(last, s, Nu, Nv, p); + ScalarUtilities.SubShifted_NP(last, s, Nu, Nv, p, t); ScalarUtilities.SubShifted_UV(last: 3, s, u0, u1, v0, v1); } @@ -697,6 +710,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 // v1 * k == v0 mod L Array.Copy(v0, z0, 4); Array.Copy(v1, z1, 4); + return true; } #endif diff --git a/crypto/src/math/ec/rfc8032/Scalar448.cs b/crypto/src/math/ec/rfc8032/Scalar448.cs index 124b91250..c3f91eef2 100644 --- a/crypto/src/math/ec/rfc8032/Scalar448.cs +++ b/crypto/src/math/ec/rfc8032/Scalar448.cs @@ -1114,7 +1114,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 #endif #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER - internal static void ReduceBasisVar(ReadOnlySpan<uint> k, Span<uint> z0, Span<uint> z1) + internal static bool ReduceBasisVar(ReadOnlySpan<uint> k, Span<uint> z0, Span<uint> z1) { /* * Split scalar k into two half-size scalars z0 and z1, such that z1 * k == z0 mod L. @@ -1125,28 +1125,34 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 Span<uint> Nu = stackalloc uint[28]; LSq.CopyTo(Nu); Span<uint> Nv = stackalloc uint[28]; Nat448.Square(k, Nv); ++Nv[0]; Span<uint> p = stackalloc uint[28]; Nat448.Mul(L, k, p); + Span<uint> t = stackalloc uint[28]; Span<uint> u0 = stackalloc uint[8]; u0.CopyFrom(L); Span<uint> u1 = stackalloc uint[8]; Span<uint> v0 = stackalloc uint[8]; v0.CopyFrom(k); Span<uint> v1 = stackalloc uint[8]; v1[0] = 1U; + // Conservative upper bound on the number of loop iterations needed + int iterations = TargetLength * 4; int last = 27; int len_Nv = ScalarUtilities.GetBitLengthPositive(last, Nv); while (len_Nv > TargetLength) { + if (--iterations < 0) + return false; + int len_p = ScalarUtilities.GetBitLength(last, p); int s = len_p - len_Nv; s &= ~(s >> 31); if ((int)p[last] < 0) { - ScalarUtilities.AddShifted_NP(last, s, Nu, Nv, p); + ScalarUtilities.AddShifted_NP(last, s, Nu, Nv, p, t); ScalarUtilities.AddShifted_UV(last: 7, s, u0, u1, v0, v1); } else { - ScalarUtilities.SubShifted_NP(last, s, Nu, Nv, p); + ScalarUtilities.SubShifted_NP(last, s, Nu, Nv, p, t); ScalarUtilities.SubShifted_UV(last: 7, s, u0, u1, v0, v1); } @@ -1167,9 +1173,10 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 // v1 * k == v0 mod L v0.CopyTo(z0); v1.CopyTo(z1); + return true; } #else - internal static void ReduceBasisVar(uint[] k, uint[] z0, uint[] z1) + internal static bool ReduceBasisVar(uint[] k, uint[] z0, uint[] z1) { /* * Split scalar k into two half-size scalars z0 and z1, such that z1 * k == z0 mod L. @@ -1180,28 +1187,34 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 uint[] Nu = new uint[28]; Array.Copy(LSq, Nu, 28); uint[] Nv = new uint[28]; Nat448.Square(k, Nv); ++Nv[0]; uint[] p = new uint[28]; Nat448.Mul(L, k, p); + uint[] t = new uint[28]; uint[] u0 = new uint[8]; Array.Copy(L, u0, 8); uint[] u1 = new uint[8]; uint[] v0 = new uint[8]; Array.Copy(k, v0, 8); uint[] v1 = new uint[8]; v1[0] = 1U; + // Conservative upper bound on the number of loop iterations needed + int iterations = TargetLength * 4; int last = 27; int len_Nv = ScalarUtilities.GetBitLengthPositive(last, Nv); while (len_Nv > TargetLength) { + if (--iterations < 0) + return false; + int len_p = ScalarUtilities.GetBitLength(last, p); int s = len_p - len_Nv; s &= ~(s >> 31); if ((int)p[last] < 0) { - ScalarUtilities.AddShifted_NP(last, s, Nu, Nv, p); + ScalarUtilities.AddShifted_NP(last, s, Nu, Nv, p, t); ScalarUtilities.AddShifted_UV(last: 7, s, u0, u1, v0, v1); } else { - ScalarUtilities.SubShifted_NP(last, s, Nu, Nv, p); + ScalarUtilities.SubShifted_NP(last, s, Nu, Nv, p, t); ScalarUtilities.SubShifted_UV(last: 7, s, u0, u1, v0, v1); } @@ -1222,6 +1235,7 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 // v1 * k == v0 mod L Array.Copy(v0, z0, 8); Array.Copy(v1, z1, 8); + return true; } #endif diff --git a/crypto/src/math/ec/rfc8032/ScalarUtilities.cs b/crypto/src/math/ec/rfc8032/ScalarUtilities.cs index c70a4f2e8..41d7f2696 100644 --- a/crypto/src/math/ec/rfc8032/ScalarUtilities.cs +++ b/crypto/src/math/ec/rfc8032/ScalarUtilities.cs @@ -12,62 +12,120 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 { #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER [MethodImpl(MethodImplOptions.AggressiveInlining)] - internal static void AddShifted_NP(int last, int s, Span<uint> Nu, ReadOnlySpan<uint> Nv, Span<uint> _p) + internal static void AddShifted_NP(int last, int s, Span<uint> Nu, ReadOnlySpan<uint> Nv, Span<uint> p, Span<uint> t) #else - internal static void AddShifted_NP(int last, int s, uint[] Nu, uint[] Nv, uint[] _p) + internal static void AddShifted_NP(int last, int s, uint[] Nu, uint[] Nv, uint[] p, uint[] t) #endif { - int sWords = s >> 5, sBits = s & 31; - - ulong cc__p = 0UL; + ulong cc_p = 0UL; ulong cc_Nu = 0UL; - if (sBits == 0) + if (s == 0) { - for (int i = sWords; i <= last; ++i) + for (int i = 0; i <= last; ++i) { + uint p_i = p[i]; + cc_Nu += Nu[i]; - cc_Nu += _p[i - sWords]; + cc_Nu += p_i; - cc__p += _p[i]; - cc__p += Nv[i - sWords]; - _p[i] = (uint)cc__p; cc__p >>= 32; + cc_p += p_i; + cc_p += Nv[i]; + p_i = (uint)cc_p; cc_p >>= 32; + p[i] = p_i; - cc_Nu += _p[i - sWords]; + cc_Nu += p_i; Nu[i] = (uint)cc_Nu; cc_Nu >>= 32; } } - else + else if (s < 32) { uint prev_p = 0U; uint prev_q = 0U; uint prev_v = 0U; - for (int i = sWords; i <= last; ++i) + for (int i = 0; i <= last; ++i) { - uint next_p = _p[i - sWords]; - uint p_s = (next_p << sBits) | (prev_p >> -sBits); - prev_p = next_p; + uint p_i = p[i]; + uint p_s = (p_i << s) | (prev_p >> -s); + prev_p = p_i; cc_Nu += Nu[i]; cc_Nu += p_s; - uint next_v = Nv[i - sWords]; - uint v_s = (next_v << sBits) | (prev_v >> -sBits); + uint next_v = Nv[i]; + uint v_s = (next_v << s) | (prev_v >> -s); prev_v = next_v; - cc__p += _p[i]; - cc__p += v_s; - _p[i] = (uint)cc__p; cc__p >>= 32; + cc_p += p_i; + cc_p += v_s; + p_i = (uint)cc_p; cc_p >>= 32; + p[i] = p_i; - uint next_q = _p[i - sWords]; - uint q_s = (next_q << sBits) | (prev_q >> -sBits); - prev_q = next_q; + uint q_s = (p_i << s) | (prev_q >> -s); + prev_q = p_i; cc_Nu += q_s; Nu[i] = (uint)cc_Nu; cc_Nu >>= 32; } } + else + { + // Copy the low limbs of the original p +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + t[..last].CopyFrom(p); +#else + Array.Copy(p, 0, t, 0, last); +#endif + + int sWords = s >> 5, sBits = s & 31; + if (sBits == 0) + { + for (int i = sWords; i <= last; ++i) + { + cc_Nu += Nu[i]; + cc_Nu += t[i - sWords]; + + cc_p += p[i]; + cc_p += Nv[i - sWords]; + p[i] = (uint)cc_p; cc_p >>= 32; + + cc_Nu += p[i - sWords]; + Nu[i] = (uint)cc_Nu; cc_Nu >>= 32; + } + } + else + { + uint prev_t = 0U; + uint prev_q = 0U; + uint prev_v = 0U; + + for (int i = sWords; i <= last; ++i) + { + uint next_t = t[i - sWords]; + uint t_s = (next_t << sBits) | (prev_t >> -sBits); + prev_t = next_t; + + cc_Nu += Nu[i]; + cc_Nu += t_s; + + uint next_v = Nv[i - sWords]; + uint v_s = (next_v << sBits) | (prev_v >> -sBits); + prev_v = next_v; + + cc_p += p[i]; + cc_p += v_s; + p[i] = (uint)cc_p; cc_p >>= 32; + + uint next_q = p[i - sWords]; + uint q_s = (next_q << sBits) | (prev_q >> -sBits); + prev_q = next_q; + + cc_Nu += q_s; + Nu[i] = (uint)cc_Nu; cc_Nu >>= 32; + } + } + } } #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER @@ -171,62 +229,120 @@ namespace Org.BouncyCastle.Math.EC.Rfc8032 #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER [MethodImpl(MethodImplOptions.AggressiveInlining)] - internal static void SubShifted_NP(int last, int s, Span<uint> Nu, ReadOnlySpan<uint> Nv, Span<uint> _p) + internal static void SubShifted_NP(int last, int s, Span<uint> Nu, ReadOnlySpan<uint> Nv, Span<uint> p, Span<uint> t) #else - internal static void SubShifted_NP(int last, int s, uint[] Nu, uint[] Nv, uint[] _p) + internal static void SubShifted_NP(int last, int s, uint[] Nu, uint[] Nv, uint[] p, uint[] t) #endif { - int sWords = s >> 5, sBits = s & 31; - - long cc__p = 0L; + long cc_p = 0L; long cc_Nu = 0L; - if (sBits == 0) + if (s == 0) { - for (int i = sWords; i <= last; ++i) + for (int i = 0; i <= last; ++i) { + uint p_i = p[i]; + cc_Nu += Nu[i]; - cc_Nu -= _p[i - sWords]; + cc_Nu -= p_i; - cc__p += _p[i]; - cc__p -= Nv[i - sWords]; - _p[i] = (uint)cc__p; cc__p >>= 32; + cc_p += p_i; + cc_p -= Nv[i]; + p_i = (uint)cc_p; cc_p >>= 32; + p[i] = p_i; - cc_Nu -= _p[i - sWords]; + cc_Nu -= p_i; Nu[i] = (uint)cc_Nu; cc_Nu >>= 32; } } - else + else if (s < 32) { uint prev_p = 0U; uint prev_q = 0U; uint prev_v = 0U; - for (int i = sWords; i <= last; ++i) + for (int i = 0; i <= last; ++i) { - uint next_p = _p[i - sWords]; - uint p_s = (next_p << sBits) | (prev_p >> -sBits); - prev_p = next_p; + uint p_i = p[i]; + uint p_s = (p_i << s) | (prev_p >> -s); + prev_p = p_i; cc_Nu += Nu[i]; cc_Nu -= p_s; - uint next_v = Nv[i - sWords]; - uint v_s = (next_v << sBits) | (prev_v >> -sBits); + uint next_v = Nv[i]; + uint v_s = (next_v << s) | (prev_v >> -s); prev_v = next_v; - cc__p += _p[i]; - cc__p -= v_s; - _p[i] = (uint)cc__p; cc__p >>= 32; + cc_p += p_i; + cc_p -= v_s; + p_i = (uint)cc_p; cc_p >>= 32; + p[i] = p_i; - uint next_q = _p[i - sWords]; - uint q_s = (next_q << sBits) | (prev_q >> -sBits); - prev_q = next_q; + uint q_s = (p_i << s) | (prev_q >> -s); + prev_q = p_i; cc_Nu -= q_s; Nu[i] = (uint)cc_Nu; cc_Nu >>= 32; } } + else + { + // Copy the low limbs of the original p +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + t[..last].CopyFrom(p); +#else + Array.Copy(p, 0, t, 0, last); +#endif + + int sWords = s >> 5, sBits = s & 31; + if (sBits == 0) + { + for (int i = sWords; i <= last; ++i) + { + cc_Nu += Nu[i]; + cc_Nu -= t[i - sWords]; + + cc_p += p[i]; + cc_p -= Nv[i - sWords]; + p[i] = (uint)cc_p; cc_p >>= 32; + + cc_Nu -= p[i - sWords]; + Nu[i] = (uint)cc_Nu; cc_Nu >>= 32; + } + } + else + { + uint prev_t = 0U; + uint prev_q = 0U; + uint prev_v = 0U; + + for (int i = sWords; i <= last; ++i) + { + uint next_t = t[i - sWords]; + uint t_s = (next_t << sBits) | (prev_t >> -sBits); + prev_t = next_t; + + cc_Nu += Nu[i]; + cc_Nu -= t_s; + + uint next_v = Nv[i - sWords]; + uint v_s = (next_v << sBits) | (prev_v >> -sBits); + prev_v = next_v; + + cc_p += p[i]; + cc_p -= v_s; + p[i] = (uint)cc_p; cc_p >>= 32; + + uint next_q = p[i - sWords]; + uint q_s = (next_q << sBits) | (prev_q >> -sBits); + prev_q = next_q; + + cc_Nu -= q_s; + Nu[i] = (uint)cc_Nu; cc_Nu >>= 32; + } + } + } } #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER |