Hi, Here is the proper RFR for 8208648: ECC Field Arithmetic Enhancements
Sorry for the confusion Bug: https://bugs.openjdk.java.net/browse/JDK-8208648 Original: http://hg.openjdk.java.net/jdk/jdk/rev/746602d9682f Webrev: http://cr.openjdk.java.net/~phh/8208648/webrev.8u.00/ JDK-8208648 is marked as jdk8u-critical-yes This is the second of a chain of three patches, JDK-8181594, JDK-8208648 and JDK-8208698 I will be sending today. The patch did not apply cleanly. The following conflicts appeared: sun/security/util/ArrayUtil.java is not present in jdk8u. ArrayUtil is a utility class with static methods. I created the file but only with the static methods that were required for this patch (all of them were included in the original patch). sun/security/util/math/intpoly/IntegerPolynomial1305.java had a minor conflict due to mismatching of the context lines sun/security/util/math/intpoly/IntegerPolynomial.java had significant amount of rejections, but they were mostly easy to fix, caused by context mismatching. Additionally, some of the new implementations of IntegerPolynomial contained an @Override for a method (finalCarryReduceLast) that is not present in the jdk8u version of IntegerPolynomial.java, so I removed the annotation. Below are the relevant changes I've done to resolve the rejects and compilation errors. Thanks, David diff --git a/src/jdk/src/share/classes/sun/security/util/ArrayUtil.java b/src/jdk/src/share/classes/sun/security/util/ArrayUtil.java new file mode 100644 index 00000000..5e5fc0aa --- /dev/null +++ b/src/jdk/src/share/classes/sun/security/util/ArrayUtil.java @@ -0,0 +1,51 @@ +/* + * 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; + +/** + * This class holds the various utility methods for array range checks. + */ + +public final class ArrayUtil { + + private static void swap(byte[] arr, int i, int j) { + byte tmp = arr[i]; + arr[i] = arr[j]; + arr[j] = tmp; + } + + public static void reverse(byte [] arr) { + int i = 0; + int j = arr.length - 1; + + while (i < j) { + swap(arr, i, j); + i++; + j--; + } + } +} + diff --git a/src/jdk/src/share/classes/sun/security/util/math/intpoly/IntegerPolynomial.java b/src/jdk/src/share/classes/sun/security/util/math/intpoly/IntegerPolynomial.java index 1846b9cb..c0eef1f4 100644 --- a/src/jdk/src/share/classes/sun/security/util/math/intpoly/IntegerPolynomial.java +++ b/src/jdk/src/share/classes/sun/security/util/math/intpoly/IntegerPolynomial.java @@ -66,9 +66,25 @@ public abstract class IntegerPolynomial implements IntegerFieldModuloP { protected final int numLimbs; private final BigInteger modulus; protected final int bitsPerLimb; + private final int maxAdds; - // must work when a==r - protected abstract void multByInt(long[] a, long b, long[] r); + /** + * Reduce an IntegerPolynomial representation (a) and store the result + * in a. Requires that a.length == numLimbs. + */ + protected abstract void reduce(long[] a); + + /** + * Multiply an IntegerPolynomial representation (a) with a long (b) and + * store the result in an IntegerPolynomial representation in a. Requires + * that a.length == numLimbs. + */ + protected void multByInt(long[] a, long b) { + for (int i = 0; i < a.length; i++) { + a[i] *= b; + } + reduce(a); + } // must work when a==r protected abstract void mult(long[] a, long[] b, long[] r); @@ -78,12 +94,14 @@ public abstract class IntegerPolynomial implements IntegerFieldModuloP { IntegerPolynomial(int bitsPerLimb, int numLimbs, + int maxAdds, BigInteger modulus) { this.numLimbs = numLimbs; this.modulus = modulus; this.bitsPerLimb = bitsPerLimb; + this.maxAdds = maxAdds; } protected int getNumLimbs() { @@ -300,6 +318,27 @@ public abstract class IntegerPolynomial implements IntegerFieldModuloP { } } + /** + * Branch-free conditional assignment of b to a. Requires that set is 0 or + * 1, and that a.length == b.length. If set==0, then the values of a and b + * will be unchanged. If set==1, then the values of b will be assigned to a. + * The behavior is undefined if swap has any value other than 0 or 1. + */ + protected static void conditionalAssign(int set, long[] a, long[] b) { + int maskValue = 0 - set; + for (int i = 0; i < a.length; i++) { + long dummyLimbs = maskValue & (a[i] ^ b[i]); + a[i] = dummyLimbs ^ a[i]; + } + } + + /** + * Branch-free conditional swap of a and b. Requires that swap is 0 or 1, + * and that a.length == b.length. If swap==0, then the values of a and b + * will be unchanged. If swap==1, then the values of a and b will be + * swapped. The behavior is undefined if swap has any value other than + * 0 or 1. + */ protected static void conditionalSwap(int swap, long[] a, long[] b) { int maskValue = 0 - swap; for (int i = 0; i < a.length; i++) { @@ -428,43 +467,52 @@ public abstract class IntegerPolynomial implements IntegerFieldModuloP { long[] newLimbs = new long[limbs.length]; mult(limbs, b.limbs, newLimbs); - return new ImmutableElement(newLimbs, true); + return new ImmutableElement(newLimbs, 0); } @Override public ImmutableElement square() { long[] newLimbs = new long[limbs.length]; IntegerPolynomial.this.square(limbs, newLimbs); - return new ImmutableElement(newLimbs, true); + return new ImmutableElement(newLimbs, 0); } public void addModPowerTwo(IntegerModuloP arg, byte[] result) { - if (!summand) { + Element other = (Element) arg; + if (!(isSummand() && other.isSummand())) { throw new ArithmeticException("Not a valid summand"); } - Element other = (Element) arg; addLimbsModPowerTwo(limbs, other.limbs, result); } public void asByteArray(byte[] result) { - if (!summand) { + if (!isSummand()) { throw new ArithmeticException("Not a valid summand"); } limbsToByteArray(limbs, result); } } - private class MutableElement extends Element + protected class MutableElement extends Element implements MutableIntegerModuloP { - protected MutableElement(long[] limbs, boolean summand) { - super(limbs, summand); + protected MutableElement(long[] limbs, int numAdds) { + super(limbs, numAdds); } @Override public ImmutableElement fixed() { - return new ImmutableElement(limbs.clone(), summand); + return new ImmutableElement(limbs.clone(), numAdds); + } + + @Override + public void conditionalSet(IntegerModuloP b, int set) { + + Element other = (Element) b; + + conditionalAssign(set, limbs, other.limbs); + numAdds = other.numAdds; } @Override diff --git a/src/jdk/src/share/classes/sun/security/util/math/intpoly/IntegerPolynomial1305.java b/src/jdk/src/share/classes/sun/security/util/math/intpoly/IntegerPolynomial1305.java index 2b33ceb2..5cc1dea2 100644 --- a/src/jdk/src/share/classes/sun/security/util/math/intpoly/IntegerPolynomial1305.java +++ b/src/jdk/src/share/classes/sun/security/util/math/intpoly/IntegerPolynomial1305.java @@ -59,7 +59,7 @@ public class IntegerPolynomial1305 extends IntegerPolynomial { } public IntegerPolynomial1305() { - super(BITS_PER_LIMB, NUM_LIMBS, MODULUS); + super(BITS_PER_LIMB, NUM_LIMBS, 1, MODULUS); posModLimbs = setPosModLimbs(); } diff --git a/src/jdk/src/share/classes/sun/security/util/math/intpoly/IntegerPolynomialP256.java b/src/jdk/src/share/classes/sun/security/util/math/intpoly/IntegerPolynomialP256.java index e364db1a..b3591e0c 100644 --- a/src/jdk/src/share/classes/sun/security/util/math/intpoly/IntegerPolynomialP256.java +++ b/src/jdk/src/share/classes/sun/security/util/math/intpoly/IntegerPolynomialP256.java @@ -50,7 +50,7 @@ public class IntegerPolynomialP256 extends IntegerPolynomial { result = result.subtract(BigInteger.valueOf(1)); return result; } - @Override + protected void finalCarryReduceLast(long[] limbs) { long c = limbs[9] >> 22; limbs[9] -= c << 22; diff --git a/src/jdk/src/share/classes/sun/security/util/math/intpoly/IntegerPolynomialP384.java b/src/jdk/src/share/classes/sun/security/util/math/intpoly/IntegerPolynomialP384.java index 91c3bab5..a726bbe8 100644 --- a/src/jdk/src/share/classes/sun/security/util/math/intpoly/IntegerPolynomialP384.java +++ b/src/jdk/src/share/classes/sun/security/util/math/intpoly/IntegerPolynomialP384.java @@ -50,7 +50,7 @@ public class IntegerPolynomialP384 extends IntegerPolynomial { result = result.subtract(BigInteger.valueOf(1)); return result; } - @Override + protected void finalCarryReduceLast(long[] limbs) { long c = limbs[13] >> 20; limbs[13] -= c << 20; diff --git a/src/jdk/src/share/classes/sun/security/util/math/intpoly/IntegerPolynomialP521.java b/src/jdk/src/share/classes/sun/security/util/math/intpoly/IntegerPolynomialP521.java index 7899b62e..38fe2ef4 100644 --- a/src/jdk/src/share/classes/sun/security/util/math/intpoly/IntegerPolynomialP521.java +++ b/src/jdk/src/share/classes/sun/security/util/math/intpoly/IntegerPolynomialP521.java @@ -47,7 +47,7 @@ public class IntegerPolynomialP521 extends IntegerPolynomial { result = result.subtract(BigInteger.valueOf(1)); return result; } - @Override + protected void finalCarryReduceLast(long[] limbs) { long c = limbs[18] >> 17; limbs[18] -= c << 17; diff --git a/src/jdk/src/share/classes/sun/security/util/math/intpoly/P256OrderField.java b/src/jdk/src/share/classes/sun/security/util/math/intpoly/P256OrderField.java index 5831d12e..f43d4cfe 100644 --- a/src/jdk/src/share/classes/sun/security/util/math/intpoly/P256OrderField.java +++ b/src/jdk/src/share/classes/sun/security/util/math/intpoly/P256OrderField.java @@ -53,7 +53,7 @@ public class P256OrderField extends IntegerPolynomial { result = result.subtract(BigInteger.valueOf(2).pow(208).multiply(BigInteger.valueOf(65536))); return result; } - @Override + protected void finalCarryReduceLast(long[] limbs) { long c = limbs[9] >> 22; limbs[9] -= c << 22; diff --git a/src/jdk/src/share/classes/sun/security/util/math/intpoly/P384OrderField.java b/src/jdk/src/share/classes/sun/security/util/math/intpoly/P384OrderField.java index 249faabd..1304cd20 100644 --- a/src/jdk/src/share/classes/sun/security/util/math/intpoly/P384OrderField.java +++ b/src/jdk/src/share/classes/sun/security/util/math/intpoly/P384OrderField.java @@ -53,7 +53,7 @@ public class P384OrderField extends IntegerPolynomial { result = result.subtract(BigInteger.valueOf(2).pow(168).multiply(BigInteger.valueOf(3710130))); return result; } - @Override + protected void finalCarryReduceLast(long[] limbs) { long c = limbs[13] >> 20; limbs[13] -= c << 20; diff --git a/src/jdk/src/share/classes/sun/security/util/math/intpoly/P521OrderField.java b/src/jdk/src/share/classes/sun/security/util/math/intpoly/P521OrderField.java index 439b7e0d..0e98db08 100644 --- a/src/jdk/src/share/classes/sun/security/util/math/intpoly/P521OrderField.java +++ b/src/jdk/src/share/classes/sun/security/util/math/intpoly/P521OrderField.java @@ -56,7 +56,7 @@ public class P521OrderField extends IntegerPolynomial { result = result.subtract(BigInteger.valueOf(2).pow(252).multiply(BigInteger.valueOf(91))); return result; } - @Override + protected void finalCarryReduceLast(long[] limbs) { long c = limbs[18] >> 17; limbs[18] -= c << 17;
