diff options
| -rw-r--r-- | crypto/src/math/raw/Mod.cs | 318 | ||||
| -rw-r--r-- | crypto/src/math/raw/Nat.cs | 29 |
2 files changed, 342 insertions, 5 deletions
diff --git a/crypto/src/math/raw/Mod.cs b/crypto/src/math/raw/Mod.cs index d4d1f716d..8d08e144d 100644 --- a/crypto/src/math/raw/Mod.cs +++ b/crypto/src/math/raw/Mod.cs @@ -25,12 +25,28 @@ namespace Org.BouncyCastle.Math.Raw throw new ArithmeticException("Inverse does not exist."); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void CheckedModOddInverse(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x, Span<uint> z) + { + if (0 == ModOddInverse(m, x, z)) + throw new ArithmeticException("Inverse does not exist."); + } +#endif + public static void CheckedModOddInverseVar(uint[] m, uint[] x, uint[] z) { if (!ModOddInverseVar(m, x, z)) throw new ArithmeticException("Inverse does not exist."); } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void CheckedModOddInverseVar(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x, Span<uint> z) + { + if (!ModOddInverseVar(m, x, z)) + throw new ArithmeticException("Inverse does not exist."); + } +#endif + public static uint Inverse32(uint d) { Debug.Assert((d & 1) == 1); @@ -41,12 +57,15 @@ namespace Org.BouncyCastle.Math.Raw x *= 2 - d * x; // d.x == 1 mod 2**12 x *= 2 - d * x; // d.x == 1 mod 2**24 x *= 2 - d * x; // d.x == 1 mod 2**48 - Debug.Assert(d * x == 1); + Debug.Assert(d * x == 1U); return x; } public static uint ModOddInverse(uint[] m, uint[] x, uint[] z) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + return ModOddInverse(m.AsSpan(), x.AsSpan(), z.AsSpan()); +#else int len32 = m.Length; Debug.Assert(len32 > 0); Debug.Assert((m[0] & 1) != 0); @@ -89,13 +108,77 @@ namespace Org.BouncyCastle.Math.Raw CNormalize30(len30, signF, D, M); Decode30(bits, D, 0, z, 0); - Debug.Assert(0 != Nat.LessThan(len32, z, m)); + Debug.Assert(0 != Nat.LessThan(m.Length, z, m)); return (uint)(EqualTo(len30, F, 1) & EqualToZero(len30, G)); +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static uint ModOddInverse(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x, Span<uint> z) + { + int len32 = m.Length; + Debug.Assert(len32 > 0); + Debug.Assert((m[0] & 1) != 0); + Debug.Assert(m[len32 - 1] != 0); + + int bits = (len32 << 5) - Integers.NumberOfLeadingZeros((int)m[len32 - 1]); + int len30 = (bits + 29) / 30; + + if (len30 <= 50) + return ImplModOddInverse(m, x, z, bits, len30, stackalloc int[len30 * 5]); + + return ImplModOddInverse(m, x, z, bits, len30, new int[len30 * 5]); } + private static uint ImplModOddInverse(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x, Span<uint> z, int bits, + int len30, Span<int> alloc) + { + Span<int> t = stackalloc int[4]; + Span<int> D = alloc[..len30]; alloc = alloc[len30..]; + Span<int> E = alloc[..len30]; alloc = alloc[len30..]; + Span<int> F = alloc[..len30]; alloc = alloc[len30..]; + Span<int> G = alloc[..len30]; alloc = alloc[len30..]; + Span<int> M = alloc[..len30]; + + E[0] = 1; + Encode30(bits, x, G); + Encode30(bits, m, M); + M.CopyTo(F); + + int delta = 0; + int m0Inv32 = (int)Inverse32((uint)M[0]); + int maxDivsteps = GetMaximumDivsteps(bits); + + for (int divSteps = 0; divSteps < maxDivsteps; divSteps += 30) + { + delta = Divsteps30(delta, F[0], G[0], t); + UpdateDE30(len30, D, E, t, m0Inv32, M); + UpdateFG30(len30, F, G, t); + } + + int signF = F[len30 - 1] >> 31; + CNegate30(len30, signF, F); + + /* + * D is in the range (-2.M, M). First, conditionally add M if D is negative, to bring it + * into the range (-M, M). Then normalize by conditionally negating (according to signF) + * and/or then adding M, to bring it into the range [0, M). + */ + CNormalize30(len30, signF, D, M); + + Decode30(bits, D, z); + Debug.Assert(0 != Nat.LessThan(m.Length, z, m)); + + return (uint)(EqualTo(len30, F, 1) & EqualToZero(len30, G)); + } +#endif + public static bool ModOddInverseVar(uint[] m, uint[] x, uint[] z) { +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + return ModOddInverseVar(m.AsSpan(), x.AsSpan(), z.AsSpan()); +#else int len32 = m.Length; Debug.Assert(len32 > 0); Debug.Assert((m[0] & 1) != 0); @@ -178,11 +261,112 @@ namespace Org.BouncyCastle.Math.Raw Debug.Assert(0 == signD); Decode30(bits, D, 0, z, 0); - Debug.Assert(!Nat.Gte(len32, z, m)); + Debug.Assert(!Nat.Gte(m.Length, z, m)); return true; +#endif + } + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static bool ModOddInverseVar(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x, Span<uint> z) + { + int len32 = m.Length; + Debug.Assert(len32 > 0); + Debug.Assert((m[0] & 1) != 0); + Debug.Assert(m[len32 - 1] != 0); + + int bits = (len32 << 5) - Integers.NumberOfLeadingZeros((int)m[len32 - 1]); + int len30 = (bits + 29) / 30; + + if (len30 <= 50) + return ImplModOddInverseVar(m, x, z, bits, len30, stackalloc int[len30 * 5]); + + return ImplModOddInverseVar(m, x, z, bits, len30, new int[len30 * 5]); } + private static bool ImplModOddInverseVar(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x, Span<uint> z, int bits, + int len30, Span<int> alloc) + { + Span<int> t = stackalloc int[4]; + Span<int> D = alloc[..len30]; alloc = alloc[len30..]; + Span<int> E = alloc[..len30]; alloc = alloc[len30..]; + Span<int> F = alloc[..len30]; alloc = alloc[len30..]; + Span<int> G = alloc[..len30]; alloc = alloc[len30..]; + Span<int> M = alloc[..len30]; + + E[0] = 1; + Encode30(bits, x, G); + Encode30(bits, m, M); + M.CopyTo(F); + + int clzG = Integers.NumberOfLeadingZeros(G[len30 - 1] | 1) - (len30 * 30 + 2 - bits); + int eta = -1 - clzG; + int lenDE = len30, lenFG = len30; + int m0Inv32 = (int)Inverse32((uint)M[0]); + int maxDivsteps = GetMaximumDivsteps(bits); + + int divsteps = 0; + while (!IsZero(lenFG, G)) + { + if (divsteps >= maxDivsteps) + return false; + + divsteps += 30; + + eta = Divsteps30Var(eta, F[0], G[0], t); + UpdateDE30(lenDE, D, E, t, m0Inv32, M); + UpdateFG30(lenFG, F, G, t); + + int fn = F[lenFG - 1]; + int gn = G[lenFG - 1]; + + int cond = (lenFG - 2) >> 31; + cond |= fn ^ (fn >> 31); + cond |= gn ^ (gn >> 31); + + if (cond == 0) + { + F[lenFG - 2] |= fn << 30; + G[lenFG - 2] |= gn << 30; + --lenFG; + } + } + + int signF = F[lenFG - 1] >> 31; + + /* + * D is in the range (-2.M, M). First, conditionally add M if D is negative, to bring it + * into the range (-M, M). Then normalize by conditionally negating (according to signF) + * and/or then adding M, to bring it into the range [0, M). + */ + int signD = D[lenDE - 1] >> 31; + if (signD < 0) + { + signD = Add30(lenDE, D, M); + } + if (signF < 0) + { + signD = Negate30(lenDE, D); + signF = Negate30(lenFG, F); + } + Debug.Assert(0 == signF); + + if (!IsOne(lenFG, F)) + return false; + + if (signD < 0) + { + signD = Add30(lenDE, D, M); + } + Debug.Assert(0 == signD); + + Decode30(bits, D, z); + Debug.Assert(!Nat.Gte(m.Length, z, m)); + + return true; + } +#endif + public static uint[] Random(uint[] p) { int len = p.Length; @@ -195,9 +379,9 @@ namespace Org.BouncyCastle.Math.Raw m |= m >> 8; m |= m >> 16; + byte[] bytes = new byte[len << 2]; do { - byte[] bytes = new byte[len << 2]; RandomSource.NextBytes(bytes); Pack.BE_To_UInt32(bytes, 0, s); s[len - 1] &= m; @@ -207,7 +391,38 @@ namespace Org.BouncyCastle.Math.Raw return s; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static void Random(ReadOnlySpan<uint> p, Span<uint> z) + { + int len = p.Length; + if (z.Length < len) + throw new ArgumentException("insufficient space", nameof(z)); + + var s = z[..len]; + + uint m = p[len - 1]; + m |= m >> 1; + m |= m >> 2; + m |= m >> 4; + m |= m >> 8; + m |= m >> 16; + + Span<byte> bytes = stackalloc byte[len << 2]; + do + { + RandomSource.NextBytes(bytes); + Pack.BE_To_UInt32(bytes, s); + s[len - 1] &= m; + } + while (Nat.Gte(len, s, p)); + } +#endif + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static int Add30(int len30, Span<int> D, ReadOnlySpan<int> M) +#else private static int Add30(int len30, int[] D, int[] M) +#endif { Debug.Assert(len30 > 0); Debug.Assert(D.Length >= len30); @@ -224,7 +439,11 @@ namespace Org.BouncyCastle.Math.Raw return c; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void CNegate30(int len30, int cond, Span<int> D) +#else private static void CNegate30(int len30, int cond, int[] D) +#endif { Debug.Assert(len30 > 0); Debug.Assert(D.Length >= len30); @@ -239,7 +458,11 @@ namespace Org.BouncyCastle.Math.Raw D[last] = c; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void CNormalize30(int len30, int condNegate, Span<int> D, ReadOnlySpan<int> M) +#else private static void CNormalize30(int len30, int condNegate, int[] D, int[] M) +#endif { Debug.Assert(len30 > 0); Debug.Assert(D.Length >= len30); @@ -277,6 +500,29 @@ namespace Org.BouncyCastle.Math.Raw } } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void Decode30(int bits, ReadOnlySpan<int> x, Span<uint> z) + { + Debug.Assert(bits > 0); + + int avail = 0; + ulong data = 0L; + + int xOff = 0, zOff = 0; + while (bits > 0) + { + while (avail < System.Math.Min(32, bits)) + { + data |= (ulong)x[xOff++] << avail; + avail += 30; + } + + z[zOff++] = (uint)data; data >>= 32; + avail -= 32; + bits -= 32; + } + } +#else private static void Decode30(int bits, int[] x, int xOff, uint[] z, int zOff) { Debug.Assert(bits > 0); @@ -297,8 +543,13 @@ namespace Org.BouncyCastle.Math.Raw bits -= 32; } } +#endif +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static int Divsteps30(int delta, int f0, int g0, Span<int> t) +#else private static int Divsteps30(int delta, int f0, int g0, int[] t) +#endif { int u = 1 << 30, v = 0, q = 0, r = 1 << 30; int f = f0, g = g0; @@ -340,7 +591,11 @@ namespace Org.BouncyCastle.Math.Raw return delta; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static int Divsteps30Var(int eta, int f0, int g0, Span<int> t) +#else private static int Divsteps30Var(int eta, int f0, int g0, int[] t) +#endif { int u = 1, v = 0, q = 0, r = 1; int f = f0, g = g0, m, w, x, y, z; @@ -403,6 +658,29 @@ namespace Org.BouncyCastle.Math.Raw return eta; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void Encode30(int bits, ReadOnlySpan<uint> x, Span<int> z) + { + Debug.Assert(bits > 0); + + int avail = 0; + ulong data = 0UL; + + int xOff = 0, zOff = 0; + while (bits > 0) + { + if (avail < System.Math.Min(30, bits)) + { + data |= (x[xOff++] & M32UL) << avail; + avail += 32; + } + + z[zOff++] = (int)data & M30; data >>= 30; + avail -= 30; + bits -= 30; + } + } +#else private static void Encode30(int bits, uint[] x, int xOff, int[] z, int zOff) { Debug.Assert(bits > 0); @@ -423,8 +701,13 @@ namespace Org.BouncyCastle.Math.Raw bits -= 30; } } +#endif +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static int EqualTo(int len, ReadOnlySpan<int> x, int y) +#else private static int EqualTo(int len, int[] x, int y) +#endif { int d = x[0] ^ y; for (int i = 1; i < len; ++i) @@ -435,7 +718,11 @@ namespace Org.BouncyCastle.Math.Raw return (d - 1) >> 31; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static int EqualToZero(int len, ReadOnlySpan<int> x) +#else private static int EqualToZero(int len, int[] x) +#endif { int d = 0; for (int i = 0; i < len; ++i) @@ -451,7 +738,11 @@ namespace Org.BouncyCastle.Math.Raw return (49 * bits + (bits < 46 ? 80 : 47)) / 17; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static bool IsOne(int len, ReadOnlySpan<int> x) +#else private static bool IsOne(int len, int[] x) +#endif { if (x[0] != 1) { @@ -467,7 +758,11 @@ namespace Org.BouncyCastle.Math.Raw return true; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static bool IsZero(int len, ReadOnlySpan<int> x) +#else private static bool IsZero(int len, int[] x) +#endif { if (x[0] != 0) { @@ -483,7 +778,11 @@ namespace Org.BouncyCastle.Math.Raw return true; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static int Negate30(int len30, Span<int> D) +#else private static int Negate30(int len30, int[] D) +#endif { Debug.Assert(len30 > 0); Debug.Assert(D.Length >= len30); @@ -499,7 +798,12 @@ namespace Org.BouncyCastle.Math.Raw return c; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void UpdateDE30(int len30, Span<int> D, Span<int> E, ReadOnlySpan<int> t, int m0Inv32, + ReadOnlySpan<int> M) +#else private static void UpdateDE30(int len30, int[] D, int[] E, int[] t, int m0Inv32, int[] M) +#endif { Debug.Assert(len30 > 0); Debug.Assert(D.Length >= len30); @@ -563,7 +867,11 @@ namespace Org.BouncyCastle.Math.Raw E[len30 - 1] = (int)ce; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + private static void UpdateFG30(int len30, Span<int> F, Span<int> G, ReadOnlySpan<int> t) +#else private static void UpdateFG30(int len30, int[] F, int[] G, int[] t) +#endif { Debug.Assert(len30 > 0); Debug.Assert(F.Length >= len30); @@ -601,4 +909,4 @@ namespace Org.BouncyCastle.Math.Raw G[len30 - 1] = (int)cg; } } -} \ No newline at end of file +} diff --git a/crypto/src/math/raw/Nat.cs b/crypto/src/math/raw/Nat.cs index 469d16d55..4065c82c2 100644 --- a/crypto/src/math/raw/Nat.cs +++ b/crypto/src/math/raw/Nat.cs @@ -599,6 +599,21 @@ namespace Org.BouncyCastle.Math.Raw return true; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static bool Gte(int len, ReadOnlySpan<uint> x, ReadOnlySpan<uint> y) + { + for (int i = len - 1; i >= 0; --i) + { + uint x_i = x[i], y_i = y[i]; + if (x_i < y_i) + return false; + if (x_i > y_i) + return true; + } + return true; + } +#endif + public static uint Inc(int len, uint[] z) { for (int i = 0; i < len; ++i) @@ -714,6 +729,20 @@ namespace Org.BouncyCastle.Math.Raw return (int)c; } +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + public static int LessThan(int len, ReadOnlySpan<uint> x, ReadOnlySpan<uint> y) + { + long c = 0; + for (int i = 0; i < len; ++i) + { + c += (long)x[i] - y[i]; + c >>= 32; + } + Debug.Assert(c == 0L || c == -1L); + return (int)c; + } +#endif + public static void Mul(int len, uint[] x, uint[] y, uint[] zz) { zz[len] = MulWord(len, x[0], y, zz); |