BIKE refactoring

6 files changed, 151 insertions, 123 deletions

diff --git a/crypto/src/pqc/crypto/bike/BikeEngine.cs b/crypto/src/pqc/crypto/bike/BikeEngine.cs
index 7e01bdb6f..e96a38d3a 100644
--- a/crypto/src/pqc/crypto/bike/BikeEngine.cs
+++ b/crypto/src/pqc/crypto/bike/BikeEngine.cs
@@ -6,6 +6,7 @@ using System.Numerics;
 
 using Org.BouncyCastle.Crypto;
 using Org.BouncyCastle.Crypto.Digests;
+using Org.BouncyCastle.Math.Raw;
 using Org.BouncyCastle.Security;
 using Org.BouncyCastle.Utilities;
 
@@ -37,9 +38,9 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
         private readonly BikeRing bikeRing;
         private readonly int L_BYTE;
         private readonly int R_BYTE;
-        private readonly int R2_BYTE;
-        //private readonly int R_UINT;
         private readonly int R2_UINT;
+        private readonly int R_ULONG;
+        private readonly int R2_ULONG;
 
         internal BikeEngine(int r, int w, int t, int l, int nbIter, int tau)
         {
@@ -52,31 +53,44 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
             this.hw = this.w / 2;
             this.L_BYTE = l / 8;
             this.R_BYTE = (r + 7) >> 3;
-            this.R2_BYTE = (2 * r + 7) >> 3;
-            //this.R_UINT = (r + 31) >> 5;
             this.R2_UINT = (2 * r + 31) >> 5;
+            this.R_ULONG = (r + 63) >> 6;
+            this.R2_ULONG = (2 * r + 63) >> 6;
             this.bikeRing = new BikeRing(r);
         }
 
         internal int SessionKeySize => L_BYTE;
 
-        private byte[] FunctionH(byte[] seed)
+        private ulong[] FunctionH(byte[] seed)
         {
-            byte[] res = new byte[2 * R_BYTE];
             IXof digest = new ShakeDigest(256);
             digest.BlockUpdate(seed, 0, seed.Length);
-            BikeUtilities.GenerateRandomByteArray(res, 2 * r, t, digest);
+            ulong[] res = new ulong[2 * R_ULONG];
+            BikeUtilities.GenerateRandomUlongs(res, 2 * r, t, digest);
             return res;
         }
 
-        private void FunctionL(byte[] e0, byte[] e1, byte[] result)
+        private void FunctionL(ulong[] e01, byte[] c1, int c1Off)
+        {
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+            Span<byte> hashRes = stackalloc byte[48];
+            Sha3Digest.CalculateDigest(e01, 16 * R_BYTE, hashRes, 384);
+            hashRes[..L_BYTE].CopyTo(c1.AsSpan(c1Off));
+#else
+            byte[] hashRes = new byte[48];
+            Sha3Digest.CalculateDigest(e01, 0, 16 * R_BYTE, hashRes, 0, 384);
+            Array.Copy(hashRes, 0, c1, c1Off, L_BYTE);
+#endif
+        }
+
+        private void FunctionK(byte[] m, byte[] c01, byte[] result)
         {
 #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
             Span<byte> hashRes = stackalloc byte[48];
 
             var digest = new Sha3Digest(384);
-            digest.BlockUpdate(e0);
-            digest.BlockUpdate(e1);
+            digest.BlockUpdate(m);
+            digest.BlockUpdate(c01);
             digest.DoFinal(hashRes);
 
             hashRes[..L_BYTE].CopyTo(result);
@@ -84,8 +98,8 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
             byte[] hashRes = new byte[48];
 
             var digest = new Sha3Digest(384);
-            digest.BlockUpdate(e0, 0, e0.Length);
-            digest.BlockUpdate(e1, 0, e1.Length);
+            digest.BlockUpdate(m, 0, m.Length);
+            digest.BlockUpdate(c01, 0, c01.Length);
             digest.DoFinal(hashRes, 0);
 
             Array.Copy(hashRes, 0, result, 0, L_BYTE);
@@ -145,19 +159,17 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
 #endif
 
             // 1. Randomly generate h0, h1
-            BikeUtilities.GenerateRandomByteArray(h0, r, hw, digest);
-            BikeUtilities.GenerateRandomByteArray(h1, r, hw, digest);
-
             ulong[] h0Element = bikeRing.Create();
             ulong[] h1Element = bikeRing.Create();
-            bikeRing.DecodeBytes(h0, h0Element);
-            bikeRing.DecodeBytes(h1, h1Element);
+            BikeUtilities.GenerateRandomUlongs(h0Element, r, hw, digest);
+            BikeUtilities.GenerateRandomUlongs(h1Element, r, hw, digest);
+            bikeRing.EncodeBytes(h0Element, h0);
+            bikeRing.EncodeBytes(h1Element, h1);
 
             // 2. Compute h
-            ulong[] t = bikeRing.Create();
-            bikeRing.Inv(h0Element, t);
-            bikeRing.Multiply(t, h1Element, t);
-            bikeRing.EncodeBytes(t, h);
+            bikeRing.Inv(h0Element, h0Element);
+            bikeRing.Multiply(h0Element, h1Element, h0Element);
+            bikeRing.EncodeBytes(h0Element, h);
 
             //3. Parse seed2 as sigma
 #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
@@ -177,37 +189,30 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
          * @param h             public key
          * @param random        Secure Random
          **/
-        internal void Encaps(byte[] c0, byte[] c1, byte[] k, byte[] h, SecureRandom random)
+        internal void Encaps(byte[] c01, byte[] k, byte[] h, SecureRandom random)
         {
             // 1. Randomly generate m by using seed1
             byte[] m = new byte[L_BYTE];
             random.NextBytes(m);
 
             // 2. Calculate e0, e1
-            byte[] eBytes = FunctionH(m);
-
-            byte[] e0Bytes = new byte[R_BYTE];
-            byte[] e1Bytes = new byte[R_BYTE];
-            SplitEBytes(eBytes, e0Bytes, e1Bytes);
-
-            ulong[] e0Element = bikeRing.Create();
-            ulong[] e1Element = bikeRing.Create();
-            bikeRing.DecodeBytes(e0Bytes, e0Element);
-            bikeRing.DecodeBytes(e1Bytes, e1Element);
+            ulong[] e01 = FunctionH(m);
 
             // 3. Calculate c
+            AlignE01From1To64(e01);
             ulong[] t = bikeRing.Create();
             bikeRing.DecodeBytes(h, t);
-            bikeRing.Multiply(t, e1Element, t);
-            bikeRing.Add(t, e0Element, t);
-            bikeRing.EncodeBytes(t, c0);
+            bikeRing.Multiply(t, 0, e01, R_ULONG, t);
+            bikeRing.Add(t, e01, t);
+            bikeRing.EncodeBytes(t, c01);
 
             //calculate c1
-            FunctionL(e0Bytes, e1Bytes, c1);
-            Bytes.XorTo(L_BYTE, m, c1);
+            AlignE01From64To8(e01);
+            FunctionL(e01, c01, R_BYTE);
+            Bytes.XorTo(L_BYTE, m, 0, c01, R_BYTE);
 
             // 4. Calculate K
-            FunctionK(m, c0, c1, k);
+            FunctionK(m, c01, k);
         }
 
         /**
@@ -233,22 +238,23 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
             byte[] syndromeBits = ComputeSyndrome(c0, h0);
 
             // 1. Compute e'
+            // TODO Produce e01 directly
             byte[] ePrimeBits = BGFDecoder(syndromeBits, h0Compact, h1Compact);
-            byte[] ePrimeBytes = new byte[2 * R_BYTE];
-            BikeUtilities.FromBitArrayToByteArray(ePrimeBytes, ePrimeBits, 0, 2 * r);
-
-            byte[] e0Bytes = new byte[R_BYTE];
-            byte[] e1Bytes = new byte[R_BYTE];
-            SplitEBytes(ePrimeBytes, e0Bytes, e1Bytes);
+            ulong[] e01 = new ulong[2 * R_ULONG];
+            BikeUtilities.FromBitsToUlongs(e01, ePrimeBits, 0, 2 * r);
 
             // 2. Compute m'
+            // TODO Merge (or produce aligned to 64)
+            AlignE01From1To64(e01);
+            AlignE01From64To8(e01);
             byte[] mPrime = new byte[L_BYTE];
-            FunctionL(e0Bytes, e1Bytes, mPrime);
+            FunctionL(e01, mPrime, 0);
             Bytes.XorTo(L_BYTE, c1, mPrime);
 
             // 3. Compute K
-            byte[] wlist = FunctionH(mPrime);
-            if (Arrays.AreEqual(ePrimeBytes, 0, R2_BYTE, wlist, 0, R2_BYTE))
+            AlignE01From8To1(e01);
+            ulong[] wlist = FunctionH(mPrime);
+            if (Arrays.AreEqual(e01, 0, R2_ULONG, wlist, 0, R2_ULONG))
             {
                 FunctionK(mPrime, c0, c1, k);
             }
@@ -285,8 +291,8 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
                 int T = Threshold(BikeUtilities.GetHammingWeight(s), r);
 
                 BFIter(s, e, T, h0Compact, h1Compact, h0CompactCol, h1CompactCol, black, gray, ctrs);
-                BFMaskedIter(s, e, black, (hw + 1) / 2 + 1, h0Compact, h1Compact, h0CompactCol, h1CompactCol);
-                BFMaskedIter(s, e, gray, (hw + 1) / 2 + 1, h0Compact, h1Compact, h0CompactCol, h1CompactCol);
+                BFMaskedIter(s, e, black, (hw + 3) / 2, h0Compact, h1Compact, h0CompactCol, h1CompactCol);
+                BFMaskedIter(s, e, gray, (hw + 3) / 2, h0Compact, h1Compact, h0CompactCol, h1CompactCol);
             }
             for (int i = 1; i < nbIter; i++)
             {
@@ -463,10 +469,10 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
         {
             switch (r)
             {
-                case 12323: return ThresholdFromParameters(hammingWeight, 0.0069722, 13.530, 36);
-                case 24659: return ThresholdFromParameters(hammingWeight, 0.005265, 15.2588, 52);
-                case 40973: return ThresholdFromParameters(hammingWeight, 0.00402312, 17.8785, 69);
-                default:    throw new ArgumentException();
+            case 12323: return ThresholdFromParameters(hammingWeight, 0.0069722, 13.530, 36);
+            case 24659: return ThresholdFromParameters(hammingWeight, 0.005265, 15.2588, 52);
+            case 40973: return ThresholdFromParameters(hammingWeight, 0.00402312, 17.8785, 69);
+            default:    throw new ArgumentException();
             }
         }
 
@@ -663,21 +669,43 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
             }
         }
 
-        private void SplitEBytes(byte[] e, byte[] e0, byte[] e1)
+        private void AlignE01From1To64(ulong[] e01)
         {
-            int partial = r & 7;
-            Array.Copy(e, 0, e0, 0, R_BYTE - 1);
-            byte split = e[R_BYTE - 1];
-            byte mask = (byte)(uint.MaxValue << partial);
-            e0[R_BYTE - 1] = (byte)(split & ~mask);
-
-            byte c = (byte)(split & mask);
-            for (int i = 0; i < R_BYTE; ++i)
-            {
-                byte next = e[R_BYTE + i];
-                e1[i] = (byte)((next << (8 - partial)) | (c >> partial));
-                c = next;
-            }
+            int partial = r & 63;
+            int shift = 64 - partial;
+            ulong mask = ulong.MaxValue << partial;
+            Debug.Assert(partial != 0);
+            Debug.Assert(shift != 0);
+
+            ulong split = e01[R_ULONG - 1];
+            ulong c = split & mask;
+            Nat.ShiftUpBits64(R_ULONG, e01, R_ULONG, shift, c);
+            e01[R_ULONG - 1] = split & ~mask;
+        }
+
+        private void AlignE01From64To8(ulong[] e01)
+        {
+            int partial = (8 * R_BYTE) & 63;
+            int shift = 64 - partial;
+            ulong mask = ulong.MaxValue << partial;
+            Debug.Assert(partial != 0);
+            Debug.Assert(shift != 0);
+
+            ulong c = Nat.ShiftDownBits64(R_ULONG, e01, R_ULONG, shift, 0UL);
+            e01[R_ULONG - 1] |= c;
+        }
+
+        private void AlignE01From8To1(ulong[] e01)
+        {
+            int partial = r & 63;
+            int shift = 8 * R_BYTE - r;
+            ulong mask = ulong.MaxValue << partial;
+            Debug.Assert(partial != 0);
+            Debug.Assert(shift != 0);
+
+            ulong split = e01[R_ULONG - 1];
+            ulong c = Nat.ShiftDownBits64(R_ULONG, e01, R_ULONG, shift, 0UL);
+            e01[R_ULONG - 1] = (split & ~mask) | ((split >> shift) & mask) | c;
         }
     }
 }
diff --git a/crypto/src/pqc/crypto/bike/BikeKemGenerator.cs b/crypto/src/pqc/crypto/bike/BikeKemGenerator.cs
index da4221967..280bb6474 100644
--- a/crypto/src/pqc/crypto/bike/BikeKemGenerator.cs
+++ b/crypto/src/pqc/crypto/bike/BikeKemGenerator.cs
@@ -23,15 +23,12 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
             BikeEngine engine = parameters.BikeEngine;
 
             byte[] K = new byte[parameters.LByte];
-            byte[] c0 = new byte[parameters.RByte];
-            byte[] c1 = new byte[parameters.LByte];
+            byte[] c01 = new byte[parameters.RByte + parameters.LByte];
             byte[] h = key.PublicKey;
 
-            engine.Encaps(c0, c1, K, h, sr);
+            engine.Encaps(c01, K, h, sr);
 
-            byte[] cipherText = Arrays.Concatenate(c0, c1);
-
-            return new SecretWithEncapsulationImpl(Arrays.CopyOfRange(K, 0, parameters.DefaultKeySize / 8), cipherText);
+            return new SecretWithEncapsulationImpl(Arrays.CopyOfRange(K, 0, parameters.DefaultKeySize / 8), c01);
         }
 
         private class SecretWithEncapsulationImpl
diff --git a/crypto/src/pqc/crypto/bike/BikePrivateKeyParameters.cs b/crypto/src/pqc/crypto/bike/BikePrivateKeyParameters.cs
index b44d33ce1..31c65e5f7 100644
--- a/crypto/src/pqc/crypto/bike/BikePrivateKeyParameters.cs
+++ b/crypto/src/pqc/crypto/bike/BikePrivateKeyParameters.cs
@@ -44,11 +44,9 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
             return sigma;
         }
 
-        internal byte[] PrivateKey => Arrays.Concatenate(Arrays.Concatenate(h0, h1), sigma);
-
         public byte[] GetEncoded()
         {
-            return PrivateKey;
+            return Arrays.ConcatenateAll(h0, h1, sigma);
         }
     }
 }
diff --git a/crypto/src/pqc/crypto/bike/BikeRing.cs b/crypto/src/pqc/crypto/bike/BikeRing.cs
index a98cc9975..f7833b167 100644
--- a/crypto/src/pqc/crypto/bike/BikeRing.cs
+++ b/crypto/src/pqc/crypto/bike/BikeRing.cs
@@ -146,8 +146,13 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
 
         internal void Multiply(ulong[] x, ulong[] y, ulong[] z)
         {
+            Multiply(x, 0, y, 0, z);
+        }
+
+        internal void Multiply(ulong[] x, int xOff, ulong[] y, int yOff, ulong[] z)
+        {
             ulong[] tt = CreateExt();
-            ImplMultiplyAcc(x, y, tt);
+            ImplMultiplyAcc(x, xOff, y, yOff, tt);
             Reduce(tt, z);
         }
 
@@ -210,20 +215,24 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
             return t + ((t >> 31) & m);
         }
 
-        private void ImplMultiplyAcc(ulong[] x, ulong[] y, ulong[] zz)
+        private void ImplMultiplyAcc(ulong[] x, int xOff, ulong[] y, int yOff, ulong[] zz)
         {
+            var xBounds = x[xOff + Size - 1];
+            var yBounds = y[yOff + Size - 1];
+            var zzBounds = zz[SizeExt - 1];
+
 #if NETCOREAPP3_0_OR_GREATER
             if (Pclmulqdq.IsSupported)
             {
                 int i = 0, limit = Size - 2;
                 while (i <= limit)
                 {
-                    var X01 = Vector128.Create(x[i], x[i + 1]);
+                    var X01 = Vector128.Create(x[xOff + i], x[xOff + i + 1]);
 
                     int j = 0;
                     while (j <= limit)
                     {
-                        var Y01 = Vector128.Create(y[j], y[j + 1]);
+                        var Y01 = Vector128.Create(y[yOff + j], y[yOff + j + 1]);
 
                         var Z01 = Pclmulqdq.CarrylessMultiply(X01, Y01, 0x00);
                         var Z12 = Sse2.Xor(Pclmulqdq.CarrylessMultiply(X01, Y01, 0x01),
@@ -242,13 +251,13 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
                 }
                 if (i < Size)
                 {
-                    var Xi = Vector128.CreateScalar(x[i]);
-                    var Yi = Vector128.CreateScalar(y[i]);
+                    var Xi = Vector128.CreateScalar(x[xOff + i]);
+                    var Yi = Vector128.CreateScalar(y[yOff + i]);
 
                     for (int j = 0; j < i; ++j)
                     {
-                        var Xj = Vector128.CreateScalar(x[j]);
-                        var Yj = Vector128.CreateScalar(y[j]);
+                        var Xj = Vector128.CreateScalar(x[xOff + j]);
+                        var Yj = Vector128.CreateScalar(y[yOff + j]);
 
                         var Z = Sse2.Xor(Pclmulqdq.CarrylessMultiply(Xi, Yj, 0x00),
                                          Pclmulqdq.CarrylessMultiply(Yi, Xj, 0x00));
@@ -289,7 +298,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
 
             for (int i = 0; i < Size; ++i)
             {
-                ImplMulwAcc(u, x[i], y[i], zz, i << 1);
+                ImplMulwAcc(u, x[xOff + i], y[yOff + i], zz, i << 1);
             }
 
             ulong v0 = zz[0], v1 = zz[1];
@@ -309,7 +318,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
 
                 while (lo < hi)
                 {
-                    ImplMulwAcc(u, x[lo] ^ x[hi], y[lo] ^ y[hi], zz, zPos);
+                    ImplMulwAcc(u, x[xOff + lo] ^ x[xOff + hi], y[yOff + lo] ^ y[yOff + hi], zz, zPos);
 
                     ++lo;
                     --hi;
diff --git a/crypto/src/pqc/crypto/bike/BikeUtilities.cs b/crypto/src/pqc/crypto/bike/BikeUtilities.cs
index 0aeeaa30b..51f261eb9 100644
--- a/crypto/src/pqc/crypto/bike/BikeUtilities.cs
+++ b/crypto/src/pqc/crypto/bike/BikeUtilities.cs
@@ -1,8 +1,7 @@
 using System;
 
-using Org.BouncyCastle.Crypto.Utilities;
 using Org.BouncyCastle.Crypto;
-using Org.BouncyCastle.Utilities;
+using Org.BouncyCastle.Crypto.Utilities;
 
 namespace Org.BouncyCastle.Pqc.Crypto.Bike
 {
@@ -18,37 +17,16 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
             return hammingWeight;
         }
 
-        internal static void FromBitArrayToByteArray(byte[] output, byte[] input, int inputOff, int inputLen)
+        internal static void FromBitsToUlongs(ulong[] output, byte[] input, int inputOff, int inputLen)
         {
-            int count = 0;
-            int pos = 0;
-            while (count < inputLen)
+            for (int i = 0; i < inputLen; ++i)
             {
-                if (count + 8 >= inputLen)
-                {// last set of bits cannot have enough 8 bits
-                    int b = input[inputOff + count];
-                    for (int j = inputLen - count - 1; j >= 1; j--)
-                    { //bin in reversed order
-                        b |= input[inputOff + count + j] << j;
-                    }
-                    output[pos] = (byte)b;
-                }
-                else
-                {
-                    int b = input[inputOff + count];
-                    for (int j = 7; j >= 1; j--)
-                    { //bin in reversed order
-                        b |= input[inputOff + count + j] << j;
-                    }
-                    output[pos] = (byte)b;
-                }
-
-                count += 8;
-                pos++;
+                ulong bit = input[inputOff + i] & 1UL;
+                output[i >> 6] |= bit << (i & 63);
             }
         }
 
-        internal static void GenerateRandomByteArray(byte[] res, int size, int weight, IXof digest)
+        internal static void GenerateRandomUlongs(ulong[] res, int size, int weight, IXof digest)
         {
 #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
             Span<byte> buf = stackalloc byte[4];
@@ -69,7 +47,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
                 temp *= (uint)(size - i);
                 uint rand_pos = (uint)i + (uint)(temp >> 32);
 
-                if (CheckBit(res, rand_pos) != 0)
+                if (CheckBit(res, rand_pos))
                 {
                     rand_pos = (uint)i;
                 }
@@ -77,18 +55,18 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
             }
         }
 
-        private static uint CheckBit(byte[] tmp, uint position)
+        private static bool CheckBit(ulong[] tmp, uint position)
         {
-            uint index = position / 8;
-            uint pos = position % 8;
-            return ((uint)tmp[index] >> (int)pos) & 1U;
+            uint index = position >> 6;
+            uint pos = position & 63;
+            return ((tmp[index] >> (int)pos) & 1UL) != 0UL;
         }
 
-        private static void SetBit(byte[] tmp, uint position)
+        private static void SetBit(ulong[] tmp, uint position)
         {
-            uint index = position / 8;
-            uint pos = position % 8;
-            tmp[index] |= (byte)(1 << (int)pos);
+            uint index = position >> 6;
+            uint pos = position & 63;
+            tmp[index] |= 1UL << (int)pos;
         }
     }
 }
diff --git a/crypto/src/util/Arrays.cs b/crypto/src/util/Arrays.cs
index a9ae6724a..da74d467a 100644
--- a/crypto/src/util/Arrays.cs
+++ b/crypto/src/util/Arrays.cs
@@ -97,6 +97,24 @@ namespace Org.BouncyCastle.Utilities
             return true;
         }
 
+        [CLSCompliant(false)]
+        public static bool AreEqual(ulong[] a, int aFromIndex, int aToIndex, ulong[] b, int bFromIndex, int bToIndex)
+        {
+            int aLength = aToIndex - aFromIndex;
+            int bLength = bToIndex - bFromIndex;
+
+            if (aLength != bLength)
+                return false;
+
+            for (int i = 0; i < aLength; ++i)
+            {
+                if (a[aFromIndex + i] != b[bFromIndex + i])
+                    return false;
+            }
+
+            return true;
+        }
+
         [Obsolete("Use 'FixedTimeEquals' instead")]
         public static bool ConstantTimeAreEqual(byte[] a, byte[] b)
         {