Introduction

Elliptic curve cryptography is a modern approach to asymmetric cryptography. It has to be considered a strong competitor to the RSA and DL-based (DSA, Diffie-Hellman) public key encryption and signature schemes.

An elliptic curves by itself is a special set of points in the 2D plane. The specific structure such curve point set offers can be exploited for cryptographic purposes. In particular, together with a carefully designed 'point addition operation' the curve's points form an algebraic group. Essential for the efficient implementation of elliptic curve cryptography is the availability of fast point addition routines.

I recommend the following books and papers for a deeper treatment of the subject:

• Wikipedia on ECC
• A primer/tutorial about ECC as appeared in the latest Phrack release.

Addition formulae

The following subpages contain some formulae for the addition of points on elliptic curves in several coordinate systems.

• Prime field curves
• Affine Coordinates
• Standard Projective Coordinates
• Jacobian Coordinates
• Modified Jacobian Coordinates
• Chudnovsky Coordinates
• Binary field curves
• Affine Coordinates
• Jacobian Coordinates
• Lopez-Dahab Coordinates

Test vectors

I provide test vectors for verification of implemented curve arithmetic on the 15 NIST standardized elliptic curves P{192,224,256,384,521},{B,K}{163,233,283,409,571}.

Misc

• There is an efficient algorithm to compute the legendre symbol (a|p) modulo a prime p.
• The algorithm of Shanks & Tonelli efficiently calculates square roots in finite prime fields.
• The task to compute the modular inverse of an element in a prime field can be accomplished using the extended euclidean algorithm.

---

The text of this page is licensed under the GNU General Public License. Copyright 2007 by B. Poettering (ecccoord AT point-at-infinity.org).
Last modified: Tue Sep 16 20:10:33 CEST 2008