A little bit of Theory on Elliptic Curve Crypto

While the theory of elliptic curves is very deep, understanding cryptographic ramifications is quite simple because all of the code depending on the math is very well localized. Here is almost everything that you need to know as a programmer to reason about using ECC. If on the other hand, you want to know how to choose family parameters, you must delve deeply into the math. If you want to break it, you must probably break new EC ground first.

Imagine an abstract data type with immutable instances which we will call points as do the mathematicians. As in Diffie-Hellman there are a few hundred bits of family parameters. Choosing these bits is complex and well beyond the scope of this note. Typically an application will adopt some fixed already invented family and these bits will then be constant and not secret.

There are about 768 bits of information specific to each point, at least for ECDSA. (x and y are both about 384 bits and y can be derived from x in a few ms.) Points can be compared for equality but there seems to be no good sense of closeness, which would be of use to either the cipherer or his adversaries.

The only operations on points are addition (+), inverse (−), compare (=), and what I will call hash (H()). Addition and inverse are like integer addition and sign reversal. There are obviously only a finite number of points (about 2384) as there are only a finite number of 32 bit integers. All of the fancy math hides in the addition routine which is a bunch of straight line arithmetic with a few very rarely taken conditional branches. The time taken is thus highly constant. All of the facts that make these points useful to crypto, are that the addition is commutative and associative and the inverse is the additive inverse. In short:

For reference, mathematicians call this a finite abelian (commutative) group. Note that the above facts also apply to the type int, but not float in C. It is also useful to know that the inverse is about one machine instruction and the addition is a few dozen instructions. Comparison is just comparing the bits as the representation is typically canonical and the hash just extracts some bits from the representation. The hash might be used as a symmetric key in a ECC Diffie-Hellman system.

Addition of points is highly analogous to multiplication modulo a family prime in classic DH algorithms, in fact is it so analogous that DH moduli and ECC points may indeed be polymorphic in the programing language sense. In classic DH we take very large powers of a known base, pub = gprv mod m. g and m are constant family parameters and widely known. pub and prv are approximately public and private keys. It is very difficult to discover prv from pub. In the ECC form of DH the group addition replaces multiplication and we have pub = prv*g where pub and g are points and prv is a large integer (2384). The notation prv*g means adding g to itself prv times. The same trick that DH uses for large exponents works as well here.

Cryptic notes on ECDSA
Some code for finite fields upon which EC relies.