From 7999d9a94a6bf6eb6de72258e5167d88a86f4d9b Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Wed, 9 Feb 2022 00:27:55 +0700 Subject: Further GCM updates --- .../src/crypto/modes/gcm/BasicGcmExponentiator.cs | 18 +++--- crypto/src/crypto/modes/gcm/BasicGcmMultiplier.cs | 6 +- crypto/src/crypto/modes/gcm/GcmUtilities.cs | 66 +++++++++++++++++++++- .../crypto/modes/gcm/Tables1kGcmExponentiator.cs | 20 ++++--- 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); } -- cgit 1.4.1