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

Reduction improvements in curve25519 and secp256r1

11 files changed, 71 insertions, 87 deletions

diff --git a/core/src/main/java/org/bouncycastle/math/ec/Nat.java b/core/src/main/java/org/bouncycastle/math/ec/Nat.java
index 812731b3..9f85e8bc 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/Nat.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/Nat.java
@@ -436,6 +436,33 @@ public abstract class Nat
         }
     }
 
+    public static int mulAddTo(int len, int[] x, int[] y, int[] zz)
+    {
+        long zc = 0;
+        for (int i = 0; i < len; ++i)
+        {
+            long c = mulWordAddTo(len, x[i], y, 0, zz, i) & M;
+            c += zc + (zz[i + len] & M);
+            zz[i + len] = (int)c;
+            zc = c >>> 32;
+        }
+        return (int)zc;
+    }
+
+    public static int mulAddTo(int len, int[] x, int xOff, int[] y, int yOff, int[] zz, int zzOff)
+    {
+        long zc = 0;
+        for (int i = 0; i < len; ++i)
+        {
+            long c = mulWordAddTo(len, x[xOff + i], y, yOff, zz, zzOff) & M;
+            c += zc + (zz[zzOff + len] & M);
+            zz[zzOff + len] = (int)c;
+            zc = c >>> 32;
+            ++zzOff;
+        }
+        return (int)zc;
+    }
+
     public static int mul31BothAdd(int len, int a, int[] x, int b, int[] y, int[] z, int zOff)
     {
         long c = 0, aVal = a & M, bVal = b & M;
diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/Curve25519Field.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/Curve25519Field.java
index 2dc3e5e1..05691931 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/Curve25519Field.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/Curve25519Field.java
@@ -29,9 +29,9 @@ public class Curve25519Field
     public static void addExt(int[] xx, int[] yy, int[] 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);
         }
     }
 
@@ -139,7 +139,7 @@ public class Curve25519Field
         int c = Nat.sub(16, xx, yy, zz);
         if (c != 0)
         {
-            Nat.addTo(16, PExt, zz);
+            addPExtTo(zz);
         }
     }
 
@@ -152,6 +152,40 @@ public class Curve25519Field
         }
     }
 
+    private static void addPExtTo(int[] zz)
+    {
+        long c = (zz[0] & M) + (PExt[0] & M);
+        zz[0] = (int)c;
+        c >>= 32;
+
+        int i = 1 - (int)c;
+        i = (i << 3) - i;
+
+        while (++i < 16)
+        {
+            c += (zz[i] & M) + (PExt[i] & M);
+            zz[i] = (int)c;
+            c >>= 32;
+        }
+    }
+
+    private static void subPExtFrom(int[] zz)
+    {
+        long c = (zz[0] & M) - (PExt[0] & M);
+        zz[0] = (int)c;
+        c >>= 32;
+
+        int i = 1 + (int)c;
+        i = (i << 3) - i;
+
+        while (++i < 16)
+        {
+            c += (zz[i] & M) - (PExt[i] & M);
+            zz[i] = (int)c;
+            c >>= 32;
+        }
+    }
+
     private static void addPInvTo(int[] z)
     {
         long c = (z[0] & M) + PInv;
diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/Nat192.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/Nat192.java
index 96a8a1b4..f080cc27 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/Nat192.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/Nat192.java
@@ -241,20 +241,6 @@ public abstract class Nat192
         return true;
     }
 
-    public static boolean gteExt(int[] xx, int[] yy)
-    {
-        for (int i = 11; i >= 0; --i)
-        {
-            int xx_i = xx[i] ^ Integer.MIN_VALUE;
-            int yy_i = yy[i] ^ Integer.MIN_VALUE;
-            if (xx_i < yy_i)
-                return false;
-            if (xx_i > yy_i)
-                return true;
-        }
-        return true;
-    }
-
     public static boolean isOne(int[] x)
     {
         if (x[0] != 1)
@@ -283,18 +269,6 @@ public abstract class Nat192
         return true;
     }
 
-    public static boolean isZeroExt(int[] xx)
-    {
-        for (int i = 0; i < 12; ++i)
-        {
-            if (xx[i] != 0)
-            {
-                return false;
-            }
-        }
-        return true;
-    }
-
     public static void mul(int[] x, int[] y, int[] zz)
     {
         long y_0 = y[0] & M;
diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/Nat224.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/Nat224.java
index 7b6d3bef..8bdb5be6 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/Nat224.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/Nat224.java
@@ -312,20 +312,6 @@ public abstract class Nat224
         return true;
     }
 
-    public static boolean gteExt(int[] xx, int[] yy)
-    {
-        for (int i = 13; i >= 0; --i)
-        {
-            int xx_i = xx[i] ^ Integer.MIN_VALUE;
-            int yy_i = yy[i] ^ Integer.MIN_VALUE;
-            if (xx_i < yy_i)
-                return false;
-            if (xx_i > yy_i)
-                return true;
-        }
-        return true;
-    }
-
     public static boolean isOne(int[] x)
     {
         if (x[0] != 1)
@@ -354,18 +340,6 @@ public abstract class Nat224
         return true;
     }
 
-    public static boolean isZeroExt(int[] xx)
-    {
-        for (int i = 0; i < 14; ++i)
-        {
-            if (xx[i] != 0)
-            {
-                return false;
-            }
-        }
-        return true;
-    }
-
     public static void mul(int[] x, int[] y, int[] zz)
     {
         long y_0 = y[0] & M;
diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/Nat256.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/Nat256.java
index 8929d6ee..4bbc687f 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/Nat256.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/Nat256.java
@@ -335,20 +335,6 @@ public abstract class Nat256
         return true;
     }
 
-    public static boolean gteExt(int[] xx, int[] yy)
-    {
-        for (int i = 15; i >= 0; --i)
-        {
-            int xx_i = xx[i] ^ Integer.MIN_VALUE;
-            int yy_i = yy[i] ^ Integer.MIN_VALUE;
-            if (xx_i < yy_i)
-                return false;
-            if (xx_i > yy_i)
-                return true;
-        }
-        return true;
-    }
-
     public static boolean isOne(int[] x)
     {
         if (x[0] != 1)
@@ -377,18 +363,6 @@ public abstract class Nat256
         return true;
     }
 
-    public static boolean isZeroExt(int[] xx)
-    {
-        for (int i = 0; i < 16; ++i)
-        {
-            if (xx[i] != 0)
-            {
-                return false;
-            }
-        }
-        return true;
-    }
-
     public static void mul(int[] x, int[] y, int[] zz)
     {
         long y_0 = y[0] & M;
diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192K1Field.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192K1Field.java
index 135f4add..38ec656d 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192K1Field.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192K1Field.java
@@ -28,7 +28,7 @@ public class SecP192K1Field
     public static void addExt(int[] xx, int[] yy, int[] zz)
     {
         int 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/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192R1Field.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192R1Field.java
index ef8b5c25..f7548708 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192R1Field.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192R1Field.java
@@ -29,7 +29,7 @@ public class SecP192R1Field
     public static void addExt(int[] xx, int[] yy, int[] zz)
     {
         int 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/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224K1Field.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224K1Field.java
index 65766e0a..ef752419 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224K1Field.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224K1Field.java
@@ -29,7 +29,7 @@ public class SecP224K1Field
     public static void addExt(int[] xx, int[] yy, int[] zz)
     {
         int 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/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1Field.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1Field.java
index 29219a8e..19f88cfb 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1Field.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1Field.java
@@ -29,7 +29,7 @@ public class SecP224R1Field
     public static void addExt(int[] xx, int[] yy, int[] zz)
     {
         int 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/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1Field.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1Field.java
index 76e12ed8..c09e5bc7 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1Field.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1Field.java
@@ -30,7 +30,7 @@ public class SecP256K1Field
     public static void addExt(int[] xx, int[] yy, int[] zz)
     {
         int 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/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1Field.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1Field.java
index 3cf1c33d..ec388239 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1Field.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1Field.java
@@ -17,6 +17,7 @@ public class SecP256R1Field
     private static final int[] _2P = new int[]{ 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001, 0x00000000, 0x00000000,
         0x00000002, 0xFFFFFFFE, 0x00000001 };
     private static final int P7 = 0xFFFFFFFF;
+    private static final int PExt15 = 0xFFFFFFFF;
 
     public static void add(int[] x, int[] y, int[] z)
     {
@@ -30,7 +31,7 @@ public class SecP256R1Field
     public static void addExt(int[] xx, int[] yy, int[] zz)
     {
         int c = Nat.add(16, xx, yy, zz);
-        if (c != 0 || Nat256.gteExt(zz, PExt))
+        if (c != 0 || ((zz[15] & PExt15) == PExt15 && Nat.gte(16, zz, PExt)))
         {
             Nat.subFrom(16, PExt, zz);
         }