# Diffie-Hellman: Calculating the private key from the public key with Java

I have the task to calculate the private key from the given public key and have the hint that the secret exponent lies in the range from $-2^{31} < e < 2^{31}$.

To find the exponent I calculate a public key and compare it to the given key. $$k_{pub} = 2^{e} \bmod {prime}$$ I start with $e = -2^{31}$ and then iterate my way up until I should find the $e$ where my calculated key equals the given public key. The problem is that it takes really long (about 20 days, if I calculated correctly). Is there a way to make it faster?

import java.math.BigInteger;

public static void main (String[] args) throws java.lang.Exception
{

BigInteger prime                = new BigInteger("FFF....FFF", 16);
BigInteger BobPublicKey         = new BigInteger("b54.....da6", 16);

BigInteger tmp = new BigInteger("0");

BigInteger j = new BigInteger(new Integer(Integer.MIN_VALUE).toString());
System.out.print("Starting to guess Bobs secret: \n" + j + "\n");

while ( !(tmp.compareTo(BobPublicKey) == 0)){
tmp = BigInteger.valueOf(2).modPow(j, prime);
System.out.print(j + "\n");
}

//correct for counting 1 too far in while loop after the actual e was found

System.out.print("Bobs secret was: " + j + "\n");

}
}

• There are better algorithms to solve the DLP, see this. May 8 '16 at 18:05

The easiest approach would be to take advantage of the identity $g^e \cdot g = g^{e+1}$. That is, if we have already computed $g^e$, and verified that it is not the value we're looking for, then to step to $g^{e+1}$, we don't compute $g^{e+1}$ from scratch; instead, we take the $g^e$ value we have, and multiply it by $g$ (modulo $p$), and that's the next value to check.
And, because you have $g=2$, this can be done as easily as adding $g^e$ to itself, and then subtracting $p$ if needed.
A more difficult (but ultimately more rewarding) optimization is to implement the 'bigstep/littlestep' algorithm. This takes the equation $g^x = g^{ak+b}$ (for $k = 2^{16}$ and $-2^{-15} \le a < 2^{15}$, $0 \le b < 2^{16}$), and rewrites it as $g^x g^{-ak} = g^b$; we then create a list of the $2^{16}$ possible $g^x g^{-ak}$ values, and the $2^{16}$ possible $g^b$ values, and search for a match (which can be done in $O(n \log n)$ time using a fast sorting algorithm); this match gives us the $a, b$ values, which immediately gives us $x$. This is obviously a lot more work; however doing this will allow you to find a match by doing around $2^{17}$ modular multiplications; this is a large gain over the previous optimization.