diff options
| -rw-r--r-- | crypto/src/pqc/crypto/bike/BikeEngine.cs | 162 | ||||
| -rw-r--r-- | crypto/src/pqc/crypto/bike/BikeKemGenerator.cs | 9 | ||||
| -rw-r--r-- | crypto/src/pqc/crypto/bike/BikePrivateKeyParameters.cs | 4 | ||||
| -rw-r--r-- | crypto/src/pqc/crypto/bike/BikeRing.cs | 29 | ||||
| -rw-r--r-- | crypto/src/pqc/crypto/bike/BikeUtilities.cs | 52 | ||||
| -rw-r--r-- | crypto/src/util/Arrays.cs | 18 |
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) { |