Further GCM updates

4 files changed, 86 insertions, 24 deletions

diff --git a/crypto/src/crypto/modes/gcm/BasicGcmExponentiator.cs b/crypto/src/crypto/modes/gcm/BasicGcmExponentiator.cs
index e7386b881..4ef1bf745 100644
--- a/crypto/src/crypto/modes/gcm/BasicGcmExponentiator.cs
+++ b/crypto/src/crypto/modes/gcm/BasicGcmExponentiator.cs
@@ -1,40 +1,38 @@
 using System;
 
-using Org.BouncyCastle.Utilities;
-
 namespace Org.BouncyCastle.Crypto.Modes.Gcm
 {
     public class BasicGcmExponentiator
         : IGcmExponentiator
     {
-        private ulong[] x;
+        private GcmUtilities.FieldElement x;
 
         public void Init(byte[] x)
         {
-            this.x = GcmUtilities.AsUlongs(x);
+            GcmUtilities.AsFieldElement(x, out this.x);
         }
 
         public void ExponentiateX(long pow, byte[] output)
         {
-            // Initial value is little-endian 1
-            ulong[] y = GcmUtilities.OneAsUlongs();
+            GcmUtilities.FieldElement y;
+            GcmUtilities.One(out y);
 
             if (pow > 0)
             {
-                ulong[] powX = Arrays.Clone(x);
+                GcmUtilities.FieldElement powX = x;
                 do
                 {
                     if ((pow & 1L) != 0)
                     {
-                        GcmUtilities.Multiply(y, powX);
+                        GcmUtilities.Multiply(ref y, ref powX);
                     }
-                    GcmUtilities.Square(powX, powX);
+                    GcmUtilities.Square(ref powX);
                     pow >>= 1;
                 }
                 while (pow > 0);
             }
 
-            GcmUtilities.AsBytes(y, output);
+            GcmUtilities.AsBytes(ref y, output);
         }
     }
 }
diff --git a/crypto/src/crypto/modes/gcm/BasicGcmMultiplier.cs b/crypto/src/crypto/modes/gcm/BasicGcmMultiplier.cs
index 1f41fd805..bf19e173d 100644
--- a/crypto/src/crypto/modes/gcm/BasicGcmMultiplier.cs
+++ b/crypto/src/crypto/modes/gcm/BasicGcmMultiplier.cs
@@ -5,16 +5,16 @@ namespace Org.BouncyCastle.Crypto.Modes.Gcm
     public class BasicGcmMultiplier
         : IGcmMultiplier
     {
-        private ulong[] H;
+        private GcmUtilities.FieldElement H;
 
         public void Init(byte[] H)
         {
-            this.H = GcmUtilities.AsUlongs(H);
+            GcmUtilities.AsFieldElement(H, out this.H);
         }
 
         public void MultiplyH(byte[] x)
         {
-            GcmUtilities.Multiply(x, H);
+            GcmUtilities.Multiply(x, ref H);
         }
     }
 }
diff --git a/crypto/src/crypto/modes/gcm/GcmUtilities.cs b/crypto/src/crypto/modes/gcm/GcmUtilities.cs
index b5c3d0908..5bbf78d0a 100644
--- a/crypto/src/crypto/modes/gcm/GcmUtilities.cs
+++ b/crypto/src/crypto/modes/gcm/GcmUtilities.cs
@@ -16,6 +16,12 @@ namespace Org.BouncyCastle.Crypto.Modes.Gcm
         private const uint E1 = 0xe1000000;
         private const ulong E1UL = (ulong)E1 << 32;
 
+        internal static void One(out FieldElement x)
+        {
+            x.n0 = 1UL << 63;
+            x.n1 = 0UL;
+        }
+
         internal static byte[] OneAsBytes()
         {
             byte[] tmp = new byte[16];
@@ -155,7 +161,7 @@ namespace Org.BouncyCastle.Crypto.Modes.Gcm
             AsBytes(t1, x);
         }
 
-        internal static void Multiply(byte[] x, ulong[] y)
+        internal static void Multiply(byte[] x, ref FieldElement y)
         {
             /*
              * "Three-way recursion" as described in "Batch binary Edwards", Daniel J. Bernstein.
@@ -166,7 +172,7 @@ namespace Org.BouncyCastle.Crypto.Modes.Gcm
 
             ulong x0 = Pack.BE_To_UInt64(x, 0);
             ulong x1 = Pack.BE_To_UInt64(x, 8);
-            ulong y0 = y[0], y1 = y[1];
+            ulong y0 = y.n0, y1 = y.n1;
             ulong x0r = Longs.Reverse(x0), x1r = Longs.Reverse(x1);
             ulong y0r = Longs.Reverse(y0), y1r = Longs.Reverse(y1);
 
@@ -285,6 +291,43 @@ namespace Org.BouncyCastle.Crypto.Modes.Gcm
             x[1] = z1;
         }
 
+        internal static void Multiply(ref FieldElement x, ref FieldElement y)
+        {
+            /*
+             * "Three-way recursion" as described in "Batch binary Edwards", Daniel J. Bernstein.
+             *
+             * Without access to the high part of a 64x64 product x * y, we use a bit reversal to calculate it:
+             *     rev(x) * rev(y) == rev((x * y) << 1) 
+             */
+
+            ulong x0 = x.n0, x1 = x.n1;
+            ulong y0 = y.n0, y1 = y.n1;
+            ulong x0r = Longs.Reverse(x0), x1r = Longs.Reverse(x1);
+            ulong y0r = Longs.Reverse(y0), y1r = Longs.Reverse(y1);
+
+            ulong h0 = Longs.Reverse(ImplMul64(x0r, y0r));
+            ulong h1 = ImplMul64(x0, y0) << 1;
+            ulong h2 = Longs.Reverse(ImplMul64(x1r, y1r));
+            ulong h3 = ImplMul64(x1, y1) << 1;
+            ulong h4 = Longs.Reverse(ImplMul64(x0r ^ x1r, y0r ^ y1r));
+            ulong h5 = ImplMul64(x0 ^ x1, y0 ^ y1) << 1;
+
+            ulong z0 = h0;
+            ulong z1 = h1 ^ h0 ^ h2 ^ h4;
+            ulong z2 = h2 ^ h1 ^ h3 ^ h5;
+            ulong z3 = h3;
+
+            z1 ^= z3 ^ (z3 >> 1) ^ (z3 >> 2) ^ (z3 >> 7);
+//          z2 ^=      (z3 << 63) ^ (z3 << 62) ^ (z3 << 57);
+            z2 ^= (z3 << 62) ^ (z3 << 57);
+
+            z0 ^= z2 ^ (z2 >> 1) ^ (z2 >> 2) ^ (z2 >> 7);
+            z1 ^= (z2 << 63) ^ (z2 << 62) ^ (z2 << 57);
+
+            x.n0 = z0;
+            x.n1 = z1;
+        }
+
         internal static void MultiplyP(uint[] x)
         {
             uint x0 = x[0], x1 = x[1], x2 = x[2], x3 = x[3];
@@ -472,6 +515,25 @@ namespace Org.BouncyCastle.Crypto.Modes.Gcm
             z[1] = z1;
         }
 
+        internal static void Square(ref FieldElement x)
+        {
+            ulong[] t = new ulong[4];
+            Interleave.Expand64To128Rev(x.n0, t, 0);
+            Interleave.Expand64To128Rev(x.n1, t, 2);
+
+            ulong z0 = t[0], z1 = t[1], z2 = t[2], z3 = t[3];
+
+            z1 ^= z3 ^ (z3 >> 1) ^ (z3 >> 2) ^ (z3 >> 7);
+//          z2 ^=      (z3 << 63) ^ (z3 << 62) ^ (z3 << 57);
+            z2 ^= (z3 << 62) ^ (z3 << 57);
+
+            z0 ^= z2 ^ (z2 >> 1) ^ (z2 >> 2) ^ (z2 >> 7);
+            z1 ^= (z2 << 63) ^ (z2 << 62) ^ (z2 << 57);
+
+            x.n0 = z0;
+            x.n1 = z1;
+        }
+
         internal static void Xor(byte[] x, byte[] y)
         {
             int i = 0;
diff --git a/crypto/src/crypto/modes/gcm/Tables1kGcmExponentiator.cs b/crypto/src/crypto/modes/gcm/Tables1kGcmExponentiator.cs
index 3667241e3..4a15712c2 100644
--- a/crypto/src/crypto/modes/gcm/Tables1kGcmExponentiator.cs
+++ b/crypto/src/crypto/modes/gcm/Tables1kGcmExponentiator.cs
@@ -14,8 +14,9 @@ namespace Org.BouncyCastle.Crypto.Modes.Gcm
 
         public void Init(byte[] x)
         {
-            ulong[] y = GcmUtilities.AsUlongs(x);
-            if (lookupPowX2 != null && Arrays.AreEqual(y, (ulong[])lookupPowX2[0]))
+            GcmUtilities.FieldElement y;
+            GcmUtilities.AsFieldElement(x, out y);
+            if (lookupPowX2 != null && y.Equals(lookupPowX2[0]))
                 return;
 
             lookupPowX2 = Platform.CreateArrayList(8);
@@ -24,20 +25,22 @@ namespace Org.BouncyCastle.Crypto.Modes.Gcm
 
         public void ExponentiateX(long pow, byte[] output)
         {
-            ulong[] y = GcmUtilities.OneAsUlongs();
+            GcmUtilities.FieldElement y;
+            GcmUtilities.One(out y);
             int bit = 0;
             while (pow > 0)
             {
                 if ((pow & 1L) != 0)
                 {
                     EnsureAvailable(bit);
-                    GcmUtilities.Multiply(y, (ulong[])lookupPowX2[bit]);
+                    GcmUtilities.FieldElement powX2 = (GcmUtilities.FieldElement)lookupPowX2[bit];
+                    GcmUtilities.Multiply(ref y, ref powX2);
                 }
                 ++bit;
                 pow >>= 1;
             }
 
-            GcmUtilities.AsBytes(y, output);
+            GcmUtilities.AsBytes(ref y, output);
         }
 
         private void EnsureAvailable(int bit)
@@ -45,12 +48,11 @@ namespace Org.BouncyCastle.Crypto.Modes.Gcm
             int count = lookupPowX2.Count;
             if (count <= bit)
             {
-                ulong[] tmp = (ulong[])lookupPowX2[count - 1];
+                GcmUtilities.FieldElement powX2 = (GcmUtilities.FieldElement)lookupPowX2[count - 1];
                 do
                 {
-                    tmp = Arrays.Clone(tmp);
-                    GcmUtilities.Square(tmp, tmp);
-                    lookupPowX2.Add(tmp);
+                    GcmUtilities.Square(ref powX2);
+                    lookupPowX2.Add(powX2);
                 }
                 while (++count <= bit);
             }