Optimized sqrt() for custom secp224r1

2 files changed, 117 insertions, 2 deletions

diff --git a/core/src/main/java/org/bouncycastle/math/ec/Mod.java b/core/src/main/java/org/bouncycastle/math/ec/Mod.java
index 2ac6c465..0345af19 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/Mod.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/Mod.java
@@ -1,5 +1,9 @@
 package org.bouncycastle.math.ec;
 
+import java.util.Random;
+
+import org.bouncycastle.crypto.util.Pack;
+
 public abstract class Mod
 {
     public static void invert(int[] p, int[] x, int[] z)
@@ -70,6 +74,31 @@ public abstract class Mod
         }
     }
 
+    public static int[] random(int[] p)
+    {
+        int len = p.length;
+        Random rand = new Random();
+        int[] s = Nat.create(len);
+
+        int m = p[len - 1];
+        m |= m >>> 1;
+        m |= m >>> 2;
+        m |= m >>> 4;
+        m |= m >>> 8;
+        m |= m >>> 16;
+
+        do
+        {
+            byte[] bytes = new byte[len << 2];
+            rand. nextBytes(bytes);
+            Pack.bigEndianToInt(bytes, 0, s);
+            s[len - 1] &= m;
+        }
+        while (Nat.gte(len, s, p));
+
+        return s;
+    }
+
     public static void subtract(int[] p, int[] x, int[] y, int[] z)
     {
         int len = p.length;
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 85081195..23a4ee82 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
@@ -4,6 +4,7 @@ import java.math.BigInteger;
 
 import org.bouncycastle.math.ec.ECFieldElement;
 import org.bouncycastle.math.ec.Mod;
+import org.bouncycastle.math.ec.Nat;
 import org.bouncycastle.util.Arrays;
 
 public class SecP224R1FieldElement extends ECFieldElement
@@ -127,8 +128,42 @@ public class SecP224R1FieldElement extends ECFieldElement
      */
     public ECFieldElement sqrt()
     {
-        ECFieldElement root = new ECFieldElement.Fp(Q, toBigInteger()).sqrt();
-        return root == null ? null : new SecP224R1FieldElement(root.toBigInteger());
+        int[] c = this.x;
+        if (Nat224.isZero(c) || Nat224.isOne(c))
+        {
+            return this;
+        }
+
+        int[] d1 = Mod.random(SecP224R1Field.P);
+        int[] e1 = Nat224.create();
+        e1[0] = 1;
+
+        int[] f = Nat224.create();
+        RP(c, d1, e1, f);
+        RS(d1, e1, f);
+
+        int[] d0 = Nat224.create();
+        int[] e0 = Nat224.create();
+
+        for (int i = 0; i < 95; ++i)
+        {
+            Nat224.copy(d1, d0);
+            Nat224.copy(e1, e0);
+
+            RS(d1, e1, f);
+
+            if (Nat224.isZero(d1))
+            {
+                break;
+            }
+        }
+
+        Mod.invert(SecP224R1Field.P, e0, f);
+        SecP224R1Field.multiply(f, d0, f);
+
+        SecP224R1Field.square(f, d1);
+
+        return Nat224.eq(c, d1) ? new SecP224R1FieldElement(f) : null;
     }
 
     public boolean equals(Object other)
@@ -151,4 +186,55 @@ public class SecP224R1FieldElement extends ECFieldElement
     {
         return Q.hashCode() ^ Arrays.hashCode(x, 0, 7);
     }
+
+    private static void RM(int[] c, int[] d0, int[] e0, int[] d1, int[] e1, int[] f)
+    {
+        int[] t = Nat224.create();
+        SecP224R1Field.multiply(e1, e0, t);
+        SecP224R1Field.multiply(t, c, t);
+        SecP224R1Field.negate(t, t);
+        SecP224R1Field.multiply(d1, d0, f);
+        SecP224R1Field.add(f, t, f);
+        SecP224R1Field.multiply(d1, e0, t);
+        Nat224.copy(f, d1);
+        SecP224R1Field.multiply(e1, d0, e1);
+        SecP224R1Field.add(e1, t, e1);
+        SecP224R1Field.square(e1, f);
+        SecP224R1Field.multiply(f, c, f);
+        SecP224R1Field.negate(f, f);
+    }
+
+    private static void RP(int[] c, int[] d1, int[] e1, int[] f)
+    {
+        SecP224R1Field.negate(c, f);
+
+        int[] d0 = Nat224.create();
+        int[] e0 = Nat224.create();
+
+        for (int i = 0; i < 7; ++i)
+        {
+            Nat224.copy(d1, d0);
+            Nat224.copy(e1, e0);
+
+            int j = 1 << i;
+            while (--j >= 0)
+            {
+                RS(d1, e1, f);
+            }
+
+            RM(c, d0, e0, d1, e1, f);
+        }
+    }
+
+    private static void RS(int[] d, int[] e, int[] f)
+    {
+        SecP224R1Field.multiply(e, d, e);
+        int[] t = Nat224.create();
+        SecP224R1Field.square(d, t);
+        SecP224R1Field.add(f, t, d);
+        SecP224R1Field.twice(e, e);
+        SecP224R1Field.multiply(f, t, f);
+        int c = Nat.shiftUpBits(7, f, 2, 0);
+        SecP224R1Field.reduce32(c, f);
+    }
 }