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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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$.
answered Jan 29, 2022 at 18:35
-
$\begingroup$ Alright, I assume $n$ is the 256-bit private key here, so the nonce is as strong as the private key itself? $\endgroup$ Commented Jan 29, 2022 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$– kelalakaCommented Jan 29, 2022 at 19:08
-
$\begingroup$ As usual, the $n$ is the order of the base point $G$. $\endgroup$– kelalakaCommented Jan 29, 2022 at 20:30