How long does it take to generate signature for Elliptic Curve keys using the P-256 curve?

Carmageddon

2/5/23, 7:00 PM

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?

0 + 0

elliptic-curves

verifiability

poncho

2/5/23, 8:31 PM

Do you have the private key to sign with?

Carmageddon

2/6/23, 3:25 AM

@poncho NO, I just edited to clarify this question.

Score:1

Crypto

fgrieu

2/5/23, 8:41 PM

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.

0 + 0

dave_thompson_085

2/5/23, 11:12 PM

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.

Carmageddon

2/6/23, 3:33 AM

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?

fgrieu

2/6/23, 5:12 AM

@dave_thompson_085: you read my mind!

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: How long does it take to generate signature for Elliptic Curve keys using the P-256 curve?

TH: ใช้เวลานานเท่าใดในการสร้างลายเซ็นสำหรับคีย์ Elliptic Curve โดยใช้เส้นโค้ง P-256

RO: Cât timp durează generarea unei semnături pentru cheile de curbă eliptică folosind curba P-256?

RU: Сколько времени занимает создание подписи для ключей на эллиптической кривой с использованием кривой P-256?

VI: Mất bao lâu để tạo chữ ký cho các phím Đường cong Elliptic bằng đường cong P-256?

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.