diff options
Diffstat (limited to 'crypto/src/pqc/math')
| -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 |
10 files changed, 2798 insertions, 0 deletions
diff --git a/crypto/src/pqc/math/linearalgebra/GF2mField.cs b/crypto/src/pqc/math/linearalgebra/GF2mField.cs new file mode 100644 index 000000000..e8182bf6f --- /dev/null +++ b/crypto/src/pqc/math/linearalgebra/GF2mField.cs @@ -0,0 +1,370 @@ +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 new file mode 100644 index 000000000..f0e44ebe6 --- /dev/null +++ b/crypto/src/pqc/math/linearalgebra/GF2mVector.cs @@ -0,0 +1,221 @@ +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 new file mode 100644 index 000000000..0a7671df6 --- /dev/null +++ b/crypto/src/pqc/math/linearalgebra/IntUtils.cs @@ -0,0 +1,159 @@ +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 new file mode 100644 index 000000000..5b3215070 --- /dev/null +++ b/crypto/src/pqc/math/linearalgebra/LittleEndianConversions.cs @@ -0,0 +1,195 @@ + +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 new file mode 100644 index 000000000..0d36958c9 --- /dev/null +++ b/crypto/src/pqc/math/linearalgebra/Permutation.cs @@ -0,0 +1,192 @@ +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 new file mode 100644 index 000000000..9dca71bee --- /dev/null +++ b/crypto/src/pqc/math/linearalgebra/PolynomialGF2mSmallM.cs @@ -0,0 +1,1266 @@ +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 new file mode 100644 index 000000000..9bc3fcd31 --- /dev/null +++ b/crypto/src/pqc/math/linearalgebra/PolynomialRingGF2.cs @@ -0,0 +1,286 @@ +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 new file mode 100644 index 000000000..f7b7b8588 --- /dev/null +++ b/crypto/src/pqc/math/linearalgebra/RandUtils.cs @@ -0,0 +1,27 @@ +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 new file mode 100644 index 000000000..eb2760f82 --- /dev/null +++ b/crypto/src/pqc/math/linearalgebra/Utils.cs @@ -0,0 +1,20 @@ + +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 new file mode 100644 index 000000000..e50c54792 --- /dev/null +++ b/crypto/src/pqc/math/linearalgebra/Vector.cs @@ -0,0 +1,62 @@ +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); + + } +} |