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

Question

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?

Hwang

Cryptography is much better suited for this type of question. This is particularly off-topic for StackOverflow, because it doesn't directly involve programming. – Birdella

I'm voting to close this question as off-topic because it belongs on crypto.stackexchange.com – Rummy

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 – Psychokinesis

@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. – Hwang

Answer 1

The one-way attribute of ECC and RSA is due to the Chinese Reminder Theoreom (CRT). A series of arithmetic divisions where only the remainder is kept (aka Modulo operation %), which results in information loss in the output. As a result, the person with the keys takes one direct path to generate the output - and any would-be attacker has to exhaust a massive number of possible paths in order to determine what key was used to create the output. If the simple division was used instead of a modulo - then key data would be present in the output and it couldn't be used for cryptography.

If you lived in a world where you had a powerful enough computer to exhaust all possibilities - then the CRT wouldn't be useful as a cryptographic primitive. The computers we have now a fairly powerful - so we balance the power of our modern machines with a keysize that introduces enough range of possibilities so that they cannot be exhausted in a timeframe that matters.

The CRT is a subset of the P vs NP problem set - so perhaps proving P=NP may lead to a way of undermining the oneway aspect of asymmetric cryptography. We know that there is a way to factor CRT using a quantum computer running Shor's Algorithm. Shor's Algorithm has proven that we can defeat the so-called "trapdoor", or one-way attributes of CRT, it is still however an expensive attack to conduct.

The following lecture is my favorite description of the CRT. It shows that there are many possible solutions for one direction forcing an attacker to exhaust them all and only one solution for the other: https://www.youtube.com/watch?v=ru7mWZJlRQg

Misdemean

It's been a long time I thought about the intricacies of CRT, Even the video you sent, got me pretty close but I had to go back and put something on paper because it's never easy to follow. But.. The IBM paper on Shore's Algo is really blowing over my head.. I hate to ask but could you suggest some reading ? I get the computing brute-forcing even for CRT, but cannot grasp this Shore's. – Ronnironnica

Answer 2

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:

• For rising to power, see Exponentiation by squaring.
• For ECC point multiplication, see point multiplication.

Vastah

This sounds like Elliptic-Curve Diffie-Hellman - is there also an elliptic curve asymmetric key crypto algorithm? - Also, maybe I didn't phrase my question totally clearly - but I guess what I mean to ask is: in your example - what is to prevent an attacker from simply listening in to the first transmission from me to the server, and then just dotting the known starting point until they hit the correct ending point? doesn't it still just take k operations? – Hwang

1) There is no pure ECC algorithm (at least that's what I know), because to decrypt any message, you need to do the "inverse dotting", but look at ElGamal ES. – Vastah

@Hwang 2) Imagine k being similarly sized as the point itself. Given computational power of today's computers (approx. 10^9 operations per second), just trying to determine k from G = kP given known values of G (sent point) and P (starting point) would take more time than what is the lifespan of the Earth; this is called elliptic curve discrete logarithm problem. If you know the power you want to raise to (your private key), you can use 2P=P+P; 4P=2P+2P... – Vastah