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 * @summary Verify that the Montgomery multiply intrinsic works and correctly checks its arguments.
41 */
42
43 public class MontgomeryMultiplyTest {
44
45 static final MethodHandles.Lookup lookup = MethodHandles.lookup();
46
47 static final MethodHandle montgomeryMultiplyHandle, montgomerySquareHandle;
48 static final MethodHandle bigIntegerConstructorHandle;
49 static final Field bigIntegerMagField;
50
51 static {
52 // Use reflection to gain access to the methods we want to test.
53 try {
54 Method m = BigInteger.class.getDeclaredMethod("montgomeryMultiply",
55 /*a*/int[].class, /*b*/int[].class, /*n*/int[].class, /*len*/int.class,
56 /*inv*/long.class, /*product*/int[].class);
57 m.setAccessible(true);
58 montgomeryMultiplyHandle = lookup.unreflect(m);
59
60 m = BigInteger.class.getDeclaredMethod("montgomerySquare",
61 /*a*/int[].class, /*n*/int[].class, /*len*/int.class,
62 /*inv*/long.class, /*product*/int[].class);
63 m.setAccessible(true);
64 montgomerySquareHandle = lookup.unreflect(m);
65
66 Constructor c
67 = BigInteger.class.getDeclaredConstructor(int.class, int[].class);
68 c.setAccessible(true);
69 bigIntegerConstructorHandle = lookup.unreflectConstructor(c);
70
71 bigIntegerMagField = BigInteger.class.getDeclaredField("mag");
72 bigIntegerMagField.setAccessible(true);
73
74 } catch (Throwable ex) {
75 throw new RuntimeException(ex);
76 }
77 }
78
79 // Invoke either the BigInteger.montgomeryMultiply or
80 // BigInteger.montgomerySquare intrinsics.
81 int[] montgomeryMultiply(int[] a, int[] b, int[] n, int len, long inv,
82 int[] product) throws Throwable {
83 int[] result =
84 (a == b) ? (int[]) montgomerySquareHandle.invokeExact(a, n, len, inv, product)
85 : (int[]) montgomeryMultiplyHandle.invokeExact(a, b, n, len, inv, product);
86 return Arrays.copyOf(result, len);
87 }
88
89 // Invoke the private constructor BigInteger(int[]).
90 BigInteger newBigInteger(int[] val) throws Throwable {
91 return (BigInteger) bigIntegerConstructorHandle.invokeExact(1, val);
92 }
93
94 // Get the private field BigInteger.mag
95 int[] mag(BigInteger n) {
96 try {
97 return (int[]) bigIntegerMagField.get(n);
98 } catch (Exception ex) {
99 throw new RuntimeException(ex);
100 }
101 }
102
103 // Montgomery multiplication
104 // Calculate a * b * r^-1 mod n)
105 //
106 // R is a power of the word size
107 // N' = R^-1 mod N
108 //
109 // T := ab
110 // m := (T mod R)N' mod R [so 0 <= m < R]
111 // t := (T + mN)/R
112 // if t >= N then return t - N else return t
113 //
114 BigInteger montgomeryMultiply(BigInteger a, BigInteger b, BigInteger N,
115 int len, BigInteger n_prime)
116 throws Throwable {
117 BigInteger T = a.multiply(b);
118 BigInteger R = BigInteger.ONE.shiftLeft(len*32);
119 BigInteger mask = R.subtract(BigInteger.ONE);
120 BigInteger m = (T.and(mask)).multiply(n_prime);
121 m = m.and(mask); // i.e. m.mod(R)
122 T = T.add(m.multiply(N));
123 T = T.shiftRight(len*32); // i.e. T.divide(R)
124 if (T.compareTo(N) > 0) {
125 T = T.subtract(N);
126 }
127 return T;
128 }
129
130 BigInteger montgomeryMultiply(int[] a_words, int[] b_words, int[] n_words,
131 int len, BigInteger inv)
132 throws Throwable {
133 BigInteger t = montgomeryMultiply(
134 newBigInteger(a_words),
135 newBigInteger(b_words),
136 newBigInteger(n_words),
137 len, inv);
138 return t;
139 }
140
141 // Check that the Montgomery multiply intrinsic returns the same
142 // result as the longhand calculation.
143 void check(int[] a_words, int[] b_words, int[] n_words, int len, BigInteger inv)
144 throws Throwable {
145 BigInteger n = newBigInteger(n_words);
146 BigInteger slow = montgomeryMultiply(a_words, b_words, n_words, len, inv);
147 BigInteger fast
148 = newBigInteger(montgomeryMultiply
149 (a_words, b_words, n_words, len, inv.longValue(), null));
150 // The intrinsic may not return the same value as the longhand
151 // calculation but they must have the same residue mod N.
152 if (!slow.mod(n).equals(fast.mod(n))) {
153 throw new RuntimeException();
154 }
155 }
156
157 Random rnd = new Random(0);
158
159 int[] random_val(int len) {
160 int[] val = new int[len];
161 for (int i = 0; i < len; i++)
162 val[i] = rnd.nextInt();
163 return val;
164 }
165
166 // Test the Montgomery multiply intrinsic with a bunch of random
167 // values of varying lengths. Do this for long enough that the
168 // caller of the intrinsic is C2-compiled.
169 void testResultValues() throws Throwable {
170 for (int j = 10; j > 0; j--) {
171 // Construct a random prime whose length in words is even
172 int lenInBits = (rnd.nextInt(32)+1)*64 + rnd.nextInt(32) + 32;
173 int lenInInts = (lenInBits + 31)/32;
174 BigInteger mod = new BigInteger(lenInBits , 2, rnd);
175 BigInteger r = BigInteger.ONE.shiftLeft(lenInInts*32);
176 BigInteger n_prime = mod.modInverse(r).negate();
177
178 for (int i = 0; i < 10000; i++) {
179 // multiply
180 check(random_val(lenInInts), random_val(lenInInts), mag(mod), lenInInts, n_prime);
181 // square
182 int[] tmp = random_val(lenInInts);
183 check(tmp, tmp, mag(mod), lenInInts, n_prime);
184 }
185 }
186 }
187
188 // Range checks
189 void testOneMontgomeryMultiplyCheck(int[] a, int[] b, int[] n, int len, long inv,
190 int[] product, Class klass) {
191 try {
192 montgomeryMultiply(a, b, n, len, inv, product);
193 } catch (Throwable ex) {
194 if (klass.isAssignableFrom(ex.getClass()))
195 return;
196 throw new RuntimeException(klass + " expected, " + ex + " was thrown");
197 }
198 throw new RuntimeException(klass + " expected, was not thrown");
199 }
200
201 void testOneMontgomeryMultiplyCheck(int[] a, int[] b, BigInteger n, int len, BigInteger inv,
202 Class klass) {
203 testOneMontgomeryMultiplyCheck(a, b, mag(n), len, inv.longValue(), null, klass);
204 }
205
206 void testOneMontgomeryMultiplyCheck(int[] a, int[] b, BigInteger n, int len, BigInteger inv,
207 int[] product, Class klass) {
208 testOneMontgomeryMultiplyCheck(a, b, mag(n), len, inv.longValue(), product, klass);
209 }
210
211 void testMontgomeryMultiplyChecks() {
212 int[] blah = random_val(40);
213 int[] small = random_val(39);
214 BigInteger mod = new BigInteger(40*32 , 2, rnd);
215 BigInteger r = BigInteger.ONE.shiftLeft(40*32);
216 BigInteger n_prime = mod.modInverse(r).negate();
217
218 // Length out of range: square
219 testOneMontgomeryMultiplyCheck(blah, blah, mod, 41, n_prime, IllegalArgumentException.class);
220 testOneMontgomeryMultiplyCheck(blah, blah, mod, 0, n_prime, IllegalArgumentException.class);
221 testOneMontgomeryMultiplyCheck(blah, blah, mod, -1, n_prime, IllegalArgumentException.class);
222 // As above, but for multiply
223 testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 41, n_prime, IllegalArgumentException.class);
224 testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 0, n_prime, IllegalArgumentException.class);
225 testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 0, n_prime, IllegalArgumentException.class);
226
227 // Length odd
228 testOneMontgomeryMultiplyCheck(small, small, mod, 39, n_prime, IllegalArgumentException.class);
229 testOneMontgomeryMultiplyCheck(small, small, mod, 0, n_prime, IllegalArgumentException.class);
230 testOneMontgomeryMultiplyCheck(small, small, mod, -1, n_prime, IllegalArgumentException.class);
231 // As above, but for multiply
232 testOneMontgomeryMultiplyCheck(small, small.clone(), mod, 39, n_prime, IllegalArgumentException.class);
233 testOneMontgomeryMultiplyCheck(small, small.clone(), mod, 0, n_prime, IllegalArgumentException.class);
234 testOneMontgomeryMultiplyCheck(small, small.clone(), mod, -1, n_prime, IllegalArgumentException.class);
235
236 // array too small
237 testOneMontgomeryMultiplyCheck(blah, blah, mod, 40, n_prime, small, IllegalArgumentException.class);
238 testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 40, n_prime, small, IllegalArgumentException.class);
239 testOneMontgomeryMultiplyCheck(small, blah, mod, 40, n_prime, blah, IllegalArgumentException.class);
240 testOneMontgomeryMultiplyCheck(blah, small, mod, 40, n_prime, blah, IllegalArgumentException.class);
241 testOneMontgomeryMultiplyCheck(blah, blah, mod, 40, n_prime, small, IllegalArgumentException.class);
242 testOneMontgomeryMultiplyCheck(small, small, mod, 40, n_prime, blah, IllegalArgumentException.class);
243 }
244
245 public static void main(String args[]) {
246 try {
247 new MontgomeryMultiplyTest().testMontgomeryMultiplyChecks();
248 new MontgomeryMultiplyTest().testResultValues();
249 } catch (Throwable ex) {
250 throw new RuntimeException(ex);
251 }
252 }
253 }