Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why is elliptic curve cryptography not widely used, compared to RSA?

crypto.stackexchange.com

Post reply on HN
Print view View original

1–10 of 31 posts

Re: Why is elliptic curve cryptography not widely used, compared to RSA?

#4

Post by S4M »

Wow, I always thought that elliptic curves were an algorithm to break cryptography like RSA. If I remember well, RSA is based on the fact that Z/pZ is a group when p is prime (for those who don't know, it's about taking the addition and multiplications for the numbers in [0..p-1] and taking the result modulo p), and elliptic curves offer a more generic framework for that...

Re: Why is elliptic curve cryptography not widely used, compared to RSA?

#6

Post by ColinWright »

S4M wrote: post #4

Wow, I always thought that elliptic curves were an algorithm to break cryptography like RSA. If I remember well, RSA is based on the fact that Z/pZ is a group when p is prime (for those who don't know, it's about taking the addition and multiplications for the numbers in [0..p-1] and taking the result modulo p), and elliptic curves offer a more generic framework for that...

Not really, no.

Very briefly ...

==== Start RSA recap

Given an integer n>1, the numbers a s.t. 0 and gcd(a,n) form a group under multiplication. That means that for every e with gcd(e,n)=1 there is a d s.t. d.e=1 (mod n).

Now take n=pq where p and q are primes. The function phi(n) counts how many elements are co-prime to n, and since n=pq that turns out to be (p-1)(q-1). So phi(n)=(p-1)(q-1). I'm going to write r=phi(n).

Take any e with gcd(e,r)=1. We can compute d s.t. d.e=1 (mod r), which means d.e = k.r+1 for some k. (Note: I'm doing this mod r, not mod n.)

Right.

Now take a message M (with 0 and gcd(M,n)=1) and compute E=M^e. We can do that fairly quickly using an adapted Russian Peasant Multiplication algorithm. This number "looks random" in some sense. You can transmit it to someone else.

They compute D=E^d. So what's that? Well, working modulo n:

    D = E^d
      = (M^e)^d
      = M^(d.e)
      = M^(k.r+1)
      = M^(k.r) x M
      = (M^r)^k x M
But Euler's extension of Fermat's Little Theorem says that if gcd(a,n)=1, then a^phi(n)=1 (mod n). Therefore M^r=1 (mod n), and so D=M.

Therefore we can recover M, so we can decrypt E.

So if you publish n and e, but keep d secret, people can send you E=M^e (mod n) and only you can read it.

Probably.

If someone can compute phi(n) then they can compute d from e and n, but we think that's the same as factoring n. Similarly, if you can compute discrete logarithms, but that seems to be about as hard as factoring.

==== End RSA recap.

All of this can be cast more abstractly in the group (Z/nZ, * ). Doing so gives us the same system in more generality. This is what ECC does. You choose and publish an elliptic curve - C. Then you choose an element, e, and compute its inverse d in C. You encrypt a message M by taking e.M (remembering that in ECC we usually use + as the operation symbol instead of * - so this is the equivalent of M^e).

And it all works.

Possibly someone who knows more about this than I will find gaping holes in the above, but I think that should get you started.

To address the other question:

    > I always thought that elliptic curves were
    > an algorithm to break cryptography like RSA
There is also Lentra's Elliptic Curve Integer Factoring Algorithm. That is basically the Pollard Rho factoring method, but in a group corresponding to an Elliptic Curve, rather than in the usual Z/nZ. Factoring integers can result in breaking RSA, and Elliptic Curves can be used in factoring, but that's a different question.

Re: Why is elliptic curve cryptography not widely used, compared to RSA?

#7

Post by seliopou »

S4M wrote: post #4

Wow, I always thought that elliptic curves were an algorithm to break cryptography like RSA. If I remember well, RSA is based on the fact that Z/pZ is a group when p is prime (for those who don't know, it's about taking the addition and multiplications for the numbers in [0..p-1] and taking the result modulo p), and elliptic curves offer a more generic framework for that...

Z/pZ is a field when p is prime. That's somewhat (indirectly) related to how the RSA algorithm works, but at a high level you're doing arithmetic in Z/nZ, where n = p * q for primes p and q.

Both RSA and ECC are based on the idea that exponentials are easy to compute, and undoing them is hard. In the case of RSA, you're exponentiating in Z/nZ and in ECC you're exponentiating in the group of points that arises from the chosen elliptic curve.

The first book in that list is a good text. It includes an appendix that includes almost everything you need to know about projective geometry to understand the theory of elliptic curves.

Re: Why is elliptic curve cryptography not widely used, compared to RSA?

#9

Post by VLM »

I thought the most interesting thing in the stack overflow was the complete lack of systems analysis.

99% of people who need encryption already have it, and they probably use RSA or at least a non-EC system. So almost by definition you're talking about converting an entire system, not just linking in a new library or CSS file...

The question is really, "Why aren't people replacing their entire SSL cert system and all their SSH shared keys just for fun?". Or maybe "Why is gradual generational turnover rate in security systems so slow?". Combining the two questions is strangely reminiscent of why does it take forever to roll out ipv6 and sunset ipv4?

Its possible for new stuff I'd evaluate the field and possibly an E.C. tech might win. But if turnover is perhaps 1% annually, its going to take a century unless theres a "crisis" or major revolutionary kick to the system.

Re: Why is elliptic curve cryptography not widely used, compared to RSA?

#10

Post by lucb1e »

VLM wrote: post #9

I thought the most interesting thing in the stack overflow was the complete lack of systems analysis. 99% of people who need encryption already have it, and they probably use RSA or at least a non-EC system. So almost by definition you're talking about converting an entire system, not just linking in a new library or CSS file... The question is really, "Why aren't people replacing their entire SSL cert system and all…

Minor note: This is not StackOverflow but a related site running the same software. SO is for coding questions specifically.
Post reply on HN