From: norm@mediacity.com (Norman Hardy)
Date: Sun, 26 Nov 1995 13:58:57 +0800
To: cypherpunks@toad.com
Subject: Learning about Elliptic Curves
Message-ID: <acddae750002100481c8@DialupEudora>
MIME-Version: 1.0
Content-Type: text/plain


I have found an easy introduction to elliptic curves. It is "Rational
Points on Elliptic Curves" by Joseph H. Silverman & John Tate.
(Springer-Verlag ISBN: 0-387-97825-9 or 3-540-97825-9) It is a breezy
undergraduate introduction. It emphasizes the mathematical elegance. It
mentions crypto applications but does not delve deeply.

Schneier recommends "Elliptic Curve Public Key Cryptosystems" by Alfred J.
Menezes. (Kluwer Academic Publishers ISBN: 0-7923-9368-6) That book has
only a very compressed theory section which already requires knowledge of
field theory. I think that the first book is a good intro to the second,
which does cover crypto applications.

What I learned is that elliptic curves are an alternative to finite fields
for crpto purposes. Here is what they have in common:
There are many (2^70 -- 2^2000) values any one of which can be represented
in the machine in constant space. a_i is the ith one of these values. If
someone sends you a_i it is real hard to figure out what i is. There is an
operation that isn't too expensive for computing a_(i+j) given a_i and a_j.
For some big integer i you can compute a_i in about (log i)^3 steps. For
RSA, knowing how to do these two computations does not reveal what the
period of the sequence is, i.e. what is the first i after 0 such that a_0 =
a_i. Knowing the period is tantamount to knowing the private key.