summary refs log tree commit diff
path: root/crypto/src/math/ec
diff options
context:
space:
mode:
Diffstat (limited to 'crypto/src/math/ec')
-rw-r--r--crypto/src/math/ec/ECCurve.cs18
-rw-r--r--crypto/src/math/ec/rfc8032/Scalar25519.cs26
-rw-r--r--crypto/src/math/ec/rfc8032/Scalar448.cs26
-rw-r--r--crypto/src/math/ec/rfc8032/ScalarUtilities.cs216
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