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];
|
