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 class task {

        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);
                 j = j.add(BigInteger.valueOf(1));  
                 System.out.print(j + "\n");

             //correct for counting 1 too far in while loop after the actual e was found
             j = j.add(BigInteger.valueOf(-1));

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

  • $\begingroup$ There are better algorithms to solve the DLP, see this. $\endgroup$
    – Aleph
    May 8 '16 at 18:05

There are several obvious ways to optimize the search.

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.

  • $\begingroup$ Thanks, the first hint made everything about 30x faster! $\endgroup$ May 9 '16 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.