dfloyd@io.com wrote:

What, exactly is elliptic curve encryption?

Well, some other have already described it. I'll list some references I've found: A Course in Number Theory and Cryptography, 2nd edition, Neal Koblitz, Springer-Verlag. Chapter 6 is titled "Elliptic Curves" and is split into four parts: basics, cryptosystems, factorization, primality testing. Elliptic Curve Public Key Cryptosystems, Alfred Menezes, Kluwer Academic Publishers. Haven't had a chance to read this book yet. Looks pretty good though :) Algorithms for Modular Elliptic Curves, J. E. Cremona, Cambridge University Press. Found this book last week, along with the above mentioned Menezes book. Likewise, I haven't had a chance to read it yet. It is divided into three parts: description of contructing elliptic curves, a collection of algorithms, a huge list of tables. The algorithms are either in Fortran or in pseudocode (unless the Fortran used allows semicolons and the sh-like FI keyword).

(Only thing I knew that the NeXT nearly had it in its OS, but the heavy hammer of ITAR squashed that...)

Yeah, for a while a friend and I tried getting that to work, but we were never successful. Then, in an version upgrade, the encryption disappeared ;) -- Karl L. Barrus: klbarrus@owlnet.rice.edu 2.3: 5AD633; D1 59 9D 48 72 E9 19 D5 3D F3 93 7E 81 B5 CC 32 2.6: 088C8F21; 97 73 9E 8B 98 3E DD B5 E8 97 64 7E 20 95 60 D9 "One man's mnemonic is another man's cryptography" - K. Cooper

What, exactly is elliptic curve encryption?

Exponentiation-based ciphers such as Diffie-Hellman use the fact that discrete logarithms are hard, but modular exponentiation is easy. So we quickly compute: x^y mod n (where n is prime) But not: log_x(x^y mod n) mod n Think of the numbers between 0 and n-1 as a group that work sort of like all Integers taken as a whole. Because they do have many of these properties, this makes these numbers an "abelian" group. So we can use some old properties from arithmatic such as: (a * b * c) mod n == (((a * b) mod n) * c) mod n With an elliptic curve, such as y^2 = x^3 - x, you can define a set of coordinates {<x0, y0>, <x1, y1> ... <xt, yt>} that are on the curve, where all x and all y are in a group like we use for Diffie-Hellman. For the different isomorphisms of the curves, you can then construct addition of coordinates, subtraction, multiplication and division, such that the results are also points on the curve. This makes this set of points an abelian group too. You can then do a Diffie Hellman analogue substituting multiplication for exponentiation, and a El Gamal analogue substituting multiplication for exponentiation and addition for multiplication. I have just recently been researching this subject, but I can provide some references tomorrow, if people are interested. I have found what appears to be an implementation of some of the artithmatic in a package called "pari", but I haven't had a chance to look at it closely. There are no p.d. elliptic curve _cryptography_ implementations that I'm aware of, which is something I'd like to see change... :-) There is an IEEE group working on a proposed standard at the moment; I need to get back to my contact with them to find out where they are at now. Most of the work in this area is being done by smart card people, because ec's seem to give you more bang for your buck in terms of modulus size, etc. Hope this helps. Doug