4 ms·

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 w

• ColinWright 13y ago
  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.
• seliopou 13y ago
  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.