Improved reduction

4 files changed, 101 insertions, 63 deletions

diff --git a/crypto/src/math/ec/custom/sec/SecP192R1Field.cs b/crypto/src/math/ec/custom/sec/SecP192R1Field.cs
index add8dd410..078ef94f8 100644
--- a/crypto/src/math/ec/custom/sec/SecP192R1Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecP192R1Field.cs
@@ -127,7 +127,29 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
 
         public static void Reduce32(uint x, uint[] z)
         {
-            if ((x != 0 && (Nat.AddWordTo(6, x, z) + Nat.AddWordAt(6, x, z, 2) != 0))
+            long cc = 0;
+
+            if (x != 0)
+            {
+                long xx06 = x;
+
+                cc += (long)z[0] + xx06;
+                z[0] = (uint)cc;
+                cc >>= 32;
+                if (cc != 0)
+                {
+                    cc += (long)z[1];
+                    z[1] = (uint)cc;
+                    cc >>= 32;
+                }
+                cc += (long)z[2] + xx06;
+                z[2] = (uint)cc;
+                cc >>= 32;
+
+                Debug.Assert(cc == 0 || cc == 1);
+            }
+
+            if ((cc != 0 && Nat.IncAt(6, z, 3) != 0)
                 || (z[5] == P5 && Nat192.Gte(z, P)))
             {
                 AddPInvTo(z);
diff --git a/crypto/src/math/ec/custom/sec/SecP224R1Field.cs b/crypto/src/math/ec/custom/sec/SecP224R1Field.cs
index 9b29ff3d1..712d6a46d 100644
--- a/crypto/src/math/ec/custom/sec/SecP224R1Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecP224R1Field.cs
@@ -95,8 +95,10 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             long t1 = xx08 + xx12;
             long t2 = xx09 + xx13;
 
+            const long n = 1;
+
             long cc = 0;
-            cc += (long)xx[0] - t0;
+            cc += (long)xx[0] - t0 + n;
             z[0] = (uint)cc;
             cc >>= 32;
             cc += (long)xx[1] - t1;
@@ -105,7 +107,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             cc += (long)xx[2] - t2;
             z[2] = (uint)cc;
             cc >>= 32;
-            cc += (long)xx[3] + t0 - xx10;
+            cc += (long)xx[3] + t0 - xx10 - n;
             z[3] = (uint)cc;
             cc >>= 32;
             cc += (long)xx[4] + t1 - xx11;
@@ -117,21 +119,41 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             cc += (long)xx[6] + xx10 - xx13;
             z[6] = (uint)cc;
             cc >>= 32;
+            cc += n;
 
-            int c = (int)cc;
-            if (c >= 0)
-            {
-                Reduce32((uint)c, z);
-            }
-            else
-            {
-                SubPInvFrom(z);
-            }
+            Debug.Assert(cc >= 0);
+
+            Reduce32((uint)cc, z);
         }
 
         public static void Reduce32(uint x, uint[] z)
         {
-            if ((x != 0 && (Nat.SubWordFrom(7, x, z) + Nat.AddWordAt(7, x, z, 3) != 0))
+            long cc = 0;
+
+            if (x != 0)
+            {
+                long xx07 = x;
+
+                cc += (long)z[0] - xx07;
+                z[0] = (uint)cc;
+                cc >>= 32;
+                if (cc != 0)
+                {
+                    cc += (long)z[1];
+                    z[1] = (uint)cc;
+                    cc >>= 32;
+                    cc += (long)z[2];
+                    z[2] = (uint)cc;
+                    cc >>= 32;
+                }
+                cc += (long)z[3] + xx07;
+                z[3] = (uint)cc;
+                cc >>= 32;
+
+                Debug.Assert(cc == 0 || cc == 1);
+            }
+
+            if ((cc != 0 && Nat.IncAt(7, z, 4) != 0)
                 || (z[6] == P6 && Nat224.Gte(z, P)))
             {
                 AddPInvTo(z);
diff --git a/crypto/src/math/ec/custom/sec/SecP256R1Field.cs b/crypto/src/math/ec/custom/sec/SecP256R1Field.cs
index 383b42a5e..cc2fe4866 100644
--- a/crypto/src/math/ec/custom/sec/SecP256R1Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecP256R1Field.cs
@@ -11,8 +11,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
         internal static readonly uint[] PExt = new uint[]{ 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF,
             0xFFFFFFFF, 0xFFFFFFFE, 0x00000001, 0xFFFFFFFE, 0x00000001, 0xFFFFFFFE, 0x00000001, 0x00000001, 0xFFFFFFFE,
             0x00000002, 0xFFFFFFFE };
-        private static readonly uint[] _2P = new uint[]{ 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001, 0x00000000, 0x00000000,
-            0x00000002, 0xFFFFFFFE, 0x00000001 };
         private const uint P7 = 0xFFFFFFFF;
         private const uint PExt15 = 0xFFFFFFFE;
 
@@ -98,8 +96,10 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             long t5 = xx13 + xx14;
             long t6 = xx14 + xx15;
 
+            const long n = 6;
+
             long cc = 0;
-            cc += (long)xx[0] + t0 - t3 - t5;
+            cc += (long)xx[0] + t0 - t3 - t5 - n;
             z[0] = (uint)cc;
             cc >>= 32;
             cc += (long)xx[1] + t1 - t4 - t6;
@@ -108,7 +108,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             cc += (long)xx[2] + t2 - t5 - xx15;
             z[2] = (uint)cc;
             cc >>= 32;
-            cc += (long)xx[3] + (t3 << 1) + xx13 - xx15 - t0;
+            cc += (long)xx[3] + (t3 << 1) + xx13 - xx15 - t0 + n;
             z[3] = (uint)cc;
             cc >>= 32;
             cc += (long)xx[4] + (t4 << 1) + xx14 - t1;
@@ -117,29 +117,17 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             cc += (long)xx[5] + (t5 << 1) + xx15 - t2;
             z[5] = (uint)cc;
             cc >>= 32;
-            cc += (long)xx[6] + (t6 << 1) + t5 - t0;
+            cc += (long)xx[6] + (t6 << 1) + t5 - t0 + n;
             z[6] = (uint)cc;
             cc >>= 32;
-            cc += (long)xx[7] + (xx15 << 1) + xx15 + xx08 - t2 - t4;
+            cc += (long)xx[7] + (xx15 << 1) + xx15 + xx08 - t2 - t4 - n;
             z[7] = (uint)cc;
             cc >>= 32;
+            cc += n;
 
-            int c = (int)cc;
-            if (c >= 0)
-            {
-                Reduce32((uint)c, z);
-            }
-            else
-            {
-                while (c < -1)
-                {
-                    c += (int)Nat256.AddTo(_2P, z) + 1;
-                }
-                while (c < 0)
-                {
-                    c += (int)Nat256.AddTo(P, z);
-                }
-            }
+            Debug.Assert(cc >= 0);
+
+            Reduce32((uint)cc, z);
         }
 
         public static void Reduce32(uint x, uint[] z)
@@ -153,21 +141,27 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
                 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;
+                if (cc != 0)
+                {
+                    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;
+                if (cc != 0)
+                {
+                    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;
diff --git a/crypto/src/math/ec/custom/sec/SecP384R1Field.cs b/crypto/src/math/ec/custom/sec/SecP384R1Field.cs
index 039c18af8..dc531f4de 100644
--- a/crypto/src/math/ec/custom/sec/SecP384R1Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecP384R1Field.cs
@@ -95,20 +95,22 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             long xx16 = xx[16], xx17 = xx[17], xx18 = xx[18], xx19 = xx[19];
             long xx20 = xx[20], xx21 = xx[21], xx22 = xx[22], xx23 = xx[23];
 
+            const long n = 1;
+
             long cc = 0;
-            cc += (long)xx[0] + xx12 + xx20 + xx21 - xx23;
+            cc += (long)xx[0] + xx12 + xx20 + xx21 - xx23 - n;
             z[0] = (uint)cc;
             cc >>= 32;
-            cc += (long)xx[1] + xx13 + xx22 + xx23 - xx12 - xx20;
+            cc += (long)xx[1] + xx13 + xx22 + xx23 - xx12 - xx20 + n;
             z[1] = (uint)cc;
             cc >>= 32;
             cc += (long)xx[2] + xx14 + xx23 - xx13 - xx21;
             z[2] = (uint)cc;
             cc >>= 32;
-            cc += (long)xx[3] + xx12 + xx15 + xx20 + xx21 - xx14 - xx22 - xx23;
+            cc += (long)xx[3] + xx12 + xx15 + xx20 + xx21 - xx14 - xx22 - xx23 - n;
             z[3] = (uint)cc;
             cc >>= 32;
-            cc += (long)xx[4] + xx12 + xx13 + xx16 + xx20 + ((xx21 - xx23) << 1) + xx22 - xx15;
+            cc += (long)xx[4] + xx12 + xx13 + xx16 + xx20 + ((xx21 - xx23) << 1) + xx22 - xx15 - n;
             z[4] = (uint)cc;
             cc >>= 32;
             cc += (long)xx[5] + xx13 + xx14 + xx17 + xx21 + (xx22 << 1) + xx23 - xx16;
@@ -132,16 +134,11 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             cc += (long)xx[11] + xx19 + xx20 + xx23 - xx22;
             z[11] = (uint)cc;
             cc >>= 32;
+            cc += n;
 
-            int c = (int)cc;
-            if (c >= 0)
-            {
-                Reduce32((uint)c, z);
-            }
-            else
-            {
-                SubPInvFrom(z);
-            }
+            Debug.Assert(cc >= 0);
+
+            Reduce32((uint)cc, z);
         }
 
         public static void Reduce32(uint x, uint[] z)
@@ -158,9 +155,12 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
                 cc += (long)z[1] - xx12;
                 z[1] = (uint)cc;
                 cc >>= 32;
-                cc += (long)z[2];
-                z[2] = (uint)cc;
-                cc >>= 32;
+                if (cc != 0)
+                {
+                    cc += (long)z[2];
+                    z[2] = (uint)cc;
+                    cc >>= 32;
+                }
                 cc += (long)z[3] + xx12;
                 z[3] = (uint)cc;
                 cc >>= 32;