Score:2

Crypto

Cracking Elliptic Curve Cryptography

James

11/9/22, 2:52 AM

I am quite new to the study of elliptic curve cryptography and as such I might be asking something with a mundane solution, but I can't easily find such a solution online. My understanding of ECC is that you can generate a private key (some integer $k$), a starting point on the curve ($G$), and a curve equation, and then generate a public key through finding $kG$. My understanding is then that your computer would perform however many operations are required to find $kG$ (if $k$ was 16 then that would be four operations).

With this data the starting point $G$, the curve equation, and the public key is made public. What I am wondering is why can't an attacker try to find out what the private key $k$ simply is, take the starting point and perform operations until they reach the public key and as such know what $k$ is? Is it based in the fact that the sender only needs 4 operations to calculate $kG$ whereas the attacker would need 16 operations (for the given example)?

1127

1 + 7

elliptic-curves

MaiaVictor

11/9/22, 5:22 AM

You need to guess a private key before you start doing the operations. If we're talking about 256-bit private keys, there are `2^256` keys to try. You'll only reach the target's public key if you guessed the correct private key. That means that, if you pick a random private key and perform operations hoping to reach the target's public key, there is only `0.0000000000...(+66 zeros)...8` chance of success per try.

James

11/9/22, 5:28 AM

But if the user's computer for instance took 10 computation to calculate a public key (a simplistic example), the attacker's computer would only need to start at $G$ and perform about 1024 computations to reach the point of $kG$. I can see this is potentially quite a large difference, but it seems like a supercomputer could get through a bigger example within a finite amount of time (weeks or so).

dave_thompson_085

11/9/22, 5:46 AM

For the sizes currently considered secure (256 or 255 bit up) this 'attack' takes more energy than exists in the universe. You need to control huge numbers -- trillions of trillions -- of other universes, which means you must be a god, and your profile does not identify you as a god. See https://crypto.stackexchange.com/questions/58373/how-to-calculate-a-private-key-from-public-key-on-elliptic-curve and more linked there.

fgrieu

11/9/22, 6:48 AM

See the [wheat and chessboard](https://en.wikipedia.org/wiki/Wheat_and_chessboard_problem) parable, only with a larger chessboard when it comes to actually used Elliptic Curves (where $k$ can take $n\approx2^{256}$ values). Incidentally, "take the starting point and perform operations until they reach the public key" is far from the best strategy: if there are $n$ possible values of $k$, it requires $\Theta(n)$ steps, when there are strategies that require only $\Theta(\sqrt n)$ steps.

user253751

11/9/22, 12:33 PM

@James Okay, now what if the user's computer took 256 computations to calculate the public key? How many computations does the attacker's computer need to do?

PrincePolka

11/9/22, 3:50 PM

"Is it based in the fact that the sender only needs 4 operations to calculate kG whereas the attacker would need 16 operations (for the given example)?" Yes

James

11/10/22, 1:23 PM

Thank you for all the examples and answers. I understand how quickly this simplistic attack becomes computationally unviable now.

Score:5

Crypto

jjj

11/9/22, 9:36 AM

To compute $kG$ you need $O(log(k))$ operations. (For every bit, double the result and and additionally add $G$ if bit is $1$). As you mentioned in a comment for around $k=1024$ you would need like $10$ operations to compute $kG$. But this example is way to small for practical use and the exponential effect does not really kick in yet. Normally, when the curve has order around $2^n$, $k$ would be of a similar magnitude as $2^n$.

So for curves with order $2^{256}$ish you need around $log(2^{256})=256$ operations to compute $kG$ but $2^{256}$ to attack it. There is only a problem with absurdly small curves with order of maybe up to a few billion or trillion (like in your example).

0 + 3

AAA

11/9/22, 4:17 PM

You can do better than $2^{256}$. You can use baby-step giant-step to recover $k$ in roughly $2^{128}$ time. Nevertheless, the point stands: it takes polynomial time to compute $kG$, but the best known attacks require exponential time to recover $k$.

James

11/10/22, 1:52 PM

If we are able to say that as an example a computer can calculate 80,000,000,000 operations per a second (eighty computers performing an operation each nano-second), which is approximately $2^{36}$ operations per second, and the fastest attacks can find the key in $2^{n/2}$ operations where $n$ is the key size, wouldn't a key size of 138 be sufficient to essentially make any attack unviable (taking approximately 3200 years to calculate)?

James

11/10/22, 1:57 PM

As an additional alternative, if there is so much worry about Quantum Computing perhaps being able to attack encryption of smaller key sizes, wouldn't it be sufficiently possible to create an Elliptic Curve Cryptosystem with large key sizes without taking too long to calculate (1024 operations doesn't seem like it would take too long for a modern computer to perform, even if each operation took 1,000,000 nanoseconds to perform)?

Gabriel Garrett

4/27/23, 6:40 AM

@AAA is there any publicly known implementation of baby-step giant-step for Elliptic Curve Encryption?

Elon Musk

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

EN: Cracking Elliptic Curve Cryptography

TH: แคร็กการเข้ารหัส Elliptic Curve

RO: Criptografie cu curbă eliptică de cracare

RU: Криптография на основе эллиптических кривых

VI: Bẻ khóa mật mã đường cong Elliptic

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.