Minor optimization for secp521r1 point doubling

3 files changed, 48 insertions, 5 deletions

diff --git a/crypto/src/math/ec/Nat.cs b/crypto/src/math/ec/Nat.cs
index b0213fb97..819979473 100644
--- a/crypto/src/math/ec/Nat.cs
+++ b/crypto/src/math/ec/Nat.cs
@@ -59,6 +59,14 @@ namespace Org.BouncyCastle.Math.EC
             return (uint)c;
         }
 
+        public static uint AddWord(int len, uint x, uint[] z)
+        {
+            ulong c = (ulong)x + z[0];
+            z[0] = (uint)c;
+            c >>= 32;
+            return c == 0 ? 0 : Inc(len, z, 1);
+        }
+
         public static uint AddWordExt(int len, uint x, uint[] zz, int zzOff)
         {
             int extLen = len << 1;
@@ -335,6 +343,30 @@ namespace Org.BouncyCastle.Math.EC
             return c >> 31;
         }
 
+        public static uint ShiftUpBits(int len, uint[] z, int bits, uint c)
+        {
+            Debug.Assert(bits > 0 && bits < 32);
+            for (int i = 0; i < len; ++i)
+            {
+                uint next = z[i];
+                z[i] = (next << bits) | (c >> -bits);
+                c = next;
+            }
+            return c >> -bits;
+        }
+
+        public static uint ShiftUpBits(int len, uint[] x, int bits, uint c, uint[] z)
+        {
+            Debug.Assert(bits > 0 && bits < 32);
+            for (int i = 0; i < len; ++i)
+            {
+                uint next = x[i];
+                z[i] = (next << bits) | (c >> -bits);
+                c = next;
+            }
+            return c >> -bits;
+        }
+
         public static void Square(int len, uint[] x, uint[] zz)
         {
             int extLen = len << 1;
diff --git a/crypto/src/math/ec/custom/sec/SecP521R1Field.cs b/crypto/src/math/ec/custom/sec/SecP521R1Field.cs
index 43f012b8b..f39a0daa6 100644
--- a/crypto/src/math/ec/custom/sec/SecP521R1Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecP521R1Field.cs
@@ -85,6 +85,18 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             z[16] = c;
         }
 
+        public static void Reduce23(uint[] z)
+        {
+            uint z16 = z[16];
+            uint c = Nat.AddWord(16, z16 >> 9, z) + (z16 & P16);
+            if (c > P16 || (c == P16 && Nat.Eq(16, z, P)))
+            {
+                c += Nat.Inc(16, z, 0);
+                c &= P16;
+            }
+            z[16] = c;
+        }
+
         public static void Square(uint[] x, uint[] z)
         {
             uint[] tt = Nat.Create(34);
diff --git a/crypto/src/math/ec/custom/sec/SecP521R1Point.cs b/crypto/src/math/ec/custom/sec/SecP521R1Point.cs
index 5da71f078..2e3a7eccb 100644
--- a/crypto/src/math/ec/custom/sec/SecP521R1Point.cs
+++ b/crypto/src/math/ec/custom/sec/SecP521R1Point.cs
@@ -216,12 +216,11 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
 
             uint[] S = Y1Squared;
             SecP521R1Field.Multiply(Y1Squared, X1.x, S);
-            SecP521R1Field.Twice(S, S);
-            SecP521R1Field.Twice(S, S);
+            Nat.ShiftUpBits(17, S, 2, 0);
+            SecP521R1Field.Reduce23(S);
 
-            SecP521R1Field.Twice(T, t1);
-            SecP521R1Field.Twice(t1, t1);
-            SecP521R1Field.Twice(t1, t1);
+            Nat.ShiftUpBits(17, T, 3, 0, t1);
+            SecP521R1Field.Reduce23(t1);
 
             SecP521R1FieldElement X3 = new SecP521R1FieldElement(T);
             SecP521R1Field.Square(M, X3.x);