What, exactly is elliptic encryption?
What, exactly is elliptic curve encryption? (Only thing I knew that the NeXT nearly had it in its OS, but the heavy hammer of ITAR squashed that...)
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
dfloyd@io.com says:
What, exactly is elliptic curve encryption?
Basically, there are ways of extending public key methods into fields other than the integers modulo some prime -- you can also perform these methods in fields based on so-called eliptic curves, and when you do it turns out that there are certain speed benefits. Perry
From: "Perry E. Metzger" <perry@imsi.com> Basically, there are ways of extending public key methods into fields other than the integers modulo some prime Small correction. While integer modulo a prime are fields (i.e. they have division), elliptic curve solutions only have a group structure, which is usually written as addition. Eric
Eric Hughes says:
From: "Perry E. Metzger" <perry@imsi.com> Basically, there are ways of extending public key methods into fields other than the integers modulo some prime
Small correction. While integer modulo a prime are fields (i.e. they have division), elliptic curve solutions only have a group structure, which is usually written as addition.
I stand corrected... .pm
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
From: db@Tadpole.COM (Doug Barnes) 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. Well, you actually get just addition and subtraction as binary operations. Multiplication is integers by elliptic curve elements and is shorthand for multiple additions. Division doesn't always make sense. 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. The multiplication takes an integer (the exponent analogue) by a curve element (the base analogue). 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. Burt Kaliski of RSA Labs is the chair of P1363. Archives are at rsa.com. Eric
participants (5)
-
db@Tadpole.COM -
dfloyd@io.com -
eric@remailer.net -
Karl Lui Barrus -
Perry E. Metzger