Optimized Sqrt() for custom secp224r1

2 files changed, 112 insertions, 2 deletions

diff --git a/crypto/src/math/ec/Mod.cs b/crypto/src/math/ec/Mod.cs
index a05ff77aa..37958e57e 100644
--- a/crypto/src/math/ec/Mod.cs
+++ b/crypto/src/math/ec/Mod.cs
@@ -1,6 +1,7 @@
 using System;
 using System.Diagnostics;
 
+using Org.BouncyCastle.Crypto.Utilities;
 using Org.BouncyCastle.Utilities;
 
 namespace Org.BouncyCastle.Math.EC
@@ -73,6 +74,31 @@ namespace Org.BouncyCastle.Math.EC
             }
         }
 
+        public static uint[] Random(uint[] p)
+        {
+            int len = p.Length;
+            Random rand = new Random();
+            uint[] s = Nat.Create(len);
+
+            uint 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.BE_To_UInt32(bytes, 0, s);
+                s[len - 1] &= m;
+            }
+            while (Nat.Gte(len, s, p));
+
+            return s;
+        }
+
         public static void Subtract(uint[] p, uint[] x, uint[] y, uint[] z)
         {
             int len = p.Length;
diff --git a/crypto/src/math/ec/custom/sec/SecP224R1FieldElement.cs b/crypto/src/math/ec/custom/sec/SecP224R1FieldElement.cs
index 41b2de7dc..b17bc8fcd 100644
--- a/crypto/src/math/ec/custom/sec/SecP224R1FieldElement.cs
+++ b/crypto/src/math/ec/custom/sec/SecP224R1FieldElement.cs
@@ -124,8 +124,41 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
          */
         public override ECFieldElement Sqrt()
         {
-            ECFieldElement root = new FpFieldElement(Q, ToBigInteger()).Sqrt();
-            return root == null ? null : new SecP224R1FieldElement(root.ToBigInteger());
+            //ECFieldElement root = new FpFieldElement(Q, ToBigInteger()).Sqrt();
+            //return root == null ? null : new SecP224R1FieldElement(root.ToBigInteger());
+
+            uint[] c = this.x;
+            if (Nat224.IsZero(c) || Nat224.IsOne(c))
+                return this;
+
+            uint[] d1 = Mod.Random(SecP224R1Field.P);
+            uint[] e1 = Nat224.Create();
+            e1[0] = 1;
+
+            uint[] f = Nat224.Create();
+            RP(c, d1, e1, f);
+            RS(d1, e1, f);
+
+            uint[] d0 = Nat224.Create();
+            uint[] 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 override bool Equals(object obj)
@@ -151,5 +184,56 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
         {
             return Q.GetHashCode() ^ Arrays.GetHashCode(x, 0, 7);
         }
+
+        private static void RM(uint[] c, uint[] d0, uint[] e0, uint[] d1, uint[] e1, uint[] f)
+        {
+            uint[] 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(uint[] c, uint[] d1, uint[] e1, uint[] f)
+        {
+            SecP224R1Field.Negate(c, f);
+
+            uint[] d0 = Nat224.Create();
+            uint[] 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(uint[] d, uint[] e, uint[] f)
+        {
+            SecP224R1Field.Multiply(e, d, e);
+            uint[] t = Nat224.Create();
+            SecP224R1Field.Square(d, t);
+            SecP224R1Field.Add(f, t, d);
+            SecP224R1Field.Twice(e, e);
+            SecP224R1Field.Multiply(f, t, f);
+            uint c = Nat.ShiftUpBits(7, f, 2, 0);
+            SecP224R1Field.Reduce32(c, f);
+        }
     }
 }