1 files changed, 185 insertions, 0 deletions
diff --git a/java/com/google/security/wycheproof/RandomUtil.java b/java/com/google/security/wycheproof/RandomUtil.java
new file mode 100644
index 0000000..388c272
--- /dev/null
+++ b/java/com/google/security/wycheproof/RandomUtil.java
@@ -0,0 +1,185 @@
+/**
+ * @license
+ * Copyright 2016 Google Inc. All rights reserved.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.google.security.wycheproof;
+
+import java.math.BigInteger;
+import java.nio.ByteBuffer;
+import java.security.GeneralSecurityException;
+import java.util.Random;
+
+/**
+ * A collection of utilities for testing random number generators. So far this util simply checks
+ * that random numbers are not generated by java.util.Random. Eventually we plan to add detection
+ * for other random number generators too.
+ *
+ * @author bleichen@google.com (Daniel Bleichenbacher)
+ */
+public class RandomUtil {
+  // Constants for java.util.Random;
+  static final long A = 0x5DEECE66DL;
+  static final long A_INVERSE = 246154705703781L;
+  static final long C = 0xBL;
+
+  /** Given a state of a java.util.Random object compute the next state. */
+  protected static long nextState(long seed) {
+    return (seed * A + C) & ((1L << 48) - 1);
+  }
+
+  /** Give the state after stepping java.util.Random n times. */
+  protected static long step(long seed, long n) {
+    long a = A;
+    long c = C;
+    n = n & 0xffffffffffffL;
+    while (n != 0) {
+      if ((n & 1) == 1) {
+        seed = seed * a + c;
+      }
+      c = c * (a + 1);
+      a = a * a;
+      n = n >> 1;
+    }
+    return seed & 0xffffffffffffL;
+  }
+
+  /** Given a state of a java.util.Random object compute the previous state. */
+  protected static long previousState(long seed) {
+    return ((seed - C) * A_INVERSE) & ((1L << 48) - 1);
+  }
+
+  /** Computes a seed that would initialize a java.util.Random object with a given state. */
+  protected static long getSeedForState(long seed) {
+    return seed ^ A;
+  }
+
+  protected static long getStateForSeed(long seed) {
+    return (seed ^ A) & 0xffffffffffffL;
+  }
+
+  /**
+   * Given two subsequent outputs x0 and x1 from java.util.Random this function computes the
+   * internal state of java.util.Random after returning x0 or returns -1 if no such state exists.
+   */
+  protected static long getState(int x0, int x1) {
+    long mask = (1L << 48) - 1;
+    long multiplier = A;
+    // The state of the random number generator after returning x0 is
+    // l0 + eps for some 0 <= eps < 2**16.
+    long l0 = ((long) x0 << 16) & mask;
+    // The state of the random number generator after returning x1 is
+    // l1 + delta for some 0 <= delta < 2**16.
+    long l1 = ((long) x1 << 16) & mask;
+    // We have l1 + delta = (l0 + eps)*multiplier + 0xBL (mod 2**48).
+    // This allows to find an upper bound w for eps * multiplier mod 2**48
+    // by assuming delta = 2**16-1.
+    long w = (l1 - l0 * multiplier + 65535L - 0xBL) & mask;
+    // The reduction eps * multiplier mod 2**48 only cuts off at most 3 bits.
+    // Hence a simple search is sufficient. The maximal number of loops is 6.
+    for (long em = w; em < (multiplier << 16); em += 1L << 48) {
+      // If the high order bits of em are guessed correctly then
+      // em == eps * multiplier + 65535 - delta.
+      long eps = em / multiplier;
+      long state0 = l0 + eps;
+      long state1 = nextState(state0);
+      if ((state1 & 0xffffffff0000L) == l1) {
+        return state0;
+      }
+    }
+    return -1;
+  }
+
+  /**
+   * Find a seed such that this integer is the result of
+   *
+   * <pre>{@code
+   * Random rand = new Random();
+   * rand.setSeed(seed);
+   * return new BigInteger(k, rand);
+   * }</pre>
+   *
+   * where k is max(64, x.BitLength());
+   *
+   * <p>Returns -1 if no such seed exists.
+   */
+  // TODO(bleichen): We want to detect cases where some of the bits
+  //   (i.e. most significant bits or least significant bits have
+  //   been modified. Often this happens during the generation
+  //   of primes or other things.
+  // TODO(bleichen): This method is incomplete.
+  protected static long getSeedFor(java.math.BigInteger x) {
+    byte[] bytes = x.toByteArray();
+    if (bytes.length == 0) {
+      return -1;
+    }
+    ByteBuffer buffer = ByteBuffer.allocate(8);
+    int offset = bytes[0] == 0 ? 1 : 0;
+    if (bytes.length - offset < 8) {
+      int size = bytes.length - offset;
+      buffer.position(8 - size);
+      buffer.put(bytes, offset, size);
+    } else {
+      buffer.put(bytes, offset, 8);
+    }
+    buffer.flip();
+    buffer.order(java.nio.ByteOrder.LITTLE_ENDIAN);
+    int x0 = buffer.getInt();
+    int x1 = buffer.getInt();
+    long state = getState(x0, x1);
+    if (state == -1) {
+      return -1;
+    }
+    return getSeedForState(previousState(state));
+  }
+
+  /** Attempts to find a seed such that it generates the prime p. Returns -1 if no seed is found. */
+  static long getSeedForPrime(BigInteger p) {
+    int confidence = 64;
+    Random rand = new Random();
+    int size = p.bitLength();
+    // Prime generation often sets the most significant bit.
+    // Hence, clearing the most significant bit can help to find
+    // the seed used for the prime generation.
+    for (BigInteger x : new BigInteger[] {p, p.clearBit(size - 1)}) {
+      long seed = getSeedFor(x);
+      if (seed != -1) {
+        rand.setSeed(seed);
+        BigInteger q = new BigInteger(size, confidence, rand);
+        if (q.equals(p)) {
+          return seed;
+        }
+      }
+    }
+    return -1;
+  }
+
+  /**
+   * Checks whether p is a random prime. A prime generated with a secure random number generator
+   * passes with probability > 1-2^{-32}. No checks are performed for primes smaller than 96 bits.
+   *
+   * @throws GeneralSecurityException if the prime was generated using java.util.Random
+   */
+  static void checkPrime(BigInteger p) throws GeneralSecurityException {
+    // We can't reliably detect java.util.Random for small primes.
+    if (p.bitLength() < 96) {
+      return;
+    }
+    long seed = getSeedForPrime(p);
+    if (seed != -1) {
+      throw new GeneralSecurityException(
+          "java.util.Random with seed " + seed + " was likely used to generate prime");
+    }
+  }
+}