News for hackers. Stuff that matters.
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.

There are no comments on this comment yet.