Join Log in
Score:2
Mr. Engineer avatar Crypto

Is it possible to brute-force the nonce used in ECDSA?

ng flag
Mr. Engineer

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?

149
0 + 0
dsa
Score:1
kelalaka avatar Crypto
in flag
kelalaka

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$.

0 + 0
Mr. Engineer avatar
ng flag
Mr. Engineer
Alright, I assume $n$ is the 256-bit private key here, so the nonce is as strong as the private key itself?
0
Reply
kelalaka avatar
in flag
kelalaka
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.
0
Reply
kelalaka avatar
in flag
kelalaka
As usual, the $n$ is the order of the base point $G$.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.