From 79e1dfa3decfae4455123894f4fdc72c21364072 Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Tue, 8 Feb 2022 20:21:35 +0700 Subject: Speed up BasicGcmMultiplier --- crypto/src/crypto/modes/gcm/BasicGcmMultiplier.cs | 4 +-- crypto/src/crypto/modes/gcm/GcmUtilities.cs | 38 +++++++++++++++++++++++ 2 files changed, 39 insertions(+), 3 deletions(-) diff --git a/crypto/src/crypto/modes/gcm/BasicGcmMultiplier.cs b/crypto/src/crypto/modes/gcm/BasicGcmMultiplier.cs index 644ddb1e2..1f41fd805 100644 --- a/crypto/src/crypto/modes/gcm/BasicGcmMultiplier.cs +++ b/crypto/src/crypto/modes/gcm/BasicGcmMultiplier.cs @@ -14,9 +14,7 @@ namespace Org.BouncyCastle.Crypto.Modes.Gcm public void MultiplyH(byte[] x) { - ulong[] t = GcmUtilities.AsUlongs(x); - GcmUtilities.Multiply(t, H); - GcmUtilities.AsBytes(t, x); + GcmUtilities.Multiply(x, H); } } } diff --git a/crypto/src/crypto/modes/gcm/GcmUtilities.cs b/crypto/src/crypto/modes/gcm/GcmUtilities.cs index ed88240f2..dbea6771c 100644 --- a/crypto/src/crypto/modes/gcm/GcmUtilities.cs +++ b/crypto/src/crypto/modes/gcm/GcmUtilities.cs @@ -129,6 +129,44 @@ namespace Org.BouncyCastle.Crypto.Modes.Gcm AsBytes(t1, x); } + internal static void Multiply(byte[] x, ulong[] 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 = Pack.BE_To_UInt64(x, 0); + ulong x1 = Pack.BE_To_UInt64(x, 8); + ulong y0 = y[0], y1 = y[1]; + 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); + + Pack.UInt64_To_BE(z0, x, 0); + Pack.UInt64_To_BE(z1, x, 8); + } + internal static void Multiply(uint[] x, uint[] y) { uint y0 = y[0], y1 = y[1], y2 = y[2], y3 = y[3]; -- cgit 1.4.1