diff options
Diffstat (limited to 'core/src/main/java/org/spongycastle/pqc/math/ntru')
17 files changed, 3737 insertions, 0 deletions
diff --git a/core/src/main/java/org/spongycastle/pqc/math/ntru/euclid/BigIntEuclidean.java b/core/src/main/java/org/spongycastle/pqc/math/ntru/euclid/BigIntEuclidean.java new file mode 100644 index 00000000..e48d2a0c --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/math/ntru/euclid/BigIntEuclidean.java @@ -0,0 +1,54 @@ +package org.spongycastle.pqc.math.ntru.euclid; + +import java.math.BigInteger; + +/** + * Extended Euclidean Algorithm in <code>BigInteger</code>s + */ +public class BigIntEuclidean +{ + public BigInteger x, y, gcd; + + private BigIntEuclidean() + { + } + + /** + * Runs the EEA on two <code>BigInteger</code>s<br> + * Implemented from pseudocode on <a href="http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm">Wikipedia</a>. + * + * @param a + * @param b + * @return a <code>BigIntEuclidean</code> object that contains the result in the variables <code>x</code>, <code>y</code>, and <code>gcd</code> + */ + public static BigIntEuclidean calculate(BigInteger a, BigInteger b) + { + BigInteger x = BigInteger.ZERO; + BigInteger lastx = BigInteger.ONE; + BigInteger y = BigInteger.ONE; + BigInteger lasty = BigInteger.ZERO; + while (!b.equals(BigInteger.ZERO)) + { + BigInteger[] quotientAndRemainder = a.divideAndRemainder(b); + BigInteger quotient = quotientAndRemainder[0]; + + BigInteger temp = a; + a = b; + b = quotientAndRemainder[1]; + + temp = x; + x = lastx.subtract(quotient.multiply(x)); + lastx = temp; + + temp = y; + y = lasty.subtract(quotient.multiply(y)); + lasty = temp; + } + + BigIntEuclidean result = new BigIntEuclidean(); + result.x = lastx; + result.y = lasty; + result.gcd = a; + return result; + } +}
\ No newline at end of file diff --git a/core/src/main/java/org/spongycastle/pqc/math/ntru/euclid/IntEuclidean.java b/core/src/main/java/org/spongycastle/pqc/math/ntru/euclid/IntEuclidean.java new file mode 100644 index 00000000..0791b01e --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/math/ntru/euclid/IntEuclidean.java @@ -0,0 +1,51 @@ +package org.spongycastle.pqc.math.ntru.euclid; + +/** + * Extended Euclidean Algorithm in <code>int</code>s + */ +public class IntEuclidean +{ + public int x, y, gcd; + + private IntEuclidean() + { + } + + /** + * Runs the EEA on two <code>int</code>s<br> + * Implemented from pseudocode on <a href="http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm">Wikipedia</a>. + * + * @param a + * @param b + * @return a <code>IntEuclidean</code> object that contains the result in the variables <code>x</code>, <code>y</code>, and <code>gcd</code> + */ + public static IntEuclidean calculate(int a, int b) + { + int x = 0; + int lastx = 1; + int y = 1; + int lasty = 0; + while (b != 0) + { + int quotient = a / b; + + int temp = a; + a = b; + b = temp % b; + + temp = x; + x = lastx - quotient * x; + lastx = temp; + + temp = y; + y = lasty - quotient * y; + lasty = temp; + } + + IntEuclidean result = new IntEuclidean(); + result.x = lastx; + result.y = lasty; + result.gcd = a; + return result; + } +}
\ No newline at end of file diff --git a/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/BigDecimalPolynomial.java b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/BigDecimalPolynomial.java new file mode 100644 index 00000000..a496060c --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/BigDecimalPolynomial.java @@ -0,0 +1,258 @@ +package org.spongycastle.pqc.math.ntru.polynomial; + +import java.math.BigDecimal; + +/** + * A polynomial with {@link BigDecimal} coefficients. + * Some methods (like <code>add</code>) change the polynomial, others (like <code>mult</code>) do + * not but return the result as a new polynomial. + */ +public class BigDecimalPolynomial +{ + private static final BigDecimal ZERO = new BigDecimal("0"); + private static final BigDecimal ONE_HALF = new BigDecimal("0.5"); + + BigDecimal[] coeffs; + + /** + * Constructs a new polynomial with <code>N</code> coefficients initialized to 0. + * + * @param N the number of coefficients + */ + BigDecimalPolynomial(int N) + { + coeffs = new BigDecimal[N]; + for (int i = 0; i < N; i++) + { + coeffs[i] = ZERO; + } + } + + /** + * Constructs a new polynomial with a given set of coefficients. + * + * @param coeffs the coefficients + */ + BigDecimalPolynomial(BigDecimal[] coeffs) + { + this.coeffs = coeffs; + } + + /** + * Constructs a <code>BigDecimalPolynomial</code> from a <code>BigIntPolynomial</code>. The two polynomials are independent of each other. + * + * @param p the original polynomial + */ + public BigDecimalPolynomial(BigIntPolynomial p) + { + int N = p.coeffs.length; + coeffs = new BigDecimal[N]; + for (int i = 0; i < N; i++) + { + coeffs[i] = new BigDecimal(p.coeffs[i]); + } + } + + /** + * Divides all coefficients by 2. + */ + public void halve() + { + for (int i = 0; i < coeffs.length; i++) + { + coeffs[i] = coeffs[i].multiply(ONE_HALF); + } + } + + /** + * Multiplies the polynomial by another. Does not change this polynomial + * but returns the result as a new polynomial. + * + * @param poly2 the polynomial to multiply by + * @return a new polynomial + */ + public BigDecimalPolynomial mult(BigIntPolynomial poly2) + { + return mult(new BigDecimalPolynomial(poly2)); + } + + /** + * Multiplies the polynomial by another, taking the indices mod N. Does not + * change this polynomial but returns the result as a new polynomial. + * + * @param poly2 the polynomial to multiply by + * @return a new polynomial + */ + public BigDecimalPolynomial mult(BigDecimalPolynomial poly2) + { + int N = coeffs.length; + if (poly2.coeffs.length != N) + { + throw new IllegalArgumentException("Number of coefficients must be the same"); + } + + BigDecimalPolynomial c = multRecursive(poly2); + + if (c.coeffs.length > N) + { + for (int k = N; k < c.coeffs.length; k++) + { + c.coeffs[k - N] = c.coeffs[k - N].add(c.coeffs[k]); + } + c.coeffs = copyOf(c.coeffs, N); + } + return c; + } + + /** + * Karazuba multiplication + */ + private BigDecimalPolynomial multRecursive(BigDecimalPolynomial poly2) + { + BigDecimal[] a = coeffs; + BigDecimal[] b = poly2.coeffs; + + int n = poly2.coeffs.length; + if (n <= 1) + { + BigDecimal[] c = coeffs.clone(); + for (int i = 0; i < coeffs.length; i++) + { + c[i] = c[i].multiply(poly2.coeffs[0]); + } + return new BigDecimalPolynomial(c); + } + else + { + int n1 = n / 2; + + BigDecimalPolynomial a1 = new BigDecimalPolynomial(copyOf(a, n1)); + BigDecimalPolynomial a2 = new BigDecimalPolynomial(copyOfRange(a, n1, n)); + BigDecimalPolynomial b1 = new BigDecimalPolynomial(copyOf(b, n1)); + BigDecimalPolynomial b2 = new BigDecimalPolynomial(copyOfRange(b, n1, n)); + + BigDecimalPolynomial A = (BigDecimalPolynomial)a1.clone(); + A.add(a2); + BigDecimalPolynomial B = (BigDecimalPolynomial)b1.clone(); + B.add(b2); + + BigDecimalPolynomial c1 = a1.multRecursive(b1); + BigDecimalPolynomial c2 = a2.multRecursive(b2); + BigDecimalPolynomial c3 = A.multRecursive(B); + c3.sub(c1); + c3.sub(c2); + + BigDecimalPolynomial c = new BigDecimalPolynomial(2 * n - 1); + for (int i = 0; i < c1.coeffs.length; i++) + { + c.coeffs[i] = c1.coeffs[i]; + } + for (int i = 0; i < c3.coeffs.length; i++) + { + c.coeffs[n1 + i] = c.coeffs[n1 + i].add(c3.coeffs[i]); + } + for (int i = 0; i < c2.coeffs.length; i++) + { + c.coeffs[2 * n1 + i] = c.coeffs[2 * n1 + i].add(c2.coeffs[i]); + } + return c; + } + } + + /** + * Adds another polynomial which can have a different number of coefficients. + * + * @param b another polynomial + */ + public void add(BigDecimalPolynomial b) + { + if (b.coeffs.length > coeffs.length) + { + int N = coeffs.length; + coeffs = copyOf(coeffs, b.coeffs.length); + for (int i = N; i < coeffs.length; i++) + { + coeffs[i] = ZERO; + } + } + for (int i = 0; i < b.coeffs.length; i++) + { + coeffs[i] = coeffs[i].add(b.coeffs[i]); + } + } + + /** + * Subtracts another polynomial which can have a different number of coefficients. + * + * @param b + */ + void sub(BigDecimalPolynomial b) + { + if (b.coeffs.length > coeffs.length) + { + int N = coeffs.length; + coeffs = copyOf(coeffs, b.coeffs.length); + for (int i = N; i < coeffs.length; i++) + { + coeffs[i] = ZERO; + } + } + for (int i = 0; i < b.coeffs.length; i++) + { + coeffs[i] = coeffs[i].subtract(b.coeffs[i]); + } + } + + /** + * Rounds all coefficients to the nearest integer. + * + * @return a new polynomial with <code>BigInteger</code> coefficients + */ + public BigIntPolynomial round() + { + int N = coeffs.length; + BigIntPolynomial p = new BigIntPolynomial(N); + for (int i = 0; i < N; i++) + { + p.coeffs[i] = coeffs[i].setScale(0, BigDecimal.ROUND_HALF_EVEN).toBigInteger(); + } + return p; + } + + /** + * Makes a copy of the polynomial that is independent of the original. + */ + public Object clone() + { + return new BigDecimalPolynomial(coeffs.clone()); + } + + private BigDecimal[] copyOf(BigDecimal[] a, int length) + { + BigDecimal[] tmp = new BigDecimal[length]; + + System.arraycopy(a, 0, tmp, 0, a.length < length ? a.length : length); + + return tmp; + } + + private BigDecimal[] copyOfRange(BigDecimal[] a, int from, int to) + { + int newLength = to - from; + BigDecimal[] tmp = new BigDecimal[to - from]; + + System.arraycopy(a, from, tmp, 0, (a.length - from) < newLength ? (a.length - from) : newLength); + + return tmp; + } + + public BigDecimal[] getCoeffs() + { + BigDecimal[] tmp = new BigDecimal[coeffs.length]; + + System.arraycopy(coeffs, 0, tmp, 0, coeffs.length); + + return tmp; + } + +} diff --git a/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/BigIntPolynomial.java b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/BigIntPolynomial.java new file mode 100644 index 00000000..2869fec8 --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/BigIntPolynomial.java @@ -0,0 +1,394 @@ +package org.spongycastle.pqc.math.ntru.polynomial; + +import java.math.BigDecimal; +import java.math.BigInteger; +import java.security.SecureRandom; +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; + +import org.spongycastle.util.Arrays; + +/** + * A polynomial with {@link BigInteger} coefficients.<br> + * Some methods (like <code>add</code>) change the polynomial, others (like <code>mult</code>) do + * not but return the result as a new polynomial. + */ +public class BigIntPolynomial +{ + private final static double LOG_10_2 = Math.log10(2); + + BigInteger[] coeffs; + + /** + * Constructs a new polynomial with <code>N</code> coefficients initialized to 0. + * + * @param N the number of coefficients + */ + BigIntPolynomial(int N) + { + coeffs = new BigInteger[N]; + for (int i = 0; i < N; i++) + { + coeffs[i] = Constants.BIGINT_ZERO; + } + } + + /** + * Constructs a new polynomial with a given set of coefficients. + * + * @param coeffs the coefficients + */ + BigIntPolynomial(BigInteger[] coeffs) + { + this.coeffs = coeffs; + } + + /** + * Constructs a <code>BigIntPolynomial</code> from a <code>IntegerPolynomial</code>. The two polynomials are + * independent of each other. + * + * @param p the original polynomial + */ + public BigIntPolynomial(IntegerPolynomial p) + { + coeffs = new BigInteger[p.coeffs.length]; + for (int i = 0; i < coeffs.length; i++) + { + coeffs[i] = BigInteger.valueOf(p.coeffs[i]); + } + } + + /** + * Generates a random polynomial with <code>numOnes</code> coefficients equal to 1, + * <code>numNegOnes</code> coefficients equal to -1, and the rest equal to 0. + * + * @param N number of coefficients + * @param numOnes number of 1's + * @param numNegOnes number of -1's + * @return + */ + static BigIntPolynomial generateRandomSmall(int N, int numOnes, int numNegOnes) + { + List coeffs = new ArrayList(); + for (int i = 0; i < numOnes; i++) + { + coeffs.add(Constants.BIGINT_ONE); + } + for (int i = 0; i < numNegOnes; i++) + { + coeffs.add(BigInteger.valueOf(-1)); + } + while (coeffs.size() < N) + { + coeffs.add(Constants.BIGINT_ZERO); + } + Collections.shuffle(coeffs, new SecureRandom()); + + BigIntPolynomial poly = new BigIntPolynomial(N); + for (int i = 0; i < coeffs.size(); i++) + { + poly.coeffs[i] = (BigInteger)coeffs.get(i); + } + return poly; + } + + /** + * Multiplies the polynomial by another, taking the indices mod N. Does not + * change this polynomial but returns the result as a new polynomial.<br> + * Both polynomials must have the same number of coefficients. + * + * @param poly2 the polynomial to multiply by + * @return a new polynomial + */ + public BigIntPolynomial mult(BigIntPolynomial poly2) + { + int N = coeffs.length; + if (poly2.coeffs.length != N) + { + throw new IllegalArgumentException("Number of coefficients must be the same"); + } + + BigIntPolynomial c = multRecursive(poly2); + + if (c.coeffs.length > N) + { + for (int k = N; k < c.coeffs.length; k++) + { + c.coeffs[k - N] = c.coeffs[k - N].add(c.coeffs[k]); + } + c.coeffs = Arrays.copyOf(c.coeffs, N); + } + return c; + } + + /** + * Karazuba multiplication + */ + private BigIntPolynomial multRecursive(BigIntPolynomial poly2) + { + BigInteger[] a = coeffs; + BigInteger[] b = poly2.coeffs; + + int n = poly2.coeffs.length; + if (n <= 1) + { + BigInteger[] c = Arrays.clone(coeffs); + for (int i = 0; i < coeffs.length; i++) + { + c[i] = c[i].multiply(poly2.coeffs[0]); + } + return new BigIntPolynomial(c); + } + else + { + int n1 = n / 2; + + BigIntPolynomial a1 = new BigIntPolynomial(Arrays.copyOf(a, n1)); + BigIntPolynomial a2 = new BigIntPolynomial(Arrays.copyOfRange(a, n1, n)); + BigIntPolynomial b1 = new BigIntPolynomial(Arrays.copyOf(b, n1)); + BigIntPolynomial b2 = new BigIntPolynomial(Arrays.copyOfRange(b, n1, n)); + + BigIntPolynomial A = (BigIntPolynomial)a1.clone(); + A.add(a2); + BigIntPolynomial B = (BigIntPolynomial)b1.clone(); + B.add(b2); + + BigIntPolynomial c1 = a1.multRecursive(b1); + BigIntPolynomial c2 = a2.multRecursive(b2); + BigIntPolynomial c3 = A.multRecursive(B); + c3.sub(c1); + c3.sub(c2); + + BigIntPolynomial c = new BigIntPolynomial(2 * n - 1); + for (int i = 0; i < c1.coeffs.length; i++) + { + c.coeffs[i] = c1.coeffs[i]; + } + for (int i = 0; i < c3.coeffs.length; i++) + { + c.coeffs[n1 + i] = c.coeffs[n1 + i].add(c3.coeffs[i]); + } + for (int i = 0; i < c2.coeffs.length; i++) + { + c.coeffs[2 * n1 + i] = c.coeffs[2 * n1 + i].add(c2.coeffs[i]); + } + return c; + } + } + + /** + * Adds another polynomial which can have a different number of coefficients, + * and takes the coefficient values mod <code>modulus</code>. + * + * @param b another polynomial + */ + void add(BigIntPolynomial b, BigInteger modulus) + { + add(b); + mod(modulus); + } + + /** + * Adds another polynomial which can have a different number of coefficients. + * + * @param b another polynomial + */ + public void add(BigIntPolynomial b) + { + if (b.coeffs.length > coeffs.length) + { + int N = coeffs.length; + coeffs = Arrays.copyOf(coeffs, b.coeffs.length); + for (int i = N; i < coeffs.length; i++) + { + coeffs[i] = Constants.BIGINT_ZERO; + } + } + for (int i = 0; i < b.coeffs.length; i++) + { + coeffs[i] = coeffs[i].add(b.coeffs[i]); + } + } + + /** + * Subtracts another polynomial which can have a different number of coefficients. + * + * @param b another polynomial + */ + public void sub(BigIntPolynomial b) + { + if (b.coeffs.length > coeffs.length) + { + int N = coeffs.length; + coeffs = Arrays.copyOf(coeffs, b.coeffs.length); + for (int i = N; i < coeffs.length; i++) + { + coeffs[i] = Constants.BIGINT_ZERO; + } + } + for (int i = 0; i < b.coeffs.length; i++) + { + coeffs[i] = coeffs[i].subtract(b.coeffs[i]); + } + } + + /** + * Multiplies each coefficient by a <code>BigInteger</code>. Does not return a new polynomial but modifies this polynomial. + * + * @param factor + */ + public void mult(BigInteger factor) + { + for (int i = 0; i < coeffs.length; i++) + { + coeffs[i] = coeffs[i].multiply(factor); + } + } + + /** + * Multiplies each coefficient by a <code>int</code>. Does not return a new polynomial but modifies this polynomial. + * + * @param factor + */ + void mult(int factor) + { + mult(BigInteger.valueOf(factor)); + } + + /** + * Divides each coefficient by a <code>BigInteger</code> and rounds the result to the nearest whole number.<br> + * Does not return a new polynomial but modifies this polynomial. + * + * @param divisor the number to divide by + */ + public void div(BigInteger divisor) + { + BigInteger d = divisor.add(Constants.BIGINT_ONE).divide(BigInteger.valueOf(2)); + for (int i = 0; i < coeffs.length; i++) + { + coeffs[i] = coeffs[i].compareTo(Constants.BIGINT_ZERO) > 0 ? coeffs[i].add(d) : coeffs[i].add(d.negate()); + coeffs[i] = coeffs[i].divide(divisor); + } + } + + /** + * Divides each coefficient by a <code>BigDecimal</code> and rounds the result to <code>decimalPlaces</code> places. + * + * @param divisor the number to divide by + * @param decimalPlaces the number of fractional digits to round the result to + * @return a new <code>BigDecimalPolynomial</code> + */ + public BigDecimalPolynomial div(BigDecimal divisor, int decimalPlaces) + { + BigInteger max = maxCoeffAbs(); + int coeffLength = (int)(max.bitLength() * LOG_10_2) + 1; + // factor = 1/divisor + BigDecimal factor = Constants.BIGDEC_ONE.divide(divisor, coeffLength + decimalPlaces + 1, BigDecimal.ROUND_HALF_EVEN); + + // multiply each coefficient by factor + BigDecimalPolynomial p = new BigDecimalPolynomial(coeffs.length); + for (int i = 0; i < coeffs.length; i++) + // multiply, then truncate after decimalPlaces so subsequent operations aren't slowed down + { + p.coeffs[i] = new BigDecimal(coeffs[i]).multiply(factor).setScale(decimalPlaces, BigDecimal.ROUND_HALF_EVEN); + } + + return p; + } + + /** + * Returns the base10 length of the largest coefficient. + * + * @return length of the longest coefficient + */ + public int getMaxCoeffLength() + { + return (int)(maxCoeffAbs().bitLength() * LOG_10_2) + 1; + } + + private BigInteger maxCoeffAbs() + { + BigInteger max = coeffs[0].abs(); + for (int i = 1; i < coeffs.length; i++) + { + BigInteger coeff = coeffs[i].abs(); + if (coeff.compareTo(max) > 0) + { + max = coeff; + } + } + return max; + } + + /** + * Takes each coefficient modulo a number. + * + * @param modulus + */ + public void mod(BigInteger modulus) + { + for (int i = 0; i < coeffs.length; i++) + { + coeffs[i] = coeffs[i].mod(modulus); + } + } + + /** + * Returns the sum of all coefficients, i.e. evaluates the polynomial at 0. + * + * @return the sum of all coefficients + */ + BigInteger sumCoeffs() + { + BigInteger sum = Constants.BIGINT_ZERO; + for (int i = 0; i < coeffs.length; i++) + { + sum = sum.add(coeffs[i]); + } + return sum; + } + + /** + * Makes a copy of the polynomial that is independent of the original. + */ + public Object clone() + { + return new BigIntPolynomial(coeffs.clone()); + } + + public int hashCode() + { + final int prime = 31; + int result = 1; + result = prime * result + Arrays.hashCode(coeffs); + return result; + } + + public boolean equals(Object obj) + { + if (this == obj) + { + return true; + } + if (obj == null) + { + return false; + } + if (getClass() != obj.getClass()) + { + return false; + } + BigIntPolynomial other = (BigIntPolynomial)obj; + if (!Arrays.areEqual(coeffs, other.coeffs)) + { + return false; + } + return true; + } + + public BigInteger[] getCoeffs() + { + return Arrays.clone(coeffs); + } +} diff --git a/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/Constants.java b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/Constants.java new file mode 100644 index 00000000..f29ce066 --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/Constants.java @@ -0,0 +1,12 @@ +package org.spongycastle.pqc.math.ntru.polynomial; + +import java.math.BigDecimal; +import java.math.BigInteger; + +public class Constants +{ + static final BigInteger BIGINT_ZERO = BigInteger.valueOf(0); + static final BigInteger BIGINT_ONE = BigInteger.valueOf(1); + + static final BigDecimal BIGDEC_ONE = BigDecimal.valueOf(1); +} diff --git a/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/DenseTernaryPolynomial.java b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/DenseTernaryPolynomial.java new file mode 100644 index 00000000..007e7249 --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/DenseTernaryPolynomial.java @@ -0,0 +1,142 @@ +package org.spongycastle.pqc.math.ntru.polynomial; + +import java.security.SecureRandom; + +import org.spongycastle.pqc.math.ntru.util.Util; +import org.spongycastle.util.Arrays; + +/** + * A <code>TernaryPolynomial</code> with a "high" number of nonzero coefficients. + */ +public class DenseTernaryPolynomial + extends IntegerPolynomial + implements TernaryPolynomial +{ + + /** + * Constructs a new <code>DenseTernaryPolynomial</code> with <code>N</code> coefficients. + * + * @param N the number of coefficients + */ + DenseTernaryPolynomial(int N) + { + super(N); + checkTernarity(); + } + + /** + * Constructs a <code>DenseTernaryPolynomial</code> from a <code>IntegerPolynomial</code>. The two polynomials are + * independent of each other. + * + * @param intPoly the original polynomial + */ + public DenseTernaryPolynomial(IntegerPolynomial intPoly) + { + this(intPoly.coeffs); + } + + /** + * Constructs a new <code>DenseTernaryPolynomial</code> with a given set of coefficients. + * + * @param coeffs the coefficients + */ + public DenseTernaryPolynomial(int[] coeffs) + { + super(coeffs); + checkTernarity(); + } + + private void checkTernarity() + { + for (int i = 0; i != coeffs.length; i++) + { + int c = coeffs[i]; + if (c < -1 || c > 1) + { + throw new IllegalStateException("Illegal value: " + c + ", must be one of {-1, 0, 1}"); + } + } + } + + /** + * Generates a random polynomial with <code>numOnes</code> coefficients equal to 1, + * <code>numNegOnes</code> coefficients equal to -1, and the rest equal to 0. + * + * @param N number of coefficients + * @param numOnes number of 1's + * @param numNegOnes number of -1's + */ + public static DenseTernaryPolynomial generateRandom(int N, int numOnes, int numNegOnes, SecureRandom random) + { + int[] coeffs = Util.generateRandomTernary(N, numOnes, numNegOnes, random); + return new DenseTernaryPolynomial(coeffs); + } + + /** + * Generates a polynomial with coefficients randomly selected from <code>{-1, 0, 1}</code>. + * + * @param N number of coefficients + */ + public static DenseTernaryPolynomial generateRandom(int N, SecureRandom random) + { + DenseTernaryPolynomial poly = new DenseTernaryPolynomial(N); + for (int i = 0; i < N; i++) + { + poly.coeffs[i] = random.nextInt(3) - 1; + } + return poly; + } + + public IntegerPolynomial mult(IntegerPolynomial poly2, int modulus) + { + // even on 32-bit systems, LongPolynomial5 multiplies faster than IntegerPolynomial + if (modulus == 2048) + { + IntegerPolynomial poly2Pos = (IntegerPolynomial)poly2.clone(); + poly2Pos.modPositive(2048); + LongPolynomial5 poly5 = new LongPolynomial5(poly2Pos); + return poly5.mult(this).toIntegerPolynomial(); + } + else + { + return super.mult(poly2, modulus); + } + } + + public int[] getOnes() + { + int N = coeffs.length; + int[] ones = new int[N]; + int onesIdx = 0; + for (int i = 0; i < N; i++) + { + int c = coeffs[i]; + if (c == 1) + { + ones[onesIdx++] = i; + } + } + return Arrays.copyOf(ones, onesIdx); + } + + public int[] getNegOnes() + { + int N = coeffs.length; + int[] negOnes = new int[N]; + int negOnesIdx = 0; + for (int i = 0; i < N; i++) + { + int c = coeffs[i]; + if (c == -1) + { + negOnes[negOnesIdx++] = i; + } + } + return Arrays.copyOf(negOnes, negOnesIdx); + } + + public int size() + { + return coeffs.length; + } +} diff --git a/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/IntegerPolynomial.java b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/IntegerPolynomial.java new file mode 100644 index 00000000..41e921bf --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/IntegerPolynomial.java @@ -0,0 +1,1358 @@ +package org.spongycastle.pqc.math.ntru.polynomial; + +import java.io.IOException; +import java.io.InputStream; +import java.math.BigInteger; +import java.util.ArrayList; +import java.util.Iterator; +import java.util.LinkedList; +import java.util.List; +import java.util.concurrent.Callable; +import java.util.concurrent.ExecutorService; +import java.util.concurrent.Executors; +import java.util.concurrent.Future; +import java.util.concurrent.LinkedBlockingQueue; + +import org.spongycastle.pqc.math.ntru.euclid.BigIntEuclidean; +import org.spongycastle.pqc.math.ntru.util.ArrayEncoder; +import org.spongycastle.pqc.math.ntru.util.Util; +import org.spongycastle.util.Arrays; + +/** + * A polynomial with <code>int</code> coefficients.<br> + * Some methods (like <code>add</code>) change the polynomial, others (like <code>mult</code>) do + * not but return the result as a new polynomial. + */ +public class IntegerPolynomial + implements Polynomial +{ + private static final int NUM_EQUAL_RESULTANTS = 3; + /** + * Prime numbers > 4500 for resultant computation. Starting them below ~4400 causes incorrect results occasionally. + * Fortunately, 4500 is about the optimum number for performance.<br/> + * This array contains enough prime numbers so primes never have to be computed on-line for any standard {@link org.spongycastle.pqc.crypto.ntru.NTRUSigningParameters}. + */ + private static final int[] PRIMES = new int[]{ + 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, + 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, + 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, + 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, + 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, + 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, + 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, + 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, + 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, + 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, + 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, + 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, + 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, + 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, + 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, + 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, + 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, + 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, + 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, + 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, + 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, + 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, + 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, + 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, + 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, + 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, + 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, + 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, + 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, + 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, + 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, + 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, + 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, + 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, + 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, + 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, + 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, + 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, + 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, + 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, + 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, + 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, + 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, + 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, + 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, + 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, + 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, + 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, + 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, + 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, + 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, + 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, + 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, + 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, + 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, + 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, + 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, + 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, + 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, + 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, + 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, + 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973}; + private static final List BIGINT_PRIMES; + + static + { + BIGINT_PRIMES = new ArrayList(); + for (int i = 0; i != PRIMES.length; i++) + { + BIGINT_PRIMES.add(BigInteger.valueOf(PRIMES[i])); + } + } + + public int[] coeffs; + + /** + * Constructs a new polynomial with <code>N</code> coefficients initialized to 0. + * + * @param N the number of coefficients + */ + public IntegerPolynomial(int N) + { + coeffs = new int[N]; + } + + /** + * Constructs a new polynomial with a given set of coefficients. + * + * @param coeffs the coefficients + */ + public IntegerPolynomial(int[] coeffs) + { + this.coeffs = coeffs; + } + + /** + * Constructs a <code>IntegerPolynomial</code> from a <code>BigIntPolynomial</code>. The two polynomials are independent of each other. + * + * @param p the original polynomial + */ + public IntegerPolynomial(BigIntPolynomial p) + { + coeffs = new int[p.coeffs.length]; + for (int i = 0; i < p.coeffs.length; i++) + { + coeffs[i] = p.coeffs[i].intValue(); + } + } + + /** + * Decodes a byte array to a polynomial with <code>N</code> ternary coefficients<br> + * Ignores any excess bytes. + * + * @param data an encoded ternary polynomial + * @param N number of coefficients + * @return the decoded polynomial + */ + public static IntegerPolynomial fromBinary3Sves(byte[] data, int N) + { + return new IntegerPolynomial(ArrayEncoder.decodeMod3Sves(data, N)); + } + + /** + * Converts a byte array produced by {@link #toBinary3Tight()} to a polynomial. + * + * @param b a byte array + * @param N number of coefficients + * @return the decoded polynomial + */ + public static IntegerPolynomial fromBinary3Tight(byte[] b, int N) + { + return new IntegerPolynomial(ArrayEncoder.decodeMod3Tight(b, N)); + } + + /** + * Reads data produced by {@link #toBinary3Tight()} from an input stream and converts it to a polynomial. + * + * @param is an input stream + * @param N number of coefficients + * @return the decoded polynomial + */ + public static IntegerPolynomial fromBinary3Tight(InputStream is, int N) + throws IOException + { + return new IntegerPolynomial(ArrayEncoder.decodeMod3Tight(is, N)); + } + + /** + * Returns a polynomial with N coefficients between <code>0</code> and <code>q-1</code>.<br> + * <code>q</code> must be a power of 2.<br> + * Ignores any excess bytes. + * + * @param data an encoded ternary polynomial + * @param N number of coefficients + * @param q + * @return the decoded polynomial + */ + public static IntegerPolynomial fromBinary(byte[] data, int N, int q) + { + return new IntegerPolynomial(ArrayEncoder.decodeModQ(data, N, q)); + } + + /** + * Returns a polynomial with N coefficients between <code>0</code> and <code>q-1</code>.<br> + * <code>q</code> must be a power of 2.<br> + * Ignores any excess bytes. + * + * @param is an encoded ternary polynomial + * @param N number of coefficients + * @param q + * @return the decoded polynomial + */ + public static IntegerPolynomial fromBinary(InputStream is, int N, int q) + throws IOException + { + return new IntegerPolynomial(ArrayEncoder.decodeModQ(is, N, q)); + } + + /** + * Encodes a polynomial with ternary coefficients to binary. + * <code>coeffs[2*i]</code> and <code>coeffs[2*i+1]</code> must not both equal -1 for any integer <code>i</code>, + * so this method is only safe to use with polynomials produced by <code>fromBinary3Sves()</code>. + * + * @return the encoded polynomial + */ + public byte[] toBinary3Sves() + { + return ArrayEncoder.encodeMod3Sves(coeffs); + } + + /** + * Converts a polynomial with ternary coefficients to binary. + * + * @return the encoded polynomial + */ + public byte[] toBinary3Tight() + { + BigInteger sum = Constants.BIGINT_ZERO; + for (int i = coeffs.length - 1; i >= 0; i--) + { + sum = sum.multiply(BigInteger.valueOf(3)); + sum = sum.add(BigInteger.valueOf(coeffs[i] + 1)); + } + + int size = (BigInteger.valueOf(3).pow(coeffs.length).bitLength() + 7) / 8; + byte[] arr = sum.toByteArray(); + + if (arr.length < size) + { + // pad with leading zeros so arr.length==size + byte[] arr2 = new byte[size]; + System.arraycopy(arr, 0, arr2, size - arr.length, arr.length); + return arr2; + } + + if (arr.length > size) + // drop sign bit + { + arr = Arrays.copyOfRange(arr, 1, arr.length); + } + return arr; + } + + /** + * Encodes a polynomial whose coefficients are between 0 and q, to binary. q must be a power of 2. + * + * @param q + * @return the encoded polynomial + */ + public byte[] toBinary(int q) + { + return ArrayEncoder.encodeModQ(coeffs, q); + } + + /** + * Multiplies the polynomial with another, taking the values mod modulus and the indices mod N + */ + public IntegerPolynomial mult(IntegerPolynomial poly2, int modulus) + { + IntegerPolynomial c = mult(poly2); + c.mod(modulus); + return c; + } + + /** + * Multiplies the polynomial with another, taking the indices mod N + */ + public IntegerPolynomial mult(IntegerPolynomial poly2) + { + int N = coeffs.length; + if (poly2.coeffs.length != N) + { + throw new IllegalArgumentException("Number of coefficients must be the same"); + } + + IntegerPolynomial c = multRecursive(poly2); + + if (c.coeffs.length > N) + { + for (int k = N; k < c.coeffs.length; k++) + { + c.coeffs[k - N] += c.coeffs[k]; + } + c.coeffs = Arrays.copyOf(c.coeffs, N); + } + return c; + } + + public BigIntPolynomial mult(BigIntPolynomial poly2) + { + return new BigIntPolynomial(this).mult(poly2); + } + + /** + * Karazuba multiplication + */ + private IntegerPolynomial multRecursive(IntegerPolynomial poly2) + { + int[] a = coeffs; + int[] b = poly2.coeffs; + + int n = poly2.coeffs.length; + if (n <= 32) + { + int cn = 2 * n - 1; + IntegerPolynomial c = new IntegerPolynomial(new int[cn]); + for (int k = 0; k < cn; k++) + { + for (int i = Math.max(0, k - n + 1); i <= Math.min(k, n - 1); i++) + { + c.coeffs[k] += b[i] * a[k - i]; + } + } + return c; + } + else + { + int n1 = n / 2; + + IntegerPolynomial a1 = new IntegerPolynomial(Arrays.copyOf(a, n1)); + IntegerPolynomial a2 = new IntegerPolynomial(Arrays.copyOfRange(a, n1, n)); + IntegerPolynomial b1 = new IntegerPolynomial(Arrays.copyOf(b, n1)); + IntegerPolynomial b2 = new IntegerPolynomial(Arrays.copyOfRange(b, n1, n)); + + IntegerPolynomial A = (IntegerPolynomial)a1.clone(); + A.add(a2); + IntegerPolynomial B = (IntegerPolynomial)b1.clone(); + B.add(b2); + + IntegerPolynomial c1 = a1.multRecursive(b1); + IntegerPolynomial c2 = a2.multRecursive(b2); + IntegerPolynomial c3 = A.multRecursive(B); + c3.sub(c1); + c3.sub(c2); + + IntegerPolynomial c = new IntegerPolynomial(2 * n - 1); + for (int i = 0; i < c1.coeffs.length; i++) + { + c.coeffs[i] = c1.coeffs[i]; + } + for (int i = 0; i < c3.coeffs.length; i++) + { + c.coeffs[n1 + i] += c3.coeffs[i]; + } + for (int i = 0; i < c2.coeffs.length; i++) + { + c.coeffs[2 * n1 + i] += c2.coeffs[i]; + } + return c; + } + } + + /** + * Computes the inverse mod <code>q; q</code> must be a power of 2.<br> + * Returns <code>null</code> if the polynomial is not invertible. + * + * @param q the modulus + * @return a new polynomial + */ + public IntegerPolynomial invertFq(int q) + { + int N = coeffs.length; + int k = 0; + IntegerPolynomial b = new IntegerPolynomial(N + 1); + b.coeffs[0] = 1; + IntegerPolynomial c = new IntegerPolynomial(N + 1); + IntegerPolynomial f = new IntegerPolynomial(N + 1); + f.coeffs = Arrays.copyOf(coeffs, N + 1); + f.modPositive(2); + // set g(x) = x^N − 1 + IntegerPolynomial g = new IntegerPolynomial(N + 1); + g.coeffs[0] = 1; + g.coeffs[N] = 1; + while (true) + { + while (f.coeffs[0] == 0) + { + for (int i = 1; i <= N; i++) + { + f.coeffs[i - 1] = f.coeffs[i]; // f(x) = f(x) / x + c.coeffs[N + 1 - i] = c.coeffs[N - i]; // c(x) = c(x) * x + } + f.coeffs[N] = 0; + c.coeffs[0] = 0; + k++; + if (f.equalsZero()) + { + return null; // not invertible + } + } + if (f.equalsOne()) + { + break; + } + if (f.degree() < g.degree()) + { + // exchange f and g + IntegerPolynomial temp = f; + f = g; + g = temp; + // exchange b and c + temp = b; + b = c; + c = temp; + } + f.add(g, 2); + b.add(c, 2); + } + + if (b.coeffs[N] != 0) + { + return null; + } + // Fq(x) = x^(N-k) * b(x) + IntegerPolynomial Fq = new IntegerPolynomial(N); + int j = 0; + k %= N; + for (int i = N - 1; i >= 0; i--) + { + j = i - k; + if (j < 0) + { + j += N; + } + Fq.coeffs[j] = b.coeffs[i]; + } + + return mod2ToModq(Fq, q); + } + + /** + * Computes the inverse mod q from the inverse mod 2 + * + * @param Fq + * @param q + * @return The inverse of this polynomial mod q + */ + private IntegerPolynomial mod2ToModq(IntegerPolynomial Fq, int q) + { + if (Util.is64BitJVM() && q == 2048) + { + LongPolynomial2 thisLong = new LongPolynomial2(this); + LongPolynomial2 FqLong = new LongPolynomial2(Fq); + int v = 2; + while (v < q) + { + v *= 2; + LongPolynomial2 temp = (LongPolynomial2)FqLong.clone(); + temp.mult2And(v - 1); + FqLong = thisLong.mult(FqLong).mult(FqLong); + temp.subAnd(FqLong, v - 1); + FqLong = temp; + } + return FqLong.toIntegerPolynomial(); + } + else + { + int v = 2; + while (v < q) + { + v *= 2; + IntegerPolynomial temp = new IntegerPolynomial(Arrays.copyOf(Fq.coeffs, Fq.coeffs.length)); + temp.mult2(v); + Fq = mult(Fq, v).mult(Fq, v); + temp.sub(Fq, v); + Fq = temp; + } + return Fq; + } + } + + /** + * Computes the inverse mod 3. + * Returns <code>null</code> if the polynomial is not invertible. + * + * @return a new polynomial + */ + public IntegerPolynomial invertF3() + { + int N = coeffs.length; + int k = 0; + IntegerPolynomial b = new IntegerPolynomial(N + 1); + b.coeffs[0] = 1; + IntegerPolynomial c = new IntegerPolynomial(N + 1); + IntegerPolynomial f = new IntegerPolynomial(N + 1); + f.coeffs = Arrays.copyOf(coeffs, N + 1); + f.modPositive(3); + // set g(x) = x^N − 1 + IntegerPolynomial g = new IntegerPolynomial(N + 1); + g.coeffs[0] = -1; + g.coeffs[N] = 1; + while (true) + { + while (f.coeffs[0] == 0) + { + for (int i = 1; i <= N; i++) + { + f.coeffs[i - 1] = f.coeffs[i]; // f(x) = f(x) / x + c.coeffs[N + 1 - i] = c.coeffs[N - i]; // c(x) = c(x) * x + } + f.coeffs[N] = 0; + c.coeffs[0] = 0; + k++; + if (f.equalsZero()) + { + return null; // not invertible + } + } + if (f.equalsAbsOne()) + { + break; + } + if (f.degree() < g.degree()) + { + // exchange f and g + IntegerPolynomial temp = f; + f = g; + g = temp; + // exchange b and c + temp = b; + b = c; + c = temp; + } + if (f.coeffs[0] == g.coeffs[0]) + { + f.sub(g, 3); + b.sub(c, 3); + } + else + { + f.add(g, 3); + b.add(c, 3); + } + } + + if (b.coeffs[N] != 0) + { + return null; + } + // Fp(x) = [+-] x^(N-k) * b(x) + IntegerPolynomial Fp = new IntegerPolynomial(N); + int j = 0; + k %= N; + for (int i = N - 1; i >= 0; i--) + { + j = i - k; + if (j < 0) + { + j += N; + } + Fp.coeffs[j] = f.coeffs[0] * b.coeffs[i]; + } + + Fp.ensurePositive(3); + return Fp; + } + + /** + * Resultant of this polynomial with <code>x^n-1</code> using a probabilistic algorithm. + * <p> + * Unlike EESS, this implementation does not compute all resultants modulo primes + * such that their product exceeds the maximum possible resultant, but rather stops + * when <code>NUM_EQUAL_RESULTANTS</code> consecutive modular resultants are equal.<br> + * This means the return value may be incorrect. Experiments show this happens in + * about 1 out of 100 cases when <code>N=439</code> and <code>NUM_EQUAL_RESULTANTS=2</code>, + * so the likelyhood of leaving the loop too early is <code>(1/100)^(NUM_EQUAL_RESULTANTS-1)</code>. + * <p> + * Because of the above, callers must verify the output and try a different polynomial if necessary. + * + * @return <code>(rho, res)</code> satisfying <code>res = rho*this + t*(x^n-1)</code> for some integer <code>t</code>. + */ + public Resultant resultant() + { + int N = coeffs.length; + + // Compute resultants modulo prime numbers. Continue until NUM_EQUAL_RESULTANTS consecutive modular resultants are equal. + LinkedList<ModularResultant> modResultants = new LinkedList<ModularResultant>(); + BigInteger prime = null; + BigInteger pProd = Constants.BIGINT_ONE; + BigInteger res = Constants.BIGINT_ONE; + int numEqual = 1; // number of consecutive modular resultants equal to each other + Iterator<BigInteger> primes = BIGINT_PRIMES.iterator(); + while (true) + { + prime = primes.hasNext() ? primes.next() : prime.nextProbablePrime(); + ModularResultant crr = resultant(prime.intValue()); + modResultants.add(crr); + + BigInteger temp = pProd.multiply(prime); + BigIntEuclidean er = BigIntEuclidean.calculate(prime, pProd); + BigInteger resPrev = res; + res = res.multiply(er.x.multiply(prime)); + BigInteger res2 = crr.res.multiply(er.y.multiply(pProd)); + res = res.add(res2).mod(temp); + pProd = temp; + + BigInteger pProd2 = pProd.divide(BigInteger.valueOf(2)); + BigInteger pProd2n = pProd2.negate(); + if (res.compareTo(pProd2) > 0) + { + res = res.subtract(pProd); + } + else if (res.compareTo(pProd2n) < 0) + { + res = res.add(pProd); + } + + if (res.equals(resPrev)) + { + numEqual++; + if (numEqual >= NUM_EQUAL_RESULTANTS) + { + break; + } + } + else + { + numEqual = 1; + } + } + + // Combine modular rho's to obtain the final rho. + // For efficiency, first combine all pairs of small resultants to bigger resultants, + // then combine pairs of those, etc. until only one is left. + while (modResultants.size() > 1) + { + ModularResultant modRes1 = modResultants.removeFirst(); + ModularResultant modRes2 = modResultants.removeFirst(); + ModularResultant modRes3 = ModularResultant.combineRho(modRes1, modRes2); + modResultants.addLast(modRes3); + } + BigIntPolynomial rhoP = modResultants.getFirst().rho; + + BigInteger pProd2 = pProd.divide(BigInteger.valueOf(2)); + BigInteger pProd2n = pProd2.negate(); + if (res.compareTo(pProd2) > 0) + { + res = res.subtract(pProd); + } + if (res.compareTo(pProd2n) < 0) + { + res = res.add(pProd); + } + + for (int i = 0; i < N; i++) + { + BigInteger c = rhoP.coeffs[i]; + if (c.compareTo(pProd2) > 0) + { + rhoP.coeffs[i] = c.subtract(pProd); + } + if (c.compareTo(pProd2n) < 0) + { + rhoP.coeffs[i] = c.add(pProd); + } + } + + return new Resultant(rhoP, res); + } + + /** + * Multithreaded version of {@link #resultant()}. + * + * @return <code>(rho, res)</code> satisfying <code>res = rho*this + t*(x^n-1)</code> for some integer <code>t</code>. + */ + public Resultant resultantMultiThread() + { + int N = coeffs.length; + + // upper bound for resultant(f, g) = ||f, 2||^deg(g) * ||g, 2||^deg(f) = squaresum(f)^(N/2) * 2^(deg(f)/2) because g(x)=x^N-1 + // see http://jondalon.mathematik.uni-osnabrueck.de/staff/phpages/brunsw/CompAlg.pdf chapter 3 + BigInteger max = squareSum().pow((N + 1) / 2); + max = max.multiply(BigInteger.valueOf(2).pow((degree() + 1) / 2)); + BigInteger max2 = max.multiply(BigInteger.valueOf(2)); + + // compute resultants modulo prime numbers + BigInteger prime = BigInteger.valueOf(10000); + BigInteger pProd = Constants.BIGINT_ONE; + LinkedBlockingQueue<Future<ModularResultant>> resultantTasks = new LinkedBlockingQueue<Future<ModularResultant>>(); + Iterator<BigInteger> primes = BIGINT_PRIMES.iterator(); + ExecutorService executor = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors()); + while (pProd.compareTo(max2) < 0) + { + if (primes.hasNext()) + { + prime = primes.next(); + } + else + { + prime = prime.nextProbablePrime(); + } + Future<ModularResultant> task = executor.submit(new ModResultantTask(prime.intValue())); + resultantTasks.add(task); + pProd = pProd.multiply(prime); + } + + // Combine modular resultants to obtain the resultant. + // For efficiency, first combine all pairs of small resultants to bigger resultants, + // then combine pairs of those, etc. until only one is left. + ModularResultant overallResultant = null; + while (!resultantTasks.isEmpty()) + { + try + { + Future<ModularResultant> modRes1 = resultantTasks.take(); + Future<ModularResultant> modRes2 = resultantTasks.poll(); + if (modRes2 == null) + { + // modRes1 is the only one left + overallResultant = modRes1.get(); + break; + } + Future<ModularResultant> newTask = executor.submit(new CombineTask(modRes1.get(), modRes2.get())); + resultantTasks.add(newTask); + } + catch (Exception e) + { + throw new IllegalStateException(e.toString()); + } + } + executor.shutdown(); + BigInteger res = overallResultant.res; + BigIntPolynomial rhoP = overallResultant.rho; + + BigInteger pProd2 = pProd.divide(BigInteger.valueOf(2)); + BigInteger pProd2n = pProd2.negate(); + + if (res.compareTo(pProd2) > 0) + { + res = res.subtract(pProd); + } + if (res.compareTo(pProd2n) < 0) + { + res = res.add(pProd); + } + + for (int i = 0; i < N; i++) + { + BigInteger c = rhoP.coeffs[i]; + if (c.compareTo(pProd2) > 0) + { + rhoP.coeffs[i] = c.subtract(pProd); + } + if (c.compareTo(pProd2n) < 0) + { + rhoP.coeffs[i] = c.add(pProd); + } + } + + return new Resultant(rhoP, res); + } + + /** + * Resultant of this polynomial with <code>x^n-1 mod p</code>. + * + * @return <code>(rho, res)</code> satisfying <code>res = rho*this + t*(x^n-1) mod p</code> for some integer <code>t</code>. + */ + public ModularResultant resultant(int p) + { + // Add a coefficient as the following operations involve polynomials of degree deg(f)+1 + int[] fcoeffs = Arrays.copyOf(coeffs, coeffs.length + 1); + IntegerPolynomial f = new IntegerPolynomial(fcoeffs); + int N = fcoeffs.length; + + IntegerPolynomial a = new IntegerPolynomial(N); + a.coeffs[0] = -1; + a.coeffs[N - 1] = 1; + IntegerPolynomial b = new IntegerPolynomial(f.coeffs); + IntegerPolynomial v1 = new IntegerPolynomial(N); + IntegerPolynomial v2 = new IntegerPolynomial(N); + v2.coeffs[0] = 1; + int da = N - 1; + int db = b.degree(); + int ta = da; + int c = 0; + int r = 1; + while (db > 0) + { + c = Util.invert(b.coeffs[db], p); + c = (c * a.coeffs[da]) % p; + a.multShiftSub(b, c, da - db, p); + v1.multShiftSub(v2, c, da - db, p); + + da = a.degree(); + if (da < db) + { + r *= Util.pow(b.coeffs[db], ta - da, p); + r %= p; + if (ta % 2 == 1 && db % 2 == 1) + { + r = (-r) % p; + } + IntegerPolynomial temp = a; + a = b; + b = temp; + int tempdeg = da; + da = db; + temp = v1; + v1 = v2; + v2 = temp; + ta = db; + db = tempdeg; + } + } + r *= Util.pow(b.coeffs[0], da, p); + r %= p; + c = Util.invert(b.coeffs[0], p); + v2.mult(c); + v2.mod(p); + v2.mult(r); + v2.mod(p); + + // drop the highest coefficient so #coeffs matches the original input + v2.coeffs = Arrays.copyOf(v2.coeffs, v2.coeffs.length - 1); + return new ModularResultant(new BigIntPolynomial(v2), BigInteger.valueOf(r), BigInteger.valueOf(p)); + } + + /** + * Computes <code>this-b*c*(x^k) mod p</code> and stores the result in this polynomial.<br/> + * See steps 4a,4b in EESS algorithm 2.2.7.1. + * + * @param b + * @param c + * @param k + * @param p + */ + private void multShiftSub(IntegerPolynomial b, int c, int k, int p) + { + int N = coeffs.length; + for (int i = k; i < N; i++) + { + coeffs[i] = (coeffs[i] - b.coeffs[i - k] * c) % p; + } + } + + /** + * Adds the squares of all coefficients. + * + * @return the sum of squares + */ + private BigInteger squareSum() + { + BigInteger sum = Constants.BIGINT_ZERO; + for (int i = 0; i < coeffs.length; i++) + { + sum = sum.add(BigInteger.valueOf(coeffs[i] * coeffs[i])); + } + return sum; + } + + /** + * Returns the degree of the polynomial + * + * @return the degree + */ + int degree() + { + int degree = coeffs.length - 1; + while (degree > 0 && coeffs[degree] == 0) + { + degree--; + } + return degree; + } + + /** + * Adds another polynomial which can have a different number of coefficients, + * and takes the coefficient values mod <code>modulus</code>. + * + * @param b another polynomial + */ + public void add(IntegerPolynomial b, int modulus) + { + add(b); + mod(modulus); + } + + /** + * Adds another polynomial which can have a different number of coefficients. + * + * @param b another polynomial + */ + public void add(IntegerPolynomial b) + { + if (b.coeffs.length > coeffs.length) + { + coeffs = Arrays.copyOf(coeffs, b.coeffs.length); + } + for (int i = 0; i < b.coeffs.length; i++) + { + coeffs[i] += b.coeffs[i]; + } + } + + /** + * Subtracts another polynomial which can have a different number of coefficients, + * and takes the coefficient values mod <code>modulus</code>. + * + * @param b another polynomial + */ + public void sub(IntegerPolynomial b, int modulus) + { + sub(b); + mod(modulus); + } + + /** + * Subtracts another polynomial which can have a different number of coefficients. + * + * @param b another polynomial + */ + public void sub(IntegerPolynomial b) + { + if (b.coeffs.length > coeffs.length) + { + coeffs = Arrays.copyOf(coeffs, b.coeffs.length); + } + for (int i = 0; i < b.coeffs.length; i++) + { + coeffs[i] -= b.coeffs[i]; + } + } + + /** + * Subtracts a <code>int</code> from each coefficient. Does not return a new polynomial but modifies this polynomial. + * + * @param b + */ + void sub(int b) + { + for (int i = 0; i < coeffs.length; i++) + { + coeffs[i] -= b; + } + } + + /** + * Multiplies each coefficient by a <code>int</code>. Does not return a new polynomial but modifies this polynomial. + * + * @param factor + */ + public void mult(int factor) + { + for (int i = 0; i < coeffs.length; i++) + { + coeffs[i] *= factor; + } + } + + /** + * Multiplies each coefficient by a 2 and applies a modulus. Does not return a new polynomial but modifies this polynomial. + * + * @param modulus a modulus + */ + private void mult2(int modulus) + { + for (int i = 0; i < coeffs.length; i++) + { + coeffs[i] *= 2; + coeffs[i] %= modulus; + } + } + + /** + * Multiplies each coefficient by a 2 and applies a modulus. Does not return a new polynomial but modifies this polynomial. + * + * @param modulus a modulus + */ + public void mult3(int modulus) + { + for (int i = 0; i < coeffs.length; i++) + { + coeffs[i] *= 3; + coeffs[i] %= modulus; + } + } + + /** + * Divides each coefficient by <code>k</code> and rounds to the nearest integer. Does not return a new polynomial but modifies this polynomial. + * + * @param k the divisor + */ + public void div(int k) + { + int k2 = (k + 1) / 2; + for (int i = 0; i < coeffs.length; i++) + { + coeffs[i] += coeffs[i] > 0 ? k2 : -k2; + coeffs[i] /= k; + } + } + + /** + * Takes each coefficient modulo 3 such that all coefficients are ternary. + */ + public void mod3() + { + for (int i = 0; i < coeffs.length; i++) + { + coeffs[i] %= 3; + if (coeffs[i] > 1) + { + coeffs[i] -= 3; + } + if (coeffs[i] < -1) + { + coeffs[i] += 3; + } + } + } + + /** + * Ensures all coefficients are between 0 and <code>modulus-1</code> + * + * @param modulus a modulus + */ + public void modPositive(int modulus) + { + mod(modulus); + ensurePositive(modulus); + } + + /** + * Reduces all coefficients to the interval [-modulus/2, modulus/2) + */ + void modCenter(int modulus) + { + mod(modulus); + for (int j = 0; j < coeffs.length; j++) + { + while (coeffs[j] < modulus / 2) + { + coeffs[j] += modulus; + } + while (coeffs[j] >= modulus / 2) + { + coeffs[j] -= modulus; + } + } + } + + /** + * Takes each coefficient modulo <code>modulus</code>. + */ + public void mod(int modulus) + { + for (int i = 0; i < coeffs.length; i++) + { + coeffs[i] %= modulus; + } + } + + /** + * Adds <code>modulus</code> until all coefficients are above 0. + * + * @param modulus a modulus + */ + public void ensurePositive(int modulus) + { + for (int i = 0; i < coeffs.length; i++) + { + while (coeffs[i] < 0) + { + coeffs[i] += modulus; + } + } + } + + /** + * Computes the centered euclidean norm of the polynomial. + * + * @param q a modulus + * @return the centered norm + */ + public long centeredNormSq(int q) + { + int N = coeffs.length; + IntegerPolynomial p = (IntegerPolynomial)clone(); + p.shiftGap(q); + + long sum = 0; + long sqSum = 0; + for (int i = 0; i != p.coeffs.length; i++) + { + int c = p.coeffs[i]; + sum += c; + sqSum += c * c; + } + + long centeredNormSq = sqSum - sum * sum / N; + return centeredNormSq; + } + + /** + * Shifts all coefficients so the largest gap is centered around <code>-q/2</code>. + * + * @param q a modulus + */ + void shiftGap(int q) + { + modCenter(q); + + int[] sorted = Arrays.clone(coeffs); + + sort(sorted); + + int maxrange = 0; + int maxrangeStart = 0; + for (int i = 0; i < sorted.length - 1; i++) + { + int range = sorted[i + 1] - sorted[i]; + if (range > maxrange) + { + maxrange = range; + maxrangeStart = sorted[i]; + } + } + + int pmin = sorted[0]; + int pmax = sorted[sorted.length - 1]; + + int j = q - pmax + pmin; + int shift; + if (j > maxrange) + { + shift = (pmax + pmin) / 2; + } + else + { + shift = maxrangeStart + maxrange / 2 + q / 2; + } + + sub(shift); + } + + private void sort(int[] ints) + { + boolean swap = true; + + while (swap) + { + swap = false; + for (int i = 0; i != ints.length - 1; i++) + { + if (ints[i] > ints[i+1]) + { + int tmp = ints[i]; + ints[i] = ints[i+1]; + ints[i+1] = tmp; + swap = true; + } + } + } + } + + /** + * Shifts the values of all coefficients to the interval <code>[-q/2, q/2]</code>. + * + * @param q a modulus + */ + public void center0(int q) + { + for (int i = 0; i < coeffs.length; i++) + { + while (coeffs[i] < -q / 2) + { + coeffs[i] += q; + } + while (coeffs[i] > q / 2) + { + coeffs[i] -= q; + } + } + } + + /** + * Returns the sum of all coefficients, i.e. evaluates the polynomial at 0. + * + * @return the sum of all coefficients + */ + public int sumCoeffs() + { + int sum = 0; + for (int i = 0; i < coeffs.length; i++) + { + sum += coeffs[i]; + } + return sum; + } + + /** + * Tests if <code>p(x) = 0</code>. + * + * @return true iff all coefficients are zeros + */ + private boolean equalsZero() + { + for (int i = 0; i < coeffs.length; i++) + { + if (coeffs[i] != 0) + { + return false; + } + } + return true; + } + + /** + * Tests if <code>p(x) = 1</code>. + * + * @return true iff all coefficients are equal to zero, except for the lowest coefficient which must equal 1 + */ + public boolean equalsOne() + { + for (int i = 1; i < coeffs.length; i++) + { + if (coeffs[i] != 0) + { + return false; + } + } + return coeffs[0] == 1; + } + + /** + * Tests if <code>|p(x)| = 1</code>. + * + * @return true iff all coefficients are equal to zero, except for the lowest coefficient which must equal 1 or -1 + */ + private boolean equalsAbsOne() + { + for (int i = 1; i < coeffs.length; i++) + { + if (coeffs[i] != 0) + { + return false; + } + } + return Math.abs(coeffs[0]) == 1; + } + + /** + * Counts the number of coefficients equal to an integer + * + * @param value an integer + * @return the number of coefficients equal to <code>value</code> + */ + public int count(int value) + { + int count = 0; + for (int i = 0; i != coeffs.length; i++) + { + if (coeffs[i] == value) + { + count++; + } + } + return count; + } + + /** + * Multiplication by <code>X</code> in <code>Z[X]/Z[X^n-1]</code>. + */ + public void rotate1() + { + int clast = coeffs[coeffs.length - 1]; + for (int i = coeffs.length - 1; i > 0; i--) + { + coeffs[i] = coeffs[i - 1]; + } + coeffs[0] = clast; + } + + public void clear() + { + for (int i = 0; i < coeffs.length; i++) + { + coeffs[i] = 0; + } + } + + public IntegerPolynomial toIntegerPolynomial() + { + return (IntegerPolynomial)clone(); + } + + public Object clone() + { + return new IntegerPolynomial(coeffs.clone()); + } + + public boolean equals(Object obj) + { + if (obj instanceof IntegerPolynomial) + { + return Arrays.areEqual(coeffs, ((IntegerPolynomial)obj).coeffs); + } + else + { + return false; + } + } + + /** + * Calls {@link IntegerPolynomial#resultant(int) + */ + private class ModResultantTask + implements Callable<ModularResultant> + { + private int modulus; + + private ModResultantTask(int modulus) + { + this.modulus = modulus; + } + + public ModularResultant call() + { + return resultant(modulus); + } + } + + /** + * Calls {@link ModularResultant#combineRho(ModularResultant, ModularResultant) + */ + private class CombineTask + implements Callable<ModularResultant> + { + private ModularResultant modRes1; + private ModularResultant modRes2; + + private CombineTask(ModularResultant modRes1, ModularResultant modRes2) + { + this.modRes1 = modRes1; + this.modRes2 = modRes2; + } + + public ModularResultant call() + { + return ModularResultant.combineRho(modRes1, modRes2); + } + } +} diff --git a/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/LongPolynomial2.java b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/LongPolynomial2.java new file mode 100644 index 00000000..513cac50 --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/LongPolynomial2.java @@ -0,0 +1,255 @@ +package org.spongycastle.pqc.math.ntru.polynomial; + +import org.spongycastle.util.Arrays; + +/** + * A polynomial class that combines two coefficients into one <code>long</code> value for + * faster multiplication in 64 bit environments.<br> + * Coefficients can be between 0 and 2047 and are stored in pairs in the bits 0..10 and 24..34 of a <code>long</code> number. + */ +public class LongPolynomial2 +{ + private long[] coeffs; // each representing two coefficients in the original IntegerPolynomial + private int numCoeffs; + + /** + * Constructs a <code>LongPolynomial2</code> from a <code>IntegerPolynomial</code>. The two polynomials are independent of each other. + * + * @param p the original polynomial. Coefficients must be between 0 and 2047. + */ + public LongPolynomial2(IntegerPolynomial p) + { + numCoeffs = p.coeffs.length; + coeffs = new long[(numCoeffs + 1) / 2]; + int idx = 0; + for (int pIdx = 0; pIdx < numCoeffs; ) + { + int c0 = p.coeffs[pIdx++]; + while (c0 < 0) + { + c0 += 2048; + } + long c1 = pIdx < numCoeffs ? p.coeffs[pIdx++] : 0; + while (c1 < 0) + { + c1 += 2048; + } + coeffs[idx] = c0 + (c1 << 24); + idx++; + } + } + + private LongPolynomial2(long[] coeffs) + { + this.coeffs = coeffs; + } + + private LongPolynomial2(int N) + { + coeffs = new long[N]; + } + + /** + * Multiplies the polynomial with another, taking the indices mod N and the values mod 2048. + */ + public LongPolynomial2 mult(LongPolynomial2 poly2) + { + int N = coeffs.length; + if (poly2.coeffs.length != N || numCoeffs != poly2.numCoeffs) + { + throw new IllegalArgumentException("Number of coefficients must be the same"); + } + + LongPolynomial2 c = multRecursive(poly2); + + if (c.coeffs.length > N) + { + if (numCoeffs % 2 == 0) + { + for (int k = N; k < c.coeffs.length; k++) + { + c.coeffs[k - N] = (c.coeffs[k - N] + c.coeffs[k]) & 0x7FF0007FFL; + } + c.coeffs = Arrays.copyOf(c.coeffs, N); + } + else + { + for (int k = N; k < c.coeffs.length; k++) + { + c.coeffs[k - N] = c.coeffs[k - N] + (c.coeffs[k - 1] >> 24); + c.coeffs[k - N] = c.coeffs[k - N] + ((c.coeffs[k] & 2047) << 24); + c.coeffs[k - N] &= 0x7FF0007FFL; + } + c.coeffs = Arrays.copyOf(c.coeffs, N); + c.coeffs[c.coeffs.length - 1] &= 2047; + } + } + + c = new LongPolynomial2(c.coeffs); + c.numCoeffs = numCoeffs; + return c; + } + + public IntegerPolynomial toIntegerPolynomial() + { + int[] intCoeffs = new int[numCoeffs]; + int uIdx = 0; + for (int i = 0; i < coeffs.length; i++) + { + intCoeffs[uIdx++] = (int)(coeffs[i] & 2047); + if (uIdx < numCoeffs) + { + intCoeffs[uIdx++] = (int)((coeffs[i] >> 24) & 2047); + } + } + return new IntegerPolynomial(intCoeffs); + } + + /** + * Karazuba multiplication + */ + private LongPolynomial2 multRecursive(LongPolynomial2 poly2) + { + long[] a = coeffs; + long[] b = poly2.coeffs; + + int n = poly2.coeffs.length; + if (n <= 32) + { + int cn = 2 * n; + LongPolynomial2 c = new LongPolynomial2(new long[cn]); + for (int k = 0; k < cn; k++) + { + for (int i = Math.max(0, k - n + 1); i <= Math.min(k, n - 1); i++) + { + long c0 = a[k - i] * b[i]; + long cu = c0 & 0x7FF000000L + (c0 & 2047); + long co = (c0 >>> 48) & 2047; + + c.coeffs[k] = (c.coeffs[k] + cu) & 0x7FF0007FFL; + c.coeffs[k + 1] = (c.coeffs[k + 1] + co) & 0x7FF0007FFL; + } + } + return c; + } + else + { + int n1 = n / 2; + + LongPolynomial2 a1 = new LongPolynomial2(Arrays.copyOf(a, n1)); + LongPolynomial2 a2 = new LongPolynomial2(Arrays.copyOfRange(a, n1, n)); + LongPolynomial2 b1 = new LongPolynomial2(Arrays.copyOf(b, n1)); + LongPolynomial2 b2 = new LongPolynomial2(Arrays.copyOfRange(b, n1, n)); + + LongPolynomial2 A = (LongPolynomial2)a1.clone(); + A.add(a2); + LongPolynomial2 B = (LongPolynomial2)b1.clone(); + B.add(b2); + + LongPolynomial2 c1 = a1.multRecursive(b1); + LongPolynomial2 c2 = a2.multRecursive(b2); + LongPolynomial2 c3 = A.multRecursive(B); + c3.sub(c1); + c3.sub(c2); + + LongPolynomial2 c = new LongPolynomial2(2 * n); + for (int i = 0; i < c1.coeffs.length; i++) + { + c.coeffs[i] = c1.coeffs[i] & 0x7FF0007FFL; + } + for (int i = 0; i < c3.coeffs.length; i++) + { + c.coeffs[n1 + i] = (c.coeffs[n1 + i] + c3.coeffs[i]) & 0x7FF0007FFL; + } + for (int i = 0; i < c2.coeffs.length; i++) + { + c.coeffs[2 * n1 + i] = (c.coeffs[2 * n1 + i] + c2.coeffs[i]) & 0x7FF0007FFL; + } + return c; + } + } + + /** + * Adds another polynomial which can have a different number of coefficients. + * + * @param b another polynomial + */ + private void add(LongPolynomial2 b) + { + if (b.coeffs.length > coeffs.length) + { + coeffs = Arrays.copyOf(coeffs, b.coeffs.length); + } + for (int i = 0; i < b.coeffs.length; i++) + { + coeffs[i] = (coeffs[i] + b.coeffs[i]) & 0x7FF0007FFL; + } + } + + /** + * Subtracts another polynomial which can have a different number of coefficients. + * + * @param b another polynomial + */ + private void sub(LongPolynomial2 b) + { + if (b.coeffs.length > coeffs.length) + { + coeffs = Arrays.copyOf(coeffs, b.coeffs.length); + } + for (int i = 0; i < b.coeffs.length; i++) + { + coeffs[i] = (0x0800000800000L + coeffs[i] - b.coeffs[i]) & 0x7FF0007FFL; + } + } + + /** + * Subtracts another polynomial which must have the same number of coefficients, + * and applies an AND mask to the upper and lower halves of each coefficients. + * + * @param b another polynomial + * @param mask a bit mask less than 2048 to apply to each 11-bit coefficient + */ + public void subAnd(LongPolynomial2 b, int mask) + { + long longMask = (((long)mask) << 24) + mask; + for (int i = 0; i < b.coeffs.length; i++) + { + coeffs[i] = (0x0800000800000L + coeffs[i] - b.coeffs[i]) & longMask; + } + } + + /** + * Multiplies this polynomial by 2 and applies an AND mask to the upper and + * lower halves of each coefficients. + * + * @param mask a bit mask less than 2048 to apply to each 11-bit coefficient + */ + public void mult2And(int mask) + { + long longMask = (((long)mask) << 24) + mask; + for (int i = 0; i < coeffs.length; i++) + { + coeffs[i] = (coeffs[i] << 1) & longMask; + } + } + + public Object clone() + { + LongPolynomial2 p = new LongPolynomial2(coeffs.clone()); + p.numCoeffs = numCoeffs; + return p; + } + + public boolean equals(Object obj) + { + if (obj instanceof LongPolynomial2) + { + return Arrays.areEqual(coeffs, ((LongPolynomial2)obj).coeffs); + } + else + { + return false; + } + } +} diff --git a/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/LongPolynomial5.java b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/LongPolynomial5.java new file mode 100644 index 00000000..f8764c68 --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/LongPolynomial5.java @@ -0,0 +1,149 @@ +package org.spongycastle.pqc.math.ntru.polynomial; + +import org.spongycastle.util.Arrays; + +/** + * A polynomial class that combines five coefficients into one <code>long</code> value for + * faster multiplication by a ternary polynomial.<br> + * Coefficients can be between 0 and 2047 and are stored in bits 0..11, 12..23, ..., 48..59 of a <code>long</code> number. + */ +public class LongPolynomial5 +{ + private long[] coeffs; // groups of 5 coefficients + private int numCoeffs; + + /** + * Constructs a <code>LongPolynomial5</code> from a <code>IntegerPolynomial</code>. The two polynomials are independent of each other. + * + * @param p the original polynomial. Coefficients must be between 0 and 2047. + */ + public LongPolynomial5(IntegerPolynomial p) + { + numCoeffs = p.coeffs.length; + + coeffs = new long[(numCoeffs + 4) / 5]; + int cIdx = 0; + int shift = 0; + for (int i = 0; i < numCoeffs; i++) + { + coeffs[cIdx] |= ((long)p.coeffs[i]) << shift; + shift += 12; + if (shift >= 60) + { + shift = 0; + cIdx++; + } + } + } + + private LongPolynomial5(long[] coeffs, int numCoeffs) + { + this.coeffs = coeffs; + this.numCoeffs = numCoeffs; + } + + /** + * Multiplies the polynomial with a <code>TernaryPolynomial</code>, taking the indices mod N and the values mod 2048. + */ + public LongPolynomial5 mult(TernaryPolynomial poly2) + { + long[][] prod = new long[5][coeffs.length + (poly2.size() + 4) / 5 - 1]; // intermediate results, the subarrays are shifted by 0,...,4 coefficients + + // multiply ones + int[] ones = poly2.getOnes(); + for (int idx = 0; idx != ones.length; idx++) + { + int pIdx = ones[idx]; + int cIdx = pIdx / 5; + int m = pIdx - cIdx * 5; // m = pIdx % 5 + for (int i = 0; i < coeffs.length; i++) + { + prod[m][cIdx] = (prod[m][cIdx] + coeffs[i]) & 0x7FF7FF7FF7FF7FFL; + cIdx++; + } + } + + // multiply negative ones + int[] negOnes = poly2.getNegOnes(); + for (int idx = 0; idx != negOnes.length; idx++) + { + int pIdx = negOnes[idx]; + int cIdx = pIdx / 5; + int m = pIdx - cIdx * 5; // m = pIdx % 5 + for (int i = 0; i < coeffs.length; i++) + { + prod[m][cIdx] = (0x800800800800800L + prod[m][cIdx] - coeffs[i]) & 0x7FF7FF7FF7FF7FFL; + cIdx++; + } + } + + // combine shifted coefficients (5 arrays) into a single array of length prod[*].length+1 + long[] cCoeffs = Arrays.copyOf(prod[0], prod[0].length + 1); + for (int m = 1; m <= 4; m++) + { + int shift = m * 12; + int shift60 = 60 - shift; + long mask = (1L << shift60) - 1; + int pLen = prod[m].length; + for (int i = 0; i < pLen; i++) + { + long upper, lower; + upper = prod[m][i] >> shift60; + lower = prod[m][i] & mask; + + cCoeffs[i] = (cCoeffs[i] + (lower << shift)) & 0x7FF7FF7FF7FF7FFL; + int nextIdx = i + 1; + cCoeffs[nextIdx] = (cCoeffs[nextIdx] + upper) & 0x7FF7FF7FF7FF7FFL; + } + } + + // reduce indices of cCoeffs modulo numCoeffs + int shift = 12 * (numCoeffs % 5); + for (int cIdx = coeffs.length - 1; cIdx < cCoeffs.length; cIdx++) + { + long iCoeff; // coefficient to shift into the [0..numCoeffs-1] range + int newIdx; + if (cIdx == coeffs.length - 1) + { + iCoeff = numCoeffs == 5 ? 0 : cCoeffs[cIdx] >> shift; + newIdx = 0; + } + else + { + iCoeff = cCoeffs[cIdx]; + newIdx = cIdx * 5 - numCoeffs; + } + + int base = newIdx / 5; + int m = newIdx - base * 5; // m = newIdx % 5 + long lower = iCoeff << (12 * m); + long upper = iCoeff >> (12 * (5 - m)); + cCoeffs[base] = (cCoeffs[base] + lower) & 0x7FF7FF7FF7FF7FFL; + int base1 = base + 1; + if (base1 < coeffs.length) + { + cCoeffs[base1] = (cCoeffs[base1] + upper) & 0x7FF7FF7FF7FF7FFL; + } + } + + return new LongPolynomial5(cCoeffs, numCoeffs); + } + + public IntegerPolynomial toIntegerPolynomial() + { + int[] intCoeffs = new int[numCoeffs]; + int cIdx = 0; + int shift = 0; + for (int i = 0; i < numCoeffs; i++) + { + intCoeffs[i] = (int)((coeffs[cIdx] >> shift) & 2047); + shift += 12; + if (shift >= 60) + { + shift = 0; + cIdx++; + } + } + return new IntegerPolynomial(intCoeffs); + } +} diff --git a/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/ModularResultant.java b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/ModularResultant.java new file mode 100644 index 00000000..7e8031fe --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/ModularResultant.java @@ -0,0 +1,46 @@ +package org.spongycastle.pqc.math.ntru.polynomial; + +import java.math.BigInteger; + +import org.spongycastle.pqc.math.ntru.euclid.BigIntEuclidean; + +/** + * A resultant modulo a <code>BigInteger</code> + */ +public class ModularResultant + extends Resultant +{ + BigInteger modulus; + + ModularResultant(BigIntPolynomial rho, BigInteger res, BigInteger modulus) + { + super(rho, res); + this.modulus = modulus; + } + + /** + * Calculates a <code>rho</code> modulo <code>m1*m2</code> from + * two resultants whose <code>rho</code>s are modulo <code>m1</code> and <code>m2</code>.<br/> + * </code>res</code> is set to <code>null</code>. + * + * @param modRes1 + * @param modRes2 + * @return <code>rho</code> modulo <code>modRes1.modulus * modRes2.modulus</code>, and <code>null</code> for </code>res</code>. + */ + static ModularResultant combineRho(ModularResultant modRes1, ModularResultant modRes2) + { + BigInteger mod1 = modRes1.modulus; + BigInteger mod2 = modRes2.modulus; + BigInteger prod = mod1.multiply(mod2); + BigIntEuclidean er = BigIntEuclidean.calculate(mod2, mod1); + + BigIntPolynomial rho1 = (BigIntPolynomial)modRes1.rho.clone(); + rho1.mult(er.x.multiply(mod2)); + BigIntPolynomial rho2 = (BigIntPolynomial)modRes2.rho.clone(); + rho2.mult(er.y.multiply(mod1)); + rho1.add(rho2); + rho1.mod(prod); + + return new ModularResultant(rho1, null, prod); + } +} diff --git a/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/Polynomial.java b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/Polynomial.java new file mode 100644 index 00000000..1d1f1dfb --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/Polynomial.java @@ -0,0 +1,42 @@ +package org.spongycastle.pqc.math.ntru.polynomial; + +public interface Polynomial +{ + + /** + * Multiplies the polynomial by an <code>IntegerPolynomial</code>, + * taking the indices mod <code>N</code>. + * + * @param poly2 a polynomial + * @return the product of the two polynomials + */ + IntegerPolynomial mult(IntegerPolynomial poly2); + + /** + * Multiplies the polynomial by an <code>IntegerPolynomial</code>, + * taking the coefficient values mod <code>modulus</code> and the indices mod <code>N</code>. + * + * @param poly2 a polynomial + * @param modulus a modulus to apply + * @return the product of the two polynomials + */ + IntegerPolynomial mult(IntegerPolynomial poly2, int modulus); + + /** + * Returns a polynomial that is equal to this polynomial (in the sense that {@link #mult(IntegerPolynomial, int)} + * returns equal <code>IntegerPolynomial</code>s). The new polynomial is guaranteed to be independent of the original. + * + * @return a new <code>IntegerPolynomial</code>. + */ + IntegerPolynomial toIntegerPolynomial(); + + /** + * Multiplies the polynomial by a <code>BigIntPolynomial</code>, taking the indices mod N. Does not + * change this polynomial but returns the result as a new polynomial.<br> + * Both polynomials must have the same number of coefficients. + * + * @param poly2 the polynomial to multiply by + * @return a new polynomial + */ + BigIntPolynomial mult(BigIntPolynomial poly2); +} diff --git a/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/ProductFormPolynomial.java b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/ProductFormPolynomial.java new file mode 100644 index 00000000..e60ce8b8 --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/ProductFormPolynomial.java @@ -0,0 +1,153 @@ +package org.spongycastle.pqc.math.ntru.polynomial; + +import java.io.ByteArrayInputStream; +import java.io.IOException; +import java.io.InputStream; +import java.security.SecureRandom; + +import org.spongycastle.util.Arrays; + +/** + * A polynomial of the form <code>f1*f2+f3</code>, where + * <code>f1,f2,f3</code> are very sparsely populated ternary polynomials. + */ +public class ProductFormPolynomial + implements Polynomial +{ + private SparseTernaryPolynomial f1, f2, f3; + + public ProductFormPolynomial(SparseTernaryPolynomial f1, SparseTernaryPolynomial f2, SparseTernaryPolynomial f3) + { + this.f1 = f1; + this.f2 = f2; + this.f3 = f3; + } + + public static ProductFormPolynomial generateRandom(int N, int df1, int df2, int df3Ones, int df3NegOnes, SecureRandom random) + { + SparseTernaryPolynomial f1 = SparseTernaryPolynomial.generateRandom(N, df1, df1, random); + SparseTernaryPolynomial f2 = SparseTernaryPolynomial.generateRandom(N, df2, df2, random); + SparseTernaryPolynomial f3 = SparseTernaryPolynomial.generateRandom(N, df3Ones, df3NegOnes, random); + return new ProductFormPolynomial(f1, f2, f3); + } + + public static ProductFormPolynomial fromBinary(byte[] data, int N, int df1, int df2, int df3Ones, int df3NegOnes) + throws IOException + { + return fromBinary(new ByteArrayInputStream(data), N, df1, df2, df3Ones, df3NegOnes); + } + + public static ProductFormPolynomial fromBinary(InputStream is, int N, int df1, int df2, int df3Ones, int df3NegOnes) + throws IOException + { + SparseTernaryPolynomial f1; + + f1 = SparseTernaryPolynomial.fromBinary(is, N, df1, df1); + SparseTernaryPolynomial f2 = SparseTernaryPolynomial.fromBinary(is, N, df2, df2); + SparseTernaryPolynomial f3 = SparseTernaryPolynomial.fromBinary(is, N, df3Ones, df3NegOnes); + return new ProductFormPolynomial(f1, f2, f3); + } + + public byte[] toBinary() + { + byte[] f1Bin = f1.toBinary(); + byte[] f2Bin = f2.toBinary(); + byte[] f3Bin = f3.toBinary(); + + byte[] all = Arrays.copyOf(f1Bin, f1Bin.length + f2Bin.length + f3Bin.length); + System.arraycopy(f2Bin, 0, all, f1Bin.length, f2Bin.length); + System.arraycopy(f3Bin, 0, all, f1Bin.length + f2Bin.length, f3Bin.length); + return all; + } + + public IntegerPolynomial mult(IntegerPolynomial b) + { + IntegerPolynomial c = f1.mult(b); + c = f2.mult(c); + c.add(f3.mult(b)); + return c; + } + + public BigIntPolynomial mult(BigIntPolynomial b) + { + BigIntPolynomial c = f1.mult(b); + c = f2.mult(c); + c.add(f3.mult(b)); + return c; + } + + public IntegerPolynomial toIntegerPolynomial() + { + IntegerPolynomial i = f1.mult(f2.toIntegerPolynomial()); + i.add(f3.toIntegerPolynomial()); + return i; + } + + public IntegerPolynomial mult(IntegerPolynomial poly2, int modulus) + { + IntegerPolynomial c = mult(poly2); + c.mod(modulus); + return c; + } + + public int hashCode() + { + final int prime = 31; + int result = 1; + result = prime * result + ((f1 == null) ? 0 : f1.hashCode()); + result = prime * result + ((f2 == null) ? 0 : f2.hashCode()); + result = prime * result + ((f3 == null) ? 0 : f3.hashCode()); + return result; + } + + public boolean equals(Object obj) + { + if (this == obj) + { + return true; + } + if (obj == null) + { + return false; + } + if (getClass() != obj.getClass()) + { + return false; + } + ProductFormPolynomial other = (ProductFormPolynomial)obj; + if (f1 == null) + { + if (other.f1 != null) + { + return false; + } + } + else if (!f1.equals(other.f1)) + { + return false; + } + if (f2 == null) + { + if (other.f2 != null) + { + return false; + } + } + else if (!f2.equals(other.f2)) + { + return false; + } + if (f3 == null) + { + if (other.f3 != null) + { + return false; + } + } + else if (!f3.equals(other.f3)) + { + return false; + } + return true; + } +} diff --git a/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/Resultant.java b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/Resultant.java new file mode 100644 index 00000000..8fa13328 --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/Resultant.java @@ -0,0 +1,28 @@ +package org.spongycastle.pqc.math.ntru.polynomial; + +import java.math.BigInteger; + +/** + * Contains a resultant and a polynomial <code>rho</code> such that + * <code>res = rho*this + t*(x^n-1) for some integer t</code>. + * + * @see IntegerPolynomial#resultant() + * @see IntegerPolynomial#resultant(int) + */ +public class Resultant +{ + /** + * A polynomial such that <code>res = rho*this + t*(x^n-1) for some integer t</code> + */ + public BigIntPolynomial rho; + /** + * Resultant of a polynomial with <code>x^n-1</code> + */ + public BigInteger res; + + Resultant(BigIntPolynomial rho, BigInteger res) + { + this.rho = rho; + this.res = res; + } +} diff --git a/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/SparseTernaryPolynomial.java b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/SparseTernaryPolynomial.java new file mode 100644 index 00000000..2fbd70a4 --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/SparseTernaryPolynomial.java @@ -0,0 +1,320 @@ +package org.spongycastle.pqc.math.ntru.polynomial; + +import java.io.IOException; +import java.io.InputStream; +import java.math.BigInteger; +import java.security.SecureRandom; + +import org.spongycastle.pqc.math.ntru.util.ArrayEncoder; +import org.spongycastle.pqc.math.ntru.util.Util; +import org.spongycastle.util.Arrays; + +/** + * A <code>TernaryPolynomial</code> with a "low" number of nonzero coefficients. + */ +public class SparseTernaryPolynomial + implements TernaryPolynomial +{ + /** + * Number of bits to use for each coefficient. Determines the upper bound for <code>N</code>. + */ + private static final int BITS_PER_INDEX = 11; + + private int N; + private int[] ones; + private int[] negOnes; + + /** + * Constructs a new polynomial. + * + * @param N total number of coefficients including zeros + * @param ones indices of coefficients equal to 1 + * @param negOnes indices of coefficients equal to -1 + */ + SparseTernaryPolynomial(int N, int[] ones, int[] negOnes) + { + this.N = N; + this.ones = ones; + this.negOnes = negOnes; + } + + /** + * Constructs a <code>DenseTernaryPolynomial</code> from a <code>IntegerPolynomial</code>. The two polynomials are + * independent of each other. + * + * @param intPoly the original polynomial + */ + public SparseTernaryPolynomial(IntegerPolynomial intPoly) + { + this(intPoly.coeffs); + } + + /** + * Constructs a new <code>SparseTernaryPolynomial</code> with a given set of coefficients. + * + * @param coeffs the coefficients + */ + public SparseTernaryPolynomial(int[] coeffs) + { + N = coeffs.length; + ones = new int[N]; + negOnes = new int[N]; + int onesIdx = 0; + int negOnesIdx = 0; + for (int i = 0; i < N; i++) + { + int c = coeffs[i]; + switch (c) + { + case 1: + ones[onesIdx++] = i; + break; + case -1: + negOnes[negOnesIdx++] = i; + break; + case 0: + break; + default: + throw new IllegalArgumentException("Illegal value: " + c + ", must be one of {-1, 0, 1}"); + } + } + ones = Arrays.copyOf(ones, onesIdx); + negOnes = Arrays.copyOf(negOnes, negOnesIdx); + } + + /** + * Decodes a byte array encoded with {@link #toBinary()} to a ploynomial. + * + * @param is an input stream containing an encoded polynomial + * @param N number of coefficients including zeros + * @param numOnes number of coefficients equal to 1 + * @param numNegOnes number of coefficients equal to -1 + * @return the decoded polynomial + * @throws IOException + */ + public static SparseTernaryPolynomial fromBinary(InputStream is, int N, int numOnes, int numNegOnes) + throws IOException + { + int maxIndex = 1 << BITS_PER_INDEX; + int bitsPerIndex = 32 - Integer.numberOfLeadingZeros(maxIndex - 1); + + int data1Len = (numOnes * bitsPerIndex + 7) / 8; + byte[] data1 = Util.readFullLength(is, data1Len); + int[] ones = ArrayEncoder.decodeModQ(data1, numOnes, maxIndex); + + int data2Len = (numNegOnes * bitsPerIndex + 7) / 8; + byte[] data2 = Util.readFullLength(is, data2Len); + int[] negOnes = ArrayEncoder.decodeModQ(data2, numNegOnes, maxIndex); + + return new SparseTernaryPolynomial(N, ones, negOnes); + } + + /** + * Generates a random polynomial with <code>numOnes</code> coefficients equal to 1, + * <code>numNegOnes</code> coefficients equal to -1, and the rest equal to 0. + * + * @param N number of coefficients + * @param numOnes number of 1's + * @param numNegOnes number of -1's + */ + public static SparseTernaryPolynomial generateRandom(int N, int numOnes, int numNegOnes, SecureRandom random) + { + int[] coeffs = Util.generateRandomTernary(N, numOnes, numNegOnes, random); + return new SparseTernaryPolynomial(coeffs); + } + + public IntegerPolynomial mult(IntegerPolynomial poly2) + { + int[] b = poly2.coeffs; + if (b.length != N) + { + throw new IllegalArgumentException("Number of coefficients must be the same"); + } + + int[] c = new int[N]; + for (int idx = 0; idx != ones.length; idx++) + { + int i = ones[idx]; + int j = N - 1 - i; + for (int k = N - 1; k >= 0; k--) + { + c[k] += b[j]; + j--; + if (j < 0) + { + j = N - 1; + } + } + } + + for (int idx = 0; idx != negOnes.length; idx++) + { + int i = negOnes[idx]; + int j = N - 1 - i; + for (int k = N - 1; k >= 0; k--) + { + c[k] -= b[j]; + j--; + if (j < 0) + { + j = N - 1; + } + } + } + + return new IntegerPolynomial(c); + } + + public IntegerPolynomial mult(IntegerPolynomial poly2, int modulus) + { + IntegerPolynomial c = mult(poly2); + c.mod(modulus); + return c; + } + + public BigIntPolynomial mult(BigIntPolynomial poly2) + { + BigInteger[] b = poly2.coeffs; + if (b.length != N) + { + throw new IllegalArgumentException("Number of coefficients must be the same"); + } + + BigInteger[] c = new BigInteger[N]; + for (int i = 0; i < N; i++) + { + c[i] = BigInteger.ZERO; + } + + for (int idx = 0; idx != ones.length; idx++) + { + int i = ones[idx]; + int j = N - 1 - i; + for (int k = N - 1; k >= 0; k--) + { + c[k] = c[k].add(b[j]); + j--; + if (j < 0) + { + j = N - 1; + } + } + } + + for (int idx = 0; idx != negOnes.length; idx++) + { + int i = negOnes[idx]; + int j = N - 1 - i; + for (int k = N - 1; k >= 0; k--) + { + c[k] = c[k].subtract(b[j]); + j--; + if (j < 0) + { + j = N - 1; + } + } + } + + return new BigIntPolynomial(c); + } + + public int[] getOnes() + { + return ones; + } + + public int[] getNegOnes() + { + return negOnes; + } + + /** + * Encodes the polynomial to a byte array writing <code>BITS_PER_INDEX</code> bits for each coefficient. + * + * @return the encoded polynomial + */ + public byte[] toBinary() + { + int maxIndex = 1 << BITS_PER_INDEX; + byte[] bin1 = ArrayEncoder.encodeModQ(ones, maxIndex); + byte[] bin2 = ArrayEncoder.encodeModQ(negOnes, maxIndex); + + byte[] bin = Arrays.copyOf(bin1, bin1.length + bin2.length); + System.arraycopy(bin2, 0, bin, bin1.length, bin2.length); + return bin; + } + + public IntegerPolynomial toIntegerPolynomial() + { + int[] coeffs = new int[N]; + for (int idx = 0; idx != ones.length; idx++) + { + int i = ones[idx]; + coeffs[i] = 1; + } + for (int idx = 0; idx != negOnes.length; idx++) + { + int i = negOnes[idx]; + coeffs[i] = -1; + } + return new IntegerPolynomial(coeffs); + } + + public int size() + { + return N; + } + + public void clear() + { + for (int i = 0; i < ones.length; i++) + { + ones[i] = 0; + } + for (int i = 0; i < negOnes.length; i++) + { + negOnes[i] = 0; + } + } + + public int hashCode() + { + final int prime = 31; + int result = 1; + result = prime * result + N; + result = prime * result + Arrays.hashCode(negOnes); + result = prime * result + Arrays.hashCode(ones); + return result; + } + + public boolean equals(Object obj) + { + if (this == obj) + { + return true; + } + if (obj == null) + { + return false; + } + if (getClass() != obj.getClass()) + { + return false; + } + SparseTernaryPolynomial other = (SparseTernaryPolynomial)obj; + if (N != other.N) + { + return false; + } + if (!Arrays.areEqual(negOnes, other.negOnes)) + { + return false; + } + if (!Arrays.areEqual(ones, other.ones)) + { + return false; + } + return true; + } +} diff --git a/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/TernaryPolynomial.java b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/TernaryPolynomial.java new file mode 100644 index 00000000..6b9530b3 --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/math/ntru/polynomial/TernaryPolynomial.java @@ -0,0 +1,25 @@ +package org.spongycastle.pqc.math.ntru.polynomial; + +/** + * A polynomial whose coefficients are all equal to -1, 0, or 1 + */ +public interface TernaryPolynomial + extends Polynomial +{ + + /** + * Multiplies the polynomial by an <code>IntegerPolynomial</code>, taking the indices mod N + */ + IntegerPolynomial mult(IntegerPolynomial poly2); + + int[] getOnes(); + + int[] getNegOnes(); + + /** + * Returns the maximum number of coefficients the polynomial can have + */ + int size(); + + void clear(); +} diff --git a/core/src/main/java/org/spongycastle/pqc/math/ntru/util/ArrayEncoder.java b/core/src/main/java/org/spongycastle/pqc/math/ntru/util/ArrayEncoder.java new file mode 100644 index 00000000..c4888cfc --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/math/ntru/util/ArrayEncoder.java @@ -0,0 +1,292 @@ +package org.spongycastle.pqc.math.ntru.util; + +import java.io.IOException; +import java.io.InputStream; +import java.math.BigInteger; + +import org.spongycastle.util.Arrays; + +/** + * Converts a coefficient array to a compact byte array and vice versa. + */ +public class ArrayEncoder +{ + /** + * Bit string to coefficient conversion table from P1363.1. Also found at + * {@link http://stackoverflow.com/questions/1562548/how-to-make-a-message-into-a-polynomial} + * <p/> + * Convert each three-bit quantity to two ternary coefficients as follows, and concatenate the resulting + * ternary quantities to obtain [the output]. + * <p/> + * <code> + * {0, 0, 0} -> {0, 0}<br/> + * {0, 0, 1} -> {0, 1}<br/> + * {0, 1, 0} -> {0, -1}<br/> + * {0, 1, 1} -> {1, 0}<br/> + * {1, 0, 0} -> {1, 1}<br/> + * {1, 0, 1} -> {1, -1}<br/> + * {1, 1, 0} -> {-1, 0}<br/> + * {1, 1, 1} -> {-1, 1}<br/> + * </code> + */ + private static final int[] COEFF1_TABLE = {0, 0, 0, 1, 1, 1, -1, -1}; + private static final int[] COEFF2_TABLE = {0, 1, -1, 0, 1, -1, 0, 1}; + /** + * Coefficient to bit string conversion table from P1363.1. Also found at + * {@link http://stackoverflow.com/questions/1562548/how-to-make-a-message-into-a-polynomial} + * <p/> + * Convert each set of two ternary coefficients to three bits as follows, and concatenate the resulting bit + * quantities to obtain [the output]: + * <p/> + * <code> + * {-1, -1} -> set "fail" to 1 and set bit string to {1, 1, 1} + * {-1, 0} -> {1, 1, 0}<br/> + * {-1, 1} -> {1, 1, 1}<br/> + * {0, -1} -> {0, 1, 0}<br/> + * {0, 0} -> {0, 0, 0}<br/> + * {0, 1} -> {0, 0, 1}<br/> + * {1, -1} -> {1, 0, 1}<br/> + * {1, 0} -> {0, 1, 1}<br/> + * {1, 1} -> {1, 0, 0}<br/> + * </code> + */ + private static final int[] BIT1_TABLE = {1, 1, 1, 0, 0, 0, 1, 0, 1}; + private static final int[] BIT2_TABLE = {1, 1, 1, 1, 0, 0, 0, 1, 0}; + private static final int[] BIT3_TABLE = {1, 0, 1, 0, 0, 1, 1, 1, 0}; + + /** + * Encodes an int array whose elements are between 0 and <code>q</code>, + * to a byte array leaving no gaps between bits.<br> + * <code>q</code> must be a power of 2. + * + * @param a the input array + * @param q the modulus + * @return the encoded array + */ + public static byte[] encodeModQ(int[] a, int q) + { + int bitsPerCoeff = 31 - Integer.numberOfLeadingZeros(q); + int numBits = a.length * bitsPerCoeff; + int numBytes = (numBits + 7) / 8; + byte[] data = new byte[numBytes]; + int bitIndex = 0; + int byteIndex = 0; + for (int i = 0; i < a.length; i++) + { + for (int j = 0; j < bitsPerCoeff; j++) + { + int currentBit = (a[i] >> j) & 1; + data[byteIndex] |= currentBit << bitIndex; + if (bitIndex == 7) + { + bitIndex = 0; + byteIndex++; + } + else + { + bitIndex++; + } + } + } + return data; + } + + /** + * Decodes a <code>byte</code> array encoded with {@link #encodeModQ(int[], int)} back to an <code>int</code> array.<br> + * <code>N</code> is the number of coefficients. <code>q</code> must be a power of <code>2</code>.<br> + * Ignores any excess bytes. + * + * @param data an encoded ternary polynomial + * @param N number of coefficients + * @param q + * @return an array containing <code>N</code> coefficients between <code>0</code> and <code>q-1</code> + */ + public static int[] decodeModQ(byte[] data, int N, int q) + { + int[] coeffs = new int[N]; + int bitsPerCoeff = 31 - Integer.numberOfLeadingZeros(q); + int numBits = N * bitsPerCoeff; + int coeffIndex = 0; + for (int bitIndex = 0; bitIndex < numBits; bitIndex++) + { + if (bitIndex > 0 && bitIndex % bitsPerCoeff == 0) + { + coeffIndex++; + } + int bit = getBit(data, bitIndex); + coeffs[coeffIndex] += bit << (bitIndex % bitsPerCoeff); + } + return coeffs; + } + + /** + * Decodes data encoded with {@link #encodeModQ(int[], int)} back to an <code>int</code> array.<br> + * <code>N</code> is the number of coefficients. <code>q</code> must be a power of <code>2</code>.<br> + * Ignores any excess bytes. + * + * @param is an encoded ternary polynomial + * @param N number of coefficients + * @param q + * @return the decoded polynomial + */ + public static int[] decodeModQ(InputStream is, int N, int q) + throws IOException + { + int qBits = 31 - Integer.numberOfLeadingZeros(q); + int size = (N * qBits + 7) / 8; + byte[] arr = Util.readFullLength(is, size); + return decodeModQ(arr, N, q); + } + + /** + * Decodes a <code>byte</code> array encoded with {@link #encodeMod3Sves(int[])} back to an <code>int</code> array + * with <code>N</code> coefficients between <code>-1</code> and <code>1</code>.<br> + * Ignores any excess bytes.<br> + * See P1363.1 section 9.2.2. + * + * @param data an encoded ternary polynomial + * @param N number of coefficients + * @return the decoded coefficients + */ + public static int[] decodeMod3Sves(byte[] data, int N) + { + int[] coeffs = new int[N]; + int coeffIndex = 0; + for (int bitIndex = 0; bitIndex < data.length * 8; ) + { + int bit1 = getBit(data, bitIndex++); + int bit2 = getBit(data, bitIndex++); + int bit3 = getBit(data, bitIndex++); + int coeffTableIndex = bit1 * 4 + bit2 * 2 + bit3; + coeffs[coeffIndex++] = COEFF1_TABLE[coeffTableIndex]; + coeffs[coeffIndex++] = COEFF2_TABLE[coeffTableIndex]; + // ignore bytes that can't fit + if (coeffIndex > N - 2) + { + break; + } + } + return coeffs; + } + + /** + * Encodes an <code>int</code> array whose elements are between <code>-1</code> and <code>1</code>, to a byte array. + * <code>coeffs[2*i]</code> and <code>coeffs[2*i+1]</code> must not both equal -1 for any integer <code>i</code>, + * so this method is only safe to use with arrays produced by {@link #decodeMod3Sves(byte[], int)}.<br> + * See P1363.1 section 9.2.3. + * + * @param arr + * @return the encoded array + */ + public static byte[] encodeMod3Sves(int[] arr) + { + int numBits = (arr.length * 3 + 1) / 2; + int numBytes = (numBits + 7) / 8; + byte[] data = new byte[numBytes]; + int bitIndex = 0; + int byteIndex = 0; + for (int i = 0; i < arr.length / 2 * 2; ) + { // if length is an odd number, throw away the highest coeff + int coeff1 = arr[i++] + 1; + int coeff2 = arr[i++] + 1; + if (coeff1 == 0 && coeff2 == 0) + { + throw new IllegalStateException("Illegal encoding!"); + } + int bitTableIndex = coeff1 * 3 + coeff2; + int[] bits = new int[]{BIT1_TABLE[bitTableIndex], BIT2_TABLE[bitTableIndex], BIT3_TABLE[bitTableIndex]}; + for (int j = 0; j < 3; j++) + { + data[byteIndex] |= bits[j] << bitIndex; + if (bitIndex == 7) + { + bitIndex = 0; + byteIndex++; + } + else + { + bitIndex++; + } + } + } + return data; + } + + /** + * Encodes an <code>int</code> array whose elements are between <code>-1</code> and <code>1</code>, to a byte array. + * + * @return the encoded array + */ + public static byte[] encodeMod3Tight(int[] intArray) + { + BigInteger sum = BigInteger.ZERO; + for (int i = intArray.length - 1; i >= 0; i--) + { + sum = sum.multiply(BigInteger.valueOf(3)); + sum = sum.add(BigInteger.valueOf(intArray[i] + 1)); + } + + int size = (BigInteger.valueOf(3).pow(intArray.length).bitLength() + 7) / 8; + byte[] arr = sum.toByteArray(); + + if (arr.length < size) + { + // pad with leading zeros so arr.length==size + byte[] arr2 = new byte[size]; + System.arraycopy(arr, 0, arr2, size - arr.length, arr.length); + return arr2; + } + + if (arr.length > size) + // drop sign bit + { + arr = Arrays.copyOfRange(arr, 1, arr.length); + } + return arr; + } + + /** + * Converts a byte array produced by {@link #encodeMod3Tight(int[])} back to an <code>int</code> array. + * + * @param b a byte array + * @param N number of coefficients + * @return the decoded array + */ + public static int[] decodeMod3Tight(byte[] b, int N) + { + BigInteger sum = new BigInteger(1, b); + int[] coeffs = new int[N]; + for (int i = 0; i < N; i++) + { + coeffs[i] = sum.mod(BigInteger.valueOf(3)).intValue() - 1; + if (coeffs[i] > 1) + { + coeffs[i] -= 3; + } + sum = sum.divide(BigInteger.valueOf(3)); + } + return coeffs; + } + + /** + * Converts data produced by {@link #encodeMod3Tight(int[])} back to an <code>int</code> array. + * + * @param is an input stream containing the data to decode + * @param N number of coefficients + * @return the decoded array + */ + public static int[] decodeMod3Tight(InputStream is, int N) + throws IOException + { + int size = (int)Math.ceil(N * Math.log(3) / Math.log(2) / 8); + byte[] arr = Util.readFullLength(is, size); + return decodeMod3Tight(arr, N); + } + + private static int getBit(byte[] arr, int bitIndex) + { + int byteIndex = bitIndex / 8; + int arrElem = arr[byteIndex] & 0xFF; + return (arrElem >> (bitIndex % 8)) & 1; + } +}
\ No newline at end of file diff --git a/core/src/main/java/org/spongycastle/pqc/math/ntru/util/Util.java b/core/src/main/java/org/spongycastle/pqc/math/ntru/util/Util.java new file mode 100644 index 00000000..b07e1cb8 --- /dev/null +++ b/core/src/main/java/org/spongycastle/pqc/math/ntru/util/Util.java @@ -0,0 +1,158 @@ +package org.spongycastle.pqc.math.ntru.util; + +import java.io.IOException; +import java.io.InputStream; +import java.security.SecureRandom; +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; + +import org.spongycastle.pqc.math.ntru.euclid.IntEuclidean; +import org.spongycastle.pqc.math.ntru.polynomial.DenseTernaryPolynomial; +import org.spongycastle.pqc.math.ntru.polynomial.SparseTernaryPolynomial; +import org.spongycastle.pqc.math.ntru.polynomial.TernaryPolynomial; +import org.spongycastle.util.Integers; + +public class Util +{ + private static volatile boolean IS_64_BITNESS_KNOWN; + private static volatile boolean IS_64_BIT_JVM; + + /** + * Calculates the inverse of n mod modulus + */ + public static int invert(int n, int modulus) + { + n %= modulus; + if (n < 0) + { + n += modulus; + } + return IntEuclidean.calculate(n, modulus).x; + } + + /** + * Calculates a^b mod modulus + */ + public static int pow(int a, int b, int modulus) + { + int p = 1; + for (int i = 0; i < b; i++) + { + p = (p * a) % modulus; + } + return p; + } + + /** + * Calculates a^b mod modulus + */ + public static long pow(long a, int b, long modulus) + { + long p = 1; + for (int i = 0; i < b; i++) + { + p = (p * a) % modulus; + } + return p; + } + + /** + * Generates a "sparse" or "dense" polynomial containing numOnes ints equal to 1, + * numNegOnes int equal to -1, and the rest equal to 0. + * + * @param N + * @param numOnes + * @param numNegOnes + * @param sparse whether to create a {@link SparseTernaryPolynomial} or {@link DenseTernaryPolynomial} + * @return a ternary polynomial + */ + public static TernaryPolynomial generateRandomTernary(int N, int numOnes, int numNegOnes, boolean sparse, SecureRandom random) + { + if (sparse) + { + return SparseTernaryPolynomial.generateRandom(N, numOnes, numNegOnes, random); + } + else + { + return DenseTernaryPolynomial.generateRandom(N, numOnes, numNegOnes, random); + } + } + + /** + * Generates an array containing numOnes ints equal to 1, + * numNegOnes int equal to -1, and the rest equal to 0. + * + * @param N + * @param numOnes + * @param numNegOnes + * @return an array of integers + */ + public static int[] generateRandomTernary(int N, int numOnes, int numNegOnes, SecureRandom random) + { + Integer one = Integers.valueOf(1); + Integer minusOne = Integers.valueOf(-1); + Integer zero = Integers.valueOf(0); + + List list = new ArrayList(); + for (int i = 0; i < numOnes; i++) + { + list.add(one); + } + for (int i = 0; i < numNegOnes; i++) + { + list.add(minusOne); + } + while (list.size() < N) + { + list.add(zero); + } + + Collections.shuffle(list, random); + + int[] arr = new int[N]; + for (int i = 0; i < N; i++) + { + arr[i] = ((Integer)list.get(i)).intValue(); + } + return arr; + } + + /** + * Takes an educated guess as to whether 64 bits are supported by the JVM. + * + * @return <code>true</code> if 64-bit support detected, <code>false</code> otherwise + */ + public static boolean is64BitJVM() + { + if (!IS_64_BITNESS_KNOWN) + { + String arch = System.getProperty("os.arch"); + String sunModel = System.getProperty("sun.arch.data.model"); + IS_64_BIT_JVM = "amd64".equals(arch) || "x86_64".equals(arch) || "ppc64".equals(arch) || "64".equals(sunModel); + IS_64_BITNESS_KNOWN = true; + } + return IS_64_BIT_JVM; + } + + /** + * Reads a given number of bytes from an <code>InputStream</code>. + * If there are not enough bytes in the stream, an <code>IOException</code> + * is thrown. + * + * @param is + * @param length + * @return an array of length <code>length</code> + * @throws IOException + */ + public static byte[] readFullLength(InputStream is, int length) + throws IOException + { + byte[] arr = new byte[length]; + if (is.read(arr) != arr.length) + { + throw new IOException("Not enough bytes to read."); + } + return arr; + } +}
\ No newline at end of file |