Elliptic curve cryptography

The crucial property of an elliptic curve is that we can define a rule for "adding" two points which are on the curve, to obtain a 3rd point which is also on the curve. This addition rule satisfies the normal properties of addition. In math jargon, the points and the addition law form a finite Abelian group.

Alice, Bob, Cathy, David... agree on a (non-secret) elliptic curve and a (non-secret) fixed curve point F. Alice chooses a secret random integer Ak which is her secret key, and publishes the curve point AP = Ak*F as her public key. Bob, Cathy and David do the same.

Now suppose Alice wishes to send a message to Bob. One method is for Alice to simply compute Ak*BP and use the result as the secret key for a conventional symmetric block cipher (say DES).

Bob can compute the same number by calculating Bk * AP, since Bk*AP = Bk*(Ak*F) = (Bk*Ak)*F = Ak*(Bk*F) = Ak*BP.

The security of the scheme is based on the assumption that it is difficult to compute k given F and k*F.

In spite of its small size, Sizzle makes no compromises in terms of security. It uses Elliptic Curve Cryptography (ECC), which has been chosen by the National Security Agency as the next generation public-key cryptographic technology for protecting sensitive U.S. Government information [2].

As far as is known, with the above provisions, if the order of the fixed point F is an n-bit prime, then computing k from k*F and F takes roughly 2^(n/2) operations.

For example, if the order of F is a 240-bit prime, then an attack would be expected to need 2^120 operations.

This is what makes the use of elliptic curves attractive - it means that public keys and signatures can be much smaller than with RSA for the same predicted security.