News for hackers. Stuff that matters.
Re:Why is elliptic curve cryptography not widely used, compa... by S4M on Monday June 10, 2013 @07:01AM (#5853508)
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, compa... by ColinWright on Monday June 10, 2013 @07:31AM (#5853601)
Not really, no.

Very briefly ...

==== Start RSA recap

Given an integer n>1, the numbers a s.t. 0<=a<n 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<=M<n 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, compa... by seliopou on Monday June 10, 2013 @07:35AM (#5853616)
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.