diff options
| -rw-r--r-- | crypto/src/pqc/crypto/bike/BikeEngine.cs | 192 | ||||
| -rw-r--r-- | crypto/src/pqc/crypto/bike/BikePolynomial.cs | 365 | ||||
| -rw-r--r-- | crypto/src/pqc/crypto/bike/BikeRing.cs | 314 | ||||
| -rw-r--r-- | crypto/src/pqc/crypto/bike/BikeUtilities.cs | 36 |
4 files changed, 399 insertions, 508 deletions
diff --git a/crypto/src/pqc/crypto/bike/BikeEngine.cs b/crypto/src/pqc/crypto/bike/BikeEngine.cs index a872c68a7..94f073bbb 100644 --- a/crypto/src/pqc/crypto/bike/BikeEngine.cs +++ b/crypto/src/pqc/crypto/bike/BikeEngine.cs @@ -1,5 +1,5 @@ using System; - +using System.Diagnostics; using Org.BouncyCastle.Crypto; using Org.BouncyCastle.Crypto.Digests; using Org.BouncyCastle.Security; @@ -10,29 +10,29 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike internal sealed class BikeEngine { // degree of R - private int r; + private readonly int r; // the row weight - private int w; + private readonly int w; // Hamming weight of h0, h1 - private int hw; + private readonly int hw; // the error weight - private int t; + private readonly int t; //the shared secret size - private int l; + private readonly int l; // number of iterations in BGF decoder - private int nbIter; + private readonly int nbIter; // tau - private int tau; + private readonly int tau; - private BikePolynomial reductionPoly; - private int L_BYTE; - private int R_BYTE; + private readonly BikeRing bikeRing; + private readonly int L_BYTE; + private readonly int R_BYTE; internal BikeEngine(int r, int w, int t, int l, int nbIter, int tau) { @@ -45,9 +45,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike this.hw = this.w / 2; this.L_BYTE = l / 8; this.R_BYTE = (r + 7) / 8; - - // generate reductionPoly (X^r + 1) - this.reductionPoly = new BikePolynomial(r); + this.bikeRing = new BikeRing(r); } internal int SessionKeySize => L_BYTE; @@ -59,24 +57,21 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike return BikeUtilities.GenerateRandomByteArray(r * 2, 2 * R_BYTE, t, digest); } - private byte[] FunctionL(byte[] e0, byte[] e1) + private void FunctionL(byte[] e0, byte[] e1, byte[] result) { byte[] hashRes = new byte[48]; - byte[] res = new byte[L_BYTE]; Sha3Digest digest = new Sha3Digest(384); digest.BlockUpdate(e0, 0, e0.Length); digest.BlockUpdate(e1, 0, e1.Length); digest.DoFinal(hashRes, 0); - Array.Copy(hashRes, 0, res, 0, L_BYTE); - return res; + Array.Copy(hashRes, 0, result, 0, L_BYTE); } - private byte[] FunctionK(byte[] m, byte[] c0, byte[] c1) + private void FunctionK(byte[] m, byte[] c0, byte[] c1, byte[] result) { byte[] hashRes = new byte[48]; - byte[] res = new byte[L_BYTE]; Sha3Digest digest = new Sha3Digest(384); digest.BlockUpdate(m, 0, m.Length); @@ -84,8 +79,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike digest.BlockUpdate(c1, 0, c1.Length); digest.DoFinal(hashRes, 0); - Array.Copy(hashRes, 0, res, 0, L_BYTE); - return res; + Array.Copy(hashRes, 0, result, 0, L_BYTE); } /** @@ -113,34 +107,17 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike digest.BlockUpdate(seed1, 0, seed1.Length); // 1. Randomly generate h0, h1 - byte[] h0Tmp = BikeUtilities.GenerateRandomByteArray(r, R_BYTE, hw, digest); - byte[] h1Tmp = BikeUtilities.GenerateRandomByteArray(r, R_BYTE, hw, digest); - - Array.Copy(h0Tmp, 0, h0, 0, h0.Length); - Array.Copy(h1Tmp, 0, h1, 0, h1.Length); - - byte[] h1Bits = new byte[r]; - byte[] h0Bits = new byte[r]; - - BikeUtilities.FromByteArrayToBitArray(h0Bits, h0Tmp); - BikeUtilities.FromByteArrayToBitArray(h1Bits, h1Tmp); + ulong[] h0Element = bikeRing.GenerateRandom(hw, digest); + ulong[] h1Element = bikeRing.GenerateRandom(hw, digest); - // remove last 0 bits (most significant bits with 0 mean non-sense) - byte[] h0Cut = BikeUtilities.RemoveLast0Bits(h0Bits); - byte[] h1Cut = BikeUtilities.RemoveLast0Bits(h1Bits); + bikeRing.EncodeBytes(h0Element, h0); + bikeRing.EncodeBytes(h1Element, h1); // 2. Compute h - BikePolynomial h0Poly = new BikePolynomial(h0Cut); - BikePolynomial h1Poly = new BikePolynomial(h1Cut); - - BikePolynomial h0Inv = h0Poly.ModInverseBigDeg(reductionPoly); - BikePolynomial hPoly = h1Poly.ModKaratsubaMultiplyBigDeg(h0Inv, reductionPoly); - - // Get coefficients of hPoly - byte[] hTmp = hPoly.GetEncoded(); - byte[] hByte = new byte[R_BYTE]; - BikeUtilities.FromBitArrayToByteArray(hByte, hTmp); - Array.Copy(hByte, 0, h, 0, h.Length); + ulong[] hElement = bikeRing.Create(); + bikeRing.Inv(h0Element, hElement); + bikeRing.Multiply(hElement, h1Element, hElement); + bikeRing.EncodeBytes(hElement, h); //3. Parse seed2 as sigma Array.Copy(seed2, 0, sigma, 0, sigma.Length); @@ -172,40 +149,35 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike BikeUtilities.FromByteArrayToBitArray(eBits, eBytes); byte[] e0Bits = Arrays.CopyOfRange(eBits, 0, r); + byte[] e0Bytes = new byte[R_BYTE]; + BikeUtilities.FromBitArrayToByteArray(e0Bytes, e0Bits); + byte[] e1Bits = Arrays.CopyOfRange(eBits, r, eBits.Length); + byte[] e1Bytes = new byte[R_BYTE]; + BikeUtilities.FromBitArrayToByteArray(e1Bytes, e1Bits); - // remove last 0 bits (most significant bits with 0 mean no sense) - byte[] e0Cut = BikeUtilities.RemoveLast0Bits(e0Bits); - byte[] e1Cut = BikeUtilities.RemoveLast0Bits(e1Bits); + ulong[] e0Element = bikeRing.Create(); + ulong[] e1Element = bikeRing.Create(); - BikePolynomial e0 = new BikePolynomial(e0Cut); - BikePolynomial e1 = new BikePolynomial(e1Cut); + bikeRing.DecodeBytes(e0Bytes, e0Element); + bikeRing.DecodeBytes(e1Bytes, e1Element); + + ulong[] hElement = bikeRing.Create(); + bikeRing.DecodeBytes(h, hElement); // 3. Calculate c // calculate c0 - byte[] h0Bits = new byte[r]; - BikeUtilities.FromByteArrayToBitArray(h0Bits, h); - BikePolynomial hPoly = new BikePolynomial(BikeUtilities.RemoveLast0Bits(h0Bits)); - BikePolynomial c0Poly = e0.Add(e1.ModKaratsubaMultiplyBigDeg(hPoly, reductionPoly)); - - byte[] c0Bits = c0Poly.GetEncoded(); - byte[] c0Bytes = new byte[R_BYTE]; - BikeUtilities.FromBitArrayToByteArray(c0Bytes, c0Bits); - Array.Copy(c0Bytes, 0, c0, 0, c0.Length); + ulong[] c0Element = bikeRing.Create(); + bikeRing.Multiply(e1Element, hElement, c0Element); + bikeRing.Add(c0Element, e0Element, c0Element); + bikeRing.EncodeBytes(c0Element, c0); //calculate c1 - byte[] e0Bytes = new byte[R_BYTE]; - BikeUtilities.FromBitArrayToByteArray(e0Bytes, e0Bits); - byte[] e1Bytes = new byte[R_BYTE]; - BikeUtilities.FromBitArrayToByteArray(e1Bytes, e1Bits); - - byte[] tmp = FunctionL(e0Bytes, e1Bytes); - byte[] c1Tmp = BikeUtilities.XorBytes(m, tmp, L_BYTE); - Array.Copy(c1Tmp, 0, c1, 0, c1.Length); + FunctionL(e0Bytes, e1Bytes, c1); + BikeUtilities.XorTo(m, c1, L_BYTE); // 4. Calculate K - byte[] kTmp = FunctionK(m, c0, c1); - Array.Copy(kTmp, 0, k, 0, kTmp.Length); + FunctionK(m, c0, c1, k); } /** @@ -221,18 +193,6 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike **/ internal void Decaps(byte[] k, byte[] h0, byte[] h1, byte[] sigma, byte[] c0, byte[] c1) { - //convert to bits - byte[] c0Bits = new byte[this.r]; - byte[] h0Bits = new byte[this.r]; - byte[] sigmaBits = new byte[this.l]; - - BikeUtilities.FromByteArrayToBitArray(c0Bits, c0); - BikeUtilities.FromByteArrayToBitArray(h0Bits, h0); - BikeUtilities.FromByteArrayToBitArray(sigmaBits, sigma); - - byte[] c0Cut = BikeUtilities.RemoveLast0Bits(c0Bits); - byte[] h0Cut = BikeUtilities.RemoveLast0Bits(h0Bits); - // Get compact version of h0, h1 int[] h0Compact = new int[hw]; int[] h1Compact = new int[hw]; @@ -240,10 +200,10 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike ConvertToCompact(h1Compact, h1); // Compute syndrome - byte[] syndrome = ComputeSyndrome(c0Cut, h0Cut); + byte[] syndromeBits = ComputeSyndrome(c0, h0); // 1. Compute e' - byte[] ePrimeBits = BGFDecoder(syndrome, h0Compact, h1Compact); + byte[] ePrimeBits = BGFDecoder(syndromeBits, h0Compact, h1Compact); byte[] ePrimeBytes = new byte[2 * R_BYTE]; BikeUtilities.FromBitArrayToByteArray(ePrimeBytes, ePrimeBits); @@ -256,30 +216,31 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike BikeUtilities.FromBitArrayToByteArray(e1Bytes, e1Bits); // 2. Compute m' - byte[] mPrime = BikeUtilities.XorBytes(c1, FunctionL(e0Bytes, e1Bytes), L_BYTE); + byte[] mPrime = new byte[L_BYTE]; + FunctionL(e0Bytes, e1Bytes, mPrime); + BikeUtilities.XorTo(c1, mPrime, L_BYTE); // 3. Compute K - byte[] tmpK = new byte[l]; byte[] wlist = FunctionH(mPrime); if (Arrays.AreEqual(ePrimeBytes, wlist)) { - tmpK = FunctionK(mPrime, c0, c1); + FunctionK(mPrime, c0, c1, k); } else { - tmpK = FunctionK(sigma, c0, c1); + FunctionK(sigma, c0, c1, k); } - Array.Copy(tmpK, 0, k, 0, tmpK.Length); } - private byte[] ComputeSyndrome(byte[] h0, byte[] c0) + private byte[] ComputeSyndrome(byte[] c0, byte[] h0) { - BikePolynomial coPoly = new BikePolynomial(c0); - BikePolynomial h0Poly = new BikePolynomial(h0); - - BikePolynomial s = coPoly.ModKaratsubaMultiplyBigDeg(h0Poly, reductionPoly); - byte[] transposedS = Transpose(s.GetEncoded()); - return transposedS; + ulong[] c0Element = bikeRing.Create(); + ulong[] h0Element = bikeRing.Create(); + bikeRing.DecodeBytes(c0, c0Element); + bikeRing.DecodeBytes(h0, h0Element); + ulong[] sElement = bikeRing.Create(); + bikeRing.Multiply(c0Element, h0Element, sElement); + return Transpose(bikeRing.EncodeBits(sElement)); } private byte[] BGFDecoder(byte[] s, int[] h0Compact, int[] h1Compact) @@ -314,12 +275,11 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike private byte[] Transpose(byte[] input) { - byte[] tmp = BikeUtilities.Append0s(input, r); // append zeros to s byte[] output = new byte[r]; - output[0] = tmp[0]; + output[0] = input[0]; for (int i = 1; i < r; i++) { - output[i] = tmp[r - i]; + output[i] = input[r - i]; } return output; } @@ -332,13 +292,14 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike // calculate for h0compact for (int j = 0; j < r; j++) { - if (Ctr(h0CompactCol, s, j) >= T) + int ctr = Ctr(h0CompactCol, s, j); + if (ctr >= T) { UpdateNewErrorIndex(e, j); updatedIndices[j] = 1; black[j] = 1; } - else if (Ctr(h0CompactCol, s, j) >= T - tau) + else if (ctr >= T - tau) { gray[j] = 1; } @@ -347,13 +308,14 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike // calculate for h1Compact for (int j = 0; j < r; j++) { - if (Ctr(h1CompactCol, s, j) >= T) + int ctr = Ctr(h1CompactCol, s, j); + if (ctr >= T) { UpdateNewErrorIndex(e, r + j); updatedIndices[r + j] = 1; black[r + j] = 1; } - else if (Ctr(h1CompactCol, s, j) >= T - tau) + else if (ctr >= T - tau) { gray[r + j] = 1; } @@ -369,13 +331,14 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike } } - private void BFMaskedIter(byte[] s, byte[] e, byte[] mask, int T, int[] h0Compact, int[] h1Compact, int[] h0CompactCol, int[] h1CompactCol) + private void BFMaskedIter(byte[] s, byte[] e, byte[] mask, int T, int[] h0Compact, int[] h1Compact, + int[] h0CompactCol, int[] h1CompactCol) { int[] updatedIndices = new int[2 * r]; for (int j = 0; j < r; j++) { - if (Ctr(h0CompactCol, s, j) >= T && mask[j] == 1) + if (mask[j] == 1 && Ctr(h0CompactCol, s, j) >= T) { UpdateNewErrorIndex(e, j); updatedIndices[j] = 1; @@ -384,7 +347,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike for (int j = 0; j < r; j++) { - if (Ctr(h1CompactCol, s, j) >= T && mask[r + j] == 1) + if (mask[r + j] == 1 && Ctr(h1CompactCol, s, j) >= T) { UpdateNewErrorIndex(e, r + j); updatedIndices[r + j] = 1; @@ -429,13 +392,20 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike private int Ctr(int[] hCompactCol, byte[] s, int j) { + Debug.Assert(0 <= j && j < r); + int count = 0; for (int i = 0; i < hw; i++) { - if (s[(hCompactCol[i] + j) % r] == 1) - { - count += 1; - } + //int sPos = (hCompactCol[i] + j) % r; + int sPos = hCompactCol[i] + j - r; + sPos += (sPos >> 31) & r; + + //if (s[sPos] == 1) + //{ + // count += 1; + //} + count += s[sPos]; } return count; } diff --git a/crypto/src/pqc/crypto/bike/BikePolynomial.cs b/crypto/src/pqc/crypto/bike/BikePolynomial.cs deleted file mode 100644 index eea34d838..000000000 --- a/crypto/src/pqc/crypto/bike/BikePolynomial.cs +++ /dev/null @@ -1,365 +0,0 @@ -using System; - -using Org.BouncyCastle.Utilities; - -namespace Org.BouncyCastle.Pqc.Crypto.Bike -{ - internal class BikePolynomial - { - /** - * For the polynomial representation the map f: R->Z*, - * <tt>poly(X) -> [coef_0, coef_1, ...]</tt> is used, where - * <tt>coef_i</tt> is the <tt>i</tt>th coefficient of the polynomial - * represented as int (see {@link GF2mField}). The polynomials are stored - * as int arrays. - */ - private readonly int[] m_coefficients; - - /** - * Construct a monomial of the given degree over the finite field GF(2^m). - * - * @param field the finite field GF(2^m) - * @param degree the degree of the monomial - */ - internal BikePolynomial(int degree) - { - // Initial value (X^degree + 1) - this.m_coefficients = new int[degree + 1]; - this.m_coefficients[degree] = 1; - this.m_coefficients[0] ^= 1; - } - - /** - * Construct the polynomial over the given finite field GF(2^m) from the - * given coefficient vector. - * - * @param field finite field GF2m - * @param coeffs the coefficient vector - */ - private BikePolynomial(int[] coeffs) - { - this.m_coefficients = coeffs; - } - - /** - * Create a polynomial over the finite field GF(2^m). - * - * @param field the finite field GF(2^m) - * @param enc byte[] polynomial in byte array form - */ - internal BikePolynomial(byte[] enc) - { - // decodes polynomial - this.m_coefficients = new int[enc.Length]; - for (int i = 0; i < m_coefficients.Length; i++) - { - m_coefficients[i] = enc[i]; - if ((m_coefficients[i] >> 1) != 0) - throw new ArgumentException( - "Error: byte array is not encoded polynomial over given finite field GF2m"); - } - // if HC = 0 for non-zero polynomial, returns error - if ((m_coefficients.Length != 1) && (m_coefficients[m_coefficients.Length - 1] == 0)) - throw new ArgumentException("Error: byte array is not encoded polynomial over given finite field GF2m"); - } - - /** - * Returns encoded polynomial, i.e., this polynomial in byte array form - * - * @return the encoded polynomial - */ - internal byte[] GetEncoded() - { - byte[] res = new byte[m_coefficients.Length]; - for (int i = 0; i < m_coefficients.Length; i++) - { - res[i] = (byte)m_coefficients[i]; - } - return res; - } - - /** - * Compute the sum of this polynomial and the given polynomial. - * - * @param addend the addend - * @return <tt>this + a</tt> (newly created) - */ - internal BikePolynomial Add(BikePolynomial addend) - { - int[] resultCoeff = Add(m_coefficients, addend.m_coefficients); - return new BikePolynomial(NormalForm(resultCoeff)); - } - - /** - * Compute the sum of two polynomials a and b over the finite field - * <tt>GF(2^m)</tt>. - * - * @param a the first polynomial - * @param b the second polynomial - * @return a + b - */ - private static int[] Add(int[] a, int[] b) - { - int[] result, addend; - if (a.Length < b.Length) - { - result = new int[b.Length]; - Array.Copy(b, 0, result, 0, b.Length); - addend = a; - } - else - { - result = new int[a.Length]; - Array.Copy(a, 0, result, 0, a.Length); - addend = b; - } - - for (int i = addend.Length - 1; i >= 0; i--) - { - result[i] ^= addend[i]; - } - - return result; - } - - private static void AddAt(int[] x, int[] z, int zPos) - { - for (int i = 0; i < x.Length; ++i) - { - z[zPos + i] ^= x[i]; - } - } - - /** - * Compute the result of the division of two polynomials over the field - * <tt>GF(2^m)</tt>. - * - * @param a the first polynomial - * @param f the second polynomial - * @return int[][] {q,r}, where a = q*f+r and deg(r) < deg(f); - */ - private static int[][] Div(int[] a, int[] f) - { - int df = ComputeDegree(f); - if (df == -1) - throw new ArithmeticException("Division by zero."); - - int degreeR1 = ComputeDegree(a); - int[][] result = new int[2][]; - result[0] = new int[System.Math.Max(0, degreeR1 - df) + 1]; - result[1] = Arrays.CopyOf(a, degreeR1 + 1); - - while (df <= degreeR1) - { - int n = degreeR1 - df; - result[0][n] ^= 1; - AddAt(f, result[1], n); - degreeR1 = ComputeDegree(result[1], degreeR1 - 1); - } - result[1] = NormalForm(result[1]); - return result; - } - - /** - * Reduce a polynomial modulo another polynomial. - * - * @param a the polynomial - * @param f the reduction polynomial - * @return <tt>a mod f</tt> - */ - private static int[] Mod(int[] a, int[] f) - { - int df = ComputeDegree(f); - if (df == -1) - throw new ArithmeticException("Division by zero"); - - int degreeR = ComputeDegree(a); - int[] result = Arrays.CopyOf(a, degreeR + 1); - - while (df <= degreeR) - { - int n = degreeR - df; - AddAt(f, result, n); - degreeR = ComputeDegree(result, degreeR - 1); - } - return NormalForm(result); - } - - /** - * Compute the degree of a polynomial. - * - * @param a the polynomial - * @return the degree of the polynomial <tt>a</tt>. If <tt>a</tt> is - * the zero polynomial, return -1. - */ - private static int ComputeDegree(int[] a) - { - return ComputeDegree(a, a.Length - 1); - } - - private static int ComputeDegree(int[] a, int from) - { - int degree; - for (degree = from; degree >= 0 && a[degree] == 0; degree--) - { - } - return degree; - } - - /** - * Strip leading zero coefficients from the given polynomial. - * - * @param a the polynomial - * @return the reduced polynomial - */ - private static int[] NormalForm(int[] a) - { - int d = ComputeDegree(a); - - // if a is the zero polynomial - if (d == -1) - { - // return new zero polynomial - return new int[1]; - } - - // if a already is in normal form - if (a.Length == d + 1) - { - // return a clone of a - return Arrays.Clone(a); - } - - // else, reduce a - int[] result = new int[d + 1]; - Array.Copy(a, 0, result, 0, d + 1); - return result; - } - - /** - * Compute the product of this polynomial and another polynomial modulo a - * third polynomial. - * - * @param a another polynomial - * @param b the reduction polynomial - * @return <tt>this * a mod b</tt> - */ - internal BikePolynomial ModKaratsubaMultiplyBigDeg(BikePolynomial a, BikePolynomial b) - { - int[] resultCoeff = ModKaratsubaMultiplyBigDeg(m_coefficients, a.m_coefficients, b.m_coefficients); - return new BikePolynomial(resultCoeff); - } - - /** - * Compute the inverse of this polynomial modulo the given polynomial. - * - * @param a the reduction polynomial - * @return <tt>this^(-1) mod a</tt> - */ - internal BikePolynomial ModInverseBigDeg(BikePolynomial a) - { - int[] resultCoeff = ModInvBigDeg(m_coefficients, a.m_coefficients); - return new BikePolynomial(resultCoeff); - } - - private static int[] ModInvBigDeg(int[] b, int[] g) - { - int[] r0 = NormalForm(g); - int[] r1 = Mod(b, g); - int[] s0 = { 0 }; - int[] s1 = { 1 }; - int[] s2; - int[][] q; - while (ComputeDegree(r1) != -1) - { - q = Div(r0, r1); - r0 = NormalForm(r1); - r1 = NormalForm(q[1]); - s2 = Add(s0, ModKaratsubaMultiplyBigDeg(q[0], s1, g)); - s0 = NormalForm(s1); - s1 = NormalForm(s2); - } - return s0; - } - - /** - * Compute the product of two polynomials modulo a third polynomial over the - * finite field <tt>GF(2^m)</tt>. - * - * @param aa the first polynomial - * @param bb the second polynomial - * @param g the reduction polynomial - * @return <tt>a * b mod g</tt> - */ - private static int[] ModKaratsubaMultiplyBigDeg(int[] aa, int[] bb, int[] g) - { - int[] a, b; - if (aa.Length >= bb.Length) - { - a = aa; - b = bb; - } - else - { - a = bb; - b = aa; - } - - int n = a.Length; - int m = b.Length; - - int[] D = new int[(n + m) / 2]; - int[] S = new int[n + m - 1]; - int[] T = new int[n + m - 1]; - int[] C = new int[n + m - 1]; - - for (int i = 0; i < m; i++) - { - D[i] = a[i] * b[i]; - } - - for (int i = 1; i < n + m - 2; i++) - { - int pLimit = System.Math.Min(m, (i + 1) >> 1); - for (int p = 0; p < pLimit; p++) - { - int q = i - p; - int aq = q < a.Length ? a[q] : 0; - - if (q < m) - { - S[i] += (a[p] + aq) * (b[p] + b[q]); - T[i] += D[p] + D[q]; - } - else if (q < n) - { - S[i] += (a[p] + aq) * b[p]; - T[i] += D[p]; - } - } - } - - for (int i = 0; i < n + m - 1; i++) - { - if (i == 0) - { - C[i] = D[i] % 2; - } - else if (i == n + m - 2) - { - C[i] = (a[a.Length - 1] * b[b.Length - 1]) % 2; - } - else if (i % 2 == 1) - { - C[i] = (S[i] - T[i]) % 2; - } - else - { - C[i] = (S[i] - T[i] + D[i / 2]) % 2; - } - } - - return Mod(C, g); - } - } -} diff --git a/crypto/src/pqc/crypto/bike/BikeRing.cs b/crypto/src/pqc/crypto/bike/BikeRing.cs new file mode 100644 index 000000000..c2b2102b8 --- /dev/null +++ b/crypto/src/pqc/crypto/bike/BikeRing.cs @@ -0,0 +1,314 @@ +using System; +using System.Diagnostics; +#if NETCOREAPP3_0_OR_GREATER +using System.Runtime.Intrinsics; +using System.Runtime.Intrinsics.X86; +#endif + +using Org.BouncyCastle.Crypto; +using Org.BouncyCastle.Crypto.Utilities; +using Org.BouncyCastle.Math.Raw; +using Org.BouncyCastle.Utilities; + +namespace Org.BouncyCastle.Pqc.Crypto.Bike +{ + internal sealed class BikeRing + { + private readonly int m_bits; + private readonly int m_size; + private readonly int m_sizeExt; + + internal BikeRing(int r) + { + if ((r & 0x80000001) != 1) + throw new ArgumentException(); + + m_bits = r; + m_size = (r + 63) >> 6; + m_sizeExt = m_size * 2; + } + + internal void Add(ulong[] x, ulong[] y, ulong[] z) + { + for (int i = 0; i < Size; ++i) + { + z[i] = x[i] ^ y[i]; + } + } + + internal void Copy(ulong[] x, ulong[] z) + { + for (int i = 0; i < Size; ++i) + { + z[i] = x[i]; + } + } + + internal ulong[] Create() + { + return new ulong[Size]; + } + + internal ulong[] CreateExt() + { + return new ulong[SizeExt]; + } + + internal ulong[] DecodeBits(byte[] bs) + { + if (bs.Length > m_bits) + throw new ArgumentException(); + + ulong[] z = Create(); + for (int i = 0; i < bs.Length; ++i) + { + ulong bit = bs[i]; + if ((bit >> 1) != 0UL) + throw new ArgumentException(); + + z[i >> 6] |= bit << (i & 63); + } + return z; + } + + internal void DecodeBytes(byte[] bs, ulong[] z) + { + int partialBits = m_bits & 63; + Pack.LE_To_UInt64(bs, 0, z, 0, Size - 1); + byte[] last = new byte[8]; + Array.Copy(bs, (Size - 1) << 3, last, 0, (partialBits + 7) >> 3); + z[Size - 1] = Pack.LE_To_UInt64(last); + Debug.Assert((z[Size - 1] >> partialBits) == 0); + } + + internal byte[] EncodeBits(ulong[] x) + { + byte[] bs = new byte[m_bits]; + for (int i = 0; i < m_bits; ++i) + { + bs[i] = (byte)((x[i >> 6] >> (i & 63)) & 1UL); + } + return bs; + } + + internal void EncodeBytes(ulong[] x, byte[] bs) + { + int partialBits = m_bits & 63; + Debug.Assert((x[Size - 1] >> partialBits) == 0); + Pack.UInt64_To_LE(x, 0, Size - 1, bs, 0); + byte[] last = new byte[8]; + Pack.UInt64_To_LE(x[Size - 1], last); + Array.Copy(last, 0, bs, (Size - 1) << 3, (partialBits + 7) >> 3); + } + + internal ulong[] GenerateRandom(int weight, IXof digest) + { + byte[] buf = new byte[4]; + int highest = Integers.HighestOneBit(m_bits); + int mask = highest | (highest - 1); + + ulong[] z = Create(); + int count = 0; + while (count < weight) + { + digest.Output(buf, 0, 4); + int candidate = (int)Pack.LE_To_UInt32(buf) & mask; + if (candidate < m_bits) + { + int pos = candidate >> 6; + ulong bit = 1UL << (candidate & 63); + if ((z[pos] & bit) == 0UL) + { + z[pos] |= bit; + ++count; + } + } + } + return z; + } + + internal void Inv(ulong[] a, ulong[] z) + { + ulong[] f = Create(); + ulong[] g = Create(); + ulong[] t = Create(); + + Copy(a, f); + Copy(a, t); + + int rSub2 = m_bits - 2; + int bits = 32 - Integers.NumberOfLeadingZeros(rSub2); + + for (int i = 1; i < bits; ++i) + { + SquareN(f, 1 << (i - 1), g); + Multiply(f, g, f); + + if ((rSub2 & (1 << i)) != 0) + { + int n = rSub2 & ((1 << i) - 1); + SquareN(f, n, g); + Multiply(t, g, t); + } + } + + Square(t, z); + } + + internal void Multiply(ulong[] x, ulong[] y, ulong[] z) + { + ulong[] tt = CreateExt(); + ImplMultiplyAcc(x, y, tt); + Reduce(tt, z); + } + + internal void Reduce(ulong[] tt, ulong[] z) + { + int partialBits = m_bits & 63; + int excessBits = 64 - partialBits; + ulong partialMask = ulong.MaxValue >> excessBits; + + ulong c = Nat.ShiftUpBits64(Size, tt, Size, excessBits, tt[Size - 1], z, 0); + Debug.Assert(c == 0UL); + + for (int i = 0; i < Size; ++i) + { + z[i] ^= tt[i]; + } + + z[Size - 1] &= partialMask; + } + + internal int Size => m_size; + + internal int SizeExt => m_sizeExt; + + internal void Square(ulong[] x, ulong[] z) + { + ulong[] tt = CreateExt(); + ImplSquare(x, tt); + Reduce(tt, z); + } + + internal void SquareN(ulong[] x, int n, ulong[] z) + { + Debug.Assert(n > 0); + + ulong[] tt = CreateExt(); + ImplSquare(x, tt); + Reduce(tt, z); + + while (--n > 0) + { + ImplSquare(z, tt); + Reduce(tt, z); + } + } + + private void ImplMultiplyAcc(ulong[] x, ulong[] y, ulong[] zz) + { + ulong[] u = new ulong[16]; + + // Schoolbook + + //for (int i = 0; i < Size; ++i) + //{ + // ulong x_i = x[i]; + + // for (int j = 0; j < Size; ++j) + // { + // ulong y_j = y[j]; + + // ImplMulwAcc(u, x_i, y_j, zz, i + j); + // } + //} + + // Arbitrary-degree Karatsuba + + for (int i = 0; i < Size; ++i) + { + ImplMulwAcc(u, x[i], y[i], zz, i << 1); + } + + ulong v0 = zz[0], v1 = zz[1]; + for (int i = 1; i < Size; ++i) + { + v0 ^= zz[i << 1]; zz[i] = v0 ^ v1; v1 ^= zz[(i << 1) + 1]; + } + + ulong w = v0 ^ v1; + for (int i = 0; i < Size; ++i) + { + zz[Size + i] = zz[i] ^ w; + } + + int last = Size - 1; + for (int zPos = 1; zPos < (last * 2); ++zPos) + { + int hi = System.Math.Min(last, zPos); + int lo = zPos - hi; + + while (lo < hi) + { + ImplMulwAcc(u, x[lo] ^ x[hi], y[lo] ^ y[hi], zz, zPos); + + ++lo; + --hi; + } + } + } + + private static void ImplMulwAcc(ulong[] u, ulong x, ulong y, ulong[] z, int zOff) + { +#if NETCOREAPP3_0_OR_GREATER + if (Pclmulqdq.IsSupported) + { + var X = Vector128.CreateScalar(x); + var Y = Vector128.CreateScalar(y); + var Z = Pclmulqdq.CarrylessMultiply(X, Y, 0x00); + z[zOff ] ^= Z.GetElement(0); + z[zOff + 1] ^= Z.GetElement(1); + return; + } +#endif + + //u[0] = 0; + u[1] = y; + for (int i = 2; i < 16; i += 2) + { + u[i ] = u[i >> 1] << 1; + u[i + 1] = u[i ] ^ y; + } + + uint j = (uint)x; + ulong g, h = 0, l = u[j & 15] + ^ u[(j >> 4) & 15] << 4; + int k = 56; + do + { + j = (uint)(x >> k); + g = u[j & 15] + ^ u[(j >> 4) & 15] << 4; + l ^= (g << k); + h ^= (g >> -k); + } + while ((k -= 8) > 0); + + for (int p = 0; p < 7; ++p) + { + x = (x & 0xFEFEFEFEFEFEFEFEUL) >> 1; + h ^= x & (ulong)((long)(y << p) >> 63); + } + + Debug.Assert(h >> 63 == 0); + + z[zOff ] ^= l; + z[zOff + 1] ^= h; + } + + private void ImplSquare(ulong[] x, ulong[] zz) + { + Interleave.Expand64To128(x, 0, Size, zz, 0); + } + } +} diff --git a/crypto/src/pqc/crypto/bike/BikeUtilities.cs b/crypto/src/pqc/crypto/bike/BikeUtilities.cs index 5facdaacf..09143aea0 100644 --- a/crypto/src/pqc/crypto/bike/BikeUtilities.cs +++ b/crypto/src/pqc/crypto/bike/BikeUtilities.cs @@ -1,6 +1,4 @@ -using System; - -using Org.BouncyCastle.Crypto.Utilities; +using Org.BouncyCastle.Crypto.Utilities; using Org.BouncyCastle.Crypto; using Org.BouncyCastle.Utilities; @@ -8,15 +6,12 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike { internal class BikeUtilities { - internal static byte[] XorBytes(byte[] a, byte[] b, int size) + internal static void XorTo(byte[] x, byte[] z, int zLen) { - byte[] output = new byte[size]; - - for (int i = 0; i < size; i++) + for (int i = 0; i < zLen; ++i) { - output[i] = (byte)(a[i] ^ b[i]); + z[i] ^= x[i]; } - return output; } internal static int GetHammingWeight(byte[] bytes) @@ -82,29 +77,6 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike } } - internal static byte[] RemoveLast0Bits(byte[] output) - { - int lastIndexOf1 = 0; - for (int i = output.Length - 1; i >= 0; i--) - { - if (output[i] == 1) - { - lastIndexOf1 = i; - break; - } - } - byte[] res = new byte[lastIndexOf1 + 1]; - Array.Copy(output, 0, res, 0, res.Length); - return res; - } - - internal static byte[] Append0s(byte[] input, int length) - { - byte[] output = new byte[length]; - Array.Copy(input, 0, output, 0, input.Length); - return output; - } - internal static byte[] GenerateRandomByteArray(int mod, int size, int weight, IXof digest) { byte[] buf = new byte[4]; |