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...)

> 
> 
> 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

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

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