1 //
2 // Copyright (c) 2000, 2015, Oracle and/or its affiliates. All rights reserved.
3 // Copyright (c) 2015, Red Hat Inc. All rights reserved.
4 // DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 //
6 // This code is free software; you can redistribute it and/or modify it
7 // under the terms of the GNU General Public License version 2 only, as
8 // published by the Free Software Foundation.
9 //
10 // This code is distributed in the hope that it will be useful, but WITHOUT
11 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 // version 2 for more details (a copy is included in the LICENSE file that
14 // accompanied this code).
15 //
16 // You should have received a copy of the GNU General Public License version
17 // 2 along with this work; if not, write to the Free Software Foundation,
18 // Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 //
20 // Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 // or visit www.oracle.com if you need additional information or have any
22 // questions.
23 //
24 //
25
26 import java.lang.invoke.MethodHandle;
27 import java.lang.invoke.MethodHandles;
28 import java.lang.invoke.MethodType;
29 import java.lang.reflect.Constructor;
30 import java.lang.reflect.Field;
31 import java.lang.reflect.Method;
32 import java.math.BigInteger;
33 import java.util.Arrays;
34 import java.util.Random;
35
36 /**
37 * @test
38 * @bug 8130150
39 * @library /testlibrary
40 * @requires (os.simpleArch == "x64") & (os.family != "windows")
41 * @summary Verify that the Montgomery multiply intrinsic works and correctly checks its arguments.
42 * @run main/othervm -XX:+IgnoreUnrecognizedVMOptions -XX:+UseMontgomerySquareIntrinsic
43 * -XX:+UseMontgomeryMultiplyIntrinsic MontgomeryMultiplyTest
44 * @run main/othervm -XX:+IgnoreUnrecognizedVMOptions -XX:+UseMontgomerySquareIntrinsic
45 * -XX:-UseMontgomeryMultiplyIntrinsic MontgomeryMultiplyTest
46 * @run main/othervm -XX:+IgnoreUnrecognizedVMOptions -XX:-UseMontgomerySquareIntrinsic
47 * -XX:+UseMontgomeryMultiplyIntrinsic MontgomeryMultiplyTest
48 */
49
50 public class MontgomeryMultiplyTest {
51
52 static final MethodHandles.Lookup lookup = MethodHandles.lookup();
53
54 static final MethodHandle montgomeryMultiplyHandle, montgomerySquareHandle;
55 static final MethodHandle bigIntegerConstructorHandle;
56 static final Field bigIntegerMagField;
57
58 static {
59 // Use reflection to gain access to the methods we want to test.
60 try {
61 Method m = BigInteger.class.getDeclaredMethod("montgomeryMultiply",
62 /*a*/int[].class, /*b*/int[].class, /*n*/int[].class, /*len*/int.class,
63 /*inv*/long.class, /*product*/int[].class);
64 m.setAccessible(true);
65 montgomeryMultiplyHandle = lookup.unreflect(m);
66
67 m = BigInteger.class.getDeclaredMethod("montgomerySquare",
68 /*a*/int[].class, /*n*/int[].class, /*len*/int.class,
69 /*inv*/long.class, /*product*/int[].class);
70 m.setAccessible(true);
71 montgomerySquareHandle = lookup.unreflect(m);
72
73 Constructor c
74 = BigInteger.class.getDeclaredConstructor(int.class, int[].class);
75 c.setAccessible(true);
76 bigIntegerConstructorHandle = lookup.unreflectConstructor(c);
77
78 bigIntegerMagField = BigInteger.class.getDeclaredField("mag");
79 bigIntegerMagField.setAccessible(true);
80
81 } catch (Throwable ex) {
82 throw new RuntimeException(ex);
83 }
84 }
85
86 // Invoke either BigInteger.montgomeryMultiply or BigInteger.montgomerySquare.
87 int[] montgomeryMultiply(int[] a, int[] b, int[] n, int len, long inv,
88 int[] product) throws Throwable {
89 int[] result =
90 (a == b) ? (int[]) montgomerySquareHandle.invokeExact(a, n, len, inv, product)
91 : (int[]) montgomeryMultiplyHandle.invokeExact(a, b, n, len, inv, product);
92 return Arrays.copyOf(result, len);
93 }
94
95 // Invoke the private constructor BigInteger(int[]).
96 BigInteger newBigInteger(int[] val) throws Throwable {
97 return (BigInteger) bigIntegerConstructorHandle.invokeExact(1, val);
98 }
99
100 // Get the private field BigInteger.mag
101 int[] mag(BigInteger n) {
102 try {
103 return (int[]) bigIntegerMagField.get(n);
104 } catch (Exception ex) {
105 throw new RuntimeException(ex);
106 }
107 }
108
109 // Montgomery multiplication
110 // Calculate a * b * r^-1 mod n)
111 //
112 // R is a power of the word size
113 // N' = R^-1 mod N
114 //
115 // T := ab
116 // m := (T mod R)N' mod R [so 0 <= m < R]
117 // t := (T + mN)/R
118 // if t >= N then return t - N else return t
119 //
120 BigInteger montgomeryMultiply(BigInteger a, BigInteger b, BigInteger N,
121 int len, BigInteger n_prime)
122 throws Throwable {
123 BigInteger T = a.multiply(b);
124 BigInteger R = BigInteger.ONE.shiftLeft(len*32);
125 BigInteger mask = R.subtract(BigInteger.ONE);
126 BigInteger m = (T.and(mask)).multiply(n_prime);
127 m = m.and(mask); // i.e. m.mod(R)
128 T = T.add(m.multiply(N));
129 T = T.shiftRight(len*32); // i.e. T.divide(R)
130 if (T.compareTo(N) > 0) {
131 T = T.subtract(N);
132 }
133 return T;
134 }
135
136 // Call the Montgomery multiply intrinsic.
137 BigInteger montgomeryMultiply(int[] a_words, int[] b_words, int[] n_words,
138 int len, BigInteger inv)
139 throws Throwable {
140 BigInteger t = montgomeryMultiply(
141 newBigInteger(a_words),
142 newBigInteger(b_words),
143 newBigInteger(n_words),
144 len, inv);
145 return t;
146 }
147
148 // Check that the Montgomery multiply intrinsic returns the same
149 // result as the longhand calculation.
150 void check(int[] a_words, int[] b_words, int[] n_words, int len, BigInteger inv)
151 throws Throwable {
152 BigInteger n = newBigInteger(n_words);
153 BigInteger slow = montgomeryMultiply(a_words, b_words, n_words, len, inv);
154 BigInteger fast
155 = newBigInteger(montgomeryMultiply
156 (a_words, b_words, n_words, len, inv.longValue(), null));
157 // The intrinsic may not return the same value as the longhand
158 // calculation but they must have the same residue mod N.
159 if (!slow.mod(n).equals(fast.mod(n))) {
160 throw new RuntimeException();
161 }
162 }
163
164 Random rnd = new Random(0);
165
166 // Return a random value of length <= bits in an array of even length
167 int[] random_val(int bits) {
168 int len = (bits+63)/64; // i.e. length in longs
169 int[] val = new int[len*2];
170 for (int i = 0; i < val.length; i++)
171 val[i] = rnd.nextInt();
172 int leadingZeros = 64 - (bits & 64);
173 if (leadingZeros >= 32) {
174 val[0] = 0;
175 val[1] &= ~(-1l << (leadingZeros & 31));
176 } else {
177 val[0] &= ~(-1l << leadingZeros);
178 }
179 return val;
180 }
181
182 void testOneLength(int lenInBits, int lenInInts) throws Throwable {
183 BigInteger mod = new BigInteger(lenInBits, 2, rnd);
184 BigInteger r = BigInteger.ONE.shiftLeft(lenInInts * 32);
185 BigInteger n_prime = mod.modInverse(r).negate();
186
187 // Make n.length even, padding with a zero if necessary
188 int[] n = mag(mod);
189 if (n.length < lenInInts) {
190 int[] x = new int[lenInInts];
191 System.arraycopy(n, 0, x, lenInInts-n.length, n.length);
192 n = x;
193 }
194
195 for (int i = 0; i < 10000; i++) {
196 // multiply
197 check(random_val(lenInBits), random_val(lenInBits), n, lenInInts, n_prime);
198 // square
199 int[] tmp = random_val(lenInBits);
200 check(tmp, tmp, n, lenInInts, n_prime);
201 }
202 }
203
204 // Test the Montgomery multiply intrinsic with a bunch of random
205 // values of varying lengths. Do this for long enough that the
206 // caller of the intrinsic is C2-compiled.
207 void testResultValues() throws Throwable {
208 // Test a couple of interesting edge cases.
209 testOneLength(1024, 32);
210 testOneLength(1025, 34);
211 for (int j = 10; j > 0; j--) {
212 // Construct a random prime whose length in words is even
213 int lenInBits = rnd.nextInt(2048) + 64;
214 int lenInInts = (lenInBits + 63)/64*2;
215 testOneLength(lenInBits, lenInInts);
216 }
217 }
218
219 // Range checks
220 void testOneMontgomeryMultiplyCheck(int[] a, int[] b, int[] n, int len, long inv,
221 int[] product, Class klass) {
222 try {
223 montgomeryMultiply(a, b, n, len, inv, product);
224 } catch (Throwable ex) {
225 if (klass.isAssignableFrom(ex.getClass()))
226 return;
227 throw new RuntimeException(klass + " expected, " + ex + " was thrown");
228 }
229 throw new RuntimeException(klass + " expected, was not thrown");
230 }
231
232 void testOneMontgomeryMultiplyCheck(int[] a, int[] b, BigInteger n, int len, BigInteger inv,
233 Class klass) {
234 testOneMontgomeryMultiplyCheck(a, b, mag(n), len, inv.longValue(), null, klass);
235 }
236
237 void testOneMontgomeryMultiplyCheck(int[] a, int[] b, BigInteger n, int len, BigInteger inv,
238 int[] product, Class klass) {
239 testOneMontgomeryMultiplyCheck(a, b, mag(n), len, inv.longValue(), product, klass);
240 }
241
242 void testMontgomeryMultiplyChecks() {
243 int[] blah = random_val(40);
244 int[] small = random_val(39);
245 BigInteger mod = new BigInteger(40*32 , 2, rnd);
246 BigInteger r = BigInteger.ONE.shiftLeft(40*32);
247 BigInteger n_prime = mod.modInverse(r).negate();
248
249 // Length out of range: square
250 testOneMontgomeryMultiplyCheck(blah, blah, mod, 41, n_prime, IllegalArgumentException.class);
251 testOneMontgomeryMultiplyCheck(blah, blah, mod, 0, n_prime, IllegalArgumentException.class);
252 testOneMontgomeryMultiplyCheck(blah, blah, mod, -1, n_prime, IllegalArgumentException.class);
253 // As above, but for multiply
254 testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 41, n_prime, IllegalArgumentException.class);
255 testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 0, n_prime, IllegalArgumentException.class);
256 testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 0, n_prime, IllegalArgumentException.class);
257
258 // Length odd
259 testOneMontgomeryMultiplyCheck(small, small, mod, 39, n_prime, IllegalArgumentException.class);
260 testOneMontgomeryMultiplyCheck(small, small, mod, 0, n_prime, IllegalArgumentException.class);
261 testOneMontgomeryMultiplyCheck(small, small, mod, -1, n_prime, IllegalArgumentException.class);
262 // As above, but for multiply
263 testOneMontgomeryMultiplyCheck(small, small.clone(), mod, 39, n_prime, IllegalArgumentException.class);
264 testOneMontgomeryMultiplyCheck(small, small.clone(), mod, 0, n_prime, IllegalArgumentException.class);
265 testOneMontgomeryMultiplyCheck(small, small.clone(), mod, -1, n_prime, IllegalArgumentException.class);
266
267 // array too small
268 testOneMontgomeryMultiplyCheck(blah, blah, mod, 40, n_prime, small, IllegalArgumentException.class);
269 testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 40, n_prime, small, IllegalArgumentException.class);
270 testOneMontgomeryMultiplyCheck(small, blah, mod, 40, n_prime, blah, IllegalArgumentException.class);
271 testOneMontgomeryMultiplyCheck(blah, small, mod, 40, n_prime, blah, IllegalArgumentException.class);
272 testOneMontgomeryMultiplyCheck(blah, blah, mod, 40, n_prime, small, IllegalArgumentException.class);
273 testOneMontgomeryMultiplyCheck(small, small, mod, 40, n_prime, blah, IllegalArgumentException.class);
274 }
275
276 public static void main(String args[]) {
277 try {
278 new MontgomeryMultiplyTest().testMontgomeryMultiplyChecks();
279 new MontgomeryMultiplyTest().testResultValues();
280 } catch (Throwable ex) {
281 throw new RuntimeException(ex);
282 }
283 }
284 }