Fix infinite loop issue when there is no sqrt

Add test case to check that Sqrt returns null for non-squares

2 files changed, 80 insertions, 30 deletions

diff --git a/crypto/src/math/ec/custom/sec/SecP224R1FieldElement.cs b/crypto/src/math/ec/custom/sec/SecP224R1FieldElement.cs
index 6837ca26e..06f47cded 100644
--- a/crypto/src/math/ec/custom/sec/SecP224R1FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecP224R1FieldElement.cs
@@ -134,39 +134,17 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             uint[] r = Mod.Random(SecP224R1Field.P);
             uint[] t = Nat224.Create();
 
-            for (;;)
-            {
-                uint[] d1 = Nat224.Create();
-                Nat224.Copy(r, d1);
-                uint[] e1 = Nat224.Create();
-                e1[0] = 1;
-                uint[] f1 = Nat224.Create();
-                RP(nc, d1, e1, f1, t);
-
-                uint[] d0 = Nat224.Create();
-                uint[] e0 = Nat224.Create();
-
-                for (int k = 1; k < 96; ++k)
-                {
-                    Nat224.Copy(d1, d0);
-                    Nat224.Copy(e1, e0);
-
-                    RS(d1, e1, f1, t);
-
-                    if (Nat224.IsZero(d1))
-                    {
-                        Mod.Invert(SecP224R1Field.P, e0, f1);
-                        SecP224R1Field.Multiply(f1, d0, f1);
-
-                        SecP224R1Field.Square(f1, d1);
-
-                        return Nat224.Eq(c, d1) ? new SecP224R1FieldElement(f1) : null;
-                    }
-                }
+            if (!IsSquare(c))
+                return null;
 
-                // Avoid any possible infinite loop due to a bad random number generator
+            while (!TrySqrt(nc, r, t))
+            {
                 SecP224R1Field.AddOne(r, r);
             }
+
+            SecP224R1Field.Square(t, r);
+
+            return Nat224.Eq(c, r) ? new SecP224R1FieldElement(t) : null;
         }
 
         public override bool Equals(object obj)
@@ -193,6 +171,23 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return Q.GetHashCode() ^ Arrays.GetHashCode(x, 0, 7);
         }
 
+        private static bool IsSquare(uint[] x)
+        {
+            uint[] t1 = Nat224.Create();
+            uint[] t2 = Nat224.Create();
+            Nat224.Copy(x, t1);
+
+            for (int i = 0; i < 7; ++i)
+            {
+                Nat224.Copy(t1, t2);
+                SecP224R1Field.SquareN(t1, 1 << i, t1);
+                SecP224R1Field.Multiply(t1, t2, t1);
+            }
+
+            SecP224R1Field.SquareN(t1, 95, t1);
+            return Nat224.IsOne(t1);
+        }
+
         private static void RM(uint[] nc, uint[] d0, uint[] e0, uint[] d1, uint[] e1, uint[] f1, uint[] t)
         {
             SecP224R1Field.Multiply(e1, e0, t);
@@ -239,5 +234,35 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             uint c = Nat.ShiftUpBits(7, f, 2, 0);
             SecP224R1Field.Reduce32(c, f);
         }
+
+        private static bool TrySqrt(uint[] nc, uint[] r, uint[] t)
+        {
+            uint[] d1 = Nat224.Create();
+            Nat224.Copy(r, d1);
+            uint[] e1 = Nat224.Create();
+            e1[0] = 1;
+            uint[] f1 = Nat224.Create();
+            RP(nc, d1, e1, f1, t);
+
+            uint[] d0 = Nat224.Create();
+            uint[] e0 = Nat224.Create();
+
+            for (int k = 1; k < 96; ++k)
+            {
+                Nat224.Copy(d1, d0);
+                Nat224.Copy(e1, e0);
+
+                RS(d1, e1, f1, t);
+
+                if (Nat224.IsZero(d1))
+                {
+                    Mod.Invert(SecP224R1Field.P, e0, t);
+                    SecP224R1Field.Multiply(t, d0, t);
+                    return true;
+                }
+            }
+
+            return false;
+        }
     }
 }
diff --git a/crypto/test/src/math/ec/test/ECPointTest.cs b/crypto/test/src/math/ec/test/ECPointTest.cs
index b3f9cb0e7..22227eed1 100644
--- a/crypto/test/src/math/ec/test/ECPointTest.cs
+++ b/crypto/test/src/math/ec/test/ECPointTest.cs
@@ -8,6 +8,7 @@ using Org.BouncyCastle.Crypto.EC;
 using Org.BouncyCastle.Math;
 using Org.BouncyCastle.Math.EC;
 using Org.BouncyCastle.Security;
+using Org.BouncyCastle.Utilities;
 
 namespace Org.BouncyCastle.Math.EC.Tests
 {
@@ -443,6 +444,28 @@ namespace Org.BouncyCastle.Math.EC.Tests
             }
         }
 
+        private void ImplSqrtTest(ECCurve c)
+        {
+            if (ECAlgorithms.IsFpCurve(c))
+            {
+                BigInteger p = c.Field.Characteristic;
+                BigInteger pMinusOne = p.Subtract(BigInteger.One);
+                BigInteger legendreExponent = p.ShiftRight(1);
+
+                int count = 0;
+                while (count < 10)
+                {
+                    BigInteger nonSquare = BigIntegers.CreateRandomInRange(BigInteger.Two, pMinusOne, secRand);
+                    if (!nonSquare.ModPow(legendreExponent, p).Equals(BigInteger.One))
+                    {
+                        ECFieldElement root = c.FromBigInteger(nonSquare).Sqrt();
+                        Assert.IsNull(root);
+                        ++count;
+                    }
+                }
+            }
+        }
+
         private void ImplAddSubtractMultiplyTwiceEncodingTestAllCoords(X9ECParameters x9ECParameters)
         {
             BigInteger n = x9ECParameters.N;
@@ -469,6 +492,8 @@ namespace Org.BouncyCastle.Math.EC.Tests
                     ECPoint q = g.Multiply(b).Normalize();
 
                     ImplAddSubtractMultiplyTwiceEncodingTest(c, q, n);
+
+                    ImplSqrtTest(c);
                 }
             }
         }