0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you mean you have access to a super computer for the attack, or you want the attack to work against a super computer? Additionally, by "deriving most likely used private keys", do you mean a function/algorithm $f$ such that $f(x_{\text{pub}}) = x_{\text{priv}}$ as efficiently as possible? $\endgroup$ – Mark Jan 11 '18 at 20:28
  • $\begingroup$ I don't have access to a supercomputer. This would be run on a supercomputer to decode for $x_{priv}$. I do not know what the most likely private keys would be, but can assume they can be generated once one pair of ($x_{priv},x_{pub}$) is found due to number theory $\endgroup$ – unseen_rider Jan 11 '18 at 20:44

Your Answer

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

Browse other questions tagged or ask your own question.