Elliptic Curve Point Multiply and Verify Core

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(2^m) which contains 2^m 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
y² = x³ + 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.

For each field degree m, NIST defined a pseudo-random curve along with a Koblitz curve. The pseudo-random curve has the form

y ² + x y = x ³ + x ² + b,

and the Koblitz curve has the form Ea:

y² + x y = x ³ + ax ² + 1

where a = 0 or 1.

Function Description

The core implements the point multiplication operation and the point verification operations. The operands for the multiplication: k, Px, Py are placed into the shared memory before the start of operation. Once the operation is complete, the results are placed back into the shared memory. The curve parameters a/b/m as well as the width of CPU memory are fixed for the particular version of the core, for example the ECC1-163/32 core work with the NIST binary curve of 163 bits and has a 32-bit wide interface to the CPU memory.

Design of ECC1 allows sharing the arbitrated CPU memory to store the arguments and results of operations. This both helps to save the silicon resource in the extremely compact implementations (smart cards) and simplify the data transfer between the CPU and the ECC1 core. The memory load during the core operation is very small, about 5% of the total cycles. If sharing memory is not desirable, an optional dedicated memory can be used.

Implementation Details

Representative synthesis results for the ECC1-163/32 are shown below.