DLP - Which algorithms for large numbers are most efficient (in terms of time) in deriving most likely used private keys via Supercomputers?

37 Views Asked by At

Solving for $x$ is known as the discrete log problem.

$$g^{x} \pmod{p} = h$$

Now presume adversary Eve has the public key, $x_{pub}$ for the below encryption scheme;

$$g^{x_{priv}} \pmod{p} = h$$

Where

  1. $g$ is a generator and is a positive integer,
  2. $p$ is an unknown prime, and is of the form $p=2q+1$ where $q$ is prime
  3. $x_{priv}$ is the unknown private key,
  4. $x_{pub}$ is the known public key,
  5. $g \pmod{p}$ is a primitive root,
  6. $g, p, x_{priv}$ and $x_{pub}$ assumed to be large.

The aim is to obtain $x_{priv}$.

I am aware of several methods of solving it such as Pollard's rho, index calculus, polig-helman, brute-force etc.

Question: Which algorithms for large numbers are most efficient (in terms of time) in deriving most likely used private keys on Supercomputers - ie each key with a probability.

I'm assuming a supercomputer has at least 64 GB of Memory, and access to multiple CPUs / GPUs.

References & links are required where possible.

This is not a homework question. I am doing this as interest. This is one of multiple questions that was originally on InfoSec SE.