-1
$\begingroup$

If you have a plain text document, known public key to verify generated signature strings against. EDIT: You do NOT know the private key, this is all you have.

Using a modern computing power with 4 cores, 12 threads, (or GPUs, if that is faster) - how long would it take to come up with a signature that the given public key would authenticate?

$\endgroup$
2
  • 2
    $\begingroup$ Do you have the private key to sign with? $\endgroup$
    – poncho
    Oct 5, 2021 at 20:31
  • $\begingroup$ @poncho NO, I just edited to clarify this question. $\endgroup$ Oct 6, 2021 at 3:25

1 Answer 1

1
$\begingroup$

If the private key is available: see this answer.

If it's not (which appear to be the hypothesis): forget about it using the computing power available. The best known attack (Pollard's rho) would require in the order of $2^{129}$ point additions. It the machine could perform these at a rate of $2^{36}$ per second (which is wildly optimistic), the division gives 300 million million million years (obtained as $2^{129-36}/86400/365$ years).

We should not even hope for a strike of luck: when we do a fraction $1/k$ of the required work, probability of success is in the order $1/(k^2)$.

Thus the best avenues of success are to somehow obtain the private key, or access to a device that can sign. Methods abound: side channel attacks, exploitation of flaws of the random number generator used for signing, exploitation of other software flaws, penetration of the IT infrastructure that has the private key, social engineering, bribery, theft, coercion.

$\endgroup$
3
  • 1
    $\begingroup$ 2^93/86400/365 is not 3 million, it is 314 billion billion (using US billions) i.e. 314x10^18. I think you may have confused 10^20 with 2^20. $\endgroup$ Oct 5, 2021 at 23:12
  • $\begingroup$ Thank you! that answer is pretty good, so I guess best hope is exploitation of flaws of the random number generator used for signing - any references to read up on those, in relation to the mentioned EC p-256 keys? Is that enough information even, at this point? $\endgroup$ Oct 6, 2021 at 3:33
  • $\begingroup$ @dave_thompson_085: you read my mind! $\endgroup$
    – fgrieu
    Oct 6, 2021 at 5:12

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.