diff --git a/crypto/src/pqc/crypto/bike/BikeEngine.cs b/crypto/src/pqc/crypto/bike/BikeEngine.cs
index 7df2703c9..ecd7d7efe 100644
--- a/crypto/src/pqc/crypto/bike/BikeEngine.cs
+++ b/crypto/src/pqc/crypto/bike/BikeEngine.cs
@@ -1,11 +1,9 @@
-using Org.BouncyCastle.Crypto;
+using System;
+
+using Org.BouncyCastle.Crypto;
using Org.BouncyCastle.Crypto.Digests;
-using Org.BouncyCastle.Pqc.Math.LinearAlgebra;
using Org.BouncyCastle.Security;
using Org.BouncyCastle.Utilities;
-using System;
-using System.Collections.Generic;
-using System.Text;
namespace Org.BouncyCastle.Pqc.Crypto.Bike
{
@@ -32,8 +30,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
// tau
private int tau;
- private GF2mField field;
- private PolynomialGF2mSmallM reductionPoly;
+ private BikePolynomial reductionPoly;
private int L_BYTE;
private int R_BYTE;
@@ -49,13 +46,8 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
this.L_BYTE = l / 8;
this.R_BYTE = (r + 7) / 8;
- // finite field GF(2)
- GF2mField field = new GF2mField(1);
- this.field = field;
-
// generate reductionPoly (X^r + 1)
- PolynomialGF2mSmallM poly = new PolynomialGF2mSmallM(field, r);
- this.reductionPoly = poly.AddMonomial(0);
+ this.reductionPoly = new BikePolynomial(r);
}
public int GetSessionKeySize()
@@ -143,11 +135,11 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
byte[] h1Cut = Utils.RemoveLast0Bits(h1Bits);
// 2. Compute h
- PolynomialGF2mSmallM h0Poly = new PolynomialGF2mSmallM(this.field, h0Cut);
- PolynomialGF2mSmallM h1Poly = new PolynomialGF2mSmallM(this.field, h1Cut);
+ BikePolynomial h0Poly = new BikePolynomial(h0Cut);
+ BikePolynomial h1Poly = new BikePolynomial(h1Cut);
- PolynomialGF2mSmallM h0Inv = h0Poly.ModInverseBigDeg(reductionPoly);
- PolynomialGF2mSmallM hPoly = h1Poly.ModKaratsubaMultiplyBigDeg(h0Inv, reductionPoly);
+ BikePolynomial h0Inv = h0Poly.ModInverseBigDeg(reductionPoly);
+ BikePolynomial hPoly = h1Poly.ModKaratsubaMultiplyBigDeg(h0Inv, reductionPoly);
// Get coefficients of hPoly
byte[] hTmp = hPoly.GetEncoded();
@@ -191,15 +183,15 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
byte[] e0Cut = Utils.RemoveLast0Bits(e0Bits);
byte[] e1Cut = Utils.RemoveLast0Bits(e1Bits);
- PolynomialGF2mSmallM e0 = new PolynomialGF2mSmallM(field, e0Cut);
- PolynomialGF2mSmallM e1 = new PolynomialGF2mSmallM(field, e1Cut);
+ BikePolynomial e0 = new BikePolynomial(e0Cut);
+ BikePolynomial e1 = new BikePolynomial(e1Cut);
// 3. Calculate c
// calculate c0
byte[] h0Bits = new byte[r];
Utils.FromByteArrayToBitArray(h0Bits, h);
- PolynomialGF2mSmallM hPoly = new PolynomialGF2mSmallM(field, Utils.RemoveLast0Bits(h0Bits));
- PolynomialGF2mSmallM c0Poly = e0.add(e1.ModKaratsubaMultiplyBigDeg(hPoly, reductionPoly));
+ BikePolynomial hPoly = new BikePolynomial(Utils.RemoveLast0Bits(h0Bits));
+ BikePolynomial c0Poly = e0.Add(e1.ModKaratsubaMultiplyBigDeg(hPoly, reductionPoly));
byte[] c0Bits = c0Poly.GetEncoded();
byte[] c0Bytes = new byte[R_BYTE];
@@ -287,10 +279,10 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
private byte[] ComputeSyndrome(byte[] h0, byte[] c0)
{
- PolynomialGF2mSmallM coPoly = new PolynomialGF2mSmallM(field, c0);
- PolynomialGF2mSmallM h0Poly = new PolynomialGF2mSmallM(field, h0);
+ BikePolynomial coPoly = new BikePolynomial(c0);
+ BikePolynomial h0Poly = new BikePolynomial(h0);
- PolynomialGF2mSmallM s = coPoly.ModKaratsubaMultiplyBigDeg(h0Poly, reductionPoly);
+ BikePolynomial s = coPoly.ModKaratsubaMultiplyBigDeg(h0Poly, reductionPoly);
byte[] transposedS = Transpose(s.GetEncoded());
return transposedS;
}
@@ -318,11 +310,11 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
BFMaskedIter(s, e, gray, (hw + 1) / 2 + 1, h0Compact, h1Compact, h0CompactCol, h1CompactCol);
}
}
+
if (Utils.GetHammingWeight(s) == 0)
- {
return e;
- }
- else return null;
+
+ return null;
}
private byte[] Transpose(byte[] input)
@@ -336,6 +328,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
}
return output;
}
+
private void BFIter(byte[] s, byte[] e, int T, int[] h0Compact, int[] h1Compact, int[] h0CompactCol, int[] h1CompactCol, byte[] black, byte[] gray)
{
int[] updatedIndices = new int[2 * r];
diff --git a/crypto/src/pqc/crypto/bike/BikeParameters.cs b/crypto/src/pqc/crypto/bike/BikeParameters.cs
index e5695c48f..e4d06b861 100644
--- a/crypto/src/pqc/crypto/bike/BikeParameters.cs
+++ b/crypto/src/pqc/crypto/bike/BikeParameters.cs
@@ -1,11 +1,11 @@
-using Org.BouncyCastle.Crypto;
-using System;
-using System.Collections.Generic;
-using System.Text;
+using System;
+
+using Org.BouncyCastle.Crypto;
namespace Org.BouncyCastle.Pqc.Crypto.Bike
{
- public class BikeParameters : ICipherParameters
+ public class BikeParameters
+ : ICipherParameters
{
// 128 bits security
public static BikeParameters bike128 = new BikeParameters("bike128", 12323, 142, 134, 256, 5, 3, 128);
@@ -26,7 +26,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
private int defaultKeySize;
private BikeEngine bikeEngine;
- internal BikeParameters(String name, int r, int w, int t, int l, int nbIter, int tau, int defaultKeySize)
+ internal BikeParameters(string name, int r, int w, int t, int l, int nbIter, int tau, int defaultKeySize)
{
this.name = name;
this.r = r;
diff --git a/crypto/src/pqc/crypto/bike/BikePolynomial.cs b/crypto/src/pqc/crypto/bike/BikePolynomial.cs
new file mode 100644
index 000000000..0d66fe433
--- /dev/null
+++ b/crypto/src/pqc/crypto/bike/BikePolynomial.cs
@@ -0,0 +1,469 @@
+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^r + 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 = NormalForm(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(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 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;
+ }
+
+ /**
+ * Compute the product of a polynomial a with an element from the finite
+ * field <tt>GF(2^m)</tt>.
+ *
+ * @param a the polynomial
+ * @param element an element of the finite field GF(2^m)
+ * @return <tt>a * element</tt>
+ */
+ private int[] MultWithElement(int[] a, int element)
+ {
+ return element == 0 ? new int[1] : Arrays.Clone(a);
+ }
+
+ /**
+ * Compute the product of a polynomial with a monomial X^k.
+ *
+ * @param a the polynomial
+ * @param k the degree of the monomial
+ * @return <tt>a * X^k</tt>
+ */
+ private static int[] MultWithMonomial(int[] a, int k)
+ {
+ int d = ComputeDegree(a);
+ if (d == -1)
+ return new int[1];
+
+ int[] result = new int[k + d + 1];
+ Array.Copy(a, 0, result, k, d + 1);
+ return result;
+ }
+
+ /**
+ * 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 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[1]{ 0 };
+ result[1] = Arrays.CopyOf(a, degreeR1 + 1);
+
+ while (df <= degreeR1)
+ {
+ int[] q;
+ int[] coeff = new int[1];
+ coeff[0] = degreeR1 == -1 ? 0 : result[1][degreeR1];
+ q = MultWithElement(f, coeff[0]);
+ int n = degreeR1 - df;
+ q = MultWithMonomial(q, n);
+ coeff = MultWithMonomial(coeff, n);
+ result[0] = Add(coeff, result[0]);
+ result[1] = Add(q, result[1]);
+ degreeR1 = ComputeDegree(result[1]);
+ }
+ return result;
+ }
+
+ /**
+ * Compute the product of two polynomials over the field <tt>GF(2^m)</tt>
+ * using a Karatzuba like multiplication.
+ *
+ * @param a the first polynomial
+ * @param b the second polynomial
+ * @return a * b
+ */
+ private int[] Multiply(int[] a, int[] b)
+ {
+ int[] mult1, mult2;
+ if (ComputeDegree(a) < ComputeDegree(b))
+ {
+ mult1 = b;
+ mult2 = a;
+ }
+ else
+ {
+ mult1 = a;
+ mult2 = b;
+ }
+
+ mult1 = NormalForm(mult1);
+ mult2 = NormalForm(mult2);
+
+ if (mult2.Length == 1)
+ return MultWithElement(mult1, mult2[0]);
+
+ int d1 = mult1.Length;
+ int d2 = mult2.Length;
+ int[] result;
+
+ if (d2 != d1)
+ {
+ int[] res1 = new int[d2];
+ int[] res2 = new int[d1 - d2];
+ Array.Copy(mult1, 0, res1, 0, res1.Length);
+ Array.Copy(mult1, d2, res2, 0, res2.Length);
+ res1 = Multiply(res1, mult2);
+ res2 = Multiply(res2, mult2);
+ res2 = MultWithMonomial(res2, d2);
+ result = Add(res1, res2);
+ }
+ else
+ {
+ d2 = (int)((uint)(d1 + 1) >> 1);
+ int d = d1 - d2;
+ int[] firstPartMult1 = new int[d2];
+ int[] firstPartMult2 = new int[d2];
+ int[] secondPartMult1 = new int[d];
+ int[] secondPartMult2 = new int[d];
+ Array.Copy(mult1, 0, firstPartMult1, 0, firstPartMult1.Length);
+ Array.Copy(mult1, d2, secondPartMult1, 0, secondPartMult1.Length);
+ Array.Copy(mult2, 0, firstPartMult2, 0, firstPartMult2.Length);
+ Array.Copy(mult2, d2, secondPartMult2, 0, secondPartMult2.Length);
+ int[] helpPoly1 = Add(firstPartMult1, secondPartMult1);
+ int[] helpPoly2 = Add(firstPartMult2, secondPartMult2);
+ int[] res1 = Multiply(firstPartMult1, firstPartMult2);
+ int[] res2 = Multiply(helpPoly1, helpPoly2);
+ int[] res3 = Multiply(secondPartMult1, secondPartMult2);
+ res2 = Add(res2, res1);
+ res2 = Add(res2, res3);
+ res3 = MultWithMonomial(res3, d2);
+ result = Add(res2, res3);
+ result = MultWithMonomial(result, d2);
+ result = Add(result, res1);
+ }
+
+ return result;
+ }
+
+ /**
+ * Reduce a polynomial modulo another polynomial.
+ *
+ * @param a the polynomial
+ * @param f the reduction polynomial
+ * @return <tt>a mod f</tt>
+ */
+ private 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 coeff = degreeR == -1 ? 0 : result[degreeR];
+ int[] q = MultWithMonomial(f, degreeR - df);
+ q = MultWithElement(q, coeff);
+ result = Add(q, result);
+ degreeR = ComputeDegree(result);
+ }
+ return 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)
+ {
+ int degree;
+ for (degree = a.Length - 1; 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 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 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 ap = a[p];
+ int aq = q < a.Length ? a[q] : 0;
+
+ int bp = b[p];
+ int dp = D[p];
+
+ if (q < m)
+ {
+ int bq = b[q];
+ int dq = D[q];
+
+ S[i] = S[i] + (ap + aq) * (bp + bq);
+ T[i] = T[i] + dp + dq;
+ }
+ else if (q < n)
+ {
+ S[i] = S[i] + ((ap + aq) * bp);
+ T[i] = T[i] + dp;
+ }
+ }
+ }
+
+ 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/BikeRandomGenerator.cs b/crypto/src/pqc/crypto/bike/BikeRandomGenerator.cs
index 4d9a90252..7117c1d9d 100644
--- a/crypto/src/pqc/crypto/bike/BikeRandomGenerator.cs
+++ b/crypto/src/pqc/crypto/bike/BikeRandomGenerator.cs
@@ -1,40 +1,21 @@
using Org.BouncyCastle.Crypto;
using Org.BouncyCastle.Crypto.Utilities;
-using System;
-using System.Collections.Generic;
-using System.Text;
+using Org.BouncyCastle.Utilities;
namespace Org.BouncyCastle.Pqc.Crypto.Bike
{
- class BikeRandomGenerator
+ internal class BikeRandomGenerator
{
- private static int BitScanReverse(int t)
- {
- int res = 0;
- while (t != 0)
- {
- t >>= 1;
- res++;
- }
-
- return res;
- }
-
private static int GetRandomInMod(int mod, IXof digest)
{
- int mask = MaskNumber(BitScanReverse(mod));
- int res = -1;
+ int highest = Integers.HighestOneBit(mod);
+ int mask = highest | (highest - 1);
while (true)
{
- res = GetRandomNumber(digest);
- res &= mask;
-
+ int res = GetRandomNumber(digest) & mask;
if (res < mod)
- {
- break;
- }
+ return res;
}
- return res;
}
private static void GenerateRandomArray(byte[] res, int mod, int weight, IXof digest)
@@ -59,8 +40,6 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
return ((a[index] >> (pos)) & 0x01);
}
-
-
private static void SetBit(byte[] a, int position)
{
int index = position / 8;
@@ -75,17 +54,11 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
return res;
}
- private static int MaskNumber(int n)
- {
- return ((1 << n) - 1);
- }
-
private static int GetRandomNumber(IXof digest)
{
byte[] output = new byte[4];
digest.Output(output, 0, output.Length);
- int tmp = (int)Pack.LE_To_UInt32(output, 0);
- return tmp;
+ return (int)Pack.LE_To_UInt32(output, 0);
}
}
}
diff --git a/crypto/src/pqc/crypto/bike/Utils.cs b/crypto/src/pqc/crypto/bike/Utils.cs
index 8a1a05e37..5d151f522 100644
--- a/crypto/src/pqc/crypto/bike/Utils.cs
+++ b/crypto/src/pqc/crypto/bike/Utils.cs
@@ -1,10 +1,8 @@
using System;
-using System.Collections.Generic;
-using System.Text;
namespace Org.BouncyCastle.Pqc.Crypto.Bike
{
- class Utils
+ internal class Utils
{
internal static byte[] XorBytes(byte[] a, byte[] b, int size)
{
@@ -34,7 +32,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
{
for (int j = 0; j != 8; j++)
{
- output[i * 8 + j] = (byte)UnsignedRightBitShiftInt(input[i] & (1 << j), j);
+ output[i * 8 + j] = (byte)((input[i] >> j) & 1);
}
}
if (output.Length % 8 != 0)
@@ -43,7 +41,7 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
int count = 0;
while (off < output.Length)
{
- output[off++] = (byte)(UnsignedRightBitShiftInt(input[max] & (1 << count), count));
+ output[off++] = (byte)((input[max] >> count) & 1);
count++;
}
}
@@ -102,18 +100,5 @@ namespace Org.BouncyCastle.Pqc.Crypto.Bike
Array.Copy(input, 0, output, 0, input.Length);
return output;
}
- internal static int UnsignedRightBitShiftInt(int a, int b)
- {
- uint tmp = (uint)a;
- tmp >>= b;
- return (int)tmp;
- }
-
- internal static long UnsignedRightBitShiftLong(long a, int b)
- {
- ulong tmp = (ulong)a;
- tmp >>= b;
- return (long)tmp;
- }
}
}
diff --git a/crypto/src/pqc/math/linearalgebra/GF2mField.cs b/crypto/src/pqc/math/linearalgebra/GF2mField.cs
deleted file mode 100644
index e8182bf6f..000000000
--- a/crypto/src/pqc/math/linearalgebra/GF2mField.cs
+++ /dev/null
@@ -1,370 +0,0 @@
-using Org.BouncyCastle.Security;
-using System;
-
-namespace Org.BouncyCastle.Pqc.Math.LinearAlgebra
-{
- public class GF2mField
- {
-
- /*
- * degree - degree of the field polynomial - the field polynomial ring -
- * polynomial ring over the finite field GF(2)
- */
-
- private int degree = 0;
-
- private int polynomial;
-
- /**
- * create a finite field GF(2^m)
- *
- * @param degree the degree of the field
- */
- public GF2mField(int degree)
- {
- if (degree >= 32)
- {
- throw new ArgumentException(
- " Error: the degree of field is too large ");
- }
- if (degree < 1)
- {
- throw new ArgumentException(
- " Error: the degree of field is non-positive ");
- }
- this.degree = degree;
- polynomial = PolynomialRingGF2.GetIrreduciblePolynomial(degree);
- }
-
- /**
- * create a finite field GF(2^m) with the fixed field polynomial
- *
- * @param degree the degree of the field
- * @param poly the field polynomial
- */
- public GF2mField(int degree, int poly)
- {
- if (degree != PolynomialRingGF2.Degree(poly))
- {
- throw new ArgumentException(
- " Error: the degree is not correct");
- }
- if (!PolynomialRingGF2.IsIrreducible(poly))
- {
- throw new ArgumentException(
- " Error: given polynomial is reducible");
- }
- this.degree = degree;
- polynomial = poly;
-
- }
-
- public GF2mField(byte[] enc)
- {
- if (enc.Length != 4)
- {
- throw new ArgumentException(
- "byte array is not an encoded finite field");
- }
- polynomial = LittleEndianConversions.OS2IP(enc);
- if (!PolynomialRingGF2.IsIrreducible(polynomial))
- {
- throw new ArgumentException(
- "byte array is not an encoded finite field");
- }
-
- degree = PolynomialRingGF2.Degree(polynomial);
- }
-
- public GF2mField(GF2mField field)
- {
- degree = field.degree;
- polynomial = field.polynomial;
- }
-
- /**
- * return degree of the field
- *
- * @return degree of the field
- */
- public int GetDegree()
- {
- return degree;
- }
-
- /**
- * return the field polynomial
- *
- * @return the field polynomial
- */
- public int GetPolynomial()
- {
- return polynomial;
- }
-
- /**
- * return the encoded form of this field
- *
- * @return the field in byte array form
- */
- public byte[] GetEncoded()
- {
- return LittleEndianConversions.I2OSP(polynomial);
- }
-
- /**
- * Return sum of two elements
- *
- * @param a
- * @param b
- * @return a+b
- */
- public int add(int a, int b)
- {
- return a ^ b;
- }
-
- /**
- * Return product of two elements
- *
- * @param a
- * @param b
- * @return a*b
- */
- public int Mult(int a, int b)
- {
- return PolynomialRingGF2.modMultiply(a, b, polynomial);
- }
-
- /**
- * compute exponentiation a^k
- *
- * @param a a field element a
- * @param k k degree
- * @return a^k
- */
- public int Exp(int a, int k)
- {
- if (k == 0)
- {
- return 1;
- }
- if (a == 0)
- {
- return 0;
- }
- if (a == 1)
- {
- return 1;
- }
- int result = 1;
- if (k < 0)
- {
- a = Inverse(a);
- k = -k;
- }
- while (k != 0)
- {
- if ((k & 1) == 1)
- {
- result = Mult(result, a);
- }
- a = Mult(a, a);
- //k >>>= 1;
- uint kTmp = (uint)k;
- kTmp >>= 1;
- k = (int) kTmp;
- }
- return result;
- }
-
- /**
- * compute the multiplicative inverse of a
- *
- * @param a a field element a
- * @return a<sup>-1</sup>
- */
- public int Inverse(int a)
- {
- int d = (1 << degree) - 2;
-
- return Exp(a, d);
- }
-
- /**
- * compute the square root of an integer
- *
- * @param a a field element a
- * @return a<sup>1/2</sup>
- */
- public int SqRoot(int a)
- {
- for (int i = 1; i < degree; i++)
- {
- a = Mult(a, a);
- }
- return a;
- }
-
- /**
- * create a random field element using PRNG sr
- *
- * @param sr SecureRandom
- * @return a random element
- */
- public int GetRandomElement(SecureRandom sr)
- {
- int result = RandUtils.NextInt(sr, 1 << degree);
- return result;
- }
-
- /**
- * create a random non-zero field element
- *
- * @return a random element
- */
- //public int getRandomNonZeroElement()
- //{
- // return getRandomNonZeroElement(CryptoServicesRegistrar.getSecureRandom());
- //}
-
- /**
- * create a random non-zero field element using PRNG sr
- *
- * @param sr SecureRandom
- * @return a random non-zero element
- */
- public int GetRandomNonZeroElement(SecureRandom sr)
- {
- int controltime = 1 << 20;
- int count = 0;
- int result = RandUtils.NextInt(sr, 1 << degree);
- while ((result == 0) && (count < controltime))
- {
- result = RandUtils.NextInt(sr, 1 << degree);
- count++;
- }
- if (count == controltime)
- {
- result = 1;
- }
- return result;
- }
-
- /**
- * @return true if e is encoded element of this field and false otherwise
- */
- public bool IsElementOfThisField(int e)
- {
- // e is encoded element of this field iff 0<= e < |2^m|
- if (degree == 31)
- {
- return e >= 0;
- }
- return e >= 0 && e < (1 << degree);
- }
-
- /*
- * help method for visual control
- */
- public String ElementToStr(int a)
- {
- String s = "";
- for (int i = 0; i < degree; i++)
- {
- if (((byte)a & 0x01) == 0)
- {
- s = "0" + s;
- }
- else
- {
- s = "1" + s;
- }
- //a >>>= 1;
- uint aTmp = (uint)a;
- aTmp >>= 1;
- a = (int)aTmp;
- }
- return s;
- }
-
- /**
- * checks if given object is equal to this field.
- * <p>
- * The method returns false whenever the given object is not GF2m.
- *
- * @param other object
- * @return true or false
- */
- public bool Equals(Object other)
- {
- if ((other == null) || !(other is GF2mField))
- {
- return false;
- }
-
- GF2mField otherField = (GF2mField)other;
-
- if ((degree == otherField.degree)
- && (polynomial == otherField.polynomial))
- {
- return true;
- }
-
- return false;
- }
-
- public int HashCode()
- {
- return polynomial;
- }
-
- /**
- * Returns a human readable form of this field.
- *
- * @return a human readable form of this field.
- */
- public String ToString()
- {
- String str = "Finite Field GF(2^" + degree + ") = " + "GF(2)[X]/<"
- + PolyToString(polynomial) + "> ";
- return str;
- }
-
- private static String PolyToString(int p)
- {
- String str = "";
- if (p == 0)
- {
- str = "0";
- }
- else
- {
- byte b = (byte)(p & 0x01);
- if (b == 1)
- {
- str = "1";
- }
- //p >>>= 1;
- uint pTmp = (uint)p;
- pTmp >>= 1;
- p = (int)pTmp;
- int i = 1;
- while (p != 0)
- {
- b = (byte)(p & 0x01);
- if (b == 1)
- {
- str = str + "+x^" + i;
- }
- //p >>>= 1;
- pTmp = (uint) p;
- pTmp >>= 1;
- p = (int)pTmp;
- i++;
- }
- }
- return str;
- }
- }
-}
\ No newline at end of file
diff --git a/crypto/src/pqc/math/linearalgebra/GF2mVector.cs b/crypto/src/pqc/math/linearalgebra/GF2mVector.cs
deleted file mode 100644
index f0e44ebe6..000000000
--- a/crypto/src/pqc/math/linearalgebra/GF2mVector.cs
+++ /dev/null
@@ -1,221 +0,0 @@
-using System;
-
-namespace Org.BouncyCastle.Pqc.Math.LinearAlgebra
-{
- /**
- * This class implements vectors over the finite field
- * <tt>GF(2<sup>m</sup>)</tt> for small <tt>m</tt> (i.e.,
- * <tt>1<m<32</tt>). It extends the abstract class {@link Vector}.
- */
-public class GF2mVector : Vector
-{
-
- /**
- * the finite field this vector is defined over
- */
- private GF2mField field;
-
- /**
- * the element array
- */
- private int[] vector;
-
- /**
- * creates the vector over GF(2^m) of given length and with elements from
- * array v (beginning at the first bit)
- *
- * @param field finite field
- * @param v array with elements of vector
- */
- public GF2mVector(GF2mField field, byte[] v)
- {
- this.field = new GF2mField(field);
-
- // decode vector
- int d = 8;
- int count = 1;
- while (field.GetDegree() > d)
- {
- count++;
- d += 8;
- }
-
- if ((v.Length % count) != 0)
- {
- throw new ArgumentException(
- "Byte array is not an encoded vector over the given finite field.");
- }
-
- length = v.Length / count;
- vector = new int[length];
- count = 0;
- for (int i = 0; i < vector.Length; i++)
- {
- for (int j = 0; j < d; j += 8)
- {
- vector[i] |= (v[count++] & 0xff) << j;
- }
- if (!field.IsElementOfThisField(vector[i]))
- {
- throw new ArgumentException(
- "Byte array is not an encoded vector over the given finite field.");
- }
- }
- }
-
- /**
- * Create a new vector over <tt>GF(2<sup>m</sup>)</tt> of the given
- * length and element array.
- *
- * @param field the finite field <tt>GF(2<sup>m</sup>)</tt>
- * @param vector the element array
- */
- public GF2mVector(GF2mField field, int[] vector)
- {
- this.field = field;
- length = vector.Length;
- for (int i = vector.Length - 1; i >= 0; i--)
- {
- if (!field.IsElementOfThisField(vector[i]))
- {
- throw new ArithmeticException(
- "Element array is not specified over the given finite field.");
- }
- }
- this.vector = IntUtils.Clone(vector);
- }
-
- /**
- * Copy constructor.
- *
- * @param other another {@link GF2mVector}
- */
- public GF2mVector(GF2mVector other)
- {
- field = new GF2mField(other.field);
- length = other.length;
- vector = IntUtils.Clone(other.vector);
- }
-
- /**
- * @return the finite field this vector is defined over
- */
- public GF2mField GetField()
- {
- return field;
- }
-
- /**
- * @return int[] form of this vector
- */
- public int[] GetIntArrayForm()
- {
- return IntUtils.Clone(vector);
- }
-
- /**
- * @return a byte array encoding of this vector
- */
- public override byte[] GetEncoded()
- {
- int d = 8;
- int count = 1;
- while (field.GetDegree() > d)
- {
- count++;
- d += 8;
- }
-
- byte[] res = new byte[vector.Length * count];
- count = 0;
- for (int i = 0; i < vector.Length; i++)
- {
- for (int j = 0; j < d; j += 8)
- {
- res[count++] = (byte)(Utils.UnsignedRightBitShiftInt(vector[i], j));
- }
- }
-
- return res;
- }
-
- /**
- * @return whether this is the zero vector (i.e., all elements are zero)
- */
- public override bool IsZero()
- {
- for (int i = vector.Length - 1; i >= 0; i--)
- {
- if (vector[i] != 0)
- {
- return false;
- }
- }
- return true;
- }
-
- /**
- * Add another vector to this vector. Method is not yet implemented.
- *
- * @param addend the other vector
- * @return <tt>this + addend</tt>
- * @throws ArithmeticException if the other vector is not defined over the same field as
- * this vector.
- * <p>
- * TODO: implement this method
- */
- public override Vector Add(Vector addend)
- {
- throw new SystemException("not implemented");
- }
-
- /**
- * Multiply this vector with a permutation.
- *
- * @param p the permutation
- * @return <tt>this*p = p*this</tt>
- */
- public override Vector Multiply(Permutation p)
- {
- int[] pVec = p.GetVector();
- if (length != pVec.Length)
- {
- throw new ArithmeticException(
- "permutation size and vector size mismatch");
- }
-
- int[] result = new int[length];
- for (int i = 0; i < pVec.Length; i++)
- {
- result[i] = vector[pVec[i]];
- }
-
- return new GF2mVector(field, result);
- }
-
- /**
- * Compare this vector with another object.
- *
- * @param other the other object
- * @return the result of the comparison
- */
- public override bool Equals(Object other)
- {
-
- if (!(other is GF2mVector))
- {
- return false;
- }
- GF2mVector otherVec = (GF2mVector)other;
-
- if (!field.Equals(otherVec.field))
- {
- return false;
- }
-
- return IntUtils.Equals(vector, otherVec.vector);
- }
-
-
- }
-}
diff --git a/crypto/src/pqc/math/linearalgebra/IntUtils.cs b/crypto/src/pqc/math/linearalgebra/IntUtils.cs
deleted file mode 100644
index 0a7671df6..000000000
--- a/crypto/src/pqc/math/linearalgebra/IntUtils.cs
+++ /dev/null
@@ -1,159 +0,0 @@
-using Org.BouncyCastle.Utilities;
-using System;
-
-namespace Org.BouncyCastle.Pqc.Math.LinearAlgebra
-{
- public class IntUtils
- {
-
- /**
- * Default constructor (private).
- */
- private IntUtils()
- {
- // empty
- }
-
- /**
- * Compare two int arrays. No null checks are performed.
- *
- * @param left the first int array
- * @param right the second int array
- * @return the result of the comparison
- */
- public static bool Equals(int[] left, int[] right)
- {
- return Arrays.AreEqual(left, right);
- }
-
- /**
- * Return a clone of the given int array. No null checks are performed.
- *
- * @param array the array to clone
- * @return the clone of the given array
- */
- public static int[] Clone(int[] array)
- {
- return Arrays.Clone(array);
- }
-
- /**
- * Fill the given int array with the given value.
- *
- * @param array the array
- * @param value the value
- */
- public static void Fill(int[] array, int value)
- {
- Arrays.Fill(array, value);
- }
-
- /**
- * Sorts this array of integers according to the Quicksort algorithm. After
- * calling this method this array is sorted in ascending order with the
- * smallest integer taking position 0 in the array.
- * <p>
- * This implementation is based on the quicksort algorithm as described in
- * <code>Data Structures In Java</code> by Thomas A. Standish, Chapter 10,
- * ISBN 0-201-30564-X.
- *
- * @param source the array of integers that needs to be sorted.
- */
- public static void Quicksort(int[] source)
- {
- Quicksort(source, 0, source.Length - 1);
- }
-
- /**
- * Sort a subarray of a source array. The subarray is specified by its start
- * and end index.
- *
- * @param source the int array to be sorted
- * @param left the start index of the subarray
- * @param right the end index of the subarray
- */
- public static void Quicksort(int[] source, int left, int right)
- {
- if (right > left)
- {
- int index = Partition(source, left, right, right);
- Quicksort(source, left, index - 1);
- Quicksort(source, index + 1, right);
- }
- }
-
- /**
- * Split a subarray of a source array into two partitions. The left
- * partition contains elements that have value less than or equal to the
- * pivot element, the right partition contains the elements that have larger
- * value.
- *
- * @param source the int array whose subarray will be splitted
- * @param left the start position of the subarray
- * @param right the end position of the subarray
- * @param pivotIndex the index of the pivot element inside the array
- * @return the new index of the pivot element inside the array
- */
- private static int Partition(int[] source, int left, int right,
- int pivotIndex)
- {
-
- int pivot = source[pivotIndex];
- source[pivotIndex] = source[right];
- source[right] = pivot;
-
- int index = left;
- int tmp = 0;
- for (int i = left; i < right; i++)
- {
- if (source[i] <= pivot)
- {
- tmp = source[index];
- source[index] = source[i];
- source[i] = tmp;
- index++;
- }
- }
-
- tmp = source[index];
- source[index] = source[right];
- source[right] = tmp;
-
- return index;
- }
-
- /**
- * Generates a subarray of a given int array.
- *
- * @param input -
- * the input int array
- * @param start -
- * the start index
- * @param end -
- * the end index
- * @return a subarray of <tt>input</tt>, ranging from <tt>start</tt> to
- * <tt>end</tt>
- */
- public static int[] SubArray( int[] input, int start,
- int end)
- {
- int[] result = new int[end - start];
- Array.Copy(input, start, result, 0, end - start);
- return result;
- }
-
- /**
- * @param input an int array
- * @return a human readable form of the given int array
- */
- public static String ToString(int[] input)
- {
- String result = "";
- for (int i = 0; i < input.Length; i++)
- {
- result += input[i] + " ";
- }
- return result;
- }
- }
-}
diff --git a/crypto/src/pqc/math/linearalgebra/LittleEndianConversions.cs b/crypto/src/pqc/math/linearalgebra/LittleEndianConversions.cs
deleted file mode 100644
index 5b3215070..000000000
--- a/crypto/src/pqc/math/linearalgebra/LittleEndianConversions.cs
+++ /dev/null
@@ -1,195 +0,0 @@
-
-using Org.BouncyCastle.Crypto.Utilities;
-
-namespace Org.BouncyCastle.Pqc.Math.LinearAlgebra
-{
- /**
- * This is a utility class containing data type conversions using little-endian
- * byte order.
- *
- */
- class LittleEndianConversions
- {
- /**
- * Default constructor (private).
- */
- private LittleEndianConversions()
- {
- // empty
- }
-
- /**
- * Convert an octet string of length 4 to an integer. No length checking is
- * performed.
- *
- * @param input the byte array holding the octet string
- * @return an integer representing the octet string <tt>input</tt>
- * @throws ArithmeticException if the length of the given octet string is larger than 4.
- */
- public static int OS2IP(byte[] input)
- {
- return (int)Pack.LE_To_UInt32(input);
- }
-
- /**
- * Convert an byte array of length 4 beginning at <tt>offset</tt> into an
- * integer.
- *
- * @param input the byte array
- * @param inOff the offset into the byte array
- * @return the resulting integer
- */
- public static int OS2IP(byte[] input, int inOff)
- {
- return (int)Pack.LE_To_UInt32(input, inOff);
- }
-
- /**
- * Convert a byte array of the given length beginning at <tt>offset</tt>
- * into an integer.
- *
- * @param input the byte array
- * @param inOff the offset into the byte array
- * @param inLen the length of the encoding
- * @return the resulting integer
- */
- public static int OS2IP(byte[] input, int inOff, int inLen)
- {
- int result = 0;
- for (int i = inLen - 1; i >= 0; i--)
- {
- result |= (input[inOff + i] & 0xff) << (8 * i);
- }
- return result;
- }
-
- /**
- * Convert a byte array of length 8 beginning at <tt>inOff</tt> into a
- * long integer.
- *
- * @param input the byte array
- * @param inOff the offset into the byte array
- * @return the resulting long integer
- */
- public static long OS2LIP(byte[] input, int inOff)
- {
- return (long)Pack.LE_To_UInt64(input, inOff);
- }
-
- /**
- * Convert an integer to an octet string of length 4.
- *
- * @param x the integer to convert
- * @return the converted integer
- */
- public static byte[] I2OSP(int x)
- {
- return Pack.UInt32_To_LE((uint)x);
- }
-
- /**
- * Convert an integer into a byte array beginning at the specified offset.
- *
- * @param value the integer to convert
- * @param output the byte array to hold the result
- * @param outOff the integer offset into the byte array
- */
- public static void I2OSP(int value, byte[] output, int outOff)
- {
- Pack.UInt32_To_LE((uint)value, output, outOff);
- }
-
- /**
- * Convert an integer to a byte array beginning at the specified offset. No
- * length checking is performed (i.e., if the integer cannot be encoded with
- * <tt>length</tt> octets, it is truncated).
- *
- * @param value the integer to convert
- * @param output the byte array to hold the result
- * @param outOff the integer offset into the byte array
- * @param outLen the length of the encoding
- */
- public static void I2OSP(int value, byte[] output, int outOff, int outLen)
- {
- uint valueTmp = (uint)value;
- for (int i = outLen - 1; i >= 0; i--)
- {
- output[outOff + i] = (byte)(valueTmp >> (8 * i));
- }
- }
-
- /**
- * Convert an integer to a byte array of length 8.
- *
- * @param input the integer to convert
- * @return the converted integer
- */
- public static byte[] I2OSP(long input)
- {
- return Pack.UInt64_To_LE((ulong)input);
- }
-
- /**
- * Convert an integer to a byte array of length 8.
- *
- * @param input the integer to convert
- * @param output byte array holding the output
- * @param outOff offset in output array where the result is stored
- */
- public static void I2OSP(long input, byte[] output, int outOff)
- {
- Pack.UInt64_To_LE((ulong)input, output, outOff);
- }
-
- /**
- * Convert an int array to a byte array of the specified length. No length
- * checking is performed (i.e., if the last integer cannot be encoded with
- * <tt>length % 4</tt> octets, it is truncated).
- *
- * @param input the int array
- * @param outLen the length of the converted array
- * @return the converted array
- */
- public static byte[] ToByteArray(int[] input, int outLen)
- {
- int intLen = input.Length;
- byte[] result = new byte[outLen];
- int index = 0;
- for (int i = 0; i <= intLen - 2; i++, index += 4)
- {
- I2OSP(input[i], result, index);
- }
- I2OSP(input[intLen - 1], result, index, outLen - index);
- return result;
- }
-
- /**
- * Convert a byte array to an int array.
- *
- * @param input the byte array
- * @return the converted array
- */
- public static int[] ToIntArray(byte[] input)
- {
- int intLen = (input.Length + 3) / 4;
- int lastLen = input.Length & 0x03;
- int[] result = new int[intLen];
-
- int index = 0;
- for (int i = 0; i <= intLen - 2; i++, index += 4)
- {
- result[i] = OS2IP(input, index);
- }
- if (lastLen != 0)
- {
- result[intLen - 1] = OS2IP(input, index, lastLen);
- }
- else
- {
- result[intLen - 1] = OS2IP(input, index);
- }
-
- return result;
- }
- }
-}
diff --git a/crypto/src/pqc/math/linearalgebra/Permutation.cs b/crypto/src/pqc/math/linearalgebra/Permutation.cs
deleted file mode 100644
index 0d36958c9..000000000
--- a/crypto/src/pqc/math/linearalgebra/Permutation.cs
+++ /dev/null
@@ -1,192 +0,0 @@
-using Org.BouncyCastle.Security;
-using System;
-
-namespace Org.BouncyCastle.Pqc.Math.LinearAlgebra
-{
- /**
- * This class implements permutations of the set {0,1,...,n-1} for some given n
- * > 0, i.e., ordered sequences containing each number <tt>m</tt> (<tt>0 <=
- * m < n</tt>)
- * once and only once.
- */
- public class Permutation
- {
-
- /**
- * perm holds the elements of the permutation vector, i.e. <tt>[perm(0),
- * perm(1), ..., perm(n-1)]</tt>
- */
- private int[] perm;
-
- /**
- * Create the identity permutation of the given size.
- *
- * @param n the size of the permutation
- */
- public Permutation(int n)
- {
- if (n <= 0)
- {
- throw new ArgumentException("invalid length");
- }
-
- perm = new int[n];
- for (int i = n - 1; i >= 0; i--)
- {
- perm[i] = i;
- }
- }
-
- /**
- * Create a permutation using the given permutation vector.
- *
- * @param perm the permutation vector
- */
- public Permutation(int[] perm)
- {
- if (!IsPermutation(perm))
- {
- throw new ArgumentException(
- "array is not a permutation vector");
- }
-
- this.perm = IntUtils.Clone(perm);
- }
-
- /**
- * Create a random permutation of the given size.
- *
- * @param n the size of the permutation
- * @param sr the source of randomness
- */
- public Permutation(int n, SecureRandom sr)
- {
- if (n <= 0)
- {
- throw new ArgumentException("invalid length");
- }
-
- perm = new int[n];
-
- int[] help = new int[n];
- for (int i = 0; i < n; i++)
- {
- help[i] = i;
- }
-
- int k = n;
- for (int j = 0; j < n; j++)
- {
- int i = RandUtils.NextInt(sr, k);
- k--;
- perm[j] = help[i];
- help[i] = help[k];
- }
- }
-
-
- /**
- * @return the permutation vector <tt>(perm(0),perm(1),...,perm(n-1))</tt>
- */
- public int[] GetVector()
- {
- return IntUtils.Clone(perm);
- }
-
- /**
- * Compute the inverse permutation <tt>P<sup>-1</sup></tt>.
- *
- * @return <tt>this<sup>-1</sup></tt>
- */
- public Permutation ComputeInverse()
- {
- Permutation result = new Permutation(perm.Length);
- for (int i = perm.Length - 1; i >= 0; i--)
- {
- result.perm[perm[i]] = i;
- }
- return result;
- }
-
- /**
- * Compute the product of this permutation and another permutation.
- *
- * @param p the other permutation
- * @return <tt>this * p</tt>
- */
- public Permutation RightMultiply(Permutation p)
- {
- if (p.perm.Length != perm.Length)
- {
- throw new ArgumentException("length mismatch");
- }
- Permutation result = new Permutation(perm.Length);
- for (int i = perm.Length - 1; i >= 0; i--)
- {
- result.perm[i] = perm[p.perm[i]];
- }
- return result;
- }
-
- /**
- * checks if given object is equal to this permutation.
- * <p>
- * The method returns false whenever the given object is not permutation.
- *
- * @param other -
- * permutation
- * @return true or false
- */
- public bool equals(Object other)
- {
-
- if (!(other is Permutation))
- {
- return false;
- }
- Permutation otherPerm = (Permutation)other;
-
- return IntUtils.Equals(perm, otherPerm.perm);
- }
-
- /**
- * @return a human readable form of the permutation
- */
- public String ToString()
- {
- String result = "[" + perm[0];
- for (int i = 1; i < perm.Length; i++)
- {
- result += ", " + perm[i];
- }
- result += "]";
- return result;
- }
-
- /**
- * Check that the given array corresponds to a permutation of the set
- * <tt>{0, 1, ..., n-1}</tt>.
- *
- * @param perm permutation vector
- * @return true if perm represents an n-permutation and false otherwise
- */
- private bool IsPermutation(int[] perm)
- {
- int n = perm.Length;
- bool[] onlyOnce = new bool[n];
-
- for (int i = 0; i < n; i++)
- {
- if ((perm[i] < 0) || (perm[i] >= n) || onlyOnce[perm[i]])
- {
- return false;
- }
- onlyOnce[perm[i]] = true;
- }
-
- return true;
- }
-
- }
-
-}
diff --git a/crypto/src/pqc/math/linearalgebra/PolynomialGF2mSmallM.cs b/crypto/src/pqc/math/linearalgebra/PolynomialGF2mSmallM.cs
deleted file mode 100644
index 9dca71bee..000000000
--- a/crypto/src/pqc/math/linearalgebra/PolynomialGF2mSmallM.cs
+++ /dev/null
@@ -1,1266 +0,0 @@
-using Org.BouncyCastle.Security;
-using Org.BouncyCastle.Utilities;
-using System;
-
-namespace Org.BouncyCastle.Pqc.Math.LinearAlgebra
-{
- public class PolynomialGF2mSmallM
- {
-
- /**
- * the finite field GF(2^m)
- */
- private GF2mField field;
-
- /**
- * the degree of this polynomial
- */
- private int degree;
-
- /**
- * 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 int[] coefficients;
-
- /*
- * some types of polynomials
- */
-
- /**
- * Constant used for polynomial construction (see constructor
- * {@link #PolynomialGF2mSmallM(GF2mField, int, char, SecureRandom)}).
- */
- public const char RANDOM_IRREDUCIBLE_POLYNOMIAL = 'I';
-
- /**
- * Construct the zero polynomial over the finite field GF(2^m).
- *
- * @param field the finite field GF(2^m)
- */
- public PolynomialGF2mSmallM(GF2mField field)
- {
- this.field = field;
- degree = -1;
- coefficients = new int[1];
- }
-
- /**
- * Construct a polynomial over the finite field GF(2^m).
- *
- * @param field the finite field GF(2^m)
- * @param deg degree of polynomial
- * @param typeOfPolynomial type of polynomial
- * @param sr PRNG
- */
- public PolynomialGF2mSmallM(GF2mField field, int deg,
- char typeOfPolynomial, SecureRandom sr)
- {
- this.field = field;
-
- switch (typeOfPolynomial)
- {
- case PolynomialGF2mSmallM.RANDOM_IRREDUCIBLE_POLYNOMIAL:
- coefficients = CreateRandomIrreduciblePolynomial(deg, sr);
- break;
- default:
- throw new ArgumentException(" Error: type "
- + typeOfPolynomial
- + " is not defined for GF2smallmPolynomial");
- }
- ComputeDegree();
- }
-
- /**
- * Create an irreducible polynomial with the given degree over the field
- * <tt>GF(2^m)</tt>.
- *
- * @param deg polynomial degree
- * @param sr source of randomness
- * @return the generated irreducible polynomial
- */
- private int[] CreateRandomIrreduciblePolynomial(int deg, SecureRandom sr)
- {
- int[] resCoeff = new int[deg + 1];
- resCoeff[deg] = 1;
- resCoeff[0] = field.GetRandomNonZeroElement(sr);
- for (int i = 1; i < deg; i++)
- {
- resCoeff[i] = field.GetRandomElement(sr);
- }
- while (!IsIrreducible(resCoeff))
- {
- int n = RandUtils.NextInt(sr, deg);
- if (n == 0)
- {
- resCoeff[0] = field.GetRandomNonZeroElement(sr);
- }
- else
- {
- resCoeff[n] = field.GetRandomElement(sr);
- }
- }
- return resCoeff;
- }
-
- /**
- * 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
- */
- public PolynomialGF2mSmallM(GF2mField field, int degree)
- {
- this.field = field;
- this.degree = degree;
- coefficients = new int[degree + 1];
- coefficients[degree] = 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
- */
- public PolynomialGF2mSmallM(GF2mField field, int[] coeffs)
- {
- this.field = field;
- coefficients = NormalForm(coeffs);
- ComputeDegree();
- }
-
- /**
- * 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
- */
- public PolynomialGF2mSmallM(GF2mField field, byte[] enc)
- {
- this.field = field;
-
- // decodes polynomial
- int d = 8;
- int count = 1;
- while (field.GetDegree() > d)
- {
- count++;
- d += 8;
- }
-
- if ((enc.Length % count) != 0)
- {
- throw new ArgumentException(
- " Error: byte array is not encoded polynomial over given finite field GF2m");
- }
-
- coefficients = new int[enc.Length / count];
- count = 0;
- for (int i = 0; i < coefficients.Length; i++)
- {
- for (int j = 0; j < d; j += 8)
- {
- coefficients[i] ^= (enc[count++] & 0x000000ff) << j;
- }
- if (!this.field.IsElementOfThisField(coefficients[i]))
- {
- 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 ((coefficients.Length != 1)
- && (coefficients[coefficients.Length - 1] == 0))
- {
- throw new ArgumentException(
- " Error: byte array is not encoded polynomial over given finite field GF2m");
- }
- ComputeDegree();
- }
-
- /**
- * Copy constructor.
- *
- * @param other another {@link PolynomialGF2mSmallM}
- */
- public PolynomialGF2mSmallM(PolynomialGF2mSmallM other)
- {
- // field needs not to be cloned since it is immutable
- field = other.field;
- degree = other.degree;
- coefficients = IntUtils.Clone(other.coefficients);
- }
-
- /**
- * Create a polynomial over the finite field GF(2^m) out of the given
- * coefficient vector. The finite field is also obtained from the
- * {@link GF2mVector}.
- *
- * @param vect the coefficient vector
- */
- public PolynomialGF2mSmallM(GF2mVector vect)
- {
- new PolynomialGF2mSmallM(vect.GetField(), vect.GetIntArrayForm());
- }
-
- /*
- * ------------------------
- */
-
- /**
- * Return the degree of this polynomial
- *
- * @return int degree of this polynomial if this is zero polynomial return
- * -1
- */
- public int GetDegree()
- {
- int d = coefficients.Length - 1;
- if (coefficients[d] == 0)
- {
- return -1;
- }
- return d;
- }
-
- /**
- * @return the head coefficient of this polynomial
- */
- public int GetHeadCoefficient()
- {
- if (degree == -1)
- {
- return 0;
- }
- return coefficients[degree];
- }
-
- /**
- * Return the head coefficient of a polynomial.
- *
- * @param a the polynomial
- * @return the head coefficient of <tt>a</tt>
- */
- private static int HeadCoefficient(int[] a)
- {
- int degree = ComputeDegree(a);
- if (degree == -1)
- {
- return 0;
- }
- return a[degree];
- }
-
- /**
- * Return the coefficient with the given index.
- *
- * @param index the index
- * @return the coefficient with the given index
- */
- public int GetCoefficient(int index)
- {
- if ((index < 0) || (index > degree))
- {
- return 0;
- }
- return coefficients[index];
- }
-
- /**
- * Returns encoded polynomial, i.e., this polynomial in byte array form
- *
- * @return the encoded polynomial
- */
- public byte[] GetEncoded()
- {
- int d = 8;
- int count = 1;
- while (field.GetDegree() > d)
- {
- count++;
- d += 8;
- }
-
- byte[] res = new byte[coefficients.Length * count];
- count = 0;
- for (int i = 0; i < coefficients.Length; i++)
- {
- for (int j = 0; j < d; j += 8)
- {
- res[count++] = (byte)(Utils.UnsignedRightBitShiftInt(coefficients[i], j));
- }
- }
-
- return res;
- }
-
- /**
- * Evaluate this polynomial <tt>p</tt> at a value <tt>e</tt> (in
- * <tt>GF(2^m)</tt>) with the Horner scheme.
- *
- * @param e the element of the finite field GF(2^m)
- * @return <tt>this(e)</tt>
- */
- public int evaluateAt(int e)
- {
- int result = coefficients[degree];
- for (int i = degree - 1; i >= 0; i--)
- {
- result = field.Mult(result, e) ^ coefficients[i];
- }
- return result;
- }
-
- /**
- * Compute the sum of this polynomial and the given polynomial.
- *
- * @param addend the addend
- * @return <tt>this + a</tt> (newly created)
- */
- public PolynomialGF2mSmallM add(PolynomialGF2mSmallM addend)
- {
- int[] resultCoeff = Add(coefficients, addend.coefficients);
- return new PolynomialGF2mSmallM(field, resultCoeff);
- }
-
- /**
- * Add the given polynomial to this polynomial (overwrite this).
- *
- * @param addend the addend
- */
- public void AddToThis(PolynomialGF2mSmallM addend)
- {
- coefficients = Add(coefficients, addend.coefficients);
- ComputeDegree();
- }
-
- /**
- * 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 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] = field.add(result[i], addend[i]);
- }
-
- return result;
- }
-
- /**
- * Compute the sum of this polynomial and the monomial of the given degree.
- *
- * @param degree the degree of the monomial
- * @return <tt>this + X^k</tt>
- */
- public PolynomialGF2mSmallM AddMonomial(int degree)
- {
- int[] monomial = new int[degree + 1];
- monomial[degree] = 1;
- int[] resultCoeff = Add(coefficients, monomial);
- return new PolynomialGF2mSmallM(field, resultCoeff);
- }
-
- /**
- * Compute the product of this polynomial with an element from GF(2^m).
- *
- * @param element an element of the finite field GF(2^m)
- * @return <tt>this * element</tt> (newly created)
- * @throws ArithmeticException if <tt>element</tt> is not an element of the finite
- * field this polynomial is defined over.
- */
- public PolynomialGF2mSmallM MultWithElement(int element)
- {
- if (!field.IsElementOfThisField(element))
- {
- throw new ArithmeticException(
- "Not an element of the finite field this polynomial is defined over.");
- }
- int[] resultCoeff = MultWithElement(coefficients, element);
- return new PolynomialGF2mSmallM(field, resultCoeff);
- }
-
- /**
- * Multiply this polynomial with an element from GF(2^m).
- *
- * @param element an element of the finite field GF(2^m)
- * @throws ArithmeticException if <tt>element</tt> is not an element of the finite
- * field this polynomial is defined over.
- */
- public void MultThisWithElement(int element)
- {
- if (!field.IsElementOfThisField(element))
- {
- throw new ArithmeticException(
- "Not an element of the finite field this polynomial is defined over.");
- }
- coefficients = MultWithElement(coefficients, element);
- ComputeDegree();
- }
-
- /**
- * Compute the product of a polynomial a with an element from the finite
- * field <tt>GF(2^m)</tt>.
- *
- * @param a the polynomial
- * @param element an element of the finite field GF(2^m)
- * @return <tt>a * element</tt>
- */
- private int[] MultWithElement(int[] a, int element)
- {
- int degree = ComputeDegree(a);
- if (degree == -1 || element == 0)
- {
- return new int[1];
- }
-
- if (element == 1)
- {
- return IntUtils.Clone(a);
- }
-
- int[] result = new int[degree + 1];
- for (int i = degree; i >= 0; i--)
- {
- result[i] = field.Mult(a[i], element);
- }
-
- return result;
- }
-
- /**
- * Compute the product of this polynomial with a monomial X^k.
- *
- * @param k the degree of the monomial
- * @return <tt>this * X^k</tt>
- */
- public PolynomialGF2mSmallM MultWithMonomial(int k)
- {
- int[] resultCoeff = MultWithMonomial(coefficients, k);
- return new PolynomialGF2mSmallM(field, resultCoeff);
- }
-
- /**
- * Compute the product of a polynomial with a monomial X^k.
- *
- * @param a the polynomial
- * @param k the degree of the monomial
- * @return <tt>a * X^k</tt>
- */
- private static int[] MultWithMonomial(int[] a, int k)
- {
- int d = ComputeDegree(a);
- if (d == -1)
- {
- return new int[1];
- }
- int[] result = new int[d + k + 1];
- Array.Copy(a, 0, result, k, d + 1);
- return result;
- }
-
- /**
- * Divide this polynomial by the given polynomial.
- *
- * @param f a polynomial
- * @return polynomial pair = {q,r} where this = q*f+r and deg(r) <
- * deg(f);
- */
- public PolynomialGF2mSmallM[] Div(PolynomialGF2mSmallM f)
- {
- int[][] resultCoeffs = Div(coefficients, f.coefficients);
- return new PolynomialGF2mSmallM[]{
- new PolynomialGF2mSmallM(field, resultCoeffs[0]),
- new PolynomialGF2mSmallM(field, resultCoeffs[1])};
- }
-
- /**
- * 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 int[][] Div(int[] a, int[] f)
- {
- int df = ComputeDegree(f);
- int da = ComputeDegree(a) + 1;
- if (df == -1)
- {
- throw new ArithmeticException("Division by zero.");
- }
- int[][] result = new int[2][];
- result[0] = new int[1];
- result[1] = new int[da];
- int hc = HeadCoefficient(f);
- hc = field.Inverse(hc);
- result[0][0] = 0;
- Array.Copy(a, 0, result[1], 0, result[1].Length);
- while (df <= ComputeDegree(result[1]))
- {
- int[] q;
- int[] coeff = new int[1];
- coeff[0] = field.Mult(HeadCoefficient(result[1]), hc);
- q = MultWithElement(f, coeff[0]);
- int n = ComputeDegree(result[1]) - df;
- q = MultWithMonomial(q, n);
- coeff = MultWithMonomial(coeff, n);
- result[0] = Add(coeff, result[0]);
- result[1] = Add(q, result[1]);
- }
- return result;
- }
-
- /**
- * Return the greatest common divisor of this and a polynomial <i>f</i>
- *
- * @param f polynomial
- * @return GCD(this, f)
- */
- public PolynomialGF2mSmallM Gcd(PolynomialGF2mSmallM f)
- {
- int[] resultCoeff = Gcd(coefficients, f.coefficients);
- return new PolynomialGF2mSmallM(field, resultCoeff);
- }
-
- /**
- * Return the greatest common divisor of two polynomials over the field
- * <tt>GF(2^m)</tt>.
- *
- * @param f the first polynomial
- * @param g the second polynomial
- * @return <tt>gcd(f, g)</tt>
- */
- private int[] Gcd(int[] f, int[] g)
- {
- int[] a = f;
- int[] b = g;
- if (ComputeDegree(a) == -1)
- {
- return b;
- }
- while (ComputeDegree(b) != -1)
- {
- int[] c = Mod(a, b);
- a = new int[b.Length];
- Array.Copy(b, 0, a, 0, a.Length);
- b = new int[c.Length];
- Array.Copy(c, 0, b, 0, b.Length);
- }
- int coeff = field.Inverse(HeadCoefficient(a));
- return MultWithElement(a, coeff);
- }
-
- /**
- * Compute the product of this polynomial and the given factor using a
- * Karatzuba like scheme.
- *
- * @param factor the polynomial
- * @return <tt>this * factor</tt>
- */
- public PolynomialGF2mSmallM Multiply(PolynomialGF2mSmallM factor)
- {
- int[] resultCoeff = Multiply(coefficients, factor.coefficients);
- return new PolynomialGF2mSmallM(field, resultCoeff);
- }
-
- /**
- * Compute the product of two polynomials over the field <tt>GF(2^m)</tt>
- * using a Karatzuba like multiplication.
- *
- * @param a the first polynomial
- * @param b the second polynomial
- * @return a * b
- */
- private int[] Multiply(int[] a, int[] b)
- {
- int[] mult1, mult2;
- if (ComputeDegree(a) < ComputeDegree(b))
- {
- mult1 = b;
- mult2 = a;
- }
- else
- {
- mult1 = a;
- mult2 = b;
- }
-
- mult1 = NormalForm(mult1);
- mult2 = NormalForm(mult2);
-
- if (mult2.Length == 1)
- {
- return MultWithElement(mult1, mult2[0]);
- }
-
- int d1 = mult1.Length;
- int d2 = mult2.Length;
- int[] result = new int[d1 + d2 - 1];
-
- if (d2 != d1)
- {
- int[] res1 = new int[d2];
- int[] res2 = new int[d1 - d2];
- Array.Copy(mult1, 0, res1, 0, res1.Length);
- Array.Copy(mult1, d2, res2, 0, res2.Length);
- res1 = Multiply(res1, mult2);
- res2 = Multiply(res2, mult2);
- res2 = MultWithMonomial(res2, d2);
- result = Add(res1, res2);
- }
- else
- {
- d2 = Utils.UnsignedRightBitShiftInt(d1 + 1, 1);
- int d = d1 - d2;
- int[] firstPartMult1 = new int[d2];
- int[] firstPartMult2 = new int[d2];
- int[] secondPartMult1 = new int[d];
- int[] secondPartMult2 = new int[d];
- Array.Copy(mult1, 0, firstPartMult1, 0,
- firstPartMult1.Length);
- Array.Copy(mult1, d2, secondPartMult1, 0,
- secondPartMult1.Length);
- Array.Copy(mult2, 0, firstPartMult2, 0,
- firstPartMult2.Length);
- Array.Copy(mult2, d2, secondPartMult2, 0,
- secondPartMult2.Length);
- int[] helpPoly1 = Add(firstPartMult1, secondPartMult1);
- int[] helpPoly2 = Add(firstPartMult2, secondPartMult2);
- int[] res1 = Multiply(firstPartMult1, firstPartMult2);
- int[] res2 = Multiply(helpPoly1, helpPoly2);
- int[] res3 = Multiply(secondPartMult1, secondPartMult2);
- res2 = Add(res2, res1);
- res2 = Add(res2, res3);
- res3 = MultWithMonomial(res3, d2);
- result = Add(res2, res3);
- result = MultWithMonomial(result, d2);
- result = Add(result, res1);
- }
-
- return result;
- }
-
- /*
- * ---------------- PART II ----------------
- *
- */
-
- /**
- * Check a polynomial for irreducibility over the field <tt>GF(2^m)</tt>.
- *
- * @param a the polynomial to check
- * @return true if a is irreducible, false otherwise
- */
- private bool IsIrreducible(int[] a)
- {
- if (a[0] == 0)
- {
- return false;
- }
- int d = ComputeDegree(a) >> 1;
- int[] u = { 0, 1 };
- int[] Y = { 0, 1 };
- int fieldDegree = field.GetDegree();
- for (int i = 0; i < d; i++)
- {
- for (int j = fieldDegree - 1; j >= 0; j--)
- {
- u = ModMultiply(u, u, a);
- }
- u = NormalForm(u);
- int[] g = Gcd(Add(u, Y), a);
- if (ComputeDegree(g) != 0)
- {
- return false;
- }
- }
- return true;
- }
-
- /**
- * Reduce this polynomial modulo another polynomial.
- *
- * @param f the reduction polynomial
- * @return <tt>this mod f</tt>
- */
- public PolynomialGF2mSmallM Mod(PolynomialGF2mSmallM f)
- {
- int[] resultCoeff = Mod(coefficients, f.coefficients);
- return new PolynomialGF2mSmallM(field, resultCoeff);
- }
-
- /**
- * Reduce a polynomial modulo another polynomial.
- *
- * @param a the polynomial
- * @param f the reduction polynomial
- * @return <tt>a mod f</tt>
- */
- private int[] Mod(int[] a, int[] f)
- {
- int df = ComputeDegree(f);
- if (df == -1)
- {
- throw new ArithmeticException("Division by zero");
- }
- int[] result = new int[a.Length];
- int hc = HeadCoefficient(f);
- hc = field.Inverse(hc);
- Array.Copy(a, 0, result, 0, result.Length);
- while (df <= ComputeDegree(result))
- {
- int[] q;
- int coeff = field.Mult(HeadCoefficient(result), hc);
- q = MultWithMonomial(f, ComputeDegree(result) - df);
- q = MultWithElement(q, coeff);
- result = Add(q, result);
- }
- 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>
- */
- public PolynomialGF2mSmallM ModMultiply(PolynomialGF2mSmallM a,
- PolynomialGF2mSmallM b)
- {
- int[] resultCoeff = ModMultiply(coefficients, a.coefficients,
- b.coefficients);
- return new PolynomialGF2mSmallM(field, resultCoeff);
- }
-
-
-
- /**
- * Square this polynomial using a squaring matrix.
- *
- * @param matrix the squaring matrix
- * @return <tt>this^2</tt> modulo the reduction polynomial implicitly
- * given via the squaring matrix
- */
- public PolynomialGF2mSmallM ModSquareMatrix(PolynomialGF2mSmallM[] matrix)
- {
-
- int length = matrix.Length;
-
- int[] resultCoeff = new int[length];
- int[] thisSquare = new int[length];
-
- // square each entry of this polynomial
- for (int i = 0; i < coefficients.Length; i++)
- {
- thisSquare[i] = field.Mult(coefficients[i], coefficients[i]);
- }
-
- // do matrix-vector multiplication
- for (int i = 0; i < length; i++)
- {
- // compute scalar product of i-th row and coefficient vector
- for (int j = 0; j < length; j++)
- {
- if (i >= matrix[j].coefficients.Length)
- {
- continue;
- }
- int scalarTerm = field.Mult(matrix[j].coefficients[i],
- thisSquare[j]);
- resultCoeff[i] = field.add(resultCoeff[i], scalarTerm);
- }
- }
-
- return new PolynomialGF2mSmallM(field, resultCoeff);
- }
-
- /**
- * Compute the product of two polynomials modulo a third polynomial over the
- * finite field <tt>GF(2^m)</tt>.
- *
- * @param a the first polynomial
- * @param b the second polynomial
- * @param g the reduction polynomial
- * @return <tt>a * b mod g</tt>
- */
- private int[] ModMultiply(int[] a, int[] b, int[] g)
- {
- return Mod(Multiply(a, b), g);
- }
-
- /**
- * Compute the square root of this polynomial modulo the given polynomial.
- *
- * @param a the reduction polynomial
- * @return <tt>this^(1/2) mod a</tt>
- */
- public PolynomialGF2mSmallM ModSquareRoot(PolynomialGF2mSmallM a)
- {
- int[] resultCoeff = IntUtils.Clone(coefficients);
- int[] help = ModMultiply(resultCoeff, resultCoeff, a.coefficients);
- while (!IsEqual(help, coefficients))
- {
- resultCoeff = NormalForm(help);
- help = ModMultiply(resultCoeff, resultCoeff, a.coefficients);
- }
-
- return new PolynomialGF2mSmallM(field, resultCoeff);
- }
-
- /**
- * Compute the square root of this polynomial using a square root matrix.
- *
- * @param matrix the matrix for computing square roots in
- * <tt>(GF(2^m))^t</tt> the polynomial ring defining the
- * square root matrix
- * @return <tt>this^(1/2)</tt> modulo the reduction polynomial implicitly
- * given via the square root matrix
- */
- public PolynomialGF2mSmallM ModSquareRootMatrix(
- PolynomialGF2mSmallM[] matrix)
- {
-
- int length = matrix.Length;
-
- int[] resultCoeff = new int[length];
-
- // do matrix multiplication
- for (int i = 0; i < length; i++)
- {
- // compute scalar product of i-th row and j-th column
- for (int j = 0; j < length; j++)
- {
- if (i >= matrix[j].coefficients.Length)
- {
- continue;
- }
- if (j < coefficients.Length)
- {
- int scalarTerm = field.Mult(matrix[j].coefficients[i],
- coefficients[j]);
- resultCoeff[i] = field.add(resultCoeff[i], scalarTerm);
- }
- }
- }
-
- // compute the square root of each entry of the result coefficients
- for (int i = 0; i < length; i++)
- {
- resultCoeff[i] = field.SqRoot(resultCoeff[i]);
- }
-
- return new PolynomialGF2mSmallM(field, resultCoeff);
- }
-
- /**
- * Compute the result of the division of this polynomial by another
- * polynomial modulo a third polynomial.
- *
- * @param divisor the divisor
- * @param modulus the reduction polynomial
- * @return <tt>this * divisor^(-1) mod modulus</tt>
- */
- public PolynomialGF2mSmallM ModDiv(PolynomialGF2mSmallM divisor,
- PolynomialGF2mSmallM modulus)
- {
- int[] resultCoeff = ModDiv(coefficients, divisor.coefficients,
- modulus.coefficients);
- return new PolynomialGF2mSmallM(field, resultCoeff);
- }
-
- /**
- * Compute the result of the division of two polynomials modulo a third
- * polynomial over the field <tt>GF(2^m)</tt>.
- *
- * @param a the first polynomial
- * @param b the second polynomial
- * @param g the reduction polynomial
- * @return <tt>a * b^(-1) mod g</tt>
- */
- private int[] ModDiv(int[] a, int[] b, int[] g)
- {
- int[] r0 = NormalForm(g);
- int[] r1 = Mod(b, g);
- int[] s0 = { 0 };
- int[] s1 = Mod(a, g);
- int[] s2;
- int[][] q;
- while (ComputeDegree(r1) != -1)
- {
- q = Div(r0, r1);
- r0 = NormalForm(r1);
- r1 = NormalForm(q[1]);
- s2 = Add(s0, ModMultiply(q[0], s1, g));
- s0 = NormalForm(s1);
- s1 = NormalForm(s2);
-
- }
- int hc = HeadCoefficient(r0);
- s0 = MultWithElement(s0, field.Inverse(hc));
- return s0;
- }
-
- /**
- * Compute the inverse of this polynomial modulo the given polynomial.
- *
- * @param a the reduction polynomial
- * @return <tt>this^(-1) mod a</tt>
- */
- public PolynomialGF2mSmallM ModInverse(PolynomialGF2mSmallM a)
- {
- int[] unit = { 1 };
- int[] resultCoeff = ModDiv(unit, coefficients, a.coefficients);
- return new PolynomialGF2mSmallM(field, resultCoeff);
- }
-
- /**
- * Compute a polynomial pair (a,b) from this polynomial and the given
- * polynomial g with the property b*this = a mod g and deg(a)<=deg(g)/2.
- *
- * @param g the reduction polynomial
- * @return PolynomialGF2mSmallM[] {a,b} with b*this = a mod g and deg(a)<=
- * deg(g)/2
- */
- public PolynomialGF2mSmallM[] ModPolynomialToFracton(PolynomialGF2mSmallM g)
- {
- int dg = g.degree >> 1;
- int[] a0 = NormalForm(g.coefficients);
- int[] a1 = Mod(coefficients, g.coefficients);
- int[] b0 = { 0 };
- int[] b1 = { 1 };
- while (ComputeDegree(a1) > dg)
- {
- int[][] q = Div(a0, a1);
- a0 = a1;
- a1 = q[1];
- int[] b2 = Add(b0, ModMultiply(q[0], b1, g.coefficients));
- b0 = b1;
- b1 = b2;
- }
-
- return new PolynomialGF2mSmallM[]{
- new PolynomialGF2mSmallM(field, a1),
- new PolynomialGF2mSmallM(field, b1)};
- }
-
- /**
- * checks if given object is equal to this polynomial.
- * <p>
- * The method returns false whenever the given object is not polynomial over
- * GF(2^m).
- *
- * @param other object
- * @return true or false
- */
- public bool equals(Object other)
- {
-
- if (other == null || !(other is PolynomialGF2mSmallM))
- {
- return false;
- }
-
- PolynomialGF2mSmallM p = (PolynomialGF2mSmallM)other;
-
- if ((field.Equals(p.field)) && (degree == p.degree)
- && (IsEqual(coefficients, p.coefficients)))
- {
- return true;
- }
-
- return false;
- }
-
- /**
- * Compare two polynomials given as int arrays.
- *
- * @param a the first polynomial
- * @param b the second polynomial
- * @return <tt>true</tt> if <tt>a</tt> and <tt>b</tt> represent the
- * same polynomials, <tt>false</tt> otherwise
- */
- private static bool IsEqual(int[] a, int[] b)
- {
- int da = ComputeDegree(a);
- int db = ComputeDegree(b);
- if (da != db)
- {
- return false;
- }
- for (int i = 0; i <= da; i++)
- {
- if (a[i] != b[i])
- {
- return false;
- }
- }
- return true;
- }
-
- /**
- * @return the hash code of this polynomial
- */
- public int HashCode()
- {
- int hash = field.HashCode();
- for (int j = 0; j < coefficients.Length; j++)
- {
- hash = hash * 31 + coefficients[j];
- }
- return hash;
- }
-
- /**
- * Returns a human readable form of the polynomial.
- *
- * @return a human readable form of the polynomial.
- */
- public String toString()
- {
- String str = " Polynomial over " + field.ToString() + ": \n";
-
- for (int i = 0; i < coefficients.Length; i++)
- {
- str = str + field.ElementToStr(coefficients[i]) + "Y^" + i + "+";
- }
- str = str + ";";
-
- return str;
- }
-
- /**
- * Compute the degree of this polynomial. If this is the zero polynomial,
- * the degree is -1.
- */
- private void ComputeDegree()
- {
- for (degree = coefficients.Length - 1; degree >= 0
- && coefficients[degree] == 0; degree--)
- {
- ;
- }
- }
-
- /**
- * 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)
- {
- int degree;
- for (degree = a.Length - 1; 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 IntUtils.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>
- */
- public PolynomialGF2mSmallM ModKaratsubaMultiplyBigDeg(PolynomialGF2mSmallM a,
- PolynomialGF2mSmallM b)
- {
- int[] resultCoeff = ModKaratsubaMultiplyBigDeg(coefficients, a.coefficients,
- b.coefficients);
- return new PolynomialGF2mSmallM(field, resultCoeff);
- }
-
- /**
- * Compute the inverse of this polynomial modulo the given polynomial.
- *
- * @param a the reduction polynomial
- * @return <tt>this^(-1) mod a</tt>
- */
- public PolynomialGF2mSmallM ModInverseBigDeg(PolynomialGF2mSmallM a)
- {
- int[] unit = { 1 };
- int[] resultCoeff = ModDivBigDeg(unit, coefficients, a.coefficients);
- return new PolynomialGF2mSmallM(field, resultCoeff);
- }
-
- private int[] ModDivBigDeg(int[] a, int[] b, int[] g)
- {
- int[] r0 = NormalForm(g);
- int[] r1 = Mod(b, g);
- int[] s0 = { 0 };
- int[] s1 = Mod(a, g);
- 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);
- }
- int hc = HeadCoefficient(r0);
- s0 = MultWithElement(s0, field.Inverse(hc));
- 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 int[] ModKaratsubaMultiplyBigDeg(int[] aa, int[] bb, int[] g)
- {
- int[] a, b;
- if (aa.Length >= bb.Length)
- {
- a = Arrays.Clone(aa);
- b = Arrays.Clone(bb);
- }
- else
- {
- a = Arrays.Clone(bb);
- b = Arrays.Clone(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++)
- {
- for (int p = 0; p < System.Math.Min(m, i); p++)
- {
- int q = i - p;
- if (p >= q)
- {
- break;
- }
-
- int ap = a[p];
- int aq = 0;
-
- if (q < a.Length)
- {
- aq = a[q];
- }
-
- int bp = b[p];
- int dp = D[p];
-
- if (q < m && p < m)
- {
- int bq = b[q];
- int dq = D[q];
-
- S[i] = S[i] + (ap + aq) * (bp + bq);
- T[i] = T[i] + dp + dq;
- }
- else if (q >= m && q < n)
- {
- S[i] = S[i] + ((ap + aq) * bp);
- T[i] = T[i] + dp;
- }
- }
- }
-
- 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;
- }
- }
- int[] res = Mod(C, g);
- return res;
- }
- }
-}
diff --git a/crypto/src/pqc/math/linearalgebra/PolynomialRingGF2.cs b/crypto/src/pqc/math/linearalgebra/PolynomialRingGF2.cs
deleted file mode 100644
index 9bc3fcd31..000000000
--- a/crypto/src/pqc/math/linearalgebra/PolynomialRingGF2.cs
+++ /dev/null
@@ -1,286 +0,0 @@
-using System;
-
-namespace Org.BouncyCastle.Pqc.Math.LinearAlgebra
-{
- /**
- * This class describes operations with polynomials over finite field GF(2), i e
- * polynomial ring R = GF(2)[X]. All operations are defined only for polynomials
- * with degree <=32. For the polynomial representation the map f: R->Z,
- * poly(X)->poly(2) is used, where integers have the binary representation. For
- * example: X^7+X^3+X+1 -> (00...0010001011)=139 Also for polynomials type
- * Integer is used.
- *
- * @see GF2mField
- */
- public class PolynomialRingGF2
- {
-
- /**
- * Default constructor (private).
- */
- private PolynomialRingGF2()
- {
- // empty
- }
-
- /**
- * Return sum of two polyomials
- *
- * @param p polynomial
- * @param q polynomial
- * @return p+q
- */
-
- public static int Add(int p, int q)
- {
- return p ^ q;
- }
-
- /**
- * Return product of two polynomials
- *
- * @param p polynomial
- * @param q polynomial
- * @return p*q
- */
-
- public static long Multiply(int p, int q)
- {
- long result = 0;
- if (q != 0)
- {
- long q1 = q & 0x00000000ffffffffL;
-
- while (p != 0)
- {
- byte b = (byte)(p & 0x01);
- if (b == 1)
- {
- result ^= q1;
- }
- p = Utils.UnsignedRightBitShiftInt(p, 1);
- q1 <<= 1;
-
- }
- }
- return result;
- }
-
- /**
- * Compute the product of two polynomials modulo a third polynomial.
- *
- * @param a the first polynomial
- * @param b the second polynomial
- * @param r the reduction polynomial
- * @return <tt>a * b mod r</tt>
- */
- public static int modMultiply(int a, int b, int r)
- {
- int result = 0;
- int p = Remainder(a, r);
- int q = Remainder(b, r);
- if (q != 0)
- {
- int d = 1 << Degree(r);
-
- while (p != 0)
- {
- byte pMod2 = (byte)(p & 0x01);
- if (pMod2 == 1)
- {
- result ^= q;
- }
- p = Utils.UnsignedRightBitShiftInt(p, 1);
- q <<= 1;
- if (q >= d)
- {
- q ^= r;
- }
- }
- }
- return result;
- }
-
- /**
- * Return the degree of a polynomial
- *
- * @param p polynomial p
- * @return degree(p)
- */
-
- public static int Degree(int p)
- {
- int result = -1;
- while (p != 0)
- {
- result++;
- p = Utils.UnsignedRightBitShiftInt(p, 1);
- }
- return result;
- }
-
- /**
- * Return the degree of a polynomial
- *
- * @param p polynomial p
- * @return degree(p)
- */
-
- public static int Degree(long p)
- {
- int result = 0;
- while (p != 0)
- {
- result++;
- p = Utils.UnsignedRightBitShiftLong(p, 1);
- }
- return result - 1;
- }
-
- /**
- * Return the remainder of a polynomial division of two polynomials.
- *
- * @param p dividend
- * @param q divisor
- * @return <tt>p mod q</tt>
- */
- public static int Remainder(int p, int q)
- {
- int result = p;
-
- if (q == 0)
- {
- // -DM Console.Error.WriteLine
- Console.Error.WriteLine("Error: to be divided by 0");
- return 0;
- }
-
- while (Degree(result) >= Degree(q))
- {
- result ^= q << (Degree(result) - Degree(q));
- }
-
- return result;
- }
-
- /**
- * Return the rest of devision two polynomials
- *
- * @param p polinomial
- * @param q polinomial
- * @return p mod q
- */
-
- public static int Rest(long p, int q)
- {
- long p1 = p;
- if (q == 0)
- {
- // -DM Console.Error.WriteLine
- Console.Error.WriteLine("Error: to be divided by 0");
- return 0;
- }
- long q1 = q & 0x00000000ffffffffL;
-
- while ((Utils.UnsignedRightBitShiftLong(p1, 32)) != 0)
- {
- p1 ^= q1 << (Degree(p1) - Degree(q1));
- }
-
- int result = (int)(p1 & 0xffffffff);
- while (Degree(result) >= Degree(q))
- {
- result ^= q << (Degree(result) - Degree(q));
- }
-
- return result;
- }
-
- /**
- * Return the greatest common divisor of two polynomials
- *
- * @param p polinomial
- * @param q polinomial
- * @return GCD(p, q)
- */
-
- public static int Gcd(int p, int q)
- {
- int a, b, c;
- a = p;
- b = q;
- while (b != 0)
- {
- c = Remainder(a, b);
- a = b;
- b = c;
-
- }
- return a;
- }
-
- /**
- * Checking polynomial for irreducibility
- *
- * @param p polinomial
- * @return true if p is irreducible and false otherwise
- */
-
- public static bool IsIrreducible(int p)
- {
- if (p == 0)
- {
- return false;
- }
- uint tmpDeg = (uint)Degree(p);
- int d = (int) tmpDeg >> 1;
- int u = 2;
- for (int i = 0; i < d; i++)
- {
- u = modMultiply(u, u, p);
- if (Gcd(u ^ 2, p) != 1)
- {
- return false;
- }
- }
- return true;
- }
-
- /**
- * Creates irreducible polynomial with degree d
- *
- * @param deg polynomial degree
- * @return irreducible polynomial p
- */
- public static int GetIrreduciblePolynomial(int deg)
- {
- if (deg < 0)
- {
- // -DM Console.Error.WriteLine
- Console.Error.WriteLine("The Degree is negative");
- return 0;
- }
- if (deg > 31)
- {
- // -DM Console.Error.WriteLine
- Console.Error.WriteLine("The Degree is more then 31");
- return 0;
- }
- if (deg == 0)
- {
- return 1;
- }
- int a = 1 << deg;
- a++;
- int b = 1 << (deg + 1);
- for (int i = a; i < b; i += 2)
- {
- if (IsIrreducible(i))
- {
- return i;
- }
- }
- return 0;
- }
- }
-}
diff --git a/crypto/src/pqc/math/linearalgebra/RandUtils.cs b/crypto/src/pqc/math/linearalgebra/RandUtils.cs
deleted file mode 100644
index f7b7b8588..000000000
--- a/crypto/src/pqc/math/linearalgebra/RandUtils.cs
+++ /dev/null
@@ -1,27 +0,0 @@
-using Org.BouncyCastle.Security;
-
-namespace Org.BouncyCastle.Pqc.Math.LinearAlgebra
-{
- public class RandUtils
- {
- public static int NextInt(SecureRandom rand, int n)
- {
-
- if ((n & -n) == n) // i.e., n is a power of 2
- {
- return (int)((n * (long)(Utils.UnsignedRightBitShiftInt(rand.NextInt(), 1))) >> 31);
- }
-
- int bits, value;
- do
- {
- bits = Utils.UnsignedRightBitShiftInt(rand.NextInt() ,1);
- value = bits % n;
- }
- while (bits - value + (n - 1) < 0);
-
- return value;
- }
- }
-
-}
diff --git a/crypto/src/pqc/math/linearalgebra/Utils.cs b/crypto/src/pqc/math/linearalgebra/Utils.cs
deleted file mode 100644
index eb2760f82..000000000
--- a/crypto/src/pqc/math/linearalgebra/Utils.cs
+++ /dev/null
@@ -1,20 +0,0 @@
-
-namespace Org.BouncyCastle.Pqc.Math.LinearAlgebra
-{
- class Utils
- {
- internal static int UnsignedRightBitShiftInt(int a, int b)
- {
- uint tmp = (uint) a;
- tmp >>= b;
- return (int) tmp;
- }
-
- internal static long UnsignedRightBitShiftLong(long a, int b)
- {
- ulong tmp = (ulong)a;
- tmp >>= b;
- return (long) tmp;
- }
- }
-}
diff --git a/crypto/src/pqc/math/linearalgebra/Vector.cs b/crypto/src/pqc/math/linearalgebra/Vector.cs
deleted file mode 100644
index e50c54792..000000000
--- a/crypto/src/pqc/math/linearalgebra/Vector.cs
+++ /dev/null
@@ -1,62 +0,0 @@
-using System;
-
-namespace Org.BouncyCastle.Pqc.Math.LinearAlgebra
-{
- /**
- * This abstract class defines vectors. It holds the length of vector.
- */
- public abstract class Vector
- {
-
- /**
- * the length of this vector
- */
- protected int length;
-
- /**
- * @return the length of this vector
- */
- public int GetLength()
- {
- return length;
- }
-
- /**
- * @return this vector as byte array
- */
- public abstract byte[] GetEncoded();
-
- /**
- * Return whether this is the zero vector (i.e., all elements are zero).
- *
- * @return <tt>true</tt> if this is the zero vector, <tt>false</tt>
- * otherwise
- */
- public abstract bool IsZero();
-
- /**
- * Add another vector to this vector.
- *
- * @param addend the other vector
- * @return <tt>this + addend</tt>
- */
- public abstract Vector Add(Vector addend);
-
- /**
- * Multiply this vector with a permutation.
- *
- * @param p the permutation
- * @return <tt>this*p = p*this</tt>
- */
- public abstract Vector Multiply(Permutation p);
-
- /**
- * Check if the given object is equal to this vector.
- *
- * @param other vector
- * @return the result of the comparison
- */
- public abstract bool Equals(Object other);
-
- }
-}
|
