|
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 BigInteger.montgomeryMultiply or BigInteger.montgomerySquare. |
|
80 int[] montgomeryMultiply(int[] a, int[] b, int[] n, int len, long inv, |
|
81 int[] product) throws Throwable { |
|
82 int[] result = |
|
83 (a == b) ? (int[]) montgomerySquareHandle.invokeExact(a, n, len, inv, product) |
|
84 : (int[]) montgomeryMultiplyHandle.invokeExact(a, b, n, len, inv, product); |
|
85 return Arrays.copyOf(result, len); |
|
86 } |
|
87 |
|
88 // Invoke the private constructor BigInteger(int[]). |
|
89 BigInteger newBigInteger(int[] val) throws Throwable { |
|
90 return (BigInteger) bigIntegerConstructorHandle.invokeExact(1, val); |
|
91 } |
|
92 |
|
93 // Get the private field BigInteger.mag |
|
94 int[] mag(BigInteger n) { |
|
95 try { |
|
96 return (int[]) bigIntegerMagField.get(n); |
|
97 } catch (Exception ex) { |
|
98 throw new RuntimeException(ex); |
|
99 } |
|
100 } |
|
101 |
|
102 // Montgomery multiplication |
|
103 // Calculate a * b * r^-1 mod n) |
|
104 // |
|
105 // R is a power of the word size |
|
106 // N' = R^-1 mod N |
|
107 // |
|
108 // T := ab |
|
109 // m := (T mod R)N' mod R [so 0 <= m < R] |
|
110 // t := (T + mN)/R |
|
111 // if t >= N then return t - N else return t |
|
112 // |
|
113 BigInteger montgomeryMultiply(BigInteger a, BigInteger b, BigInteger N, |
|
114 int len, BigInteger n_prime) |
|
115 throws Throwable { |
|
116 BigInteger T = a.multiply(b); |
|
117 BigInteger R = BigInteger.ONE.shiftLeft(len*32); |
|
118 BigInteger mask = R.subtract(BigInteger.ONE); |
|
119 BigInteger m = (T.and(mask)).multiply(n_prime); |
|
120 m = m.and(mask); // i.e. m.mod(R) |
|
121 T = T.add(m.multiply(N)); |
|
122 T = T.shiftRight(len*32); // i.e. T.divide(R) |
|
123 if (T.compareTo(N) > 0) { |
|
124 T = T.subtract(N); |
|
125 } |
|
126 return T; |
|
127 } |
|
128 |
|
129 // Call the Montgomery multiply intrinsic. |
|
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 // Return a random value of length <= bits in an array of even length |
|
160 int[] random_val(int bits) { |
|
161 int len = (bits+63)/64; // i.e. length in longs |
|
162 int[] val = new int[len*2]; |
|
163 for (int i = 0; i < val.length; i++) |
|
164 val[i] = rnd.nextInt(); |
|
165 int leadingZeros = 64 - (bits & 64); |
|
166 if (leadingZeros >= 32) { |
|
167 val[0] = 0; |
|
168 val[1] &= ~(-1l << (leadingZeros & 31)); |
|
169 } else { |
|
170 val[0] &= ~(-1l << leadingZeros); |
|
171 } |
|
172 return val; |
|
173 } |
|
174 |
|
175 void testOneLength(int lenInBits, int lenInInts) throws Throwable { |
|
176 BigInteger mod = new BigInteger(lenInBits, 2, rnd); |
|
177 BigInteger r = BigInteger.ONE.shiftLeft(lenInInts * 32); |
|
178 BigInteger n_prime = mod.modInverse(r).negate(); |
|
179 |
|
180 // Make n.length even, padding with a zero if necessary |
|
181 int[] n = mag(mod); |
|
182 if (n.length < lenInInts) { |
|
183 int[] x = new int[lenInInts]; |
|
184 System.arraycopy(n, 0, x, lenInInts-n.length, n.length); |
|
185 n = x; |
|
186 } |
|
187 |
|
188 for (int i = 0; i < 10000; i++) { |
|
189 // multiply |
|
190 check(random_val(lenInBits), random_val(lenInBits), n, lenInInts, n_prime); |
|
191 // square |
|
192 int[] tmp = random_val(lenInBits); |
|
193 check(tmp, tmp, n, lenInInts, n_prime); |
|
194 } |
|
195 } |
|
196 |
|
197 // Test the Montgomery multiply intrinsic with a bunch of random |
|
198 // values of varying lengths. Do this for long enough that the |
|
199 // caller of the intrinsic is C2-compiled. |
|
200 void testResultValues() throws Throwable { |
|
201 // Test a couple of interesting edge cases. |
|
202 testOneLength(1024, 32); |
|
203 testOneLength(1025, 34); |
|
204 for (int j = 10; j > 0; j--) { |
|
205 // Construct a random prime whose length in words is even |
|
206 int lenInBits = rnd.nextInt(2048) + 64; |
|
207 int lenInInts = (lenInBits + 63)/64*2; |
|
208 testOneLength(lenInBits, lenInInts); |
|
209 } |
|
210 } |
|
211 |
|
212 // Range checks |
|
213 void testOneMontgomeryMultiplyCheck(int[] a, int[] b, int[] n, int len, long inv, |
|
214 int[] product, Class klass) { |
|
215 try { |
|
216 montgomeryMultiply(a, b, n, len, inv, product); |
|
217 } catch (Throwable ex) { |
|
218 if (klass.isAssignableFrom(ex.getClass())) |
|
219 return; |
|
220 throw new RuntimeException(klass + " expected, " + ex + " was thrown"); |
|
221 } |
|
222 throw new RuntimeException(klass + " expected, was not thrown"); |
|
223 } |
|
224 |
|
225 void testOneMontgomeryMultiplyCheck(int[] a, int[] b, BigInteger n, int len, BigInteger inv, |
|
226 Class klass) { |
|
227 testOneMontgomeryMultiplyCheck(a, b, mag(n), len, inv.longValue(), null, klass); |
|
228 } |
|
229 |
|
230 void testOneMontgomeryMultiplyCheck(int[] a, int[] b, BigInteger n, int len, BigInteger inv, |
|
231 int[] product, Class klass) { |
|
232 testOneMontgomeryMultiplyCheck(a, b, mag(n), len, inv.longValue(), product, klass); |
|
233 } |
|
234 |
|
235 void testMontgomeryMultiplyChecks() { |
|
236 int[] blah = random_val(40); |
|
237 int[] small = random_val(39); |
|
238 BigInteger mod = new BigInteger(40*32 , 2, rnd); |
|
239 BigInteger r = BigInteger.ONE.shiftLeft(40*32); |
|
240 BigInteger n_prime = mod.modInverse(r).negate(); |
|
241 |
|
242 // Length out of range: square |
|
243 testOneMontgomeryMultiplyCheck(blah, blah, mod, 41, n_prime, IllegalArgumentException.class); |
|
244 testOneMontgomeryMultiplyCheck(blah, blah, mod, 0, n_prime, IllegalArgumentException.class); |
|
245 testOneMontgomeryMultiplyCheck(blah, blah, mod, -1, n_prime, IllegalArgumentException.class); |
|
246 // As above, but for multiply |
|
247 testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 41, n_prime, IllegalArgumentException.class); |
|
248 testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 0, n_prime, IllegalArgumentException.class); |
|
249 testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 0, n_prime, IllegalArgumentException.class); |
|
250 |
|
251 // Length odd |
|
252 testOneMontgomeryMultiplyCheck(small, small, mod, 39, n_prime, IllegalArgumentException.class); |
|
253 testOneMontgomeryMultiplyCheck(small, small, mod, 0, n_prime, IllegalArgumentException.class); |
|
254 testOneMontgomeryMultiplyCheck(small, small, mod, -1, n_prime, IllegalArgumentException.class); |
|
255 // As above, but for multiply |
|
256 testOneMontgomeryMultiplyCheck(small, small.clone(), mod, 39, n_prime, IllegalArgumentException.class); |
|
257 testOneMontgomeryMultiplyCheck(small, small.clone(), mod, 0, n_prime, IllegalArgumentException.class); |
|
258 testOneMontgomeryMultiplyCheck(small, small.clone(), mod, -1, n_prime, IllegalArgumentException.class); |
|
259 |
|
260 // array too small |
|
261 testOneMontgomeryMultiplyCheck(blah, blah, mod, 40, n_prime, small, IllegalArgumentException.class); |
|
262 testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 40, n_prime, small, IllegalArgumentException.class); |
|
263 testOneMontgomeryMultiplyCheck(small, blah, mod, 40, n_prime, blah, IllegalArgumentException.class); |
|
264 testOneMontgomeryMultiplyCheck(blah, small, mod, 40, n_prime, blah, IllegalArgumentException.class); |
|
265 testOneMontgomeryMultiplyCheck(blah, blah, mod, 40, n_prime, small, IllegalArgumentException.class); |
|
266 testOneMontgomeryMultiplyCheck(small, small, mod, 40, n_prime, blah, IllegalArgumentException.class); |
|
267 } |
|
268 |
|
269 public static void main(String args[]) { |
|
270 try { |
|
271 new MontgomeryMultiplyTest().testMontgomeryMultiplyChecks(); |
|
272 new MontgomeryMultiplyTest().testResultValues(); |
|
273 } catch (Throwable ex) { |
|
274 throw new RuntimeException(ex); |
|
275 } |
|
276 } |
|
277 } |