Fix infinite loop issue when there is no sqrt

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

1 files changed, 56 insertions, 29 deletions

diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1FieldElement.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1FieldElement.java
index 74ebc047..90e03de3 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1FieldElement.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1FieldElement.java
@@ -140,39 +140,19 @@ public class SecP224R1FieldElement extends ECFieldElement
         int[] r = Mod.random(SecP224R1Field.P);
         int[] t = Nat224.create();
 
-        for (;;)
+        if (!isSquare(c))
         {
-            int[] d1 = Nat224.create();
-            Nat224.copy(r, d1);
-            int[] e1 = Nat224.create();
-            e1[0] = 1;
-            int[] f1 = Nat224.create();
-            RP(nc, d1, e1, f1, t);
-
-            int[] d0 = Nat224.create();
-            int[] 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;
-                }
-            }
+            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 boolean equals(Object other)
@@ -196,6 +176,23 @@ public class SecP224R1FieldElement extends ECFieldElement
         return Q.hashCode() ^ Arrays.hashCode(x, 0, 7);
     }
 
+    private static boolean isSquare(int[] x)
+    {
+        int[] t1 = Nat224.create();
+        int[] 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(int[] nc, int[] d0, int[] e0, int[] d1, int[] e1, int[] f1, int[] t)
     {
         SecP224R1Field.multiply(e1, e0, t);
@@ -242,4 +239,34 @@ public class SecP224R1FieldElement extends ECFieldElement
         int c = Nat.shiftUpBits(7, f, 2, 0);
         SecP224R1Field.reduce32(c, f);
     }
+
+    private static boolean trySqrt(int[] nc, int[] r, int[] t)
+    {
+        int[] d1 = Nat224.create();
+        Nat224.copy(r, d1);
+        int[] e1 = Nat224.create();
+        e1[0] = 1;
+        int[] f1 = Nat224.create();
+        RP(nc, d1, e1, f1, t);
+
+        int[] d0 = Nat224.create();
+        int[] 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;
+    }
 }