Create a gist now

Instantly share code, notes, and snippets.

anonymous /Main.java Secret
Created Mar 21, 2013

Embed
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)));
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment