8181594: Efficient and constant-time modular arithmetic
Summary: Field arithmetic library for crypto algorithms like Poly1305 and X25519
Reviewed-by: xuelei
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/java.base/share/classes/sun/security/util/math/ImmutableIntegerModuloP.java Tue May 08 09:21:51 2018 -0400
@@ -0,0 +1,34 @@
+/*
+ * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation. Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+package sun.security.util.math;
+
+/**
+ * An interface for immutable integers modulo a prime value.
+ */
+
+public interface ImmutableIntegerModuloP extends IntegerModuloP {
+}
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/java.base/share/classes/sun/security/util/math/IntegerFieldModuloP.java Tue May 08 09:21:51 2018 -0400
@@ -0,0 +1,115 @@
+/*
+ * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation. Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+package sun.security.util.math;
+
+import java.math.BigInteger;
+
+/**
+ * An interface for the field of integers modulo a prime number. An
+ * implementation of this interface can be used to get properties of the
+ * field and to produce field elements of type ImmutableIntegerModuloP from
+ * other objects and representations of field elements.
+ */
+
+public interface IntegerFieldModuloP {
+
+ /**
+ * Get the size of the field as a BigInteger. This size is equal to the
+ * prime modulus used to construct the field.
+ *
+ * @return the size of the field.
+ */
+ BigInteger getSize();
+
+ /**
+ * Get the additive identity element 0
+ *
+ * @return the additive identity element
+ */
+ ImmutableIntegerModuloP get0();
+
+ /**
+ * Get the multiplicative identity element 1
+ *
+ * @return the multiplicative identity element
+ */
+ ImmutableIntegerModuloP get1();
+
+ /**
+ * Get the field element equivalent to the supplied BigInteger value. The
+ * supplied value may be negative or larger than the modulus that defines
+ * the field.
+ *
+ * @param v a BigInteger value
+ * @return the field element corresponding to v
+ */
+ ImmutableIntegerModuloP getElement(BigInteger v);
+
+ /**
+ * Get a "small" value according to this implementation. This value may
+ * be used in optimized forms of some operations to avoid unnecessary
+ * calculations. For example, multiplication is much faster when it is
+ * known that one of the numbers fits within a single limb.
+ *
+ * The definition of "small", and the range of accepted values, is
+ * implementation-specific.
+ *
+ * @param v the small integer value
+ * @throws IllegalArgumentException when the value is not small
+ */
+ SmallValue getSmallValue(int v);
+
+ /**
+ * Get a field element from a little-endian unsigned integer stored in an
+ * array. The entire array will be used, and the supplied value may be
+ * larger than the modulus that defines the field. The array will not be
+ * modified.
+ *
+ * @param v an array containing a little-endian unsigned integer
+ * @return the field element corresponding to v
+ */
+ default ImmutableIntegerModuloP getElement(byte[] v) {
+ return getElement(v, 0, v.length, (byte) 0);
+ }
+
+ /**
+ * Get a field element from a little-endian unsigned integer stored at the
+ * specified position in an array. The supplied value may be
+ * larger than the modulus that defines the field. This method also takes
+ * a byte which is interpreted as an additional high-order byte of the
+ * number. The array will not be modified.
+ *
+ * @param v an array containing a little-endian unsigned integer
+ * @param offset the starting position of the integer
+ * @param length the number of bytes to read
+ * @param highByte the high-order byte of the number
+ * @return the field element corresponding to the bytes at the specified
+ * position
+ */
+ ImmutableIntegerModuloP getElement(byte[] v, int offset, int length,
+ byte highByte);
+}
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/java.base/share/classes/sun/security/util/math/IntegerModuloP.java Tue May 08 09:21:51 2018 -0400
@@ -0,0 +1,205 @@
+/*
+ * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation. Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+package sun.security.util.math;
+
+import java.math.BigInteger;
+
+/**
+ * The base interface for integers modulo a prime value. Objects of this
+ * type may be either mutable or immutable, and subinterfaces can be used
+ * to specify that an object is mutable or immutable. This type should never
+ * be used to declare local/member variables, but it may be used for
+ * formal parameters of a method. None of the methods in this interface
+ * modify the value of arguments or this.
+ *
+ * The behavior of this interface depends on the particular implementation.
+ * For example, some implementations only support a limited number of add
+ * operations before each multiply operation. See the documentation of the
+ * implementation for details.
+ *
+ * @see ImmutableIntegerModuloP
+ * @see MutableIntegerModuloP
+ */
+public interface IntegerModuloP {
+
+ /**
+ * Get the field associated with this element.
+ *
+ * @return the field
+ */
+ IntegerFieldModuloP getField();
+
+ /**
+ * Get the canonical value of this element as a BigInteger. This value
+ * will always be in the range [0, p), where p is the prime that defines
+ * the field. This method performs reduction and other computation to
+ * produce the result.
+ *
+ * @return the value as a BigInteger
+ */
+ BigInteger asBigInteger();
+
+ /**
+ * Return this value as a fixed (immutable) element. This method will
+ * copy the underlying representation if the object is mutable.
+ *
+ * @return a fixed element with the same value
+ */
+ ImmutableIntegerModuloP fixed();
+
+ /**
+ * Return this value as a mutable element. This method will always copy
+ * the underlying representation.
+ *
+ * @return a mutable element with the same value
+ */
+ MutableIntegerModuloP mutable();
+
+ /**
+ * Add this field element with the supplied element and return the result.
+ *
+ * @param b the sumand
+ * @return this + b
+ */
+ ImmutableIntegerModuloP add(IntegerModuloP b);
+
+ /**
+ * Compute the additive inverse of the field element
+ * @return the addditiveInverse (0 - this)
+ */
+ ImmutableIntegerModuloP additiveInverse();
+
+ /**
+ * Multiply this field element with the supplied element and return the
+ * result.
+ *
+ * @param b the multiplicand
+ * @return this * b
+ */
+ ImmutableIntegerModuloP multiply(IntegerModuloP b);
+
+ /**
+ * Perform an addition modulo a power of two and return the little-endian
+ * encoding of the result. The value is (this' + b') % 2^(8 * len),
+ * where this' and b' are the canonical integer values equivalent to
+ * this and b.
+ *
+ * @param b the sumand
+ * @param len the length of the desired array
+ * @return a byte array of length len containing the result
+ */
+ default byte[] addModPowerTwo(IntegerModuloP b, int len) {
+ byte[] result = new byte[len];
+ addModPowerTwo(b, result);
+ return result;
+ }
+
+ /**
+ * Perform an addition modulo a power of two and store the little-endian
+ * encoding of the result in the supplied array. The value is
+ * (this' + b') % 2^(8 * result.length), where this' and b' are the
+ * canonical integer values equivalent to this and b.
+ *
+ * @param b the sumand
+ * @param result an array which stores the result upon return
+ */
+ void addModPowerTwo(IntegerModuloP b, byte[] result);
+
+ /**
+ * Returns the little-endian encoding of this' % 2^(8 * len), where this'
+ * is the canonical integer value equivalent to this.
+ *
+ * @param len the length of the desired array
+ * @return a byte array of length len containing the result
+ */
+ default byte[] asByteArray(int len) {
+ byte[] result = new byte[len];
+ asByteArray(result);
+ return result;
+ }
+
+ /**
+ * Places the little-endian encoding of this' % 2^(8 * result.length)
+ * into the supplied array, where this' is the canonical integer value
+ * equivalent to this.
+ *
+ * @param result an array which stores the result upon return
+ */
+ void asByteArray(byte[] result);
+
+ /**
+ * Compute the multiplicative inverse of this field element.
+ *
+ * @return the multiplicative inverse (1 / this)
+ */
+ default ImmutableIntegerModuloP multiplicativeInverse() {
+ return pow(getField().getSize().subtract(BigInteger.valueOf(2)));
+ }
+
+ /**
+ * Subtract the supplied element from this one and return the result.
+ * @param b the subtrahend
+ *
+ * @return the difference (this - b)
+ */
+ default ImmutableIntegerModuloP subtract(IntegerModuloP b) {
+ return add(b.additiveInverse());
+ }
+
+ /**
+ * Calculate the square of this element and return the result. This method
+ * should be used instead of a.multiply(a) because implementations may
+ * include optimizations that only apply to squaring.
+ *
+ * @return the product (this * this)
+ */
+ default ImmutableIntegerModuloP square() {
+ return multiply(this);
+ }
+
+ /**
+ * Calculate the power this^b and return the result.
+ *
+ * @param b the exponent
+ * @return the value of this^b
+ */
+ default ImmutableIntegerModuloP pow(BigInteger b) {
+ //Default implementation is square and multiply
+ MutableIntegerModuloP y = getField().get1().mutable();
+ MutableIntegerModuloP x = mutable();
+ int bitLength = b.bitLength();
+ for (int bit = 0; bit < bitLength; bit++) {
+ if (b.testBit(bit)) {
+ // odd
+ y.setProduct(x);
+ }
+ x.setSquare();
+ }
+ return y.fixed();
+ }
+
+}
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/java.base/share/classes/sun/security/util/math/MutableIntegerModuloP.java Tue May 08 09:21:51 2018 -0400
@@ -0,0 +1,135 @@
+/*
+ * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation. Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+package sun.security.util.math;
+
+import java.nio.ByteBuffer;
+
+/**
+ * An interface for mutable integers modulo a prime value. This interface
+ * should be used to improve performance and avoid the allocation of a large
+ * number of temporary objects.
+ *
+ * Methods in this interface that modify the value also return the modified
+ * element. This structure enables fluent expressions like:
+ * a.setSum(b).setProduct(c).setDifference(d).setSquare()
+ *
+ */
+
+public interface MutableIntegerModuloP extends IntegerModuloP {
+
+ /**
+ * Swap the value of this with the value of b when swap has the value 1.
+ * No change is made to either element when swap has the value 0. The
+ * result is undefined when swap has a value other than 0 or 1. The swap
+ * parameter is an int (rather than boolean) to allow the implementation
+ * to perform the swap using branch-free integer arithmetic.
+ *
+ * @param b the element to conditionally swap with
+ * @param swap an int that determines whether to swap
+ */
+ void conditionalSwapWith(MutableIntegerModuloP b, int swap);
+
+ /**
+ * Set the value of this element equal to the value of the supplied
+ * element. The argument is not modified.
+ *
+ * @param v the element whose value should be copied to this
+ * @return this
+ */
+ MutableIntegerModuloP setValue(IntegerModuloP v);
+
+ /**
+ * Set the value equal to the little-endian unsigned integer stored at the
+ * specified position in an array. The range of accepted values is
+ * implementation-specific. This method also takes a byte which is
+ * interpreted as an additional high-order byte of the number.
+ *
+ * @param v an array containing a little-endian unsigned integer
+ * @param offset the starting position of the integer
+ * @param length the number of bytes to read
+ * @param highByte the high-order byte of the number
+ * @return this
+ */
+ MutableIntegerModuloP setValue(byte[] v, int offset, int length,
+ byte highByte);
+
+ /**
+ * Set the value equal to the little-endian unsigned integer stored in a
+ * buffer. The range of accepted values is implementation-specific.
+ * This method also takes a byte which is interpreted as an additional
+ * high-order byte of the number.
+ *
+ * @param buf a buffer containing a little-endian unsigned integer
+ * @param length the number of bytes to read
+ * @param highByte the high-order byte of the number
+ * @return this
+ */
+ MutableIntegerModuloP setValue(ByteBuffer buf, int length, byte highByte);
+
+ /**
+ * Set the value of this element equal to this * this.
+ *
+ * @return this
+ */
+ MutableIntegerModuloP setSquare();
+
+ /**
+ * Set the value of this element equal to this + b. The argument is
+ * not modified.
+ *
+ * @param b the sumand
+ * @return this
+ */
+ MutableIntegerModuloP setSum(IntegerModuloP b);
+
+ /**
+ * Set the value of this element equal to this - b. The argument is
+ * not modified.
+ *
+ * @param b the subtrahend
+ * @return this
+ */
+ MutableIntegerModuloP setDifference(IntegerModuloP b);
+
+ /**
+ * Set the value of this element equal to this * b. The argument is
+ * not modified.
+ *
+ * @param b the multiplicand
+ * @return this
+ */
+ MutableIntegerModuloP setProduct(IntegerModuloP b);
+
+ /**
+ * Set the value of this element equal to this * v. The argument is
+ * not modified.
+ *
+ * @param v the small multiplicand
+ * @return this
+ */
+ MutableIntegerModuloP setProduct(SmallValue v);
+}
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/java.base/share/classes/sun/security/util/math/SmallValue.java Tue May 08 09:21:51 2018 -0400
@@ -0,0 +1,38 @@
+/*
+ * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation. Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+package sun.security.util.math;
+
+/**
+ * A "small" value that can be used with the field arithmetic library. This
+ * interface enables optimizations based on the fact that certain values are
+ * known to be small, where the definition of small is specific to the the
+ * arithmetic implementation.
+ */
+
+public interface SmallValue {
+}
+
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/java.base/share/classes/sun/security/util/math/intpoly/IntegerPolynomial.java Tue May 08 09:21:51 2018 -0400
@@ -0,0 +1,576 @@
+/*
+ * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation. Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+package sun.security.util.math.intpoly;
+
+import sun.security.util.math.*;
+
+import java.math.BigInteger;
+import java.nio.ByteBuffer;
+import java.nio.ByteOrder;
+import java.util.Arrays;
+
+/**
+ * A large number polynomial representation using sparse limbs of signed
+ * long (64-bit) values. Limb values will always fit within a long, so inputs
+ * to multiplication must be less than 32 bits. All IntegerPolynomial
+ * implementations allow at most one addition before multiplication. Additions
+ * after that will result in an ArithmeticException.
+ *
+ * The following element operations are branch-free for all subclasses:
+ *
+ * fixed
+ * mutable
+ * add
+ * additiveInverse
+ * multiply
+ * square
+ * subtract
+ * conditionalSwapWith
+ * setValue (may branch on high-order byte parameter only)
+ * setSum
+ * setDifference
+ * setProduct
+ * setSquare
+ *
+ * All other operations may branch in some subclasses.
+ *
+ */
+
+public abstract class IntegerPolynomial implements IntegerFieldModuloP {
+
+ protected static final BigInteger TWO = BigInteger.valueOf(2);
+
+ protected final int numLimbs;
+ private final BigInteger modulus;
+ protected final int bitsPerLimb;
+
+ // must work when a==r
+ protected abstract void multByInt(long[] a, long b, long[] r);
+
+ // must work when a==r
+ protected abstract void mult(long[] a, long[] b, long[] r);
+
+ // must work when a==r
+ protected abstract void square(long[] a, long[] r);
+
+ IntegerPolynomial(int bitsPerLimb,
+ int numLimbs,
+ BigInteger modulus) {
+
+
+ this.numLimbs = numLimbs;
+ this.modulus = modulus;
+ this.bitsPerLimb = bitsPerLimb;
+ }
+
+ protected int getNumLimbs() {
+ return numLimbs;
+ }
+
+ @Override
+ public BigInteger getSize() {
+ return modulus;
+ }
+
+ @Override
+ public ImmutableElement get0() {
+ return new ImmutableElement(false);
+ }
+
+ @Override
+ public ImmutableElement get1() {
+ return new ImmutableElement(true);
+ }
+
+ @Override
+ public ImmutableElement getElement(BigInteger v) {
+ return new ImmutableElement(v);
+ }
+
+ @Override
+ public SmallValue getSmallValue(int value) {
+ int maxMag = 1 << (bitsPerLimb - 1);
+ if (Math.abs(value) >= maxMag) {
+ throw new IllegalArgumentException(
+ "max magnitude is " + maxMag);
+ }
+ return new Limb(value);
+ }
+
+ /**
+ * This version of encode takes a ByteBuffer that is properly ordered, and
+ * may extract larger values (e.g. long) from the ByteBuffer for better
+ * performance. The implementation below only extracts bytes from the
+ * buffer, but this method may be overridden in field-specific
+ * implementations.
+ */
+ protected void encode(ByteBuffer buf, int length, byte highByte,
+ long[] result) {
+ int numHighBits = 32 - Integer.numberOfLeadingZeros(highByte);
+ int numBits = 8 * length + numHighBits;
+ int maxBits = bitsPerLimb * result.length;
+ if (numBits > maxBits) {
+ throw new ArithmeticException("Value is too large.");
+ }
+
+ int limbIndex = 0;
+ long curLimbValue = 0;
+ int bitPos = 0;
+ for (int i = 0; i < length; i++) {
+ long curV = buf.get() & 0xFF;
+
+ if (bitPos + 8 >= bitsPerLimb) {
+ int bitsThisLimb = bitsPerLimb - bitPos;
+ curLimbValue += (curV & (0xFF >> (8 - bitsThisLimb))) << bitPos;
+ result[limbIndex++] = curLimbValue;
+ curLimbValue = curV >> bitsThisLimb;
+ bitPos = 8 - bitsThisLimb;
+ }
+ else {
+ curLimbValue += curV << bitPos;
+ bitPos += 8;
+ }
+ }
+
+ // one more for the high byte
+ if (highByte != 0) {
+ long curV = highByte & 0xFF;
+ if (bitPos + 8 >= bitsPerLimb) {
+ int bitsThisLimb = bitsPerLimb - bitPos;
+ curLimbValue += (curV & (0xFF >> (8 - bitsThisLimb))) << bitPos;
+ result[limbIndex++] = curLimbValue;
+ curLimbValue = curV >> bitsThisLimb;
+ }
+ else {
+ curLimbValue += curV << bitPos;
+ }
+ }
+
+ if (limbIndex < numLimbs) {
+ result[limbIndex++] = curLimbValue;
+ }
+ Arrays.fill(result, limbIndex, numLimbs, 0);
+
+ postEncodeCarry(result);
+ }
+
+ protected void encode(byte[] v, int offset, int length, byte highByte,
+ long[] result) {
+
+ ByteBuffer buf = ByteBuffer.wrap(v, offset, length);
+ buf.order(ByteOrder.LITTLE_ENDIAN);
+ encode(buf, length, highByte, result);
+ }
+
+ protected void postEncodeCarry(long[] v) {
+ carry(v);
+ }
+
+ public ImmutableElement getElement(byte[] v, int offset, int length,
+ byte highByte) {
+
+ long[] result = new long[numLimbs];
+
+ encode(v, offset, length, highByte, result);
+
+ return new ImmutableElement(result, true);
+ }
+
+ protected BigInteger evaluate(long[] limbs) {
+ BigInteger result = BigInteger.ZERO;
+ for (int i = limbs.length - 1; i >= 0; i--) {
+ result = result.shiftLeft(bitsPerLimb)
+ .add(BigInteger.valueOf(limbs[i]));
+ }
+ return result.mod(modulus);
+ }
+
+ protected long carryValue(long x) {
+ // compressing carry operation
+ // if large positive number, carry one more to make it negative
+ // if large negative number (closer to zero), carry one fewer
+ return (x + (1 << (bitsPerLimb - 1))) >> bitsPerLimb;
+ }
+
+ protected void carry(long[] limbs, int start, int end) {
+
+ for (int i = start; i < end; i++) {
+
+ long carry = carryOut(limbs, i);
+ limbs[i + 1] += carry;
+ }
+ }
+
+ protected void carry(long[] limbs) {
+
+ carry(limbs, 0, limbs.length - 1);
+ }
+
+ // carry out of the specified position and return the carry value
+ protected long carryOut(long[] limbs, int index) {
+ long carry = carryValue(limbs[index]);
+ limbs[index] -= (carry << bitsPerLimb);
+ return carry;
+ }
+
+ private void setLimbsValue(BigInteger v, long[] limbs) {
+ // set all limbs positive, and then carry
+ setLimbsValuePositive(v, limbs);
+ carry(limbs);
+ }
+
+ protected void setLimbsValuePositive(BigInteger v, long[] limbs) {
+ BigInteger mod = BigInteger.valueOf(1 << bitsPerLimb);
+ for (int i = 0; i < limbs.length; i++) {
+ limbs[i] = v.mod(mod).longValue();
+ v = v.shiftRight(bitsPerLimb);
+ }
+ }
+
+ // v must be final reduced. I.e. all limbs in [0, bitsPerLimb)
+ // and value in [0, modulus)
+ protected void decode(long[] v, byte[] dst, int offset, int length) {
+
+ int nextLimbIndex = 0;
+ long curLimbValue = v[nextLimbIndex++];
+ int bitPos = 0;
+ for (int i = 0; i < length; i++) {
+
+ int dstIndex = i + offset;
+ if (bitPos + 8 >= bitsPerLimb) {
+ dst[dstIndex] = (byte) curLimbValue;
+ curLimbValue = v[nextLimbIndex++];
+ int bitsAdded = bitsPerLimb - bitPos;
+ int bitsLeft = 8 - bitsAdded;
+
+ dst[dstIndex] += (curLimbValue & (0xFF >> bitsAdded))
+ << bitsAdded;
+ curLimbValue >>= bitsLeft;
+ bitPos = bitsLeft;
+ } else {
+ dst[dstIndex] = (byte) curLimbValue;
+ curLimbValue >>= 8;
+ bitPos += 8;
+ }
+ }
+ }
+
+ protected void addLimbs(long[] a, long[] b, long[] dst) {
+ for (int i = 0; i < dst.length; i++) {
+ dst[i] = a[i] + b[i];
+ }
+ }
+
+ protected static void conditionalSwap(int swap, long[] a, long[] b) {
+ int maskValue = 0 - swap;
+ for (int i = 0; i < a.length; i++) {
+ long dummyLimbs = maskValue & (a[i] ^ b[i]);
+ a[i] = dummyLimbs ^ a[i];
+ b[i] = dummyLimbs ^ b[i];
+ }
+ }
+
+ private void bigIntToByteArray(BigInteger bi, byte[] result) {
+ byte[] biBytes = bi.toByteArray();
+ // biBytes is backwards and possibly too big
+ // Copy the low-order bytes into result in reverse
+ int sourceIndex = biBytes.length - 1;
+ for (int i = 0; i < result.length; i++) {
+ if (sourceIndex >= 0) {
+ result[i] = biBytes[sourceIndex--];
+ }
+ else {
+ result[i] = 0;
+ }
+ }
+ }
+
+ protected void limbsToByteArray(long[] limbs, byte[] result) {
+
+ bigIntToByteArray(evaluate(limbs), result);
+ }
+
+ protected void addLimbsModPowerTwo(long[] limbs, long[] other,
+ byte[] result) {
+
+ BigInteger bi1 = evaluate(limbs);
+ BigInteger bi2 = evaluate(other);
+ BigInteger biResult = bi1.add(bi2);
+ bigIntToByteArray(biResult, result);
+ }
+
+ private abstract class Element implements IntegerModuloP {
+
+ protected long[] limbs;
+ protected boolean summand = false;
+
+ public Element(BigInteger v) {
+ limbs = new long[numLimbs];
+ setValue(v);
+ }
+
+ public Element(boolean v) {
+ limbs = new long[numLimbs];
+ limbs[0] = v ? 1l : 0l;
+ summand = true;
+ }
+
+ private Element(long[] limbs, boolean summand) {
+ this.limbs = limbs;
+ this.summand = summand;
+ }
+
+ private void setValue(BigInteger v) {
+ setLimbsValue(v, limbs);
+ summand = true;
+ }
+
+ @Override
+ public IntegerFieldModuloP getField() {
+ return IntegerPolynomial.this;
+ }
+
+ @Override
+ public BigInteger asBigInteger() {
+ return evaluate(limbs);
+ }
+
+ @Override
+ public MutableElement mutable() {
+ return new MutableElement(limbs.clone(), summand);
+ }
+
+ @Override
+ public ImmutableElement add(IntegerModuloP genB) {
+
+ Element b = (Element) genB;
+ if (!(summand && b.summand)) {
+ throw new ArithmeticException("Not a valid summand");
+ }
+
+ long[] newLimbs = new long[limbs.length];
+ for (int i = 0; i < limbs.length; i++) {
+ newLimbs[i] = limbs[i] + b.limbs[i];
+ }
+
+ return new ImmutableElement(newLimbs, false);
+ }
+
+ @Override
+ public ImmutableElement additiveInverse() {
+
+ long[] newLimbs = new long[limbs.length];
+ for (int i = 0; i < limbs.length; i++) {
+ newLimbs[i] = -limbs[i];
+ }
+
+ ImmutableElement result = new ImmutableElement(newLimbs, summand);
+ return result;
+ }
+
+ protected long[] cloneLow(long[] limbs) {
+ long[] newLimbs = new long[numLimbs];
+ copyLow(limbs, newLimbs);
+ return newLimbs;
+ }
+ protected void copyLow(long[] limbs, long[] out) {
+ System.arraycopy(limbs, 0, out, 0, out.length);
+ }
+
+ @Override
+ public ImmutableElement multiply(IntegerModuloP genB) {
+
+ Element b = (Element) genB;
+
+ long[] newLimbs = new long[limbs.length];
+ mult(limbs, b.limbs, newLimbs);
+ return new ImmutableElement(newLimbs, true);
+ }
+
+ @Override
+ public ImmutableElement square() {
+ long[] newLimbs = new long[limbs.length];
+ IntegerPolynomial.this.square(limbs, newLimbs);
+ return new ImmutableElement(newLimbs, true);
+ }
+
+ public void addModPowerTwo(IntegerModuloP arg, byte[] result) {
+ if (!summand) {
+ throw new ArithmeticException("Not a valid summand");
+ }
+
+ Element other = (Element) arg;
+ addLimbsModPowerTwo(limbs, other.limbs, result);
+ }
+
+ public void asByteArray(byte[] result) {
+ if (!summand) {
+ throw new ArithmeticException("Not a valid summand");
+ }
+ limbsToByteArray(limbs, result);
+ }
+ }
+
+ private class MutableElement extends Element
+ implements MutableIntegerModuloP {
+
+ protected MutableElement(long[] limbs, boolean summand) {
+ super(limbs, summand);
+ }
+
+ @Override
+ public ImmutableElement fixed() {
+ return new ImmutableElement(limbs.clone(), summand);
+ }
+
+ @Override
+ public void conditionalSwapWith(MutableIntegerModuloP b, int swap) {
+
+ MutableElement other = (MutableElement) b;
+
+ conditionalSwap(swap, limbs, other.limbs);
+ boolean summandTemp = summand;
+ summand = other.summand;
+ other.summand = summandTemp;
+ }
+
+
+ @Override
+ public MutableElement setValue(IntegerModuloP v) {
+ Element other = (Element) v;
+
+ System.arraycopy(other.limbs, 0, limbs, 0, other.limbs.length);
+ summand = other.summand;
+ return this;
+ }
+
+ @Override
+ public MutableElement setValue(byte[] arr, int offset,
+ int length, byte highByte) {
+
+ encode(arr, offset, length, highByte, limbs);
+ summand = true;
+
+ return this;
+ }
+
+ @Override
+ public MutableElement setValue(ByteBuffer buf, int length,
+ byte highByte) {
+
+ encode(buf, length, highByte, limbs);
+ summand = true;
+
+ return this;
+ }
+
+ @Override
+ public MutableElement setProduct(IntegerModuloP genB) {
+ Element b = (Element) genB;
+ mult(limbs, b.limbs, limbs);
+ summand = true;
+ return this;
+ }
+
+ @Override
+ public MutableElement setProduct(SmallValue v) {
+ int value = ((Limb) v).value;
+ multByInt(limbs, value, limbs);
+ summand = true;
+ return this;
+ }
+
+ @Override
+ public MutableElement setSum(IntegerModuloP genB) {
+
+ Element b = (Element) genB;
+ if (!(summand && b.summand)) {
+ throw new ArithmeticException("Not a valid summand");
+ }
+
+ for (int i = 0; i < limbs.length; i++) {
+ limbs[i] = limbs[i] + b.limbs[i];
+ }
+
+ summand = false;
+ return this;
+ }
+
+ @Override
+ public MutableElement setDifference(IntegerModuloP genB) {
+
+ Element b = (Element) genB;
+ if (!(summand && b.summand)) {
+ throw new ArithmeticException("Not a valid summand");
+ }
+
+ for (int i = 0; i < limbs.length; i++) {
+ limbs[i] = limbs[i] - b.limbs[i];
+ }
+
+ return this;
+ }
+
+ @Override
+ public MutableElement setSquare() {
+ IntegerPolynomial.this.square(limbs, limbs);
+ summand = true;
+ return this;
+ }
+
+ }
+
+ class ImmutableElement extends Element implements ImmutableIntegerModuloP {
+
+ protected ImmutableElement(BigInteger v) {
+ super(v);
+ }
+
+ protected ImmutableElement(boolean v) {
+ super(v);
+ }
+
+ protected ImmutableElement(long[] limbs, boolean summand) {
+ super(limbs, summand);
+ }
+
+ @Override
+ public ImmutableElement fixed() {
+ return this;
+ }
+
+ }
+
+ class Limb implements SmallValue {
+ int value;
+
+ Limb(int value) {
+ this.value = value;
+ }
+ }
+
+
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/java.base/share/classes/sun/security/util/math/intpoly/IntegerPolynomial1305.java Tue May 08 09:21:51 2018 -0400
@@ -0,0 +1,301 @@
+/*
+ * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation. Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+package sun.security.util.math.intpoly;
+
+import java.lang.invoke.MethodHandles;
+import java.lang.invoke.VarHandle;
+import java.math.BigInteger;
+import java.nio.*;
+
+/**
+ * An IntegerFieldModuloP designed for use with the Poly1305 authenticator.
+ * The representation uses 5 signed long values.
+ *
+ * In addition to the branch-free operations specified in the parent class,
+ * the following operations are branch-free:
+ *
+ * addModPowerTwo
+ * asByteArray
+ *
+ */
+
+public class IntegerPolynomial1305 extends IntegerPolynomial {
+
+ protected static final int SUBTRAHEND = 5;
+ protected static final int NUM_LIMBS = 5;
+ private static final int POWER = 130;
+ private static final int BITS_PER_LIMB = 26;
+ private static final BigInteger MODULUS
+ = TWO.pow(POWER).subtract(BigInteger.valueOf(SUBTRAHEND));
+
+ private final long[] posModLimbs;
+
+ private long[] setPosModLimbs() {
+ long[] result = new long[NUM_LIMBS];
+ setLimbsValuePositive(MODULUS, result);
+ return result;
+ }
+
+ public IntegerPolynomial1305() {
+ super(BITS_PER_LIMB, NUM_LIMBS, MODULUS);
+ posModLimbs = setPosModLimbs();
+ }
+
+ protected void mult(long[] a, long[] b, long[] r) {
+
+ // Use grade-school multiplication into primitives to avoid the
+ // temporary array allocation. This is equivalent to the following
+ // code:
+ // long[] c = new long[2 * NUM_LIMBS - 1];
+ // for(int i = 0; i < NUM_LIMBS; i++) {
+ // for(int j - 0; j < NUM_LIMBS; j++) {
+ // c[i + j] += a[i] * b[j]
+ // }
+ // }
+
+ long c0 = (a[0] * b[0]);
+ long c1 = (a[0] * b[1]) + (a[1] * b[0]);
+ long c2 = (a[0] * b[2]) + (a[1] * b[1]) + (a[2] * b[0]);
+ long c3 = (a[0] * b[3]) + (a[1] * b[2]) + (a[2] * b[1]) + (a[3] * b[0]);
+ long c4 = (a[0] * b[4]) + (a[1] * b[3]) + (a[2] * b[2]) + (a[3] * b[1]) + (a[4] * b[0]);
+ long c5 = (a[1] * b[4]) + (a[2] * b[3]) + (a[3] * b[2]) + (a[4] * b[1]);
+ long c6 = (a[2] * b[4]) + (a[3] * b[3]) + (a[4] * b[2]);
+ long c7 = (a[3] * b[4]) + (a[4] * b[3]);
+ long c8 = (a[4] * b[4]);
+
+ carryReduce(r, c0, c1, c2, c3, c4, c5, c6, c7, c8);
+ }
+
+ private void carryReduce(long[] r, long c0, long c1, long c2, long c3,
+ long c4, long c5, long c6, long c7, long c8) {
+ //reduce(2, 2)
+ r[2] = c2 + (c7 * SUBTRAHEND);
+ c3 += (c8 * SUBTRAHEND);
+
+ // carry(3, 2)
+ long carry3 = carryValue(c3);
+ r[3] = c3 - (carry3 << BITS_PER_LIMB);
+ c4 += carry3;
+
+ long carry4 = carryValue(c4);
+ r[4] = c4 - (carry4 << BITS_PER_LIMB);
+ c5 += carry4;
+
+ // reduce(0, 2)
+ r[0] = c0 + (c5 * SUBTRAHEND);
+ r[1] = c1 + (c6 * SUBTRAHEND);
+
+ // carry(0, 4)
+ carry(r);
+ }
+
+ protected void multByInt(long[] a, long b, long[] r) {
+
+ for (int i = 0; i < a.length; i++) {
+ r[i] = a[i] * b;
+ }
+
+ reduce(r);
+ }
+
+ @Override
+ protected void square(long[] a, long[] r) {
+ // Use grade-school multiplication with a simple squaring optimization.
+ // Multiply into primitives to avoid the temporary array allocation.
+ // This is equivalent to the following code:
+ // long[] c = new long[2 * NUM_LIMBS - 1];
+ // for(int i = 0; i < NUM_LIMBS; i++) {
+ // c[2 * i] = a[i] * a[i];
+ // for(int j = i + 1; j < NUM_LIMBS; j++) {
+ // c[i + j] += 2 * a[i] * a[j]
+ // }
+ // }
+
+ long c0 = (a[0] * a[0]);
+ long c1 = 2 * (a[0] * a[1]);
+ long c2 = 2 * (a[0] * a[2]) + (a[1] * a[1]);
+ long c3 = 2 * (a[0] * a[3] + a[1] * a[2]);
+ long c4 = 2 * (a[0] * a[4] + a[1] * a[3]) + (a[2] * a[2]);
+ long c5 = 2 * (a[1] * a[4] + a[2] * a[3]);
+ long c6 = 2 * (a[2] * a[4]) + (a[3] * a[3]);
+ long c7 = 2 * (a[3] * a[4]);
+ long c8 = (a[4] * a[4]);
+
+ carryReduce(r, c0, c1, c2, c3, c4, c5, c6, c7, c8);
+ }
+
+ @Override
+ protected void encode(ByteBuffer buf, int length, byte highByte,
+ long[] result) {
+ if (length == 16) {
+ long low = buf.getLong();
+ long high = buf.getLong();
+ encode(high, low, highByte, result);
+ } else {
+ super.encode(buf, length, highByte, result);
+ }
+ }
+
+ protected void encode(long high, long low, byte highByte, long[] result) {
+ result[0] = low & 0x3FFFFFFL;
+ result[1] = (low >>> 26) & 0x3FFFFFFL;
+ result[2] = (low >>> 52) + ((high & 0x3FFFL) << 12);
+ result[3] = (high >>> 14) & 0x3FFFFFFL;
+ result[4] = (high >>> 40) + (highByte << 24L);
+ }
+
+ private static final VarHandle AS_LONG_LE = MethodHandles
+ .byteArrayViewVarHandle(long[].class, ByteOrder.LITTLE_ENDIAN);
+
+ protected void encode(byte[] v, int offset, int length, byte highByte,
+ long[] result) {
+ if (length == 16) {
+ long low = (long) AS_LONG_LE.get(v, offset);
+ long high = (long) AS_LONG_LE.get(v, offset + 8);
+ encode(high, low, highByte, result);
+ } else {
+ super.encode(v, offset, length, highByte, result);
+ }
+ }
+
+ protected void modReduceIn(long[] limbs, int index, long x) {
+ // this only works when BITS_PER_LIMB * NUM_LIMBS = POWER exactly
+ long reducedValue = (x * SUBTRAHEND);
+ limbs[index - NUM_LIMBS] += reducedValue;
+ }
+
+ protected final void modReduce(long[] limbs, int start, int end) {
+
+ for (int i = start; i < end; i++) {
+ modReduceIn(limbs, i, limbs[i]);
+ limbs[i] = 0;
+ }
+ }
+
+ protected void modReduce(long[] limbs) {
+
+ modReduce(limbs, NUM_LIMBS, NUM_LIMBS - 1);
+ }
+
+ @Override
+ protected long carryValue(long x) {
+ // This representation has plenty of extra space, so we can afford to
+ // do a simplified carry operation that is more time-efficient.
+
+ return x >> BITS_PER_LIMB;
+ }
+
+
+ protected void reduce(long[] limbs) {
+ long carry3 = carryOut(limbs, 3);
+ long new4 = carry3 + limbs[4];
+
+ long carry4 = carryValue(new4);
+ limbs[4] = new4 - (carry4 << BITS_PER_LIMB);
+
+ modReduceIn(limbs, 5, carry4);
+ carry(limbs);
+ }
+
+ // Convert reduced limbs into a number between 0 and MODULUS-1
+ private void finalReduce(long[] limbs) {
+
+ addLimbs(limbs, posModLimbs, limbs);
+ // now all values are positive, so remaining operations will be unsigned
+
+ // unsigned carry out of last position and reduce in to first position
+ long carry = limbs[NUM_LIMBS - 1] >> BITS_PER_LIMB;
+ limbs[NUM_LIMBS - 1] -= carry << BITS_PER_LIMB;
+ modReduceIn(limbs, NUM_LIMBS, carry);
+
+ // unsigned carry on all positions
+ carry = 0;
+ for (int i = 0; i < NUM_LIMBS; i++) {
+ limbs[i] += carry;
+ carry = limbs[i] >> BITS_PER_LIMB;
+ limbs[i] -= carry << BITS_PER_LIMB;
+ }
+ // reduce final carry value back in
+ modReduceIn(limbs, NUM_LIMBS, carry);
+ // we only reduce back in a nonzero value if some value was carried out
+ // of the previous loop. So at least one remaining value is small.
+
+ // One more carry is all that is necessary. Nothing will be carried out
+ // at the end
+ carry = 0;
+ for (int i = 0; i < NUM_LIMBS; i++) {
+ limbs[i] += carry;
+ carry = limbs[i] >> BITS_PER_LIMB;
+ limbs[i] -= carry << BITS_PER_LIMB;
+ }
+
+ // limbs are positive and all less than 2^BITS_PER_LIMB
+ // but the value may be greater than the MODULUS.
+ // Subtract the max limb values only if all limbs end up non-negative
+ int smallerNonNegative = 1;
+ long[] smaller = new long[NUM_LIMBS];
+ for (int i = NUM_LIMBS - 1; i >= 0; i--) {
+ smaller[i] = limbs[i] - posModLimbs[i];
+ // expression on right is 1 if smaller[i] is nonnegative,
+ // 0 otherwise
+ smallerNonNegative *= (int) (smaller[i] >> 63) + 1;
+ }
+ conditionalSwap(smallerNonNegative, limbs, smaller);
+
+ }
+
+ @Override
+ protected void limbsToByteArray(long[] limbs, byte[] result) {
+
+ long[] reducedLimbs = limbs.clone();
+ finalReduce(reducedLimbs);
+
+ decode(reducedLimbs, result, 0, result.length);
+ }
+
+ @Override
+ protected void addLimbsModPowerTwo(long[] limbs, long[] other,
+ byte[] result) {
+
+ long[] reducedOther = other.clone();
+ long[] reducedLimbs = limbs.clone();
+ finalReduce(reducedLimbs);
+
+ addLimbs(reducedLimbs, reducedOther, reducedLimbs);
+
+ // may carry out a value which can be ignored
+ long carry = 0;
+ for (int i = 0; i < NUM_LIMBS; i++) {
+ reducedLimbs[i] += carry;
+ carry = reducedLimbs[i] >> BITS_PER_LIMB;
+ reducedLimbs[i] -= carry << BITS_PER_LIMB;
+ }
+
+ decode(reducedLimbs, result, 0, result.length);
+ }
+
+}
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/java.base/share/classes/sun/security/util/math/intpoly/IntegerPolynomial25519.java Tue May 08 09:21:51 2018 -0400
@@ -0,0 +1,204 @@
+/*
+ * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation. Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+package sun.security.util.math.intpoly;
+
+import java.math.BigInteger;
+
+public class IntegerPolynomial25519 extends IntegerPolynomial {
+
+ private static final int POWER = 255;
+ private static final int SUBTRAHEND = 19;
+ private static final int NUM_LIMBS = 10;
+ private static final int BITS_PER_LIMB = 26;
+ public static final BigInteger MODULUS
+ = TWO.pow(POWER).subtract(BigInteger.valueOf(SUBTRAHEND));
+
+ // BITS_PER_LIMB does not divide POWER, so reduction is a bit complicated
+ // The constants below help split up values during reduction
+ private static final int BIT_OFFSET = NUM_LIMBS * BITS_PER_LIMB - POWER;
+ private static final int LIMB_MASK = -1 >>> (64 - BITS_PER_LIMB);
+ private static final int RIGHT_BIT_OFFSET = BITS_PER_LIMB - BIT_OFFSET;
+
+ public IntegerPolynomial25519() {
+ super(BITS_PER_LIMB, NUM_LIMBS, MODULUS);
+ }
+
+ @Override
+ protected void mult(long[] a, long[] b, long[] r) {
+
+ // Use grade-school multiplication into primitives to avoid the
+ // temporary array allocation. This is equivalent to the following
+ // code:
+ // long[] c = new long[2 * NUM_LIMBS - 1];
+ // for(int i = 0; i < NUM_LIMBS; i++) {
+ // for(int j - 0; j < NUM_LIMBS; j++) {
+ // c[i + j] += a[i] * b[j]
+ // }
+ // }
+
+ long c0 = (a[0] * b[0]);
+ long c1 = (a[0] * b[1]) + (a[1] * b[0]);
+ long c2 = (a[0] * b[2]) + (a[1] * b[1]) + (a[2] * b[0]);
+ long c3 = (a[0] * b[3]) + (a[1] * b[2]) + (a[2] * b[1]) + (a[3] * b[0]);
+ long c4 = (a[0] * b[4]) + (a[1] * b[3]) + (a[2] * b[2]) + (a[3] * b[1]) + (a[4] * b[0]);
+ long c5 = (a[0] * b[5]) + (a[1] * b[4]) + (a[2] * b[3]) + (a[3] * b[2]) + (a[4] * b[1]) + (a[5] * b[0]);
+ long c6 = (a[0] * b[6]) + (a[1] * b[5]) + (a[2] * b[4]) + (a[3] * b[3]) + (a[4] * b[2]) + (a[5] * b[1]) + (a[6] * b[0]);
+ long c7 = (a[0] * b[7]) + (a[1] * b[6]) + (a[2] * b[5]) + (a[3] * b[4]) + (a[4] * b[3]) + (a[5] * b[2]) + (a[6] * b[1]) + (a[7] * b[0]);
+ long c8 = (a[0] * b[8]) + (a[1] * b[7]) + (a[2] * b[6]) + (a[3] * b[5]) + (a[4] * b[4]) + (a[5] * b[3]) + (a[6] * b[2]) + (a[7] * b[1]) + (a[8] * b[0]);
+ long c9 = (a[0] * b[9]) + (a[1] * b[8]) + (a[2] * b[7]) + (a[3] * b[6]) + (a[4] * b[5]) + (a[5] * b[4]) + (a[6] * b[3]) + (a[7] * b[2]) + (a[8] * b[1]) + (a[9] * b[0]);
+ long c10 = (a[1] * b[9]) + (a[2] * b[8]) + (a[3] * b[7]) + (a[4] * b[6]) + (a[5] * b[5]) + (a[6] * b[4]) + (a[7] * b[3]) + (a[8] * b[2]) + (a[9] * b[1]);
+ long c11 = (a[2] * b[9]) + (a[3] * b[8]) + (a[4] * b[7]) + (a[5] * b[6]) + (a[6] * b[5]) + (a[7] * b[4]) + (a[8] * b[3]) + (a[9] * b[2]);
+ long c12 = (a[3] * b[9]) + (a[4] * b[8]) + (a[5] * b[7]) + (a[6] * b[6]) + (a[7] * b[5]) + (a[8] * b[4]) + (a[9] * b[3]);
+ long c13 = (a[4] * b[9]) + (a[5] * b[8]) + (a[6] * b[7]) + (a[7] * b[6]) + (a[8] * b[5]) + (a[9] * b[4]);
+ long c14 = (a[5] * b[9]) + (a[6] * b[8]) + (a[7] * b[7]) + (a[8] * b[6]) + (a[9] * b[5]);
+ long c15 = (a[6] * b[9]) + (a[7] * b[8]) + (a[8] * b[7]) + (a[9] * b[6]);
+ long c16 = (a[7] * b[9]) + (a[8] * b[8]) + (a[9] * b[7]);
+ long c17 = (a[8] * b[9]) + (a[9] * b[8]);
+ long c18 = a[9] * b[9];
+
+ carryReduce(r, c0, c1, c2, c3, c4, c5, c6, c7, c8,
+ c9, c10, c11, c12, c13, c14, c15, c16, c17, c18);
+
+ }
+
+ private void carryReduce(long[] r, long c0, long c1, long c2,
+ long c3, long c4, long c5, long c6,
+ long c7, long c8, long c9, long c10,
+ long c11, long c12, long c13, long c14,
+ long c15, long c16, long c17, long c18) {
+ // reduce(7,2)
+ long reducedValue17 = (c17 * SUBTRAHEND);
+ c7 += (reducedValue17 << BIT_OFFSET) & LIMB_MASK;
+ c8 += reducedValue17 >> RIGHT_BIT_OFFSET;
+
+ long reducedValue18 = (c18 * SUBTRAHEND);
+ c8 += (reducedValue18 << BIT_OFFSET) & LIMB_MASK;
+ c9 += reducedValue18 >> RIGHT_BIT_OFFSET;
+
+ // carry(8,2)
+ long carry8 = carryValue(c8);
+ r[8] = c8 - (carry8 << BITS_PER_LIMB);
+ c9 += carry8;
+
+ long carry9 = carryValue(c9);
+ r[9] = c9 - (carry9 << BITS_PER_LIMB);
+ c10 += carry9;
+
+ // reduce(0,7)
+ long reducedValue10 = (c10 * SUBTRAHEND);
+ r[0] = c0 + ((reducedValue10 << BIT_OFFSET) & LIMB_MASK);
+ c1 += reducedValue10 >> RIGHT_BIT_OFFSET;
+
+ long reducedValue11 = (c11 * SUBTRAHEND);
+ r[1] = c1 + ((reducedValue11 << BIT_OFFSET) & LIMB_MASK);
+ c2 += reducedValue11 >> RIGHT_BIT_OFFSET;
+
+ long reducedValue12 = (c12 * SUBTRAHEND);
+ r[2] = c2 + ((reducedValue12 << BIT_OFFSET) & LIMB_MASK);
+ c3 += reducedValue12 >> RIGHT_BIT_OFFSET;
+
+ long reducedValue13 = (c13 * SUBTRAHEND);
+ r[3] = c3 + ((reducedValue13 << BIT_OFFSET) & LIMB_MASK);
+ c4 += reducedValue13 >> RIGHT_BIT_OFFSET;
+
+ long reducedValue14 = (c14 * SUBTRAHEND);
+ r[4] = c4 + ((reducedValue14 << BIT_OFFSET) & LIMB_MASK);
+ c5 += reducedValue14 >> RIGHT_BIT_OFFSET;
+
+ long reducedValue15 = (c15 * SUBTRAHEND);
+ r[5] = c5 + ((reducedValue15 << BIT_OFFSET) & LIMB_MASK);
+ c6 += reducedValue15 >> RIGHT_BIT_OFFSET;
+
+ long reducedValue16 = (c16 * SUBTRAHEND);
+ r[6] = c6 + ((reducedValue16 << BIT_OFFSET) & LIMB_MASK);
+ r[7] = c7 + (reducedValue16 >> RIGHT_BIT_OFFSET);
+
+ // carry(0,9)
+ carry(r, 0, 9);
+ }
+
+ protected void multByInt(long[] a, long b, long[] r) {
+ for (int i = 0; i < a.length; i++) {
+ r[i] = a[i] * b;
+ }
+
+ // carry(8, 2)
+ long carry8 = carryValue(r[8]);
+ r[8] -= (carry8 << BITS_PER_LIMB);
+ r[9] += carry8;
+
+ long carry9 = carryValue(r[9]);
+ r[9] -= (carry9 << BITS_PER_LIMB);
+
+ // reduce(0, 1)
+ long reducedValue10 = (carry9 * SUBTRAHEND);
+ r[0] += ((reducedValue10 << BIT_OFFSET) & LIMB_MASK);
+ r[1] += reducedValue10 >> RIGHT_BIT_OFFSET;
+
+ // carry(0, 9)
+ carry(r, 0, 9);
+ }
+
+ @Override
+ protected void square(long[] a, long[] r) {
+
+ // Use grade-school multiplication with a simple squaring optimization.
+ // Multiply into primitives to avoid the temporary array allocation.
+ // This is equivalent to the following code:
+ // long[] c = new long[2 * NUM_LIMBS - 1];
+ // for(int i = 0; i < NUM_LIMBS; i++) {
+ // c[2 * i] = a[i] * a[i];
+ // for(int j = i + 1; j < NUM_LIMBS; j++) {
+ // c[i + j] += 2 * a[i] * a[j]
+ // }
+ // }
+
+ long c0 = a[0] * a[0];
+ long c1 = 2 * a[0] * a[1];
+ long c2 = a[1] * a[1] + 2 * a[0] * a[2];
+ long c3 = 2 * (a[0] * a[3] + a[1] * a[2]);
+ long c4 = a[2] * a[2] + 2 * (a[0] * a[4] + a[1] * a[3]);
+ long c5 = 2 * (a[0] * a[5] + a[1] * a[4] + a[2] * a[3]);
+ long c6 = a[3] * a[3] + 2 * (a[0] * a[6] + a[1] * a[5] + a[2] * a[4]);
+ long c7 = 2 * (a[0] * a[7] + a[1] * a[6] + a[2] * a[5] + a[3] * a[4]);
+ long c8 = a[4] * a[4] + 2 * (a[0] * a[8] + a[1] * a[7] + a[2] * a[6] + a[3] * a[5]);
+ long c9 = 2 * (a[0] * a[9] + a[1] * a[8] + a[2] * a[7] + a[3] * a[6] + a[4] * a[5]);
+ long c10 = a[5] * a[5] + 2 * (a[1] * a[9] + a[2] * a[8] + a[3] * a[7] + a[4] * a[6]);
+ long c11 = 2 * (a[2] * a[9] + a[3] * a[8] + a[4] * a[7] + a[5] * a[6]);
+ long c12 = a[6] * a[6] + 2 * (a[3] * a[9] + a[4] * a[8] + a[5] * a[7]);
+ long c13 = 2 * (a[4] * a[9] + a[5] * a[8] + a[6] * a[7]);
+ long c14 = a[7] * a[7] + 2 * (a[5] * a[9] + a[6] * a[8]);
+ long c15 = 2 * (a[6] * a[9] + a[7] * a[8]);
+ long c16 = a[8] * a[8] + 2 * a[7] * a[9];
+ long c17 = 2 * a[8] * a[9];
+ long c18 = a[9] * a[9];
+
+ carryReduce(r, c0, c1, c2, c3, c4, c5, c6, c7, c8,
+ c9, c10, c11, c12, c13, c14, c15, c16, c17, c18);
+ }
+
+
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/java.base/share/classes/sun/security/util/math/intpoly/IntegerPolynomial448.java Tue May 08 09:21:51 2018 -0400
@@ -0,0 +1,236 @@
+/*
+ * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation. Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+package sun.security.util.math.intpoly;
+
+import java.math.BigInteger;
+
+public class IntegerPolynomial448 extends IntegerPolynomial {
+
+ private static final int POWER = 448;
+ private static final int NUM_LIMBS = 16;
+ private static final int BITS_PER_LIMB = 28;
+ public static final BigInteger MODULUS
+ = TWO.pow(POWER).subtract(TWO.pow(POWER / 2))
+ .subtract(BigInteger.valueOf(1));
+
+ public IntegerPolynomial448() {
+ super(BITS_PER_LIMB, NUM_LIMBS, MODULUS);
+ }
+
+ @Override
+ protected void mult(long[] a, long[] b, long[] r) {
+
+ // Use grade-school multiplication into primitives to avoid the
+ // temporary array allocation. This is equivalent to the following
+ // code:
+ // long[] c = new long[2 * NUM_LIMBS - 1];
+ // for(int i = 0; i < NUM_LIMBS; i++) {
+ // for(int j - 0; j < NUM_LIMBS; j++) {
+ // c[i + j] += a[i] * b[j]
+ // }
+ // }
+
+ long c0 = (a[0] * b[0]);
+ long c1 = (a[0] * b[1]) + (a[1] * b[0]);
+ long c2 = (a[0] * b[2]) + (a[1] * b[1]) + (a[2] * b[0]);
+ long c3 = (a[0] * b[3]) + (a[1] * b[2]) + (a[2] * b[1]) + (a[3] * b[0]);
+ long c4 = (a[0] * b[4]) + (a[1] * b[3]) + (a[2] * b[2]) + (a[3] * b[1]) + (a[4] * b[0]);
+ long c5 = (a[0] * b[5]) + (a[1] * b[4]) + (a[2] * b[3]) + (a[3] * b[2]) + (a[4] * b[1]) + (a[5] * b[0]);
+ long c6 = (a[0] * b[6]) + (a[1] * b[5]) + (a[2] * b[4]) + (a[3] * b[3]) + (a[4] * b[2]) + (a[5] * b[1]) + (a[6] * b[0]);
+ long c7 = (a[0] * b[7]) + (a[1] * b[6]) + (a[2] * b[5]) + (a[3] * b[4]) + (a[4] * b[3]) + (a[5] * b[2]) + (a[6] * b[1]) + (a[7] * b[0]);
+ long c8 = (a[0] * b[8]) + (a[1] * b[7]) + (a[2] * b[6]) + (a[3] * b[5]) + (a[4] * b[4]) + (a[5] * b[3]) + (a[6] * b[2]) + (a[7] * b[1]) + (a[8] * b[0]);
+ long c9 = (a[0] * b[9]) + (a[1] * b[8]) + (a[2] * b[7]) + (a[3] * b[6]) + (a[4] * b[5]) + (a[5] * b[4]) + (a[6] * b[3]) + (a[7] * b[2]) + (a[8] * b[1]) + (a[9] * b[0]);
+ long c10 = (a[0] * b[10]) + (a[1] * b[9]) + (a[2] * b[8]) + (a[3] * b[7]) + (a[4] * b[6]) + (a[5] * b[5]) + (a[6] * b[4]) + (a[7] * b[3]) + (a[8] * b[2]) + (a[9] * b[1]) + (a[10] * b[0]);
+ long c11 = (a[0] * b[11]) + (a[1] * b[10]) + (a[2] * b[9]) + (a[3] * b[8]) + (a[4] * b[7]) + (a[5] * b[6]) + (a[6] * b[5]) + (a[7] * b[4]) + (a[8] * b[3]) + (a[9] * b[2]) + (a[10] * b[1]) + (a[11] * b[0]);
+ long c12 = (a[0] * b[12]) + (a[1] * b[11]) + (a[2] * b[10]) + (a[3] * b[9]) + (a[4] * b[8]) + (a[5] * b[7]) + (a[6] * b[6]) + (a[7] * b[5]) + (a[8] * b[4]) + (a[9] * b[3]) + (a[10] * b[2]) + (a[11] * b[1]) + (a[12] * b[0]);
+ long c13 = (a[0] * b[13]) + (a[1] * b[12]) + (a[2] * b[11]) + (a[3] * b[10]) + (a[4] * b[9]) + (a[5] * b[8]) + (a[6] * b[7]) + (a[7] * b[6]) + (a[8] * b[5]) + (a[9] * b[4]) + (a[10] * b[3]) + (a[11] * b[2]) + (a[12] * b[1]) + (a[13] * b[0]);
+ long c14 = (a[0] * b[14]) + (a[1] * b[13]) + (a[2] * b[12]) + (a[3] * b[11]) + (a[4] * b[10]) + (a[5] * b[9]) + (a[6] * b[8]) + (a[7] * b[7]) + (a[8] * b[6]) + (a[9] * b[5]) + (a[10] * b[4]) + (a[11] * b[3]) + (a[12] * b[2]) + (a[13] * b[1]) + (a[14] * b[0]);
+ long c15 = (a[0] * b[15]) + (a[1] * b[14]) + (a[2] * b[13]) + (a[3] * b[12]) + (a[4] * b[11]) + (a[5] * b[10]) + (a[6] * b[9]) + (a[7] * b[8]) + (a[8] * b[7]) + (a[9] * b[6]) + (a[10] * b[5]) + (a[11] * b[4]) + (a[12] * b[3]) + (a[13] * b[2]) + (a[14] * b[1]) + (a[15] * b[0]);
+ long c16 = (a[1] * b[15]) + (a[2] * b[14]) + (a[3] * b[13]) + (a[4] * b[12]) + (a[5] * b[11]) + (a[6] * b[10]) + (a[7] * b[9]) + (a[8] * b[8]) + (a[9] * b[7]) + (a[10] * b[6]) + (a[11] * b[5]) + (a[12] * b[4]) + (a[13] * b[3]) + (a[14] * b[2]) + (a[15] * b[1]);
+ long c17 = (a[2] * b[15]) + (a[3] * b[14]) + (a[4] * b[13]) + (a[5] * b[12]) + (a[6] * b[11]) + (a[7] * b[10]) + (a[8] * b[9]) + (a[9] * b[8]) + (a[10] * b[7]) + (a[11] * b[6]) + (a[12] * b[5]) + (a[13] * b[4]) + (a[14] * b[3]) + (a[15] * b[2]);
+ long c18 = (a[3] * b[15]) + (a[4] * b[14]) + (a[5] * b[13]) + (a[6] * b[12]) + (a[7] * b[11]) + (a[8] * b[10]) + (a[9] * b[9]) + (a[10] * b[8]) + (a[11] * b[7]) + (a[12] * b[6]) + (a[13] * b[5]) + (a[14] * b[4]) + (a[15] * b[3]);
+ long c19 = (a[4] * b[15]) + (a[5] * b[14]) + (a[6] * b[13]) + (a[7] * b[12]) + (a[8] * b[11]) + (a[9] * b[10]) + (a[10] * b[9]) + (a[11] * b[8]) + (a[12] * b[7]) + (a[13] * b[6]) + (a[14] * b[5]) + (a[15] * b[4]);
+ long c20 = (a[5] * b[15]) + (a[6] * b[14]) + (a[7] * b[13]) + (a[8] * b[12]) + (a[9] * b[11]) + (a[10] * b[10]) + (a[11] * b[9]) + (a[12] * b[8]) + (a[13] * b[7]) + (a[14] * b[6]) + (a[15] * b[5]);
+ long c21 = (a[6] * b[15]) + (a[7] * b[14]) + (a[8] * b[13]) + (a[9] * b[12]) + (a[10] * b[11]) + (a[11] * b[10]) + (a[12] * b[9]) + (a[13] * b[8]) + (a[14] * b[7]) + (a[15] * b[6]);
+ long c22 = (a[7] * b[15]) + (a[8] * b[14]) + (a[9] * b[13]) + (a[10] * b[12]) + (a[11] * b[11]) + (a[12] * b[10]) + (a[13] * b[9]) + (a[14] * b[8]) + (a[15] * b[7]);
+ long c23 = (a[8] * b[15]) + (a[9] * b[14]) + (a[10] * b[13]) + (a[11] * b[12]) + (a[12] * b[11]) + (a[13] * b[10]) + (a[14] * b[9]) + (a[15] * b[8]);
+ long c24 = (a[9] * b[15]) + (a[10] * b[14]) + (a[11] * b[13]) + (a[12] * b[12]) + (a[13] * b[11]) + (a[14] * b[10]) + (a[15] * b[9]);
+ long c25 = (a[10] * b[15]) + (a[11] * b[14]) + (a[12] * b[13]) + (a[13] * b[12]) + (a[14] * b[11]) + (a[15] * b[10]);
+ long c26 = (a[11] * b[15]) + (a[12] * b[14]) + (a[13] * b[13]) + (a[14] * b[12]) + (a[15] * b[11]);
+ long c27 = (a[12] * b[15]) + (a[13] * b[14]) + (a[14] * b[13]) + (a[15] * b[12]);
+ long c28 = (a[13] * b[15]) + (a[14] * b[14]) + (a[15] * b[13]);
+ long c29 = (a[14] * b[15]) + (a[15] * b[14]);
+ long c30 = (a[15] * b[15]);
+
+ carryReduce(r, c0, c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12,
+ c13, c14, c15, c16, c17, c18, c19, c20, c21, c22, c23, c24, c25,
+ c26, c27, c28, c29, c30);
+ }
+
+ private void carryReduce(long[] r, long c0, long c1, long c2, long c3,
+ long c4, long c5, long c6, long c7, long c8,
+ long c9, long c10, long c11, long c12, long c13,
+ long c14, long c15, long c16, long c17, long c18,
+ long c19, long c20, long c21, long c22, long c23,
+ long c24, long c25, long c26, long c27, long c28,
+ long c29, long c30) {
+
+ // reduce(8, 7)
+ c8 += c24;
+ c16 += c24;
+
+ c9 += c25;
+ c17 += c25;
+
+ c10 += c26;
+ c18 += c26;
+
+ c11 += c27;
+ c19 += c27;
+
+ c12 += c28;
+ c20 += c28;
+
+ c13 += c29;
+ c21 += c29;
+
+ c14 += c30;
+ c22 += c30;
+
+ // reduce(4, 4)
+ r[4] = c4 + c20;
+ r[12] = c12 + c20;
+
+ r[5] = c5 + c21;
+ r[13] = c13 + c21;
+
+ r[6] = c6 + c22;
+ c14 += c22;
+
+ r[7] = c7 + c23;
+ c15 += c23;
+
+ //carry(14, 2)
+ long carry14 = carryValue(c14);
+ r[14] = c14 - (carry14 << BITS_PER_LIMB);
+ c15 += carry14;
+
+ long carry15 = carryValue(c15);
+ r[15] = c15 - (carry15 << BITS_PER_LIMB);
+ c16 += carry15;
+
+ // reduce(0, 4)
+ r[0] = c0 + c16;
+ r[8] = c8 + c16;
+
+ r[1] = c1 + c17;
+ r[9] = c9 + c17;
+
+ r[2] = c2 + c18;
+ r[10] = c10 + c18;
+
+ r[3] = c3 + c19;
+ r[11] = c11 + c19;
+
+ // carry(0, 15)
+ carry(r, 0, 15);
+ }
+
+ protected void multByInt(long[] a, long b, long[] r) {
+ for (int i = 0; i < a.length; i++) {
+ r[i] = a[i] * b;
+ }
+
+ // carry(14, 2)
+ long carry14 = carryValue(r[14]);
+ r[14] -= (carry14 << BITS_PER_LIMB);
+ r[15] += carry14;
+
+ long carry15 = carryValue(r[15]);
+ r[15] -= (carry15 << BITS_PER_LIMB);
+
+ // reduce(0, 1)
+ r[0] += carry15;
+ r[8] += carry15;
+
+ // carry(0, 15)
+ carry(r, 0, 15);
+ }
+
+ @Override
+ protected void square(long[] a, long[] r) {
+
+ // Use grade-school multiplication with a simple squaring optimization.
+ // Multiply into primitives to avoid the temporary array allocation.
+ // This is equivalent to the following code:
+ // long[] c = new long[2 * NUM_LIMBS - 1];
+ // for(int i = 0; i < NUM_LIMBS; i++) {
+ // c[2 * i] = a[i] * a[i];
+ // for(int j = i + 1; j < NUM_LIMBS; j++) {
+ // c[i + j] += 2 * a[i] * a[j]
+ // }
+ // }
+
+ long c0 = a[0] * a[0];
+ long c1 = 2 * a[0] * a[1];
+ long c2 = a[1] * a[1] + 2 * a[0] * a[2];
+ long c3 = 2 * (a[0] * a[3] + a[1] * a[2]);
+ long c4 = a[2] * a[2] + 2 * (a[0] * a[4] + a[1] * a[3]);
+ long c5 = 2 * (a[0] * a[5] + a[1] * a[4] + a[2] * a[3]);
+ long c6 = a[3] * a[3] + 2 * (a[0] * a[6] + a[1] * a[5] + a[2] * a[4]);
+ long c7 = 2 * (a[0] * a[7] + a[1] * a[6] + a[2] * a[5] + a[3] * a[4]);
+ long c8 = a[4] * a[4] + 2 * (a[0] * a[8] + a[1] * a[7] + a[2] * a[6] + a[3] * a[5]);
+ long c9 = 2 * (a[0] * a[9] + a[1] * a[8] + a[2] * a[7] + a[3] * a[6] + a[4] * a[5]);
+ long c10 = a[5] * a[5] + 2 * (a[0] * a[10] + a[1] * a[9] + a[2] * a[8] + a[3] * a[7] + a[4] * a[6]);
+ long c11 = 2 * (a[0] * a[11] + a[1] * a[10] + a[2] * a[9] + a[3] * a[8] + a[4] * a[7] + a[5] * a[6]);
+ long c12 = a[6] * a[6] + 2 * (a[0] * a[12] + a[1] * a[11] + a[2] * a[10] + a[3] * a[9] + a[4] * a[8] + a[5] * a[7]);
+ long c13 = 2 * (a[0] * a[13] + a[1] * a[12] + a[2] * a[11] + a[3] * a[10] + a[4] * a[9] + a[5] * a[8] + a[6] * a[7]);
+ long c14 = a[7] * a[7] + 2 * (a[0] * a[14] + a[1] * a[13] + a[2] * a[12] + a[3] * a[11] + a[4] * a[10] + a[5] * a[9] + a[6] * a[8]);
+ long c15 = 2 * (a[0] * a[15] + a[1] * a[14] + a[2] * a[13] + a[3] * a[12] + a[4] * a[11] + a[5] * a[10] + a[6] * a[9] + a[7] * a[8]);
+ long c16 = a[8] * a[8] + 2 * (a[1] * a[15] + a[2] * a[14] + a[3] * a[13] + a[4] * a[12] + a[5] * a[11] + a[6] * a[10] + a[7] * a[9]);
+ long c17 = 2 * (a[2] * a[15] + a[3] * a[14] + a[4] * a[13] + a[5] * a[12] + a[6] * a[11] + a[7] * a[10] + a[8] * a[9]);
+ long c18 = a[9] * a[9] + 2 * (a[3] * a[15] + a[4] * a[14] + a[5] * a[13] + a[6] * a[12] + a[7] * a[11] + a[8] * a[10]);
+ long c19 = 2 * (a[4] * a[15] + a[5] * a[14] + a[6] * a[13] + a[7] * a[12] + a[8] * a[11] + a[9] * a[10]);
+ long c20 = a[10] * a[10] + 2 * (a[5] * a[15] + a[6] * a[14] + a[7] * a[13] + a[8] * a[12] + a[9] * a[11]);
+ long c21 = 2 * (a[6] * a[15] + a[7] * a[14] + a[8] * a[13] + a[9] * a[12] + a[10] * a[11]);
+ long c22 = a[11] * a[11] + 2 * (a[7] * a[15] + a[8] * a[14] + a[9] * a[13] + a[10] * a[12]);
+ long c23 = 2 * (a[8] * a[15] + a[9] * a[14] + a[10] * a[13] + a[11] * a[12]);
+ long c24 = a[12] * a[12] + 2 * (a[9] * a[15] + a[10] * a[14] + a[11] * a[13]);
+ long c25 = 2 * (a[10] * a[15] + a[11] * a[14] + a[12] * a[13]);
+ long c26 = a[13] * a[13] + 2 * (a[11] * a[15] + a[12] * a[14]);
+ long c27 = 2 * (a[12] * a[15] + a[13] * a[14]);
+ long c28 = a[14] * a[14] + 2 * a[13] * a[15];
+ long c29 = 2 * a[14] * a[15];
+ long c30 = a[15] * a[15];
+
+ carryReduce(r, c0, c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12,
+ c13, c14, c15, c16, c17, c18, c19, c20, c21, c22, c23, c24, c25,
+ c26, c27, c28, c29, c30);
+
+ }
+
+
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/test/jdk/sun/security/util/math/BigIntegerModuloP.java Tue May 08 09:21:51 2018 -0400
@@ -0,0 +1,273 @@
+/*
+ * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation. Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+import sun.security.util.math.*;
+
+import java.math.BigInteger;
+import java.nio.ByteBuffer;
+
+/**
+ * Arithmetic in the field of integers modulo a prime value implemented using
+ * BigInteger. This implementation is very versatile, but it is slow and none
+ * of the operations are value-independent. This class is intended for use in
+ * testing and prototyping, and production code should probably use a more
+ * specialized arithmetic implementation.
+ */
+
+public class BigIntegerModuloP implements IntegerFieldModuloP {
+
+ private final BigInteger p;
+
+ public BigIntegerModuloP(BigInteger p) {
+ this.p = p;
+ }
+
+ @Override
+ public BigInteger getSize() {
+ return p;
+ }
+
+ @Override
+ public ImmutableElement get0() {
+ return new ImmutableElement(BigInteger.ZERO);
+ }
+ @Override
+ public ImmutableElement get1() {
+ return new ImmutableElement(BigInteger.ONE);
+ }
+ @Override
+ public ImmutableElement getElement(BigInteger v) {
+ return new ImmutableElement(v);
+ }
+ @Override
+ public ImmutableElement getElement(byte[] v, int offset, int length,
+ byte highByte) {
+ byte[] bigIntIn = new byte[length + 1];
+ System.arraycopy(v, offset, bigIntIn, 0, length);
+ bigIntIn[length] = highByte;
+ reverse(bigIntIn);
+ return new ImmutableElement(new BigInteger(1, bigIntIn).mod(getSize()));
+ }
+ @Override
+ public SmallValue getSmallValue(int i) {
+ return new SmallElement(i);
+ }
+
+ private abstract class Element implements IntegerModuloP {
+
+ protected BigInteger v;
+
+ protected Element(BigInteger v) {
+ this.v = v;
+ }
+
+ protected Element(boolean v) {
+ this.v = BigInteger.valueOf(v ? 1 : 0);
+ }
+
+ private BigInteger getModulus() {
+ return getField().getSize();
+ }
+
+ @Override
+ public IntegerFieldModuloP getField() {
+ return BigIntegerModuloP.this;
+ }
+
+ @Override
+ public BigInteger asBigInteger() {
+ return v;
+ }
+
+ @Override
+ public MutableElement mutable() {
+ return new MutableElement(v);
+ }
+
+ @Override
+ public ImmutableElement fixed() {
+ return new ImmutableElement(v);
+ }
+
+ @Override
+ public ImmutableElement add(IntegerModuloP b) {
+ return new ImmutableElement(
+ v.add(b.asBigInteger()).mod(getModulus()));
+ }
+
+ @Override
+ public ImmutableElement additiveInverse() {
+ return new ImmutableElement(v.negate().mod(getModulus()));
+ }
+
+ @Override
+ public ImmutableElement multiply(IntegerModuloP b) {
+ return new ImmutableElement(
+ v.multiply(b.asBigInteger()).mod(getModulus()));
+ }
+
+ @Override
+ public void addModPowerTwo(IntegerModuloP arg, byte[] result) {
+ BigInteger biThis = asBigInteger();
+ BigInteger biArg = arg.asBigInteger();
+ bigIntAsByteArray(biThis.add(biArg), result);
+ }
+
+ private void bigIntAsByteArray(BigInteger arg, byte[] result) {
+ byte[] bytes = arg.toByteArray();
+ // bytes is backwards and possibly too big
+ // Copy the low-order bytes into result in reverse
+ int sourceIndex = bytes.length - 1;
+ for (int i = 0; i < result.length; i++) {
+ if (sourceIndex >= 0) {
+ result[i] = bytes[sourceIndex--];
+ } else {
+ result[i] = 0;
+ }
+ }
+ }
+
+ @Override
+ public void asByteArray(byte[] result) {
+ bigIntAsByteArray(v, result);
+ }
+ }
+
+ private class ImmutableElement extends Element
+ implements ImmutableIntegerModuloP {
+
+ private ImmutableElement(BigInteger v) {
+ super(v);
+ }
+ }
+
+ private class MutableElement extends Element
+ implements MutableIntegerModuloP {
+
+ private MutableElement(BigInteger v) {
+ super(v);
+ }
+
+ @Override
+ public void conditionalSwapWith(MutableIntegerModuloP b, int swap) {
+ if (swap == 1) {
+ BigInteger temp = v;
+ v = b.asBigInteger();
+ ((Element) b).v = temp;
+ }
+ }
+
+ @Override
+ public MutableElement setValue(IntegerModuloP v) {
+ this.v = ((Element) v).v;
+
+ return this;
+ }
+
+ @Override
+ public MutableElement setValue(byte[] arr, int offset, int length,
+ byte highByte) {
+ byte[] bigIntIn = new byte[length + 1];
+ System.arraycopy(arr, offset, bigIntIn, 0, length);
+ bigIntIn[length] = highByte;
+ reverse(bigIntIn);
+ v = new BigInteger(bigIntIn).mod(getSize());
+
+ return this;
+ }
+
+ @Override
+ public MutableElement setValue(ByteBuffer buf, int length,
+ byte highByte) {
+ byte[] bigIntIn = new byte[length + 1];
+ buf.get(bigIntIn, 0, length);
+ bigIntIn[length] = highByte;
+ reverse(bigIntIn);
+ v = new BigInteger(bigIntIn).mod(getSize());
+
+ return this;
+ }
+
+ @Override
+ public MutableElement setSquare() {
+ v = v.multiply(v).mod(getSize());
+ return this;
+ }
+
+ @Override
+ public MutableElement setProduct(IntegerModuloP b) {
+ Element other = (Element) b;
+ v = v.multiply(other.v).mod(getSize());
+ return this;
+ }
+
+ @Override
+ public MutableElement setProduct(SmallValue value) {
+ BigInteger bigIntValue = ((SmallElement) value).asBigInteger();
+ v = v.multiply(bigIntValue).mod(getSize());
+ return this;
+ }
+
+ @Override
+ public MutableElement setSum(IntegerModuloP b) {
+ Element other = (Element) b;
+ v = v.add(other.v).mod(getSize());
+ return this;
+ }
+
+ @Override
+ public MutableElement setDifference(IntegerModuloP b) {
+ Element other = (Element) b;
+ v = v.subtract(other.v).mod(getSize());
+ return this;
+ }
+
+ }
+
+ private class SmallElement extends ImmutableElement implements SmallValue {
+
+ public SmallElement(int v) {
+ super(BigInteger.valueOf(v).mod(getSize()));
+ }
+ }
+
+ private static void swap(byte[] arr, int i, int j) {
+ byte tmp = arr[i];
+ arr[i] = arr[j];
+ arr[j] = tmp;
+ }
+
+ private static void reverse(byte [] arr) {
+ int i = 0;
+ int j = arr.length - 1;
+
+ while (i < j) {
+ swap(arr, i, j);
+ i++;
+ j--;
+ }
+ }
+
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/test/jdk/sun/security/util/math/TestIntegerModuloP.java Tue May 08 09:21:51 2018 -0400
@@ -0,0 +1,377 @@
+/*
+ * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * @test
+ * @bug 8181594
+ * @summary Test proper operation of integer field arithmetic
+ * @modules java.base/sun.security.util java.base/sun.security.util.math java.base/sun.security.util.math.intpoly
+ * @build BigIntegerModuloP
+ * @run main TestIntegerModuloP sun.security.util.math.intpoly.IntegerPolynomial25519 32 0
+ * @run main TestIntegerModuloP sun.security.util.math.intpoly.IntegerPolynomial448 56 1
+ * @run main TestIntegerModuloP sun.security.util.math.intpoly.IntegerPolynomial1305 16 2
+ */
+
+import sun.security.util.math.*;
+import java.util.function.*;
+
+import java.util.*;
+import java.math.*;
+import java.nio.*;
+
+public class TestIntegerModuloP {
+
+ static BigInteger TWO = BigInteger.valueOf(2);
+
+ // The test has a list of functions, and it selects randomly from that list
+
+ // The function types
+ interface ElemFunction extends BiFunction
+ <MutableIntegerModuloP, IntegerModuloP, IntegerModuloP> { }
+ interface ElemArrayFunction extends BiFunction
+ <MutableIntegerModuloP, IntegerModuloP, byte[]> { }
+ interface TriConsumer <T, U, V> {
+ void accept(T t, U u, V v);
+ }
+ interface ElemSetFunction extends TriConsumer
+ <MutableIntegerModuloP, IntegerModuloP, byte[]> { }
+
+ // The lists of functions. Multiple lists are needed because the test
+ // respects the limitations of the arithmetic implementations.
+ static final List<ElemFunction> ADD_FUNCTIONS = new ArrayList<>();
+ static final List<ElemFunction> MULT_FUNCTIONS = new ArrayList<>();
+ static final List<ElemArrayFunction> ARRAY_FUNCTIONS = new ArrayList<>();
+ static final List<ElemSetFunction> SET_FUNCTIONS = new ArrayList<>();
+
+ static void setUpFunctions(IntegerFieldModuloP field, int length) {
+
+ ADD_FUNCTIONS.clear();
+ MULT_FUNCTIONS.clear();
+ SET_FUNCTIONS.clear();
+ ARRAY_FUNCTIONS.clear();
+
+ byte highByte = (byte)
+ (field.getSize().bitLength() > length * 8 ? 1 : 0);
+
+ // add functions are (im)mutable add/subtract
+ ADD_FUNCTIONS.add(IntegerModuloP::add);
+ ADD_FUNCTIONS.add(IntegerModuloP::subtract);
+ ADD_FUNCTIONS.add(MutableIntegerModuloP::setSum);
+ ADD_FUNCTIONS.add(MutableIntegerModuloP::setDifference);
+ // also include functions that return the first/second argument
+ ADD_FUNCTIONS.add((a, b) -> a);
+ ADD_FUNCTIONS.add((a, b) -> b);
+
+ // mult functions are (im)mutable multiply and square
+ MULT_FUNCTIONS.add(IntegerModuloP::multiply);
+ MULT_FUNCTIONS.add((a, b) -> a.square());
+ MULT_FUNCTIONS.add((a, b) -> b.square());
+ MULT_FUNCTIONS.add(MutableIntegerModuloP::setProduct);
+ MULT_FUNCTIONS.add((a, b) -> a.setSquare());
+ // also test multiplication by a small value
+ MULT_FUNCTIONS.add((a, b) -> a.setProduct(b.getField().getSmallValue(
+ b.asBigInteger().mod(BigInteger.valueOf(262144)).intValue())));
+
+ // set functions are setValue with various argument types
+ SET_FUNCTIONS.add((a, b, c) -> a.setValue(b));
+ SET_FUNCTIONS.add((a, b, c) ->
+ a.setValue(c, 0, c.length, (byte) 0));
+ SET_FUNCTIONS.add((a, b, c) ->
+ a.setValue(ByteBuffer.wrap(c, 0, c.length).order(ByteOrder.LITTLE_ENDIAN),
+ c.length, highByte));
+
+ // array functions return the (possibly modified) value as byte array
+ ARRAY_FUNCTIONS.add((a, b ) -> a.asByteArray(length));
+ ARRAY_FUNCTIONS.add((a, b) -> a.addModPowerTwo(b, length));
+ }
+
+ public static void main(String[] args) {
+
+ String className = args[0];
+ final int length = Integer.parseInt(args[1]);
+ int seed = Integer.parseInt(args[2]);
+
+ Class<IntegerFieldModuloP> fieldBaseClass = IntegerFieldModuloP.class;
+ try {
+ Class<? extends IntegerFieldModuloP> clazz =
+ Class.forName(className).asSubclass(fieldBaseClass);
+ IntegerFieldModuloP field =
+ clazz.getDeclaredConstructor().newInstance();
+
+ setUpFunctions(field, length);
+
+ runFieldTest(field, length, seed);
+ } catch (Exception ex) {
+ throw new RuntimeException(ex);
+ }
+
+ System.out.println("All tests passed");
+ }
+
+
+ static void assertEqual(IntegerModuloP e1, IntegerModuloP e2) {
+
+ if (!e1.asBigInteger().equals(e2.asBigInteger())) {
+ throw new RuntimeException("values not equal: "
+ + e1.asBigInteger() + " != " + e2.asBigInteger());
+ }
+ }
+
+ // A class that holds pairs of actual/expected values, and allows
+ // computation on these pairs.
+ static class TestPair<T extends IntegerModuloP> {
+ private final T test;
+ private final T baseline;
+
+ public TestPair(T test, T baseline) {
+ this.test = test;
+ this.baseline = baseline;
+ }
+
+ public T getTest() {
+ return test;
+ }
+ public T getBaseline() {
+ return baseline;
+ }
+
+ private void assertEqual() {
+ TestIntegerModuloP.assertEqual(test, baseline);
+ }
+
+ public TestPair<MutableIntegerModuloP> mutable() {
+ return new TestPair<>(test.mutable(), baseline.mutable());
+ }
+
+ public
+ <R extends IntegerModuloP, X extends IntegerModuloP>
+ TestPair<X> apply(BiFunction<T, R, X> func, TestPair<R> right) {
+ X testResult = func.apply(test, right.test);
+ X baselineResult = func.apply(baseline, right.baseline);
+ return new TestPair(testResult, baselineResult);
+ }
+
+ public
+ <U extends IntegerModuloP, V>
+ void apply(TriConsumer<T, U, V> func, TestPair<U> right, V argV) {
+ func.accept(test, right.test, argV);
+ func.accept(baseline, right.baseline, argV);
+ }
+
+ public
+ <R extends IntegerModuloP>
+ void applyAndCheckArray(BiFunction<T, R, byte[]> func,
+ TestPair<R> right) {
+ byte[] testResult = func.apply(test, right.test);
+ byte[] baselineResult = func.apply(baseline, right.baseline);
+ if (!Arrays.equals(testResult, baselineResult)) {
+ throw new RuntimeException("Array values do not match: "
+ + byteArrayToHexString(testResult) + " != "
+ + byteArrayToHexString(baselineResult));
+ }
+ }
+
+ }
+
+ static String byteArrayToHexString(byte[] arr) {
+ StringBuilder result = new StringBuilder();
+ for (int i = 0; i < arr.length; ++i) {
+ byte curVal = arr[i];
+ result.append(Character.forDigit(curVal >> 4 & 0xF, 16));
+ result.append(Character.forDigit(curVal & 0xF, 16));
+ }
+ return result.toString();
+ }
+
+ static TestPair<IntegerModuloP>
+ applyAndCheck(ElemFunction func, TestPair<MutableIntegerModuloP> left,
+ TestPair<IntegerModuloP> right) {
+
+ TestPair<IntegerModuloP> result = left.apply(func, right);
+ result.assertEqual();
+ left.assertEqual();
+ right.assertEqual();
+
+ return result;
+ }
+
+ static void
+ setAndCheck(ElemSetFunction func, TestPair<MutableIntegerModuloP> left,
+ TestPair<IntegerModuloP> right, byte[] argV) {
+
+ left.apply(func, right, argV);
+ left.assertEqual();
+ right.assertEqual();
+ }
+
+ static TestPair<MutableIntegerModuloP>
+ applyAndCheckMutable(ElemFunction func,
+ TestPair<MutableIntegerModuloP> left,
+ TestPair<IntegerModuloP> right) {
+
+ TestPair<IntegerModuloP> result = applyAndCheck(func, left, right);
+
+ TestPair<MutableIntegerModuloP> mutableResult = result.mutable();
+ mutableResult.assertEqual();
+ result.assertEqual();
+ left.assertEqual();
+ right.assertEqual();
+
+ return mutableResult;
+ }
+
+ static void
+ cswapAndCheck(int swap, TestPair<MutableIntegerModuloP> left,
+ TestPair<MutableIntegerModuloP> right) {
+
+ left.getTest().conditionalSwapWith(right.getTest(), swap);
+ left.getBaseline().conditionalSwapWith(right.getBaseline(), swap);
+
+ left.assertEqual();
+ right.assertEqual();
+
+ }
+
+ // Request arithmetic that should overflow, and ensure that overflow is
+ // detected.
+ static void runOverflowTest(TestPair<IntegerModuloP> elem) {
+
+ TestPair<MutableIntegerModuloP> mutableElem = elem.mutable();
+
+ try {
+ for (int i = 0; i < 1000; i++) {
+ applyAndCheck(MutableIntegerModuloP::setSum, mutableElem, elem);
+ }
+ applyAndCheck(MutableIntegerModuloP::setProduct, mutableElem, elem);
+ } catch (ArithmeticException ex) {
+ // this is expected
+ }
+
+ mutableElem = elem.mutable();
+ try {
+ for (int i = 0; i < 1000; i++) {
+ elem = applyAndCheck(IntegerModuloP::add,
+ mutableElem, elem);
+ }
+ applyAndCheck(IntegerModuloP::multiply, mutableElem, elem);
+ } catch (ArithmeticException ex) {
+ // this is expected
+ }
+ }
+
+ // Run a large number of random operations and ensure that
+ // results are correct
+ static void runOperationsTest(Random random, int length,
+ TestPair<IntegerModuloP> elem,
+ TestPair<IntegerModuloP> right) {
+
+ TestPair<MutableIntegerModuloP> left = elem.mutable();
+
+ for (int i = 0; i < 10000; i++) {
+
+ ElemFunction addFunc1 =
+ ADD_FUNCTIONS.get(random.nextInt(ADD_FUNCTIONS.size()));
+ TestPair<MutableIntegerModuloP> result1 =
+ applyAndCheckMutable(addFunc1, left, right);
+
+ // left could have been modified, so turn it back into a summand
+ applyAndCheckMutable((a, b) -> a.setSquare(), left, right);
+
+ ElemFunction addFunc2 =
+ ADD_FUNCTIONS.get(random.nextInt(ADD_FUNCTIONS.size()));
+ TestPair<IntegerModuloP> result2 =
+ applyAndCheck(addFunc2, left, right);
+
+ ElemFunction multFunc2 =
+ MULT_FUNCTIONS.get(random.nextInt(MULT_FUNCTIONS.size()));
+ TestPair<MutableIntegerModuloP> multResult =
+ applyAndCheckMutable(multFunc2, result1, result2);
+
+ int swap = random.nextInt(2);
+ cswapAndCheck(swap, left, multResult);
+
+ ElemSetFunction setFunc =
+ SET_FUNCTIONS.get(random.nextInt(SET_FUNCTIONS.size()));
+ byte[] valueArr = new byte[length];
+ random.nextBytes(valueArr);
+ setAndCheck(setFunc, result1, result2, valueArr);
+
+ // left could have been modified, so to turn it back into a summand
+ applyAndCheckMutable((a, b) -> a.setSquare(), left, right);
+
+ ElemArrayFunction arrayFunc =
+ ARRAY_FUNCTIONS.get(random.nextInt(ARRAY_FUNCTIONS.size()));
+ left.applyAndCheckArray(arrayFunc, right);
+ }
+ }
+
+ // Run all the tests for a given field
+ static void runFieldTest(IntegerFieldModuloP testField,
+ int length, int seed) {
+ System.out.println("Testing: " + testField.getClass().getSimpleName());
+
+ Random random = new Random(seed);
+
+ IntegerFieldModuloP baselineField =
+ new BigIntegerModuloP(testField.getSize());
+
+ int numBits = testField.getSize().bitLength();
+ BigInteger r =
+ new BigInteger(numBits, random).mod(testField.getSize());
+ TestPair<IntegerModuloP> rand =
+ new TestPair(testField.getElement(r), baselineField.getElement(r));
+
+ runOverflowTest(rand);
+
+ // check combinations of operations for different kinds of elements
+ List<TestPair<IntegerModuloP>> testElements = new ArrayList<>();
+ testElements.add(rand);
+ testElements.add(new TestPair(testField.get0(), baselineField.get0()));
+ testElements.add(new TestPair(testField.get1(), baselineField.get1()));
+ byte[] testArr = {121, 37, -100, -5, 76, 33};
+ testElements.add(new TestPair(testField.getElement(testArr),
+ baselineField.getElement(testArr)));
+
+ testArr = new byte[length];
+ random.nextBytes(testArr);
+ testElements.add(new TestPair(testField.getElement(testArr),
+ baselineField.getElement(testArr)));
+
+ random.nextBytes(testArr);
+ byte highByte = (byte) (numBits > length * 8 ? 1 : 0);
+ testElements.add(
+ new TestPair(
+ testField.getElement(testArr, 0, testArr.length, highByte),
+ baselineField.getElement(testArr, 0, testArr.length, highByte)
+ )
+ );
+
+ for (int i = 0; i < testElements.size(); i++) {
+ for (int j = 0; j < testElements.size(); j++) {
+ runOperationsTest(random, length, testElements.get(i),
+ testElements.get(j));
+ }
+ }
+ }
+}
+