Use Nat methods instead of specific Nat*.*Ext methods

Reduction improvements in curve25519 and secp256r1

10 files changed, 44 insertions, 84 deletions

diff --git a/crypto/src/math/ec/custom/sec/Curve25519Field.cs b/crypto/src/math/ec/custom/sec/Curve25519Field.cs
index c2924a2a0..ee0f88311 100644
--- a/crypto/src/math/ec/custom/sec/Curve25519Field.cs
+++ b/crypto/src/math/ec/custom/sec/Curve25519Field.cs
@@ -26,9 +26,9 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
         public static void AddExt(uint[] xx, uint[] yy, uint[] zz)
         {
             Nat.Add(16, xx, yy, zz);
-            if (Nat256.GteExt(zz, PExt))
+            if (Nat.Gte(16, zz, PExt))
             {
-                Nat.SubFrom(16, PExt, zz);
+                SubPExtFrom(zz);
             }
         }
 
@@ -136,7 +136,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             int c = Nat.Sub(16, xx, yy, zz);
             if (c != 0)
             {
-                Nat.AddTo(16, PExt, zz);
+                AddPExtTo(zz);
             }
         }
 
@@ -149,6 +149,40 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             }
         }
 
+        private static void AddPExtTo(uint[] zz)
+        {
+            ulong c = (ulong)zz[0] + PExt[0];
+            zz[0] = (uint)c;
+            c >>= 32;
+
+            int i = 1 - (int)c;
+            i = (i << 3) - i;
+
+            while (++i < 16)
+            {
+                c += (ulong)zz[i] + PExt[i];
+                zz[i] = (uint)c;
+                c >>= 32;
+            }
+        }
+
+        private static void SubPExtFrom(uint[] zz)
+        {
+            long c = (long)zz[0] - PExt[0];
+            zz[0] = (uint)c;
+            c >>= 32;
+
+            int i = 1 + (int)c;
+            i = (i << 3) - i;
+
+            while (++i < 16)
+            {
+                c += (long)zz[i] - PExt[i];
+                zz[i] = (uint)c;
+                c >>= 32;
+            }
+        }
+
         private static void AddPInvTo(uint[] z)
         {
             ulong c = (ulong)z[0] + PInv;
diff --git a/crypto/src/math/ec/custom/sec/Nat192.cs b/crypto/src/math/ec/custom/sec/Nat192.cs
index 0ecbc06de..87dbcec84 100644
--- a/crypto/src/math/ec/custom/sec/Nat192.cs
+++ b/crypto/src/math/ec/custom/sec/Nat192.cs
@@ -235,19 +235,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return true;
         }
 
-        public static bool GteExt(uint[] xx, uint[] yy)
-        {
-            for (int i = 11; i >= 0; --i)
-            {
-                uint xx_i = xx[i], yy_i = yy[i];
-                if (xx_i < yy_i)
-                    return false;
-                if (xx_i > yy_i)
-                    return true;
-            }
-            return true;
-        }
-
         public static bool IsOne(uint[] x)
         {
             if (x[0] != 1)
@@ -276,18 +263,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return true;
         }
 
-        public static bool IsZeroExt(uint[] xx)
-        {
-            for (int i = 0; i < 12; ++i)
-            {
-                if (xx[i] != 0)
-                {
-                    return false;
-                }
-            }
-            return true;
-        }
-
         public static void Mul(uint[] x, uint[] y, uint[] zz)
         {
             ulong y_0 = y[0];
diff --git a/crypto/src/math/ec/custom/sec/Nat224.cs b/crypto/src/math/ec/custom/sec/Nat224.cs
index f8021b19a..62edc6baf 100644
--- a/crypto/src/math/ec/custom/sec/Nat224.cs
+++ b/crypto/src/math/ec/custom/sec/Nat224.cs
@@ -306,19 +306,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return true;
         }
 
-        public static bool GteExt(uint[] xx, uint[] yy)
-        {
-            for (int i = 13; i >= 0; --i)
-            {
-                uint xx_i = xx[i], yy_i = yy[i];
-                if (xx_i < yy_i)
-                    return false;
-                if (xx_i > yy_i)
-                    return true;
-            }
-            return true;
-        }
-
         public static bool IsOne(uint[] x)
         {
             if (x[0] != 1)
@@ -347,18 +334,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return true;
         }
 
-        public static bool IsZeroExt(uint[] xx)
-        {
-            for (int i = 0; i < 14; ++i)
-            {
-                if (xx[i] != 0)
-                {
-                    return false;
-                }
-            }
-            return true;
-        }
-
         public static void Mul(uint[] x, uint[] y, uint[] zz)
         {
             ulong y_0 = y[0];
diff --git a/crypto/src/math/ec/custom/sec/Nat256.cs b/crypto/src/math/ec/custom/sec/Nat256.cs
index 9c19f41ba..93501cd94 100644
--- a/crypto/src/math/ec/custom/sec/Nat256.cs
+++ b/crypto/src/math/ec/custom/sec/Nat256.cs
@@ -329,19 +329,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return true;
         }
 
-        public static bool GteExt(uint[] xx, uint[] yy)
-        {
-            for (int i = 15; i >= 0; --i)
-            {
-                uint xx_i = xx[i], yy_i = yy[i];
-                if (xx_i < yy_i)
-                    return false;
-                if (xx_i > yy_i)
-                    return true;
-            }
-            return true;
-        }
-
         public static bool IsOne(uint[] x)
         {
             if (x[0] != 1)
@@ -370,18 +357,6 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return true;
         }
 
-        public static bool IsZeroExt(uint[] xx)
-        {
-            for (int i = 0; i < 16; ++i)
-            {
-                if (xx[i] != 0)
-                {
-                    return false;
-                }
-            }
-            return true;
-        }
-
         public static void Mul(uint[] x, uint[] y, uint[] zz)
         {
             ulong y_0 = y[0];
diff --git a/crypto/src/math/ec/custom/sec/SecP192K1Field.cs b/crypto/src/math/ec/custom/sec/SecP192K1Field.cs
index 8ce5619a0..6f6f28f91 100644
--- a/crypto/src/math/ec/custom/sec/SecP192K1Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecP192K1Field.cs
@@ -27,7 +27,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
         public static void AddExt(uint[] xx, uint[] yy, uint[] zz)
         {
             uint c = Nat.Add(12, xx, yy, zz);
-            if (c != 0 || (zz[11] == PExt11 && Nat192.GteExt(zz, PExt)))
+            if (c != 0 || (zz[11] == PExt11 && Nat.Gte(12, zz, PExt)))
             {
                 if (Nat.AddTo(PExtInv.Length, PExtInv, zz) != 0)
                 {
diff --git a/crypto/src/math/ec/custom/sec/SecP192R1Field.cs b/crypto/src/math/ec/custom/sec/SecP192R1Field.cs
index 8e2aad5af..add8dd410 100644
--- a/crypto/src/math/ec/custom/sec/SecP192R1Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecP192R1Field.cs
@@ -26,7 +26,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
         public static void AddExt(uint[] xx, uint[] yy, uint[] zz)
         {
             uint c = Nat.Add(12, xx, yy, zz);
-            if (c != 0 || (zz[11] == PExt11 && Nat192.GteExt(zz, PExt)))
+            if (c != 0 || (zz[11] == PExt11 && Nat.Gte(12, zz, PExt)))
             {
                 if (Nat.AddTo(PExtInv.Length, PExtInv, zz) != 0)
                 {
diff --git a/crypto/src/math/ec/custom/sec/SecP224K1Field.cs b/crypto/src/math/ec/custom/sec/SecP224K1Field.cs
index 57fd1179a..89eb6258e 100644
--- a/crypto/src/math/ec/custom/sec/SecP224K1Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecP224K1Field.cs
@@ -28,7 +28,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
         public static void AddExt(uint[] xx, uint[] yy, uint[] zz)
         {
             uint c = Nat.Add(14, xx, yy, zz);
-            if (c != 0 || (zz[13] == PExt13 && Nat224.GteExt(zz, PExt)))
+            if (c != 0 || (zz[13] == PExt13 && Nat.Gte(14, zz, PExt)))
             {
                 if (Nat.AddTo(PExtInv.Length, PExtInv, zz) != 0)
                 {
diff --git a/crypto/src/math/ec/custom/sec/SecP224R1Field.cs b/crypto/src/math/ec/custom/sec/SecP224R1Field.cs
index 8ffc9aa65..9b29ff3d1 100644
--- a/crypto/src/math/ec/custom/sec/SecP224R1Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecP224R1Field.cs
@@ -26,7 +26,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
         public static void AddExt(uint[] xx, uint[] yy, uint[] zz)
         {
             uint c = Nat.Add(14, xx, yy, zz);
-            if (c != 0 || (zz[13] == PExt13 && Nat224.GteExt(zz, PExt)))
+            if (c != 0 || (zz[13] == PExt13 && Nat.Gte(14, zz, PExt)))
             {
                 if (Nat.AddTo(PExtInv.Length, PExtInv, zz) != 0)
                 {
diff --git a/crypto/src/math/ec/custom/sec/SecP256K1Field.cs b/crypto/src/math/ec/custom/sec/SecP256K1Field.cs
index aa82013b2..42564fd4f 100644
--- a/crypto/src/math/ec/custom/sec/SecP256K1Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecP256K1Field.cs
@@ -29,7 +29,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
         public static void AddExt(uint[] xx, uint[] yy, uint[] zz)
         {
             uint c = Nat.Add(16, xx, yy, zz);
-            if (c != 0 || (zz[15] == PExt15 && Nat256.GteExt(zz, PExt)))
+            if (c != 0 || (zz[15] == PExt15 && Nat.Gte(16, zz, PExt)))
             {
                 if (Nat.AddTo(PExtInv.Length, PExtInv, zz) != 0)
                 {
diff --git a/crypto/src/math/ec/custom/sec/SecP256R1Field.cs b/crypto/src/math/ec/custom/sec/SecP256R1Field.cs
index de383046d..cd4702f16 100644
--- a/crypto/src/math/ec/custom/sec/SecP256R1Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecP256R1Field.cs
@@ -14,6 +14,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
         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;
 
         public static void Add(uint[] x, uint[] y, uint[] z)
         {
@@ -27,7 +28,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
         public static void AddExt(uint[] xx, uint[] yy, uint[] zz)
         {
             uint c = Nat.Add(16, xx, yy, zz);
-            if (c != 0 || Nat256.GteExt(zz, PExt))
+            if (c != 0 || (zz[15] >= PExt15 && Nat.Gte(16, zz, PExt)))
             {
                 Nat.SubFrom(16, PExt, zz);
             }