'safegcd' modular inversion

2 files changed, 143 insertions, 13 deletions

diff --git a/crypto/src/math/ec/rfc7748/X25519Field.cs b/crypto/src/math/ec/rfc7748/X25519Field.cs
index 6843e274a..ffede563b 100644
--- a/crypto/src/math/ec/rfc7748/X25519Field.cs
+++ b/crypto/src/math/ec/rfc7748/X25519Field.cs
@@ -1,6 +1,8 @@
 using System;
 using System.Diagnostics;
 
+using Org.BouncyCastle.Math.Raw;
+
 namespace Org.BouncyCastle.Math.EC.Rfc7748
 {
     public abstract class X25519Field
@@ -11,6 +13,8 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
         private const int M25 = 0x01FFFFFF;
         private const int M26 = 0x03FFFFFF;
 
+        private static readonly uint[] P32 = new uint[]{ 0xFFFFFFEDU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU,
+            0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0x7FFFFFFFU };
         private static readonly int[] RootNegOne = { 0x020EA0B0, 0x0386C9D2, 0x00478C4E, 0x0035697F, 0x005E8630,
             0x01FBD7A7, 0x0340264F, 0x01F0B2B4, 0x00027E0E, 0x00570649 };
 
@@ -128,6 +132,14 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
             }
         }
 
+        [CLSCompliantAttribute(false)]
+        public static void Decode(uint[] x, int xOff, int[] z)
+        {
+            Decode128(x, xOff, z, 0);
+            Decode128(x, xOff + 4, z, 5);
+            z[9] &= M24;
+        }
+
         public static void Decode(byte[] x, int xOff, int[] z)
         {
             Decode128(x, xOff, z, 0);
@@ -135,6 +147,17 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
             z[9] &= M24;
         }
 
+        private static void Decode128(uint[] x, int xOff, int[] z, int zOff)
+        {
+            uint t0 = x[xOff + 0], t1 = x[xOff + 1], t2 = x[xOff + 2], t3 = x[xOff + 3];
+
+            z[zOff + 0] = (int)t0 & M26;
+            z[zOff + 1] = (int)((t1 <<  6) | (t0 >> 26)) & M26;
+            z[zOff + 2] = (int)((t2 << 12) | (t1 >> 20)) & M25;
+            z[zOff + 3] = (int)((t3 << 19) | (t2 >> 13)) & M26;
+            z[zOff + 4] = (int)(t3 >> 7);
+        }
+
         private static void Decode128(byte[] bs, int off, int[] z, int zOff)
         {
             uint t0 = Decode32(bs, off + 0);
@@ -158,12 +181,30 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
             return n;
         }
 
+        [CLSCompliantAttribute(false)]
+        public static void Encode(int[] x, uint[] z, int zOff)
+        {
+            Encode128(x, 0, z, zOff);
+            Encode128(x, 5, z, zOff + 4);
+        }
+
         public static void Encode(int[] x, byte[] z, int zOff)
         {
             Encode128(x, 0, z, zOff);
             Encode128(x, 5, z, zOff + 16);
         }
 
+        private static void Encode128(int[] x, int xOff, uint[] z, int zOff)
+        {
+            uint x0 = (uint)x[xOff + 0], x1 = (uint)x[xOff + 1], x2 = (uint)x[xOff + 2], x3 = (uint)x[xOff + 3],
+                x4 = (uint)x[xOff + 4];
+
+            z[zOff + 0] =  x0        | (x1 << 26);
+            z[zOff + 1] = (x1 >>  6) | (x2 << 20);
+            z[zOff + 2] = (x2 >> 12) | (x3 << 13);
+            z[zOff + 3] = (x3 >> 19) | (x4 <<  7);
+        }
+
         private static void Encode128(int[] x, int xOff, byte[] bs, int off)
         {
             uint x0 = (uint)x[xOff + 0], x1 = (uint)x[xOff + 1], x2 = (uint)x[xOff + 2];
@@ -185,15 +226,36 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
 
         public static void Inv(int[] x, int[] z)
         {
-            // z = x^(p-2) = x^7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEB
-            // (250 1s) (1 0s) (1 1s) (1 0s) (2 1s)
-            // Addition chain: [1] [2] 3 5 10 15 25 50 75 125 [250]
+            //int[] x2 = Create();
+            //int[] t = Create();
+            //PowPm5d8(x, x2, t);
+            //Sqr(t, 3, t);
+            //Mul(t, x2, z);
 
-            int[] x2 = Create();
             int[] t = Create();
-            PowPm5d8(x, x2, t);
-            Sqr(t, 3, t);
-            Mul(t, x2, z);
+            uint[] u = new uint[8];
+
+            Copy(x, 0, t, 0);
+            Normalize(t);
+            Encode(t, u, 0);
+
+            Mod.ModOddInverse(P32, u, u);
+
+            Decode(u, 0, z);
+        }
+
+        public static void InvVar(int[] x, int[] z)
+        {
+            int[] t = Create();
+            uint[] u = new uint[8];
+
+            Copy(x, 0, t, 0);
+            Normalize(t);
+            Encode(t, u, 0);
+
+            Mod.ModOddInverseVar(P32, u, u);
+
+            Decode(u, 0, z);
         }
 
         public static int IsZero(int[] x)
diff --git a/crypto/src/math/ec/rfc7748/X448Field.cs b/crypto/src/math/ec/rfc7748/X448Field.cs
index 240518cde..4d3be5cda 100644
--- a/crypto/src/math/ec/rfc7748/X448Field.cs
+++ b/crypto/src/math/ec/rfc7748/X448Field.cs
@@ -1,6 +1,8 @@
 using System;
 using System.Diagnostics;
 
+using Org.BouncyCastle.Math.Raw;
+
 namespace Org.BouncyCastle.Math.EC.Rfc7748
 {
     [CLSCompliantAttribute(false)]
@@ -10,6 +12,10 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
 
         private const uint M28 = 0x0FFFFFFFU;
 
+        private static readonly uint[] P32 = new uint[]{ 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU,
+            0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFEU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU, 0xFFFFFFFFU,
+            0xFFFFFFFFU, 0xFFFFFFFFU };
+
         protected X448Field() {}
 
         public static void Add(uint[] x, uint[] y, uint[] z)
@@ -129,6 +135,12 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
             }
         }
 
+        public static void Decode(uint[] x, int xOff, uint[] z)
+        {
+            Decode224(x, xOff, z, 0);
+            Decode224(x, xOff + 7, z, 8);
+        }
+
         public static void Decode(byte[] x, int xOff, uint[] z)
         {
             Decode56(x, xOff, z, 0);
@@ -141,6 +153,21 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
             Decode56(x, xOff + 49, z, 14);
         }
 
+        private static void Decode224(uint[] x, int xOff, uint[] z, int zOff)
+        {
+            uint x0 = x[xOff + 0], x1 = x[xOff + 1], x2 = x[xOff + 2], x3 = x[xOff + 3];
+            uint x4 = x[xOff + 4], x5 = x[xOff + 5], x6 = x[xOff + 6];
+
+            z[zOff + 0] = x0 & M28;
+            z[zOff + 1] = (x0 >> 28 | x1 <<  4) & M28;
+            z[zOff + 2] = (x1 >> 24 | x2 <<  8) & M28;
+            z[zOff + 3] = (x2 >> 20 | x3 << 12) & M28;
+            z[zOff + 4] = (x3 >> 16 | x4 << 16) & M28;
+            z[zOff + 5] = (x4 >> 12 | x5 << 20) & M28;
+            z[zOff + 6] = (x5 >>  8 | x6 << 24) & M28;
+            z[zOff + 7] = x6 >> 4;
+        }
+
         private static uint Decode24(byte[] bs, int off)
         {
             uint n = bs[off];
@@ -166,6 +193,12 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
             z[zOff + 1] = (lo >> 28) | (hi << 4);
         }
 
+        public static void Encode(uint[] x, uint[] z, int zOff)
+        {
+            Encode224(x, 0, z, zOff);
+            Encode224(x, 8, z, zOff + 7);
+        }
+
         public static void Encode(uint[] x, byte[] z, int zOff)
         {
             Encode56(x, 0, z, zOff);
@@ -178,6 +211,20 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
             Encode56(x, 14, z, zOff + 49);
         }
 
+        private static void Encode224(uint[] x, int xOff, uint[] z, int zOff)
+        {
+            uint x0 = x[xOff + 0], x1 = x[xOff + 1], x2 = x[xOff + 2], x3 = x[xOff + 3];
+            uint x4 = x[xOff + 4], x5 = x[xOff + 5], x6 = x[xOff + 6], x7 = x[xOff + 7];
+
+            z[zOff + 0] =  x0        | (x1 << 28);
+            z[zOff + 1] = (x1 >>  4) | (x2 << 24);
+            z[zOff + 2] = (x2 >>  8) | (x3 << 20);
+            z[zOff + 3] = (x3 >> 12) | (x4 << 16);
+            z[zOff + 4] = (x4 >> 16) | (x5 << 12);
+            z[zOff + 5] = (x5 >> 20) | (x6 <<  8);
+            z[zOff + 6] = (x6 >> 24) | (x7 <<  4);
+        }
+
         private static void Encode24(uint n, byte[] bs, int off)
         {
             bs[  off] = (byte)(n      );
@@ -202,14 +249,35 @@ namespace Org.BouncyCastle.Math.EC.Rfc7748
 
         public static void Inv(uint[] x, uint[] z)
         {
-            // z = x^(p-2) = x^(2^448 - 2^224 - 3)
-            // (223 1s) (1 0s) (222 1s) (1 0s) (1 1s)
-            // Addition chain: [1] 2 3 6 9 18 19 37 74 111 [222] [223]
+            //uint[] t = Create();
+            //PowPm3d4(x, t);
+            //Sqr(t, 2, t);
+            //Mul(t, x, z);
 
             uint[] t = Create();
-            PowPm3d4(x, t);
-            Sqr(t, 2, t);
-            Mul(t, x, z);
+            uint[] u = new uint[14];
+
+            Copy(x, 0, t, 0);
+            Normalize(t);
+            Encode(t, u, 0);
+
+            Mod.ModOddInverse(P32, u, u);
+
+            Decode(u, 0, z);
+        }
+
+        public static void InvVar(uint[] x, uint[] z)
+        {
+            uint[] t = Create();
+            uint[] u = new uint[14];
+
+            Copy(x, 0, t, 0);
+            Normalize(t);
+            Encode(t, u, 0);
+
+            Mod.ModOddInverseVar(P32, u, u);
+
+            Decode(u, 0, z);
         }
 
         public static int IsZero(uint[] x)