Instantly share code, notes, and snippets.

# anonymous/Quux.javaSecret Created Mar 25, 2013

Solution to http://corner.squareup.com/2013/03/puzzle-square-root.html using a timing attack on BigInteger.divide()
 package square; import static java.lang.Double.MAX_EXPONENT; import static java.lang.Double.MIN_EXPONENT; import static java.lang.Double.POSITIVE_INFINITY; import static java.lang.Double.doubleToRawLongBits; import static java.lang.Double.longBitsToDouble; import static java.lang.Math.getExponent; import static java.lang.Math.rint; import static square.Quux.Guava.DoubleUtils.SIGNIFICAND_BITS; import static square.Quux.Guava.DoubleUtils.getSignificand; import static square.Quux.Guava.DoubleUtils.isFinite; import java.math.BigInteger; import java.security.SecureRandom; import square.Quux.Guava.BigIntegerMath; public final class Quux { static final class NFinder { private final BigInteger n = new BigInteger(SquareRoot.BITS, new SecureRandom()).pow(2); private static final int CALIBRATE_LOOPS = 100000; private static final int WARMUP_LOOPS = 200000; private static final int TEST_LOOPS = 100000; // at least twice as fast as slow private static final double FAST_RATIO = 0.50; // 75% of the slowest seen in calibration is still slow private static final double SLOW_RATIO = 0.75; // warm up the JIT public void warmUp() { System.out.println("Warming up JIT"); final SecureRandom random = new SecureRandom(); for (int i = 0; i < WARMUP_LOOPS; i++) { BigInteger root = new BigInteger(SquareRoot.BITS, random); calibrateAnswer(root); SquareRoot.answer(root); } } private long calibrateTime() { long min = Long.MAX_VALUE; for (int i = 0; i < CALIBRATE_LOOPS; i++) { // final BigInteger root = n.add(BigInteger.ONE); final BigInteger root = BigInteger.ONE .shiftLeft(n.bitLength() - 2); long time = System.nanoTime(); calibrateAnswer(root); time = System.nanoTime() - time; min = Math.min(min, time); } return min; } private void calibrateAnswer(BigInteger root) { if (n.divide(root).equals(root)) { // The goal is to reach this line System.out.println("Square root!"); } } public BigInteger findN() { System.out.println("Calibrating"); final long minSlowTime = calibrateTime(); System.out.println("Solving"); BigInteger lowerBound = BigInteger.ZERO; final int maxBit = (SquareRoot.BITS + 1) * 2; for (int i = 0; i <= maxBit; i++) { System.out.println("Solving bit " + (maxBit - i)); final BigInteger bit = BigInteger.ONE.shiftLeft(maxBit - i); final BigInteger candidate = lowerBound.add(bit); if (isSlow(candidate, minSlowTime)) { lowerBound = candidate; } } return lowerBound.add(BigInteger.ONE); } private static boolean isSlow(BigInteger candidate, long minSlowTime) { for (;;) { long min = Long.MAX_VALUE; for (int i = 0; i < TEST_LOOPS; i++) { long time = System.nanoTime(); SquareRoot.answer(candidate); time = System.nanoTime() - time; if (time < minSlowTime * FAST_RATIO) { System.out.println("" + time + " < " + (minSlowTime) + " * " + FAST_RATIO); return false; } min = Math.min(time, min); } if (min >= minSlowTime * SLOW_RATIO) { System.out.println("" + min + " >= " + minSlowTime + " * " + SLOW_RATIO); return true; } System.out.println("Result was inconclusive. min=" + min + "; minSlowTime=" + minSlowTime); } } } /* * The classes contained in Guava are all derived directly from the Apache * licensed classes of the same names in the Google Guava project. */ static final class Guava { private Guava() { } /** * A class for arithmetic on values of type {@code BigInteger}. * *

* The implementations of many methods in this class are based on * material from Henry S. Warren, Jr.'s Hacker's Delight, * (Addison Wesley, 2002). * *