Instantly share code, notes, and snippets.

# anonymous/Main.javaSecret Created Mar 21, 2013

Timing attack on SquareRoot.answer. It uses the timing attack to find the square, then hunts around the root.
 import square.SquareRoot; import java.math.BigInteger; import java.util.Date; public class Main { public static long timeit(BigInteger n) { long begin = System.nanoTime(); for (int i=0; i < 200; i++) { SquareRoot.answer(n); } long end = System.nanoTime(); return (end - begin); } public static BigInteger findSqrt(BigInteger n) { BigInteger potentialRoot = new BigInteger("2"); if (n.compareTo(potentialRoot) <= 0) { if (n.equals(BigInteger.ZERO)) { return n; } else { return BigInteger.ONE; } } potentialRoot = n.divide(potentialRoot); while (true) { BigInteger npotentialRoot = n.divide(potentialRoot).add(potentialRoot).shiftRight(1); if (potentialRoot.subtract(npotentialRoot).abs().compareTo(BigInteger.TEN) < 0) { for (int x = 10; x > -11; x--) { BigInteger tst = potentialRoot.add(new BigInteger("" + x)); BigInteger tstP1 = tst.add(BigInteger.ONE); if (tst.multiply(tst).compareTo(n) != tstP1.multiply(tstP1).compareTo(n)) { return tst; } } } potentialRoot = npotentialRoot; } } public static boolean isTooHigh(long tooBigTime, BigInteger mid) { long minTime = Long.MAX_VALUE; long midTime = 0; for (int i=1; i < 40; i++) { long t = timeit(mid); minTime = Math.min(midTime, t); midTime += t; } midTime /= 40; if ((midTime - minTime > tooBigTime / 4) || (midTime > 4 * tooBigTime && midTime < 7 * tooBigTime)) { // System.out.print("T"); return isTooHigh(tooBigTime, mid); } return midTime <= 4 * tooBigTime; } public static void main(String[] args) throws InterruptedException { for (int i=1; i < 257; i++) { SquareRoot.answer(new BigInteger("" + i)); } BigInteger high = new BigInteger("2").pow(20002); for (int i=1; i < 1000; i++) { timeit(high); // warm up jit } long tooBigTime = 0; while (true) { long minBigTime = Long.MAX_VALUE; tooBigTime = 0; for (int i=1; i < 10; i++) { long t = timeit(high); tooBigTime += t; minBigTime = Math.min(minBigTime, t); } tooBigTime /= 10; if (tooBigTime - minBigTime < tooBigTime / 8) break; System.out.println(tooBigTime + " " + minBigTime); for (int i=1; i < 1000; i++) { timeit(high); // warm up jit } } BigInteger low = new BigInteger("256"); BigInteger hundred = new BigInteger("100"); int ticklen = 0; while (high.compareTo(low.add(BigInteger.ONE)) > 0) { int spotlen = high.subtract(low).toString().length() / 100; if (spotlen != ticklen) { System.out.println(spotlen + " " + new Date()); ticklen = spotlen; } if (high.subtract(low).compareTo(hundred) > 0) { BigInteger step = high.subtract(low).divide(BigInteger.TEN); BigInteger guess = high.subtract(step); while (guess.compareTo(low) > 0) { if (isTooHigh(tooBigTime, guess) || isTooHigh(tooBigTime, guess.subtract(BigInteger.ONE))) { high = guess; guess = high.subtract(step); } else { low = guess; } } } else { BigInteger mid = high.add(low).shiftRight(1); if (isTooHigh(tooBigTime, mid)) { high = mid; } else { low = mid; } } } BigInteger guess = findSqrt(low); for (int x = -100; x < 100; x++) { SquareRoot.answer(guess.add(new BigInteger("" + x))); } } }