Optimization for custom curve reduction when only a few bits need

reducing; used to delay reduction in point doubling.

15 files changed, 214 insertions, 30 deletions

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 a0de05ab..03f2814d 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
@@ -107,6 +107,15 @@ public abstract class Nat192
         return (int)c;
     }
 
+    public static int addWord(int x, int[] z, int zOff)
+    {
+        // assert zzOff <= 5;
+        long c = (x & M) + (z[zOff + 0] & M);
+        z[zOff + 0] = (int)c;
+        c >>>= 32;
+        return c == 0 ? 0 : inc(z, zOff + 1);
+    }
+
     public static int addWordExt(int x, int[] zz, int zzOff)
     {
         // assert zzOff <= 11;
@@ -139,6 +148,19 @@ public abstract class Nat192
         return -1;
     }
 
+    public static int decExt(int[] z, int zOff)
+    {
+        // assert zOff <= 12;
+        for (int i = zOff; i < 12; ++i)
+        {
+            if (--z[i] != -1)
+            {
+                return 0;
+            }
+        }
+        return -1;
+    }
+
     public static int[] fromBigInteger(BigInteger x)
     {
         if (x.signum() < 0 || x.bitLength() > 192)
@@ -404,6 +426,24 @@ public abstract class Nat192
         return c == 0 ? 0 : inc(z, zOff + 4);
     }
 
+    public static int mul33WordAdd(int x, int y, int[] z, int zOff)
+    {
+        // assert x >>> 31 == 0;
+        // assert zOff <= 3;
+
+        long c = 0, xVal = x & M, yVal = y & M;
+        c += yVal * xVal + (z[zOff + 0] & M);
+        z[zOff + 0] = (int)c;
+        c >>>= 32;
+        c += yVal + (z[zOff + 1] & M);
+        z[zOff + 1] = (int)c;
+        c >>>= 32;
+        c += (z[zOff + 2] & M);
+        z[zOff + 2] = (int)c;
+        c >>>= 32;
+        return c == 0 ? 0 : inc(z, zOff + 3);
+    }
+
     public static int mulWordDwordAdd(int x, long y, int[] z, int zOff)
     {
         // assert zOff <= 3;
@@ -698,6 +738,24 @@ public abstract class Nat192
         return (int)c;
     }
 
+    public static int subWord(int x, int[] z, int zOff)
+    {
+        // assert zOff <= 5;
+        long c = (z[zOff + 0] & M) - (x & M);
+        z[zOff + 0] = (int)c;
+        c >>= 32;
+        return c == 0 ? 0 : dec(z, zOff + 1);
+    }
+
+    public static int subWordExt(int x, int[] zz, int zzOff)
+    {
+        // assert zzOff <= 11;
+        long c = (zz[zzOff + 0] & M) - (x & M);
+        zz[zzOff + 0] = (int)c;
+        c >>= 32;
+        return c == 0 ? 0 : decExt(zz, zzOff + 1);
+    }
+
     public static BigInteger toBigInteger(int[] x)
     {
         byte[] bs = new byte[24];
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 3bb3518e..4fa0b95e 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
@@ -735,6 +735,24 @@ public abstract class Nat224
         return c == 0 ? 0 : inc(z, zOff + 4);
     }
 
+    public static int mul33WordAdd(int x, int y, int[] z, int zOff)
+    {
+        // assert x >>> 31 == 0;
+        // assert zOff <= 4;
+
+        long c = 0, xVal = x & M, yVal = y & M;
+        c += yVal * xVal + (z[zOff + 0] & M);
+        z[zOff + 0] = (int)c;
+        c >>>= 32;
+        c += yVal + (z[zOff + 1] & M);
+        z[zOff + 1] = (int)c;
+        c >>>= 32;
+        c += (z[zOff + 2] & M);
+        z[zOff + 2] = (int)c;
+        c >>>= 32;
+        return c == 0 ? 0 : inc(z, zOff + 3);
+    }
+
     public static int mulWordDwordAdd(int x, long y, int[] z, int zOff)
     {
         // assert zOff <= 4;
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 e5a820e6..f974135a 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
@@ -786,6 +786,24 @@ public abstract class Nat256
         return c == 0 ? 0 : inc(z, zOff + 4);
     }
 
+    public static int mul33WordAdd(int x, int y, int[] z, int zOff)
+    {
+        // assert x >>> 31 == 0;
+        // assert zOff <= 5;
+
+        long c = 0, xVal = x & M, yVal = y & M;
+        c += yVal * xVal + (z[zOff + 0] & M);
+        z[zOff + 0] = (int)c;
+        c >>>= 32;
+        c += yVal + (z[zOff + 1] & M);
+        z[zOff + 1] = (int)c;
+        c >>>= 32;
+        c += (z[zOff + 2] & M);
+        z[zOff + 2] = (int)c;
+        c >>>= 32;
+        return c == 0 ? 0 : inc(z, zOff + 3);
+    }
+
     public static int mulWordDwordAdd(int x, long y, int[] z, int zOff)
     {
         // assert zOff <= 5;
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 0bd5a384..f4f60d58 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
@@ -96,6 +96,18 @@ public class SecP192K1Field
         }
     }
 
+    public static void reduce32(int x, int[] z)
+    {
+        int c = Nat192.mul33WordAdd(PInv33, x, z, 0);
+
+        // assert c == 0L || c == 1L;
+
+        if (c != 0 || (z[5] == P5 && Nat192.gte(z, P)))
+        {
+            Nat192.addDWord(PInv, z, 0);
+        }
+    }
+
     public static void square(int[] x, int[] z)
     {
         int[] tt = Nat192.createExt();
diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192K1Point.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192K1Point.java
index da9e5e24..44f8c7fe 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192K1Point.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192K1Point.java
@@ -3,6 +3,7 @@ package org.bouncycastle.math.ec.custom.sec;
 import org.bouncycastle.math.ec.ECCurve;
 import org.bouncycastle.math.ec.ECFieldElement;
 import org.bouncycastle.math.ec.ECPoint;
+import org.bouncycastle.math.ec.Nat;
 
 public class SecP192K1Point extends ECPoint
 {
@@ -225,12 +226,11 @@ public class SecP192K1Point extends ECPoint
 
         int[] S = Y1Squared;
         SecP192K1Field.multiply(Y1Squared, X1.x, S);
-        SecP192K1Field.twice(S, S);
-        SecP192K1Field.twice(S, S);
+        int 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/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 02d0b72e..6b5db1d9 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
@@ -131,6 +131,15 @@ public class SecP192R1Field
         }
     }
 
+    public static void reduce32(int x, int[] z)
+    {
+        int 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(int[] x, int[] z)
     {
         int[] tt = Nat192.createExt();
diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192R1Point.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192R1Point.java
index fb62217d..49116119 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192R1Point.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192R1Point.java
@@ -3,6 +3,7 @@ package org.bouncycastle.math.ec.custom.sec;
 import org.bouncycastle.math.ec.ECCurve;
 import org.bouncycastle.math.ec.ECFieldElement;
 import org.bouncycastle.math.ec.ECPoint;
+import org.bouncycastle.math.ec.Nat;
 
 public class SecP192R1Point extends ECPoint
 {
@@ -237,12 +238,11 @@ public class SecP192R1Point extends ECPoint
 
         int[] S = Y1Squared;
         SecP192R1Field.multiply(Y1Squared, X1.x, S);
-        SecP192R1Field.twice(S, S);
-        SecP192R1Field.twice(S, S);
+        int 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/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 a6b6eb82..d5cd4072 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
@@ -97,6 +97,18 @@ public class SecP224K1Field
         }
     }
 
+    public static void reduce32(int x, int[] z)
+    {
+        int c = Nat224.mul33WordAdd(PInv33, x, z, 0);
+
+        // assert c == 0L || c == 1L;
+
+        if (c != 0 || (z[6] == P6 && Nat224.gte(z, P)))
+        {
+            Nat224.addDWord(PInv, z, 0);
+        }
+    }
+
     public static void square(int[] x, int[] z)
     {
         int[] tt = Nat224.createExt();
diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224K1Point.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224K1Point.java
index 30dc6bc8..d5eb8294 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224K1Point.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224K1Point.java
@@ -3,6 +3,7 @@ package org.bouncycastle.math.ec.custom.sec;
 import org.bouncycastle.math.ec.ECCurve;
 import org.bouncycastle.math.ec.ECFieldElement;
 import org.bouncycastle.math.ec.ECPoint;
+import org.bouncycastle.math.ec.Nat;
 
 public class SecP224K1Point extends ECPoint
 {
@@ -225,12 +226,11 @@ public class SecP224K1Point extends ECPoint
 
         int[] S = Y1Squared;
         SecP224K1Field.multiply(Y1Squared, X1.x, S);
-        SecP224K1Field.twice(S, S);
-        SecP224K1Field.twice(S, S);
+        int 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/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 af0b3320..d828b71c 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
@@ -138,6 +138,15 @@ public class SecP224R1Field
         }
     }
 
+    public static void reduce32(int x, int[] z)
+    {
+        int c = Nat224.subWord(x, z, 0) + Nat224.addWord(x, z, 3);
+        if (c != 0 || (z[6] == P6 && Nat224.gte(z, P)))
+        {
+            Nat224.sub(z, P, z);
+        }
+    }
+
     public static void square(int[] x, int[] z)
     {
         int[] tt = Nat224.createExt();
diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1Point.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1Point.java
index 57cd4272..177b2fec 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1Point.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1Point.java
@@ -3,6 +3,7 @@ package org.bouncycastle.math.ec.custom.sec;
 import org.bouncycastle.math.ec.ECCurve;
 import org.bouncycastle.math.ec.ECFieldElement;
 import org.bouncycastle.math.ec.ECPoint;
+import org.bouncycastle.math.ec.Nat;
 
 public class SecP224R1Point extends ECPoint
 {
@@ -235,12 +236,11 @@ public class SecP224R1Point extends ECPoint
 
         int[] S = Y1Squared;
         SecP224R1Field.multiply(Y1Squared, X1.x, S);
-        SecP224R1Field.twice(S, S);
-        SecP224R1Field.twice(S, S);
+        int 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/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 b3fbeb56..bf9ec919 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
@@ -98,6 +98,18 @@ public class SecP256K1Field
         }
     }
 
+    public static void reduce32(int x, int[] z)
+    {
+        int c = Nat256.mul33WordAdd(PInv33, x, z, 0);
+
+        // assert c == 0L || c == 1L;
+
+        if (c != 0 || (z[7] == P7 && Nat256.gte(z, P)))
+        {
+            Nat256.addDWord(PInv, z, 0);
+        }
+    }
+
     public static void square(int[] x, int[] z)
     {
         int[] tt = Nat256.createExt();
diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1Point.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1Point.java
index f1d07cad..d6a42694 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1Point.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1Point.java
@@ -3,6 +3,7 @@ package org.bouncycastle.math.ec.custom.sec;
 import org.bouncycastle.math.ec.ECCurve;
 import org.bouncycastle.math.ec.ECFieldElement;
 import org.bouncycastle.math.ec.ECPoint;
+import org.bouncycastle.math.ec.Nat;
 
 public class SecP256K1Point extends ECPoint
 {
@@ -225,12 +226,11 @@ public class SecP256K1Point extends ECPoint
 
         int[] S = Y1Squared;
         SecP256K1Field.multiply(Y1Squared, X1.x, S);
-        SecP256K1Field.twice(S, S);
-        SecP256K1Field.twice(S, S);
+        int 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/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 21ecc226..9fee3adf 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
@@ -146,6 +146,42 @@ public class SecP256R1Field
         }
     }
 
+    public static void reduce32(int x, int[] z)
+    {
+        long xx08 = x & M;
+
+        long cc = 0;
+        cc += (z[0] & M) + xx08;
+        z[0] = (int)cc;
+        cc >>= 32;
+        cc += (z[1] & M);
+        z[1] = (int)cc;
+        cc >>= 32;
+        cc += (z[2] & M);
+        z[2] = (int)cc;
+        cc >>= 32;
+        cc += (z[3] & M) - xx08;
+        z[3] = (int)cc;
+        cc >>= 32;
+        cc += (z[4] & M);
+        z[4] = (int)cc;
+        cc >>= 32;
+        cc += (z[5] & M);
+        z[5] = (int)cc;
+        cc >>= 32;
+        cc += (z[6] & M) - xx08;
+        z[6] = (int)cc;
+        cc >>= 32;
+        cc += (z[7] & M) + xx08;
+        z[7] = (int)cc;
+        cc >>= 32;
+
+        if (cc != 0 || (z[7] == P7 && Nat256.gte(z, P)))
+        {
+            Nat256.sub(z, P, z);
+        }
+    }
+
     public static void square(int[] x, int[] z)
     {
         int[] tt = Nat256.createExt();
diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1Point.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1Point.java
index fe971c27..acabefe3 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1Point.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1Point.java
@@ -3,6 +3,7 @@ package org.bouncycastle.math.ec.custom.sec;
 import org.bouncycastle.math.ec.ECCurve;
 import org.bouncycastle.math.ec.ECFieldElement;
 import org.bouncycastle.math.ec.ECPoint;
+import org.bouncycastle.math.ec.Nat;
 
 public class SecP256R1Point extends ECPoint
 {
@@ -235,12 +236,11 @@ public class SecP256R1Point extends ECPoint
 
         int[] S = Y1Squared;
         SecP256R1Field.multiply(Y1Squared, X1.x, S);
-        SecP256R1Field.twice(S, S);
-        SecP256R1Field.twice(S, S);
+        int 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);