An Elliptic Curve Cryptography (ECC) Tutorial

Elliptic curves are useful far beyond the fact that they shed a huge amount of light on the congruent number problem. For example, many people (probably you!) use them on a daily basis, since they are used to make some of the best public-key cryptosystems (= methods for sending secret data).

I think the Wikipedea opening description of Elliptic curve cryptography is OK (no comment about the rest of the article):

Elliptic curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz [1] and Victor S. Miller [2] in 1985.

Elliptic curves are also used in several integer factorization algorithms that have applications in cryptography, such as, for instance, Lenstra elliptic curve factorization, but this use of elliptic curves is not usually referred to as "elliptic curve cryptography."

[...] As for other popular public key cryptosystems, no mathematical proof of difficulty has been published for ECC as of 2006. However, the U.S. National Security Agency has endorsed ECC technology by including it in its Suite B set of recommended algorithms. Although the RSA patent has expired, there are patents in force covering some aspects of ECC.
Note: Neal Koblitz is a math professor here at UW. He wrote the book on the congruent number problem (I scanned some of it for the website). You might see him around this summer, since he's teaching a summer school class.
Image koblitz

Basic Problem: How can people or computers send secret messages to each other without having to send out passwords ahead of time? How did mathematicians put the guys with briefcases handcuffed to their hands out of business?

Sandor Kovacs will go into great detail about this question in his course, and you might view today as a preview of some of what he'll do, with the bonus that today you get to try it out on a computer. Today I'll just give you the chance to understand and play with one example that addresses this basic problem.



Subsections
William Stein 2006-07-07