Optimize Sqrt() for custom curve secp224k1

1 files changed, 87 insertions, 2 deletions

diff --git a/crypto/src/math/ec/custom/sec/SecP224K1FieldElement.cs b/crypto/src/math/ec/custom/sec/SecP224K1FieldElement.cs
index cd9426769..123efd2ab 100644
--- a/crypto/src/math/ec/custom/sec/SecP224K1FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecP224K1FieldElement.cs
@@ -10,6 +10,10 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
     {
         public static readonly BigInteger Q = SecP224K1Curve.q;
 
+        // Calculated as BigInteger.Two.ModPow(Q.ShiftRight(2), Q)
+        private static readonly uint[] PRECOMP_POW2 = new uint[]{ 0x33bfd202, 0xdcfad133, 0x2287624a, 0xc3811ba8,
+            0xa85558fc, 0x1eaef5d7, 0x8edf154c };
+
         protected internal readonly uint[] x;
 
         public SecP224K1FieldElement(BigInteger x)
@@ -125,8 +129,89 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
          */
         public override ECFieldElement Sqrt()
         {
-            ECFieldElement root = new FpFieldElement(Q, ToBigInteger()).Sqrt();
-            return root == null ? null : new SecP224K1FieldElement(root.ToBigInteger());
+            /*
+             * Q == 8m + 5, so we use Pocklington's method for this case.
+             *
+             * First, raise this element to the exponent 2^221 - 2^29 - 2^9 - 2^8 - 2^6 - 2^4 - 2^1 (i.e. m + 1)
+             * 
+             * Breaking up the exponent's binary representation into "repunits", we get:
+             * { 191 1s } { 1 0s } { 19 1s } { 2 0s } { 1 1s } { 1 0s} { 1 1s } { 1 0s} { 3 1s } { 1 0s}
+             * 
+             * Therefore we need an addition chain containing 1, 3, 19, 191 (the lengths of the repunits)
+             * We use: [1], 2, [3], 4, 8, 11, [19], 23, 42, 84, 107, [191]
+             */
+
+            uint[] x1 = this.x;
+            if (Nat224.IsZero(x1) || Nat224.IsOne(x1))
+                return this;
+
+            uint[] x2 = Nat224.Create();
+            SecP224K1Field.Square(x1, x2);
+            SecP224K1Field.Multiply(x2, x1, x2);
+            uint[] x3 = x2;
+            SecP224K1Field.Square(x2, x3);
+            SecP224K1Field.Multiply(x3, x1, x3);
+            uint[] x4 = Nat224.Create();
+            SecP224K1Field.Square(x3, x4);
+            SecP224K1Field.Multiply(x4, x1, x4);
+            uint[] x8 = Nat224.Create();
+            SecP224K1Field.SquareN(x4, 4, x8);
+            SecP224K1Field.Multiply(x8, x4, x8);
+            uint[] x11 = Nat224.Create();
+            SecP224K1Field.SquareN(x8, 3, x11);
+            SecP224K1Field.Multiply(x11, x3, x11);
+            uint[] x19 = x11;
+            SecP224K1Field.SquareN(x11, 8, x19);
+            SecP224K1Field.Multiply(x19, x8, x19);
+            uint[] x23 = x8;
+            SecP224K1Field.SquareN(x19, 4, x23);
+            SecP224K1Field.Multiply(x23, x4, x23);
+            uint[] x42 = x4;
+            SecP224K1Field.SquareN(x23, 19, x42);
+            SecP224K1Field.Multiply(x42, x19, x42);
+            uint[] x84 = Nat224.Create();
+            SecP224K1Field.SquareN(x42, 42, x84);
+            SecP224K1Field.Multiply(x84, x42, x84);
+            uint[] x107 = x42;
+            SecP224K1Field.SquareN(x84, 23, x107);
+            SecP224K1Field.Multiply(x107, x23, x107);
+            uint[] x191 = x23;
+            SecP224K1Field.SquareN(x107, 84, x191);
+            SecP224K1Field.Multiply(x191, x84, x191);
+
+            uint[] t1 = x191;
+            SecP224K1Field.SquareN(t1, 20, t1);
+            SecP224K1Field.Multiply(t1, x19, t1);
+            SecP224K1Field.SquareN(t1, 3, t1);
+            SecP224K1Field.Multiply(t1, x1, t1);
+            SecP224K1Field.SquareN(t1, 2, t1);
+            SecP224K1Field.Multiply(t1, x1, t1);
+            SecP224K1Field.SquareN(t1, 4, t1);
+            SecP224K1Field.Multiply(t1, x3, t1);
+            SecP224K1Field.Square(t1, t1);
+
+            uint[] t2 = x84;
+            SecP224K1Field.Square(t1, t2);
+
+            if (Arrays.AreEqual(x1, t2))
+            {
+                return new SecP224K1FieldElement(t1);
+            }
+
+            /*
+             * If the first guess is incorrect, we multiply by a precomputed power of 2 to get the second guess,
+             * which is ((4x)^(m + 1))/2 mod Q
+             */
+            SecP224K1Field.Multiply(t1, PRECOMP_POW2, t1);
+
+            SecP224K1Field.Square(t1, t2);
+
+            if (Arrays.AreEqual(x1, t2))
+            {
+                return new SecP224K1FieldElement(t1);
+            }
+
+            return null;
         }
 
         public override bool Equals(object obj)