Provided, that you have to multiply a well known G by the private key to obtain the public key, why not keep adding G to itself until you reach the public key. The private key should be the number of times you've added the G to itself. Is it correct? And if so - why isn't it feasible?
$\begingroup$
$\endgroup$
8
-
4$\begingroup$ Hint: how many times would one have to add G to itself to have reasonable probability to see that plan suceed? What's the largest number of times mankind has repeatedly performed a task even remotely similar to adding G (once), say by the order of magnitude of the number of bits involved in the calculation? For a possible point of comparison on the later, see here. $\endgroup$– fgrieu ♦Apr 15, 2018 at 11:33
-
2$\begingroup$ You may also want to note that this is not how the public key is computed from the private key. $\endgroup$– SEJPMApr 15, 2018 at 14:19
-
2$\begingroup$ @SEJPM Highly underrated comment. Cryptographic teaching should emphasize more that the only reason exponentiation is useful for crypto is because square-and-multiply (or whatever you call it) provides an exponential advantage over an attacker. Fast exponentiation algorithms are really the core of discrete-logarithm-based systems, rather than just another optimization. $\endgroup$– yyyyyyyApr 15, 2018 at 17:25
-
$\begingroup$ All elliptic curve cryptography tutorials I found online explain, that public key is calculated from private key by adding G to itself k times, where k is the private key. So why can't we calculate the private key using my algorithm? $\endgroup$– Matthias DanetzkyApr 16, 2018 at 5:10
-
1$\begingroup$ @MatthiasDanetzky Those tutorials are wrong. The public key is computed from the private key by an operation that is mathematically equivalent to adding the base point $G$ to itself $k$ times, but the actual computation performed is different (see SEJPM's comment). You are correct that ECC (and other incarnations of the same theme) couldn't possibly be secure if one really just naïvely added a point to itself $k$ times. $\endgroup$– yyyyyyyApr 16, 2018 at 8:46
|
Show 3 more comments
2 Answers
$\begingroup$
$\endgroup$
1
Yes your method is mathematically correct but it isn't feasible because of the size of the secret key $k$ that is used in practice.
Typically you are using curves over $\mathbb{F}_q$ where $\log_2 q \approx 256$. This means that there are $2^{256}$ possibilities for $k$ and, on average, it will take a very, very, very long time to find the correct one.
As a comparison, the Universe itself is estimated to be "only" $2^{58.5}$ seconds old. This means that even if you could try $1,000,000 \approx 2^{20}$ values of $k$ every second, it would take you $2^{255-20} = 2^{235}$ seconds to try half of the possible values. This amount of time is $2^{235-58.5} = 2^{176.5}$ times greater than the age of the Universe.
-
3$\begingroup$ FYI, the field over which the curve is defined is not the ring in which private scalars live. The order of the field and the order of the scalar ring can't be much different—Hasse's theorem restricts them to be pretty close—so the conclusion doesn't change, but the reasoning isn't quite right. (And for the best generic attacks (better than this one), what matters is not the order of the scalar ring, but the largest prime factor of the scalar ring. E.g., for Curve25519, the scalar ring has order near $2^{255}$, but it is $8p_1$ for a 252-bit prime $p_1$; the size of $p_1$ is what matters.) $\endgroup$ May 2, 2018 at 21:37
$\begingroup$
$\endgroup$
1
Turns out, that the public key is not calculated by adding G to itself k (private key) times. It is calculated by first changing the k to binary form and multiplying the public key variable by 2 (adding to itself) for each bit while adding G if the current bit has value of one.
-
2$\begingroup$ That does not answer the question. Also, there are other very common ways to calculate the private key from the public key, thus "It is calculated" is often wrong, and should be "It can be calculated more efficiently, for example" $\endgroup$– fgrieu ♦Apr 17, 2018 at 8:24