5.2Hardware implementation

meet the performance requirements. This section gives an introduction to hardware implementation of elliptic curve systems. The main design issues are discussed in §5.2.1. Architectures for finite field processors are introduced in §5.2.2. We begin with an overview of some basic concepts of hardware design.

Gate A gate is a small electronic circuit that modifies its inputs and produces a single output. The most common gate has two inputs (but may have more). Gates comprise the basic building blocks of modern computing devices. The most common gates are NOT (inverting its input), NAND (logical AND of two inputs followed by inversion), NOR (logical OR of two inputs followed by inversion), and their more costly cousins AND and OR. Gate count typically refers to the equivalent numbers of 2-input NAND gates.

VLSI Very large scale integration (VLSI) refers to the building of circuits with gate counts exceeding 10,000. A VLSI circuit starts with a description in VHDL, Verilog, or other hardware-description languages that is compiled either into information needed to produce the circuit (known as synthesis) or into source code to be run on general-purpose machines (known as a simulation). The design of VLSI circuits involves a trade-off between circuit-delay caused by the speed of signal propagation and power dissipation. Judicious layouts of the physical circuit affect both. Other tools available include layout editors to assist with block placement and timing-analysis tools to tune the design. These custom designs can be costly in terms of time, money and other resources.

FPGA A field-programmable gate array (FPGA) consists of a number of logic blocks each of which typically contains more than a single gate and interconnections between them. These can be converted into circuits by judicious application of power to close or open specific electrical paths. In essence, the FPGA is programmed. The change is reversible, allowing circuits to be created and modified after manufacture (hence “field-programmable”). An FPGA can be large with a sea of gates numbering 20,000 or more. FPGAs were originally introduced as a means of prototyping but are increasingly being used to create application-specific circuits that will often outperform binary code running on generic processors. Programming is typically done with vendor-specific tools similar to those used in creating VLSI circuits.

Gate Array A gate array consists of a regular array of logic blocks where each logic block typically contains more than a single gate and also interconnections between these blocks. Circuits are formed by judiciously fusing connections between blocks. This process is irreversible. With the advent of FPGAs that provide considerably more flexibility, gate array technology seems to be used far less.

ASIC Application-specific integrated circuit (ASIC) is the terminology used in regard to VLSI or gate array.

accelerator for finite field arithmetic only, and then use an off-the-shelf microprocessor to perform the higher-level functions of elliptic curve point arithmetic. It is important to note that an efficient finite field multiplier does not necessarily yield an efficient point multiplier—all layers of the hierarchy need to be optimized.

Moving point addition and doubling and then point multiplication to hardware provides a more efficient ECC processor at the expense of more complexity. In all cases a combination of both efficient algorithms and hardware architectures is required.

One approach to higher functionality is the processor depicted in Figure 5.3. Along with program and data memory, the three main components are an arithmetic logic unit (AU), an arithmetic unit controller (AUC), and a main controller (MC). The AU performs the basic field operations of addition, squaring, multiplication, and inversion, and is controlled by the AUC. The AUC executes the elliptic curve operations of point addition and doubling. The MC coordinates and executes the method chosen for point multiplication, and interacts with the host system.

Figure 5.3. Elliptic curve processor architecture.

Let’s consider how a higher functionality processor might handle the computation of k P for a randomly chosen integer k. The host commands the processor to generate k P where the integer k and the (affine) coordinates of P are provided by the host. The integer k is loaded into the MC, and the coordinates of P are loaded into the AU. The MC instructs the AUC to do its initialization which may include converting the affine coordinates of P to projective coordinates needed by the point addition and doubling formulae. The MC scans the bits of k and instructs the AUC to perform the appropriate elliptic curve operations, which in turn instructs the AU to perform the appropriate finite field operations. After all bits of k are processed, the MC instructs the AUC to convert the result back to affine coordinates. The host reads the coordinates of k P from the registers in the AU. Two important consequences of having two controllers are the ability to permit parallel processing and pipelining of operations. The MC can also use the data storage capability to implement algorithms that use precomputation to compute k P more efficiently (see §3.3).

228 5. Implementation Issues

Criteria for selecting hardware designs

The following are some of the issues that have to considered in hardware design. It should be emphasized that a good design demands a thorough understanding of the target platform, operating environment, and performance and security requirements.

1.Cost is always a significant issue with hardware designers, and is driven by all of the criteria that follow.

2.Hardware vs. software. Is there a compelling argument to choose a hardware accelerator over a software implementation?

3.Throughput. A device that will be installed into a server will likely need to do hundreds or thousands of elliptic curve operations per second whereas devices designed for handheld computers will require only a small fraction of this.

4.Complexity. The more levels of the hierarchy that the device implements, the more complex the circuitry becomes. This translates into more silicon area on a custom VLSI device or a much larger FPGA. It will also result in higher cost.

5.Flexibility. Issues pertinent here include the ability of the device to perform computations on curves over binary fields and prime fields.

6.Algorithm agility. Many cryptographic protocols require cryptographic algorithms to be negotiated on a per-session basis (e.g., SSL). Reconfigurable hardware might be an attractive feature provided that performance is not significantly impacted.

7.Power consumption. Depending on the environment where the device will operate, power consumption may or may not be a major issue. For example, contactless smart cards are very constrained by the amount of power available for cryptographic operations whereas a server can afford much higher power consumption.

8.Security should always be paramount in any design consideration. If the device is designed to perform only point additions and doublings, then it is activated during a point multiplication k P by the bits associated with the random value k. Without careful design of the overall architecture, bits of k could be leaked by side-channel attacks. Countermeasures to attacks based on timing, power analysis, and electromagnetic radiation (see §5.3) should be considered based on the environment in which the device will operate.

9.Overall system architecture. If the overall system has a microprocessor with enough free cycles to handle protocol functionality above finite field arithmetic (see Figure 5.2), then, depending on other criteria, this may be good reason to design the device for finite field arithmetic only.

10.Implementation platform. A custom VLSI or gate array design or an FPGA may be used. FPGAs typically have a high per unit cost versus VLSI and gate array devices. Design costs are however significantly higher for VLSI implementations.

230 5. Implementation Issues

to a polynomial basis. If f (z) is the reduction polynomial, then we write f (z) = zm + r (z), where degr ≤ m − 1.

Moreover, if r (z) = rm−1zm−1 + · · · + r2 z2 + r1z + r0, then we represent r (z) by the binary vector

r = (rm−1, . . . , r2, r1, r0).

A multiplier is said to be bit-serial if it generates one bit of the product at each clock cycle. It is digit-serial if it generates more than one bit of the product at each clock cycle. We present bit-serial multipliers for the three cases:

(i)fixed field size with arbitrary reduction polynomial;

(ii)fixed field size with fixed reduction polynomial; and

(iii)variable field size (with arbitrary or fixed reduction polynomials). We also describe a digit-serial multiplier for the fourth case:

(iv)fixed field size with fixed reduction polynomial.

In Figures 5.4–5.11, the following symbols are used to denote operations on bits A,

B, C:

(i) Fixed field size with arbitrary reduction polynomial Algorithm 5.3, which multiplies a multiplicand a F2m and a multiplier b F2m , processes the bits of b from left (most significant) to right (least significant). The multiplier, called a most significant bit first (MSB) multiplier, is depicted in Figure 5.4 for the case m = 5. In Figure 5.4 b is a shift register and c is a shift register whose low-end bit is tied to 0. An MSB multiplier can perform a multiplication in F2m in m clock cycles.

Algorithm 5.3 Most significant bit first (MSB) multiplier for F2m

INPUT: a = (am−1, . . . , a1, a0), b = (bm−1, . . . , b1, b0) F2m , and reduction polynomial f (z) = zm + r (z).

OUTPUT: c = a · b.

1.Set c ← 0.

2.For i from m − 1 downto 0 do

2.1c ← leftshift(c) + cm−1r .

2.2c ← c + bi a.

3.Return(c).

b4

Figure 5.4. Most significant bit first (MSB) multiplier for F25 .

Algorithm 5.4, which multiplies a multiplicand a F2m and a multiplier b F2m , processes the bits of b from right (least significant) to left (most significant). The multiplier, called a least significant bit first (LSB) multiplier, is depicted in Figure 5.5.

Algorithm 5.4 Least significant bit first (LSB) multiplier for F2m

INPUT: a = (am−1, . . . , a1, a0), b = (bm−1, . . . , b1, b0) F2m , and reduction polynomial f (z) = zm + r (z).

OUTPUT: c = a · b.

1.Set c ← 0.

2.For i from 0 to m − 1 do

2.1c ← c + bi a.

2.2a ← leftshift(a) + am−1r .

3.Return(c).

One difference between the MSB and LSB multipliers is that the contents of two of the four registers in Figure 5.4 are not altered during a multiplication, while three of the four registers in Figure 5.5 are altered. In other words, the MSB multiplier only has to clock two registers per clock cycle, as compared to three for the LSB multiplier.

(ii) Fixed field size with fixed reduction polynomial If the reduction polynomial f (z) is fixed and is selected to be a trinomial or pentanomial, then the design of the multiplier is significantly less complex since a register to hold the reduction polynomial is no longer needed. Figure 5.6 illustrates an MSB multiplier for F25 with fixed reduction polynomial f (z) = z5 + z2 + 1.

232 5. Implementation Issues

Figure 5.5. Least significant bit first (LSB) multiplier for F25 .

Figure 5.6. MSB multiplier with fixed reduction polynomial f (z) = z5 + z2 + 1.

(iii) Variable field size The MSB multiplier in Figure 5.4 can be extended to multiply elements in the fields F2m for m {m1, m2, . . . , mt }, where m1 < m2 < · · · < mt . Each register has length mt . Figure 5.7 illustrates an MSB multiplier that can implement multiplication in any field F2m for m {1, 2, . . . , 10}, and for any reduction polynomial. Note that only the contents of registers b and c change at each clock cycle. The controller loads the bits of a, b and r from high-order to low-order and sets the unused bits to 0. Although the unused cells are clocked, they consume little power since their contents do not change.

The circuit can be simplified if each field has a fixed reduction polynomial, preferably a trinomial or a pentanomial. Figure 5.8 illustrates a variable field size MSB multiplier for F25 , F27 , and F210 with the fixed reduction polynomials z5 + z2 + 1,

k = 2 and l = 3. Figure 5.10 shows the circuit for digit multiplication excluding the interconnect of Figure 5.9 and the interconnect on the c register for the final reduction modulo f (z). The final reduction interconnect will require multiplexors.

Squaring

Squaring can of course be performed using any of the multipliers described above. If the reduction polynomial f (z) is fixed and is a trinomial or a pentanomial, then it is possible to design a circuit that will perform a squaring operation in a single clock cycle (vs. m clock cycles for the bit-serial multipliers). Moreover, the squaring circuit will add very little complexity to the multiplication circuit. A squaring circuit that takes only one clock cycle is important when inversion is done by multiplication (see below).

236 5. Implementation Issues

c= a2

=a6 z12 + a5z10 + a4z8 + a3 z6 + a2 z4 + a1z2 + a0

=(a6 + a3)z6 + a6 z5 + (a5 + a2)z4 + a5 z3 + (a4 + a1)z2 + a4 z + a0.

A squaring circuit is illustrated in Figure 5.11.

Figure 5.11. Squaring circuit for F27 with fixed reduction polynomial f (z) = z7 + z + 1.

Inversion

The most difficult finite field operation to implement in hardware is inversion. There are two basic types of inversion algorithms: those based on the extended Euclidean algorithm and its variants (cf. §2.3.6), and those that use field multiplication. Inversion by multiplication does not add significantly to the complexity of a hardware design, but can severely impact performance if it is needed frequently. This is the reason why most hardware (and for that matter software) designers prefer projective coordinates over affine. Additional functionality must be incorporated into the controller but extensive modifications to the core circuit are not required. If affine coordinates are preferred, then inversion will undoubtedly be the bottleneck in performance thereby necessitating an inversion circuit based on the extended Euclidean algorithm. Such a circuit will add more complexity to both the core circuit and the controller. It seems that the added complexity does not justify implementing inversion by the extended Euclidean algorithm, and therefore we restrict our attention to inversion methods that use multiplication.

Let a be a nonzero element in F2m . Inversion by multiplication uses the fact that

Since 2m − 2 = m−1 2i , we have

i=1

i=1

Thus, a−1 can be computed by m − 1 squarings and m − 2 multiplications. We next show how the number of multiplications can be reduced. First observe that

a−1 = a2m −2 = (a2m−1−1)2.

Hence a−1 can be computed in one squaring once a2m−1−1 has been evaluated. Now if m is odd then

If we let

b = a2(m−1)/2−1,

then by (5.4) we have

a2m−1−1 = b · b2(m−1)/2 .

Hence a2m−1−1 can be computed with one multiplication and (m − 1)/2 squarings once b has been evaluated. Similarly, if m is even then

2m−1 − 1 = 2(2m−2 − 1) + 1 = 2(2(m−2)/2 − 1)(2(m−2)/2 + 1) + 1. (5.5)

If we let

c = a2(m−2)/2−1,

then by (5.5) we have

a2m−1−1 = a · c · c2(m−2)/2 2 .

Hence a2m−1−1 can be computed with two multiplications and m/2 squarings once c has been evaluated. This procedure can be repeated recursively to eventually compute a−1. The total number of multiplications in this procedure can be shown to be

where w(m − 1) denotes the number of 1s in the binary representation of m − 1, while the total number of squarings is m − 1. This inversion procedure is shown in Algorithm 5.6 when m is odd.

Algorithm 5.6 Inversion in F2m (m odd)

INPUT: Nonzero element a F2m .

OUTPUT: a−1.

1.Set A ← a2, B ← 1, x ← (m − 1)/2.

2.While x = 0 do

2.1A ← A · A2x .

2.2If x is even then x ← x/2;

Else B ← B · A, A ← A2, x ← (x − 1)/2.

3.Return(B).