Create a gist now

Instantly share code, notes, and snippets.

anonymous /Main.java Secret
Created Mar 21, 2013

What would you like to do?
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