Elliptic curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S. Miller in 1985.
A binary field is a finite field GF(2m) which contains 2m elements for some m (called the degree of the field). The elements of this field are the bit strings of length m, and the field arithmetic is implemented in terms of operations on the bits.
An elliptic curve is a plane curve which is isomorphic to a curve defined by an equation of the form
y2 = x3 + ax + b
The set of points on such a curve — all solutions of the above equation together with a point at infinity — form an Abelian group, with the point at infinity as identity element and a generator element G. The use of elliptic curves in cryptography is based on an assumption that the “point multiplication” operation (for an integer k, finding kG = G+G+G+…+G) is relatively easy to calculate, but very hard to
“reverse” (i.e., finding k when only kG and G are known requires enormous computing power for large k and m).
The two critical ECC operations that greatly benefit from hardware acceleration are:
|| “Point multiplication”, i.e. calculation of coordinates of the point Q = kP given an integer k and point P. This operation is by far the most computationally intensive, and its hardware implementation improves the performance of the ECC algorithm and power consumed by the device.
||“Point verification” simply verifies if the given point P indeed belongs to the curve. This is important, because the value of kP for a point P that does not belong to the curve, might reveal the secret random number k. Although the verification is much less computationally intensive than the multiplication, its implementation in hardware allows to provide a complete solution (no finite field calculations in firmware) at virtually zero cost in gates.
The following table gives the approximate size (m) of the binary filed used in ECC to match the corresponding strength of the symmetric cipher (per NIST recommendations). For comparison, the bit length of comparable RSA public key solutions is also provided.
| 112 (3DES)
| 128 (AES-128)
| 256 (AES-256)
For each field degree m, NIST defined a pseudo-random curve along with a Koblitz curve. The pseudo-random curve has the form
2 + x y = x 3 + x
2 + b,
and the Koblitz curve has the form Ea:
y2 + x y = x
3 + ax 2 + 1
where a = 0 or 1.