# In Diffie Hellman key exchange using Elliptic Curve cryptography, how are the public keys calculated?

While calculating the public key, $$d * G = (X_a, Y_a)$$ and similarly for $$(X_b, Y_b)$$, where $$d$$ is the private key. If calculating $$d * G$$ means adding $$G$$ to itself $$d$$ times, why can't the same be done to guess the private key '$$d$$' by an intruder - adding $$G$$ to itself until he gets the public key and hence find the private key? How is the calculation of public key efficient and guessing it computationally infeasible?

• I found out that there are faster ways to multiply other than simply adding, but again I don't understand how that makes it impossible for the intruder to guess the private key using the same method? Commented Jun 2, 2021 at 17:28
• That is the elliptic curve discrete logarithm problem, look it up. As an analogy, the fact that you can quickly multiply integers does not mean you can quickly do the reverse, i.e. to factorize an integer. This is similar ...
– Sil
Commented Jun 2, 2021 at 18:03
• @Sil So does that mean there is a huge number of 'd's producing the same product d*G. So checking all of them is infeasible? Commented Jun 2, 2021 at 18:40
• It's not abou that (integer factorization is unique for example), it's that just by adding the point until you hit the one you want would take you too long for it to be of any use.
– Sil
Commented Jun 2, 2021 at 18:58

Current day elliptic curve cryptosystems use keys 200+ bits long. In this context it means that your group has size $$2^{200} \approx 10^{60},$$ so on average you will need to compute $$G,2G,\ldots,dG$$ until $$d \geq 5\times 10^{59}$$ until you hit the point $$(X_a,Y_a)$$ and discover the discrete logarithm $$d.$$
• (a)if the device is really weak they can be computed centrally and loaded on to the device during customisation, or more importantly, (b) since $d$ is known to the device a square and multiply type algorithm can be used to do the addition. It is the discrete log that is hard, the other direction is easy, if you have the trapdoor information, i.e., $d.$ Commented Jun 3, 2021 at 7:23