What makes the trapdoor function in elliptic curve cryptography hard to reverse?

6
votes

I've been reading this article on elliptic-curve crypto and how it works: http://arstechnica.com/security/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/

In the article, they state:

It turns out that if you have two points [on an elliptic curve], an initial point "dotted" with itself n times to arrive at a final point [on the curve], finding out n when you only know the final point and the first point is hard.

It goes on to state that the only way to find out n (if you only have the first and final points, and you know the curve eqn), is to repeatedly dot the initial point until you finally have the matching final point.

I think I understand all this - but what confuses me is - if n is the private key, and the final point corresponds to the public key (which I think is the case), then doesn't it take the exact same amount of work to compute the public key from the private, as it does the private from the public (both just have to recursively dot a point on the curve)? am I misunderstanding something about what the article is saying?

1
cryptographyelliptic-curve
Cryptography is much better suited for this type of question. This is particularly off-topic for StackOverflow, because it doesn't directly involve programming. - Artjom B.
I'm voting to close this question as off-topic because it belongs on crypto.stackexchange.com - erickson
If you naively computed B+B+B+... n times, it'd be indeed too expensive. But you can Compute 2B=B+B and then 4B=2B+2B etc. reducing the number of point additions to the logarithm of the exponent. See en.wikipedia.org/wiki/Exponentiation_by_squaring - CodesInChaos
@ArtjomB - sorry - I didn't know there was a crypto based stack exchange! I can search and maybe re-ask over there. Thanks - and my bad. - user1971524

1 Answers

0
votes

EDIT: I previously stated that n is not the private key. In your example, n is either server or client private key.

How it works is that there is a starting point known to anybody.

  • You select random integer k and do the "dotting operation" k-times. Then you send this new point to the server. (k is your private key)
  • Server does the same with the starting point, but q-times and sends it to you. (q is server's private key)
  • You take the point you got from server and "dot" it k-times. The final point would be the starting point "dotted" k*q-times.
  • Server does the same with point it got from you. And again its final point would be the starting point "dotted" q*k-times.

That means the final point (= the starting point "dotted" k*q-times) is the shared secret since all what any attacker would know is the starting point, the starting point dotted k-times and the starting point dotted q-times. And given only those data, it's practically impossible to find the final point as a product of k*q unless any of those known.

EDIT: No, it doesn't take the same time to compute k from G = kP given known values of G (sent point) and P (starting point). More in comment section and: