Improve reduction speed for secp192k1 and secp256k1 custom fields

4 files changed, 126 insertions, 16 deletions

diff --git a/crypto/src/math/ec/custom/sec/Nat192.cs b/crypto/src/math/ec/custom/sec/Nat192.cs
index 55e684cc2..b61c7a468 100644
--- a/crypto/src/math/ec/custom/sec/Nat192.cs
+++ b/crypto/src/math/ec/custom/sec/Nat192.cs
@@ -321,6 +321,40 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             }
         }
 
+        public static ulong Mul33AddExt(uint x, uint[] yy, int yyOff, uint[] zz, int zzOff)
+        {
+            Debug.Assert(x >> 31 == 0);
+            Debug.Assert(yyOff <= 6);
+            Debug.Assert(zzOff <= 6);
+            ulong c = 0, xVal = x;
+            ulong yy00 = yy[yyOff + 0];
+            c += xVal * yy00 + zz[zzOff + 0];
+            zz[zzOff + 0] = (uint)c;
+            c >>= 32;
+            ulong yy01 = yy[yyOff + 1];
+            c += xVal * yy01 + yy00 + zz[zzOff + 1];
+            zz[zzOff + 1] = (uint)c;
+            c >>= 32;
+            ulong yy02 = yy[yyOff + 2];
+            c += xVal * yy02 + yy01 + zz[zzOff + 2];
+            zz[zzOff + 2] = (uint)c;
+            c >>= 32;
+            ulong yy03 = yy[yyOff + 3];
+            c += xVal * yy03 + yy02 + zz[zzOff + 3];
+            zz[zzOff + 3] = (uint)c;
+            c >>= 32;
+            ulong yy04 = yy[yyOff + 4];
+            c += xVal * yy04 + yy03 + zz[zzOff + 4];
+            zz[zzOff + 4] = (uint)c;
+            c >>= 32;
+            ulong yy05 = yy[yyOff + 5];
+            c += xVal * yy05 + yy04 + zz[zzOff + 5];
+            zz[zzOff + 5] = (uint)c;
+            c >>= 32;
+            c += yy05;
+            return c;
+        }
+
         public static uint MulWordAddExt(uint x, uint[] yy, int yyOff, uint[] zz, int zzOff)
         {
             Debug.Assert(yyOff <= 6);
@@ -347,6 +381,28 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return (uint)c;
         }
 
+        public static uint Mul33DWordAdd(uint x, ulong y, uint[] z, int zOff)
+        {
+            Debug.Assert(x >> 31 == 0);
+            Debug.Assert(zOff < 2);
+            ulong c = 0, xVal = x;
+            ulong y00 = y & M;
+            c += xVal * y00 + z[zOff + 0];
+            z[zOff + 0] = (uint)c;
+            c >>= 32;
+            ulong y01 = y >> 32;
+            c += xVal * y01 + y00 + z[zOff + 1];
+            z[zOff + 1] = (uint)c;
+            c >>= 32;
+            c += y01 + z[zOff + 2];
+            z[zOff + 2] = (uint)c;
+            c >>= 32;
+            c += z[zOff + 3];
+            z[zOff + 3] = (uint)c;
+            c >>= 32;
+            return c == 0 ? 0 : Inc(z, zOff + 4);
+        }
+
         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 12a860bf1..c71bc8322 100644
--- a/crypto/src/math/ec/custom/sec/Nat256.cs
+++ b/crypto/src/math/ec/custom/sec/Nat256.cs
@@ -353,6 +353,48 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             }
         }
 
+        public static ulong Mul33AddExt(uint x, uint[] yy, int yyOff, uint[] zz, int zzOff)
+        {
+            Debug.Assert(x >> 31 == 0);
+            Debug.Assert(yyOff <= 8);
+            Debug.Assert(zzOff <= 8);
+            ulong c = 0, xVal = x;
+            ulong yy00 = yy[yyOff + 0];
+            c += xVal * yy00 + zz[zzOff + 0];
+            zz[zzOff + 0] = (uint)c;
+            c >>= 32;
+            ulong yy01 = yy[yyOff + 1];
+            c += xVal * yy01 + yy00 + zz[zzOff + 1];
+            zz[zzOff + 1] = (uint)c;
+            c >>= 32;
+            ulong yy02 = yy[yyOff + 2];
+            c += xVal * yy02 + yy01 + zz[zzOff + 2];
+            zz[zzOff + 2] = (uint)c;
+            c >>= 32;
+            ulong yy03 = yy[yyOff + 3];
+            c += xVal * yy03 + yy02 + zz[zzOff + 3];
+            zz[zzOff + 3] = (uint)c;
+            c >>= 32;
+            ulong yy04 = yy[yyOff + 4];
+            c += xVal * yy04 + yy03 + zz[zzOff + 4];
+            zz[zzOff + 4] = (uint)c;
+            c >>= 32;
+            ulong yy05 = yy[yyOff + 5];
+            c += xVal * yy05 + yy04 + zz[zzOff + 5];
+            zz[zzOff + 5] = (uint)c;
+            c >>= 32;
+            ulong yy06 = yy[yyOff + 6];
+            c += xVal * yy06 + yy05 + zz[zzOff + 6];
+            zz[zzOff + 6] = (uint)c;
+            c >>= 32;
+            ulong yy07 = yy[yyOff + 7];
+            c += xVal * yy07 + yy06 + zz[zzOff + 7];
+            zz[zzOff + 7] = (uint)c;
+            c >>= 32;
+            c += yy07;
+            return c;
+        }
+
         public static uint MulWordAddExt(uint x, uint[] yy, int yyOff, uint[] zz, int zzOff)
         {
             Debug.Assert(yyOff <= 8);
@@ -385,6 +427,28 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             return (uint)c;
         }
 
+        public static uint Mul33DWordAdd(uint x, ulong y, uint[] z, int zOff)
+        {
+            Debug.Assert(x >> 31 == 0);
+            Debug.Assert(zOff < 4);
+            ulong c = 0, xVal = x;
+            ulong y00 = y & M;
+            c += xVal * y00 + z[zOff + 0];
+            z[zOff + 0] = (uint)c;
+            c >>= 32;
+            ulong y01 = y >> 32;
+            c += xVal * y01 + y00 + z[zOff + 1];
+            z[zOff + 1] = (uint)c;
+            c >>= 32;
+            c += y01 + z[zOff + 2];
+            z[zOff + 2] = (uint)c;
+            c >>= 32;
+            c += z[zOff + 3];
+            z[zOff + 3] = (uint)c;
+            c >>= 32;
+            return c == 0 ? 0 : Inc(z, zOff + 4);
+        }
+
         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 30c107c86..9da3c0257 100644
--- a/crypto/src/math/ec/custom/sec/SecP192K1Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecP192K1Field.cs
@@ -12,7 +12,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             0x00000000, 0xFFFFDC6E, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF };
         private const uint PExt11 = 0xFFFFFFFF;
         private const ulong PInv = 0x00000001000011C9L;
-        private const uint PInvLow = 0x11C9;
+        private const uint PInv33 = 0x11C9;
 
         public static void Add(uint[] x, uint[] y, uint[] z)
         {
@@ -86,13 +86,8 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
 
         public static void Reduce(uint[] tt, uint[] z)
         {
-            long extra = -(long)tt[6];
-            extra += (long)Nat192.MulWordAddExt(PInvLow, tt, 6, tt, 0);
-            extra += (long)Nat192.AddToExt(tt, 6, tt, 1) << 32;
-            extra += (long)tt[6];
-
-            ulong c = Nat192.MulWordDwordAdd(PInvLow, (ulong)extra, tt, 0);
-            c += Nat192.AddDWord((ulong)extra, tt, 1);
+            ulong c = Nat192.Mul33AddExt(PInv33, tt, 6, tt, 0);
+            c = Nat192.Mul33DWordAdd(PInv33, c, tt, 0);
 
             Debug.Assert(c == 0 || c == 1);
 
diff --git a/crypto/src/math/ec/custom/sec/SecP256K1Field.cs b/crypto/src/math/ec/custom/sec/SecP256K1Field.cs
index 6fe575b38..e7a73359f 100644
--- a/crypto/src/math/ec/custom/sec/SecP256K1Field.cs
+++ b/crypto/src/math/ec/custom/sec/SecP256K1Field.cs
@@ -14,7 +14,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
             0xFFFFFFFF, 0xFFFFFFFF };
         private const uint PExt15 = 0xFFFFFFFF;
         private const ulong PInv = 0x00000001000003D1UL;
-        private const uint PInvLow = 0x3D1;
+        private const uint PInv33 = 0x3D1;
 
         public static void Add(uint[] x, uint[] y, uint[] z)
         {
@@ -88,13 +88,8 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec
 
         public static void Reduce(uint[] tt, uint[] z)
         {
-            long extra = -(long)tt[8];
-            extra += (long)Nat256.MulWordAddExt(PInvLow, tt, 8, tt, 0);
-            extra += (long)Nat256.AddToExt(tt, 8, tt, 1) << 32;
-            extra += (long)tt[8];
-
-            ulong c = Nat256.MulWordDwordAdd(PInvLow, (ulong)extra, tt, 0);
-            c += Nat256.AddDWord((ulong)extra, tt, 1);
+            ulong c = Nat256.Mul33AddExt(PInv33, tt, 8, tt, 0);
+            c = Nat256.Mul33DWordAdd(PInv33, c, tt, 0);
 
             Debug.Assert(c == 0 || c == 1);