diff options
| -rw-r--r-- | crypto/src/pqc/crypto/bike/BikeEngine.cs | 47 | ||||
| -rw-r--r-- | crypto/src/pqc/crypto/bike/BikeParameters.cs | 12 | ||||
| -rw-r--r-- | crypto/src/pqc/crypto/bike/BikePolynomial.cs | 469 | ||||
| -rw-r--r-- | crypto/src/pqc/crypto/bike/BikeRandomGenerator.cs | 41 | ||||
| -rw-r--r-- | crypto/src/pqc/crypto/bike/Utils.cs | 21 | ||||
| -rw-r--r-- | crypto/src/pqc/math/linearalgebra/GF2mField.cs | 370 | ||||
| -rw-r--r-- | crypto/src/pqc/math/linearalgebra/GF2mVector.cs | 221 | ||||
| -rw-r--r-- | crypto/src/pqc/math/linearalgebra/IntUtils.cs | 159 | ||||
| -rw-r--r-- | crypto/src/pqc/math/linearalgebra/LittleEndianConversions.cs | 195 | ||||
| -rw-r--r-- | crypto/src/pqc/math/linearalgebra/Permutation.cs | 192 | ||||
| -rw-r--r-- | crypto/src/pqc/math/linearalgebra/PolynomialGF2mSmallM.cs | 1266 | ||||
| -rw-r--r-- | crypto/src/pqc/math/linearalgebra/PolynomialRingGF2.cs | 286 | ||||
| -rw-r--r-- | crypto/src/pqc/math/linearalgebra/RandUtils.cs | 27 | ||||
| -rw-r--r-- | crypto/src/pqc/math/linearalgebra/Utils.cs | 20 | ||||
| -rw-r--r-- | crypto/src/pqc/math/linearalgebra/Vector.cs | 62 |
15 files changed, 505 insertions, 2883 deletions
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); - - } -} |