2
$\begingroup$

It is a well-known fact that knowing the nonce used in signing the ECDSA signature allows the private key to be computed easily from that signature. If I understand it correctly, this nonce is a positive integer of finite size, so there aren't that many possibilities compared to trying to brute-force the private key directly. Actually, I read that in some cases knowing only one bit of nonce is enough to find it (lattice attacks). So is it possible with a powerful computer to brute-force the nonce in sensible time to get the private key?

$\endgroup$

1 Answer 1

1
$\begingroup$

You are confusing the biased-nonce attack with brute force. The lattice attacks require a bias on the generation of the nonce to recover the key.

Brute-forcing the nonce, on the other hand, is not possible for a classical attacker if you use a 256-bit curve since $k$ is chosen from $[1,n-1]$ uniform randomly where $n$ is the order of the base point $G$.

$\endgroup$
3
  • $\begingroup$ Alright, I assume $n$ is the 256-bit private key here, so the nonce is as strong as the private key itself? $\endgroup$ Jan 29 at 19:01
  • $\begingroup$ They don't have the same problems. The key is secret and used for a long time. On the other hand, the nonce is selected randomly for each signature. If there is a bias or collision on the nonce, the secret key can be found. The key generation process must be strong, too. If there are some weakness over there, one can exploit it, too. $\endgroup$
    – kelalaka
    Jan 29 at 19:08
  • $\begingroup$ As usual, the $n$ is the order of the base point $G$. $\endgroup$
    – kelalaka
    Jan 29 at 20:30

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.