In this example, from Coursera's cryptography I course, we'll try to compute it for some 153-digits numbers using a MITM technique. The exercise is as such:

Your goal this week is to write a program to compute discrete log modulo a primep. Letgbe some element inZ*pand suppose you are givenhinZ*psuch thath = g^xwherexis between 1 and 2^40. A basic brute force attack is to just try all possible values in 2^40 time, but our MITM attack will take just 2^20 time.

Let B=2^20. Sincexis less than B^2 we can write the unknown x base B as x=x0 B+x1 where x0,x1 are in the range [0,B-1]. Then h = g^x = g^(x0 B+x1) = (g^B)^x0·g^x1 in Zp. And then we have h/(g^x1) = (g^B) ^ x0 in Zp.

The variables in this equation are x0,x1 and everything else is known: you are given g,h and B=2^20. Since the variables x0 and x1 are now on different sides of the equation we can find a solution using meet in the middle:

- First build a hash table of all possible values of the left hand side h/(g^x1) for x1=0,1,…,2^20.

- Then for each value x0=0,1,2,…,2^20 check if the right hand side (g^B)^x0 is in this hash table. If so, then you have found a solution (x0,x1) from which you can compute the required x as x=x0B+x1.

We will now find

*x*such that*h*=*g^x*.```
import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
public class Main {
//sample numbers. Note we MUST use BigIntegers
static BigInteger h = new BigInteger("3239475104050450443565264378728065788649097520952449527834792452971981976143292558073856937958553180532878928001494706097394108577585732452307673444020333");
static BigInteger g = new BigInteger("11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568");
static BigInteger p = new BigInteger("13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171");
static long B = 1048576;//2^20
//build hashtable of all possible h/(g^x1) for x1 in 0..B
private static Map<BigInteger, Long> leftHash(){
Map<BigInteger, Long> m = new HashMap<BigInteger, Long>();
BigInteger n, gpow, ginversepow;
for(long i=0; i<B; i++){
//compute g^x1 mod p
gpow = g.modPow(new BigInteger(i+""), p);
//compute 1/(g^x1) mod p
ginversepow = gpow.modInverse(p);
//compute h/(g^x1) mod p
n = h.multiply(ginversepow);
n = n.mod(p);
//store in hashtable
m.put(n, i);
}
System.out.println("Hashtable done");
return m;
}
//compute n = g^B^x0 for x0 in 0..B, then check if n is in hashtable. If it is, we found (x0, x1) and can compute x as x0*B+x1
private static long computeDiscreteLog(Map<BigInteger, Long> m){
BigInteger n;
long res = 0;
//compute g^B
BigInteger gB = g.modPow(new BigInteger(B+""), p);
for(long i=0; i<B; i++){
//compute g^B^x0
n = gB.modPow(new BigInteger(i+""), p);
if(m.containsKey(n)){
res = i*B+m.get(n);
break;
}
}
return res;
}
public static void main(String [] args){
Map<BigInteger, Long> m = leftHash();
long res = computeDiscreteLog(m);
System.out.println("Found "+res);
}
}
```

This comment has been removed by the author.

ReplyDeleteThis comment has been removed by the author.

ReplyDelete