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 }