< prev index next >
src/java.base/share/classes/java/math/BigInteger.java
Print this page
rev 12150 : 8046943: JEP 246: Leverage CPU Instructions for GHASH and RSA
Summary: Add montgomeryMultiply intrinsic
Reviewed-by: kvn
*** 2602,2611 ****
--- 2602,2622 ----
}
static int[] bnExpModThreshTable = {7, 25, 81, 241, 673, 1793,
Integer.MAX_VALUE}; // Sentinel
+ private int[] montgomeryMultiply(int[] a, int[] b, int[] n, int len, long inv,
+ int[] product) {
+ if (a == b) {
+ product = squareToLen(a, len, product);
+ } else {
+ product = multiplyToLen(a, len, b, len, product);
+ }
+ int[] result = montReduce(product, n, len, (int)inv);
+ return result;
+ }
+
/**
* Returns a BigInteger whose value is x to the power of y mod z.
* Assumes: z is odd && x < z.
*/
private BigInteger oddModPow(BigInteger y, BigInteger z) {
*** 2677,2686 ****
--- 2688,2708 ----
int[] base = mag.clone();
int[] exp = y.mag;
int[] mod = z.mag;
int modLen = mod.length;
+ // Make modLen even. It is conventional to use a cryptographic
+ // modulus that is 512, 768, 1024, or 2048 bits, so this code
+ // will not normally be executed. However, it is necessary for
+ // the correct functioning of the HotSpot intrinsics.
+ if ((modLen & 1) != 0) {
+ int[] x = new int[modLen + 1];
+ System.arraycopy(mod, 0, x, 1, modLen);
+ mod = x;
+ modLen++;
+ }
+
// Select an appropriate window size
int wbits = 0;
int ebits = bitLength(exp, exp.length);
// if exponent is 65537 (0x10001), use minimum window size
if ((ebits != 17) || (exp[0] != 65537)) {
*** 2695,2737 ****
// Allocate table for precomputed odd powers of base in Montgomery form
int[][] table = new int[tblmask][];
for (int i=0; i < tblmask; i++)
table[i] = new int[modLen];
! // Compute the modular inverse
! int inv = -MutableBigInteger.inverseMod32(mod[modLen-1]);
// Convert base to Montgomery form
int[] a = leftShift(base, base.length, modLen << 5);
MutableBigInteger q = new MutableBigInteger(),
a2 = new MutableBigInteger(a),
b2 = new MutableBigInteger(mod);
MutableBigInteger r= a2.divide(b2, q);
table[0] = r.toIntArray();
// Pad table[0] with leading zeros so its length is at least modLen
if (table[0].length < modLen) {
int offset = modLen - table[0].length;
int[] t2 = new int[modLen];
! for (int i=0; i < table[0].length; i++)
! t2[i+offset] = table[0][i];
table[0] = t2;
}
// Set b to the square of the base
! int[] b = squareToLen(table[0], modLen, null);
! b = montReduce(b, mod, modLen, inv);
// Set t to high half of b
int[] t = Arrays.copyOf(b, modLen);
// Fill in the table with odd powers of the base
for (int i=1; i < tblmask; i++) {
! int[] prod = multiplyToLen(t, modLen, table[i-1], modLen, null);
! table[i] = montReduce(prod, mod, modLen, inv);
}
// Pre load the window that slides over the exponent
int bitpos = 1 << ((ebits-1) & (32-1));
--- 2717,2760 ----
// Allocate table for precomputed odd powers of base in Montgomery form
int[][] table = new int[tblmask][];
for (int i=0; i < tblmask; i++)
table[i] = new int[modLen];
! // Compute the modular inverse of the least significant 64-bit
! // digit of the modulus
! long n0 = (mod[modLen-1] & LONG_MASK) + ((mod[modLen-2] & LONG_MASK) << 32);
! long inv = -MutableBigInteger.inverseMod64(n0);
// Convert base to Montgomery form
int[] a = leftShift(base, base.length, modLen << 5);
MutableBigInteger q = new MutableBigInteger(),
a2 = new MutableBigInteger(a),
b2 = new MutableBigInteger(mod);
+ b2.normalize(); // MutableBigInteger.divide() assumes that its
+ // divisor is in normal form.
MutableBigInteger r= a2.divide(b2, q);
table[0] = r.toIntArray();
// Pad table[0] with leading zeros so its length is at least modLen
if (table[0].length < modLen) {
int offset = modLen - table[0].length;
int[] t2 = new int[modLen];
! System.arraycopy(table[0], 0, t2, offset, table[0].length);
table[0] = t2;
}
// Set b to the square of the base
! int[] b = montgomeryMultiply(table[0], table[0], mod, modLen, inv, null);
// Set t to high half of b
int[] t = Arrays.copyOf(b, modLen);
// Fill in the table with odd powers of the base
for (int i=1; i < tblmask; i++) {
! table[i] = montgomeryMultiply(t, table[i-1], mod, modLen, inv, null);
}
// Pre load the window that slides over the exponent
int bitpos = 1 << ((ebits-1) & (32-1));
*** 2798,2809 ****
if (isone) {
b = mult.clone();
isone = false;
} else {
t = b;
! a = multiplyToLen(t, modLen, mult, modLen, a);
! a = montReduce(a, mod, modLen, inv);
t = a; a = b; b = t;
}
}
// Check if done
--- 2821,2831 ----
if (isone) {
b = mult.clone();
isone = false;
} else {
t = b;
! a = montgomeryMultiply(t, mult, mod, modLen, inv, a);
t = a; a = b; b = t;
}
}
// Check if done
*** 2811,2831 ****
break;
// Square the input
if (!isone) {
t = b;
! a = squareToLen(t, modLen, a);
! a = montReduce(a, mod, modLen, inv);
t = a; a = b; b = t;
}
}
// Convert result out of Montgomery form and return
int[] t2 = new int[2*modLen];
System.arraycopy(b, 0, t2, modLen, modLen);
! b = montReduce(t2, mod, modLen, inv);
t2 = Arrays.copyOf(b, modLen);
return new BigInteger(1, t2);
}
--- 2833,2852 ----
break;
// Square the input
if (!isone) {
t = b;
! a = montgomeryMultiply(t, t, mod, modLen, inv, a);
t = a; a = b; b = t;
}
}
// Convert result out of Montgomery form and return
int[] t2 = new int[2*modLen];
System.arraycopy(b, 0, t2, modLen, modLen);
! b = montReduce(t2, mod, modLen, (int)inv);
t2 = Arrays.copyOf(b, modLen);
return new BigInteger(1, t2);
}
< prev index next >