[Java] Compute discrete logarithm

The discrete logarithm is a widely used concept in cryptography since it's pretty easy and fast to compute when knowing the crypto secrets, but it's otherwise really hard to crack by normal means.

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 prime p. Let g be some element in Z*p and suppose you are given h in Z*p such that h = g^x where x is 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. Since x is 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);  
      }  
   
 }