Optimization for custom curve reduction when only a few bits need reducing; used to delay reduction in point doubling.

15 files changed, 205 insertions, 30 deletions

diff --git a/crypto/src/math/ec/custom/sec/Nat192.cs b/crypto/src/math/ec/custom/sec/Nat192.cs
index 6d908d1ca..35bf75445 100644
--- a/crypto/src/math/ec/custom/sec/Nat192.cs
+++ b/crypto/src/math/ec/custom/sec/Nat192.cs
@@ -108,6 +108,15 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return (uint)c;
         }
 
+        public static uint AddWord(uint x, uint[] z, int zOff)
+        {
+            Debug.Assert(zOff <= 5);
+            ulong c = (ulong)x + z[zOff + 0];
+            z[zOff + 0] = (uint)c;
+            c >>= 32;
+            return c == 0 ? 0 : Inc(z, zOff + 1);
+        }
+
         public static uint AddWordExt(uint x, uint[] zz, int zzOff)
         {
             Debug.Assert(zzOff <= 11);
@@ -140,6 +149,19 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return -1;
         }
 
+        public static int DecExt(uint[] z, int zOff)
+        {
+            Debug.Assert(zOff <= 12);
+            for (int i = zOff; i < 12; ++i)
+            {
+                if (--z[i] != uint.MaxValue)
+                {
+                    return 0;
+                }
+            }
+            return -1;
+        }
+
         public static uint[] FromBigInteger(BigInteger x)
         {
             if (x.SignValue < 0 || x.BitLength > 192)
@@ -400,6 +422,23 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return c == 0 ? 0 : Inc(z, zOff + 4);
         }
 
+        public static uint Mul33WordAdd(uint x, uint y, uint[] z, int zOff)
+        {
+            Debug.Assert(x >> 31 == 0);
+            Debug.Assert(zOff <=3);
+            ulong c = 0, yVal = y;
+            c += yVal * x + z[zOff + 0];
+            z[zOff + 0] = (uint)c;
+            c >>= 32;
+            c += yVal + z[zOff + 1];
+            z[zOff + 1] = (uint)c;
+            c >>= 32;
+            c += z[zOff + 2];
+            z[zOff + 2] = (uint)c;
+            c >>= 32;
+            return c == 0 ? 0 : Inc(z, zOff + 3);
+        }
+
         public static uint MulWordDwordAdd(uint x, ulong y, uint[] z, int zOff)
         {
             Debug.Assert(zOff <= 3);
@@ -695,6 +734,24 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return (int)c;
         }
 
+        public static int SubWord(uint x, uint[] z, int zOff)
+        {
+            Debug.Assert(zOff <= 5);
+            long c = (long)z[zOff + 0] - x;
+            z[zOff + 0] = (uint)c;
+            c >>= 32;
+            return c == 0 ? 0 : Dec(z, zOff + 1);
+        }
+
+        public static int SubWordExt(uint x, uint[] zz, int zzOff)
+        {
+            Debug.Assert(zzOff <= 11);
+            long c = (long)zz[zzOff + 0] - x;
+            zz[zzOff + 0] = (uint)c;
+            c >>= 32;
+            return c == 0 ? 0 : DecExt(zz, zzOff + 1);
+        }
+
         public static BigInteger ToBigInteger(uint[] x)
         {
             byte[] bs = new byte[24];
diff --git a/crypto/src/math/ec/custom/sec/Nat224.cs b/crypto/src/math/ec/custom/sec/Nat224.cs
index 72950e8a6..a391fc248 100644
--- a/crypto/src/math/ec/custom/sec/Nat224.cs
+++ b/crypto/src/math/ec/custom/sec/Nat224.cs
@@ -730,6 +730,23 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return c == 0 ? 0 : Inc(z, zOff + 4);
         }
 
+        public static uint Mul33WordAdd(uint x, uint y, uint[] z, int zOff)
+        {
+            Debug.Assert(x >> 31 == 0);
+            Debug.Assert(zOff <= 4);
+            ulong c = 0, yVal = y;
+            c += yVal * x + z[zOff + 0];
+            z[zOff + 0] = (uint)c;
+            c >>= 32;
+            c += yVal + z[zOff + 1];
+            z[zOff + 1] = (uint)c;
+            c >>= 32;
+            c += z[zOff + 2];
+            z[zOff + 2] = (uint)c;
+            c >>= 32;
+            return c == 0 ? 0 : Inc(z, zOff + 3);
+        }
+
         public static uint MulWordDwordAdd(uint x, ulong y, uint[] z, int zOff)
         {
             Debug.Assert(zOff <= 4);
diff --git a/crypto/src/math/ec/custom/sec/Nat256.cs b/crypto/src/math/ec/custom/sec/Nat256.cs
index c846f56fb..aa6f4e5eb 100644
--- a/crypto/src/math/ec/custom/sec/Nat256.cs
+++ b/crypto/src/math/ec/custom/sec/Nat256.cs
@@ -781,6 +781,23 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return c == 0 ? 0 : Inc(z, zOff + 4);
         }
 
+        public static uint Mul33WordAdd(uint x, uint y, uint[] z, int zOff)
+        {
+            Debug.Assert(x >> 31 == 0);
+            Debug.Assert(zOff <= 5);
+            ulong c = 0, yVal = y;
+            c += yVal * x + z[zOff + 0];
+            z[zOff + 0] = (uint)c;
+            c >>= 32;
+            c += yVal + z[zOff + 1];
+            z[zOff + 1] = (uint)c;
+            c >>= 32;
+            c += z[zOff + 2];
+            z[zOff + 2] = (uint)c;
+            c >>= 32;
+            return c == 0 ? 0 : Inc(z, zOff + 3);
+        }
+
         public static uint MulWordDwordAdd(uint x, ulong y, uint[] z, int zOff)
         {
             Debug.Assert(zOff <= 5);
diff --git a/crypto/src/math/ec/custom/sec/SecP192K1Field.cs b/crypto/src/math/ec/custom/sec/SecP192K1Field.cs
index 832db0fbe..eef42eecc 100644
--- a/crypto/src/math/ec/custom/sec/SecP192K1Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecP192K1Field.cs
@@ -97,6 +97,18 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             }
         }
 
+        public static void Reduce32(uint x, uint[] z)
+        {
+            uint c = Nat192.Mul33WordAdd(PInv33, x, z, 0);
+
+            Debug.Assert(c == 0 || c == 1);
+
+            if (c != 0 || (z[5] == P5 && Nat192.Gte(z, P)))
+            {
+                Nat192.AddDWord(PInv, z, 0);
+            }
+        }
+
         public static void Square(uint[] x, uint[] z)
         {
             uint[] tt = Nat192.CreateExt();
diff --git a/crypto/src/math/ec/custom/sec/SecP192K1Point.cs b/crypto/src/math/ec/custom/sec/SecP192K1Point.cs
index 364c62480..1c6573aca 100644
--- a/crypto/src/math/ec/custom/sec/SecP192K1Point.cs
+++ b/crypto/src/math/ec/custom/sec/SecP192K1Point.cs
@@ -205,12 +205,11 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
 
             uint[] S = Y1Squared;
             SecP192K1Field.Multiply(Y1Squared, X1.x, S);
-            SecP192K1Field.Twice(S, S);
-            SecP192K1Field.Twice(S, S);
+            uint c = Nat.ShiftUpBits(6, S, 2, 0);
+            SecP192K1Field.Reduce32(c, S);
 
-            SecP192K1Field.Twice(T, t1);
-            SecP192K1Field.Twice(t1, t1);
-            SecP192K1Field.Twice(t1, t1);
+            c = Nat.ShiftUpBits(6, T, 3, 0, t1);
+            SecP192K1Field.Reduce32(c, t1);
 
             SecP192K1FieldElement X3 = new SecP192K1FieldElement(T);
             SecP192K1Field.Square(M, X3.x);
diff --git a/crypto/src/math/ec/custom/sec/SecP192R1Field.cs b/crypto/src/math/ec/custom/sec/SecP192R1Field.cs
index fdb1fa863..3871d9abb 100644
--- a/crypto/src/math/ec/custom/sec/SecP192R1Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecP192R1Field.cs
@@ -131,6 +131,15 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             }
         }
 
+        public static void Reduce32(uint x, uint[] z)
+        {
+            uint c = Nat192.AddWord(x, z, 0) + Nat192.AddWord(x, z, 2);
+            if (c != 0 || (z[5] == P5 && Nat192.Gte(z, P)))
+            {
+                Nat192.Sub(z, P, z);
+            }
+        }
+
         public static void Square(uint[] x, uint[] z)
         {
             uint[] tt = Nat192.CreateExt();
diff --git a/crypto/src/math/ec/custom/sec/SecP192R1Point.cs b/crypto/src/math/ec/custom/sec/SecP192R1Point.cs
index 0dd81f0c7..29a26c941 100644
--- a/crypto/src/math/ec/custom/sec/SecP192R1Point.cs
+++ b/crypto/src/math/ec/custom/sec/SecP192R1Point.cs
@@ -217,12 +217,11 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
 
             uint[] S = Y1Squared;
             SecP192R1Field.Multiply(Y1Squared, X1.x, S);
-            SecP192R1Field.Twice(S, S);
-            SecP192R1Field.Twice(S, S);
+            uint c = Nat.ShiftUpBits(6, S, 2, 0);
+            SecP192R1Field.Reduce32(c, S);
 
-            SecP192R1Field.Twice(T, t1);
-            SecP192R1Field.Twice(t1, t1);
-            SecP192R1Field.Twice(t1, t1);
+            c = Nat.ShiftUpBits(6, T, 3, 0, t1);
+            SecP192R1Field.Reduce32(c, t1);
 
             SecP192R1FieldElement X3 = new SecP192R1FieldElement(T);
             SecP192R1Field.Square(M, X3.x);
diff --git a/crypto/src/math/ec/custom/sec/SecP224K1Field.cs b/crypto/src/math/ec/custom/sec/SecP224K1Field.cs
index edc938d22..ce07eff67 100644
--- a/crypto/src/math/ec/custom/sec/SecP224K1Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecP224K1Field.cs
@@ -98,6 +98,18 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             }
         }
 
+        public static void Reduce32(uint x, uint[] z)
+        {
+            uint c = Nat224.Mul33WordAdd(PInv33, x, z, 0);
+
+            Debug.Assert(c == 0 || c == 1);
+
+            if (c != 0 || (z[6] == P6 && Nat224.Gte(z, P)))
+            {
+                Nat224.AddDWord(PInv, z, 0);
+            }
+        }
+
         public static void Square(uint[] x, uint[] z)
         {
             uint[] tt = Nat224.CreateExt();
diff --git a/crypto/src/math/ec/custom/sec/SecP224K1Point.cs b/crypto/src/math/ec/custom/sec/SecP224K1Point.cs
index f85c64981..c7119401d 100644
--- a/crypto/src/math/ec/custom/sec/SecP224K1Point.cs
+++ b/crypto/src/math/ec/custom/sec/SecP224K1Point.cs
@@ -205,12 +205,11 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
 
             uint[] S = Y1Squared;
             SecP224K1Field.Multiply(Y1Squared, X1.x, S);
-            SecP224K1Field.Twice(S, S);
-            SecP224K1Field.Twice(S, S);
+            uint c = Nat.ShiftUpBits(7, S, 2, 0);
+            SecP224K1Field.Reduce32(c, S);
 
-            SecP224K1Field.Twice(T, t1);
-            SecP224K1Field.Twice(t1, t1);
-            SecP224K1Field.Twice(t1, t1);
+            c = Nat.ShiftUpBits(7, T, 3, 0, t1);
+            SecP224K1Field.Reduce32(c, t1);
 
             SecP224K1FieldElement X3 = new SecP224K1FieldElement(T);
             SecP224K1Field.Square(M, X3.x);
diff --git a/crypto/src/math/ec/custom/sec/SecP224R1Field.cs b/crypto/src/math/ec/custom/sec/SecP224R1Field.cs
index 4eb04325a..1cb3fe352 100644
--- a/crypto/src/math/ec/custom/sec/SecP224R1Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecP224R1Field.cs
@@ -137,6 +137,15 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             }
         }
 
+        public static void Reduce32(uint x, uint[] z)
+        {
+            int c = Nat224.SubWord(x, z, 0) + (int)Nat224.AddWord(x, z, 3);
+            if (c != 0 || (z[6] == P6 && Nat224.Gte(z, P)))
+            {
+                Nat224.Sub(z, P, z);
+            }
+        }
+
         public static void Square(uint[] x, uint[] z)
         {
             uint[] tt = Nat224.CreateExt();
diff --git a/crypto/src/math/ec/custom/sec/SecP224R1Point.cs b/crypto/src/math/ec/custom/sec/SecP224R1Point.cs
index 251415179..31cef6929 100644
--- a/crypto/src/math/ec/custom/sec/SecP224R1Point.cs
+++ b/crypto/src/math/ec/custom/sec/SecP224R1Point.cs
@@ -217,12 +217,11 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
 
             uint[] S = Y1Squared;
             SecP224R1Field.Multiply(Y1Squared, X1.x, S);
-            SecP224R1Field.Twice(S, S);
-            SecP224R1Field.Twice(S, S);
+            uint c = Nat.ShiftUpBits(7, S, 2, 0);
+            SecP224R1Field.Reduce32(c, S);
 
-            SecP224R1Field.Twice(T, t1);
-            SecP224R1Field.Twice(t1, t1);
-            SecP224R1Field.Twice(t1, t1);
+            c = Nat.ShiftUpBits(7, T, 3, 0, t1);
+            SecP224R1Field.Reduce32(c, t1);
 
             SecP224R1FieldElement X3 = new SecP224R1FieldElement(T);
             SecP224R1Field.Square(M, X3.x);
diff --git a/crypto/src/math/ec/custom/sec/SecP256K1Field.cs b/crypto/src/math/ec/custom/sec/SecP256K1Field.cs
index b3c964982..8852339d3 100644
--- a/crypto/src/math/ec/custom/sec/SecP256K1Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecP256K1Field.cs
@@ -99,6 +99,18 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             }
         }
 
+        public static void Reduce32(uint x, uint[] z)
+        {
+            uint c = Nat256.Mul33WordAdd(PInv33, x, z, 0);
+
+            Debug.Assert(c == 0 || c == 1);
+
+            if (c != 0 || (z[7] == P7 && Nat256.Gte(z, P)))
+            {
+                Nat256.AddDWord(PInv, z, 0);
+            }
+        }
+
         public static void Square(uint[] x, uint[] z)
         {
             uint[] tt = Nat256.CreateExt();
diff --git a/crypto/src/math/ec/custom/sec/SecP256K1Point.cs b/crypto/src/math/ec/custom/sec/SecP256K1Point.cs
index d981911a6..d8e1eb83a 100644
--- a/crypto/src/math/ec/custom/sec/SecP256K1Point.cs
+++ b/crypto/src/math/ec/custom/sec/SecP256K1Point.cs
@@ -205,12 +205,11 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
 
             uint[] S = Y1Squared;
             SecP256K1Field.Multiply(Y1Squared, X1.x, S);
-            SecP256K1Field.Twice(S, S);
-            SecP256K1Field.Twice(S, S);
+            uint c = Nat.ShiftUpBits(8, S, 2, 0);
+            SecP256K1Field.Reduce32(c, S);
 
-            SecP256K1Field.Twice(T, t1);
-            SecP256K1Field.Twice(t1, t1);
-            SecP256K1Field.Twice(t1, t1);
+            c = Nat.ShiftUpBits(8, T, 3, 0, t1);
+            SecP256K1Field.Reduce32(c, t1);
 
             SecP256K1FieldElement X3 = new SecP256K1FieldElement(T);
             SecP256K1Field.Square(M, X3.x);
diff --git a/crypto/src/math/ec/custom/sec/SecP256R1Field.cs b/crypto/src/math/ec/custom/sec/SecP256R1Field.cs
index 88a13f513..9e366bffe 100644
--- a/crypto/src/math/ec/custom/sec/SecP256R1Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecP256R1Field.cs
@@ -145,6 +145,42 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             }
         }
 
+        public static void Reduce32(uint x, uint[] z)
+        {
+            long xx08 = x;
+
+            long cc = 0;
+            cc += (long)z[0] + xx08;
+            z[0] = (uint)cc;
+            cc >>= 32;
+            cc += (long)z[1];
+            z[1] = (uint)cc;
+            cc >>= 32;
+            cc += (long)z[2];
+            z[2] = (uint)cc;
+            cc >>= 32;
+            cc += (long)z[3] - xx08;
+            z[3] = (uint)cc;
+            cc >>= 32;
+            cc += (long)z[4];
+            z[4] = (uint)cc;
+            cc >>= 32;
+            cc += (long)z[5];
+            z[5] = (uint)cc;
+            cc >>= 32;
+            cc += (long)z[6] - xx08;
+            z[6] = (uint)cc;
+            cc >>= 32;
+            cc += (long)z[7] + xx08;
+            z[7] = (uint)cc;
+            cc >>= 32;
+
+            if (cc != 0 || (z[7] == P7 && Nat256.Gte(z, P)))
+            {
+                Nat256.Sub(z, P, z);
+            }
+        }
+
         public static void Square(uint[] x, uint[] z)
         {
             uint[] tt = Nat256.CreateExt();
diff --git a/crypto/src/math/ec/custom/sec/SecP256R1Point.cs b/crypto/src/math/ec/custom/sec/SecP256R1Point.cs
index be54e0dda..e25ff5f7a 100644
--- a/crypto/src/math/ec/custom/sec/SecP256R1Point.cs
+++ b/crypto/src/math/ec/custom/sec/SecP256R1Point.cs
@@ -217,12 +217,11 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
 
             uint[] S = Y1Squared;
             SecP256R1Field.Multiply(Y1Squared, X1.x, S);
-            SecP256R1Field.Twice(S, S);
-            SecP256R1Field.Twice(S, S);
+            uint c = Nat.ShiftUpBits(8, S, 2, 0);
+            SecP256R1Field.Reduce32(c, S);
 
-            SecP256R1Field.Twice(T, t1);
-            SecP256R1Field.Twice(t1, t1);
-            SecP256R1Field.Twice(t1, t1);
+            c = Nat.ShiftUpBits(8, T, 3, 0, t1);
+            SecP256R1Field.Reduce32(c, t1);
 
             SecP256R1FieldElement X3 = new SecP256R1FieldElement(T);
             SecP256R1Field.Square(M, X3.x);