2
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – arjunsiva
    Commented Jun 2, 2021 at 17:28
  • 2
    $\begingroup$ 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 ... $\endgroup$
    – Sil
    Commented Jun 2, 2021 at 18:03
  • $\begingroup$ @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? $\endgroup$
    – arjunsiva
    Commented Jun 2, 2021 at 18:40
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sil
    Commented Jun 2, 2021 at 18:58

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ How are the public keys (Xa, Ya) calculated in the first place in small devices, if they require so much computation? $\endgroup$
    – arjunsiva
    Commented Jun 3, 2021 at 6:31
  • 1
    $\begingroup$ (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.$ $\endgroup$
    – kodlu
    Commented Jun 3, 2021 at 7:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .