Hardware/Software Co-Design Implementations of Elliptic Curve Cryptosystems

INTRODUCTION

Elliptic Curve Cryptosystems (ECCs) (Cohen et al., 2005; Hankerson et al., 2004) have been recently attracting increased attention. The ability to use smaller key sizes and the computationally more efficient ECC algorithms are two main reasons why elliptic curve cryptosystems are becoming more popular. They are considered to be particularly suitable for implementation on platforms with constrained storage and/or battery specifications, e.g., smart cards or mobile devices.

Hardware/software co-design was first proposed by Franke and Purvis (1991) as a new design approach that combines the hardware and software perspectives from the earliest stages of the design process and exploits the design flexibility and efficient allocation of functions that such an approach offers. The main goal of hardware/software co-design is to achieve better designs and meet system-level objectives by concurrently designing both hardware and software (Micheli and Gupta, 1997). This study presents a survey of hardware/software co-design implementations of elliptic curve cryptosystems.

FINITE FIELD ARITHMETIC

In abstract algebra, a finite field is a field that contains only finitely many elements. Finite fields are important in number theory, algebraic geometry, Galois theory, coding theory and cryptography (Biggs, 2003; McEliece, 1987; Lidl and Niederreiter, 1994).

A group is a set of elements G together with one binary operation,◊, which have the following properties:

Abelian groups are groups with commutative group operation; i.e., a◊b = b◊a ∀ a, b

(1)

Additive groups, are groups with the + group operator, denoted as:

(2)

Similarly, multiplicative groups, are groups with the x group operator, denoted as:

(3)

The order of a group G, represented by the symbol |G|, is the number of elements in the group. A field is a set of elements F with two binary operations, represented here as addition + and multiplication x, which have the following properties:

Finite fields or Galois field, so named in honor of Evariste Galois are represented by the symbol GF(q). For any prime p and positive integer m, there always exists a Galois field of order q = p^m. The prime p is called the characteristic of the finite field GF(p^m).

ELLIPTIC CURVE CRYPTOSYSTEMS

Elliptic Curve Cryptosystem (ECC), which was originally proposed by Koblitz (1987) and Miller (1986) is seen as a serious alternative to RSA (Rivest et al., 1978) with much shorter key size. ECC with key size of 128-256 bits is shown to offer equal security to that of RSA with key size of 1-2 K bits. To date, no significant breakthroughs have been made in determining weaknesses in the ECC algorithm, which is based on the discrete logarithm problem over points on an elliptic curve. The fact that the problem appears so difficult to crack means that key sizes can be reduced in size considerably, even exponentially (Hankerson et al., 2004). This made ECC become a serious challenge to RSA. The advantage of ECC is being recognized recently where, it is being incorporated in many standards. ECCs have gained popularity for cryptographic applications because of the short key compared with earlier public key cryptosystems such as RSA (Rivest et al., 1978; ElGamal, 1985). They are considered particularly suitable for implementations on smart cards or mobile devices.

Extensive research has been done on the underlying math, security strength and efficient implementations of elliptic curve cryptosystems. Among the different fields that can underlie elliptic curves, prime fields GF(p) and binary fields G F(2^m) have shown to be best suited for cryptographic applications. An elliptic curve E over the finite field GF(p) defined by the parameters a, b ∈ GF(p) with p>3, consists of the set of points p = (x, y), where, x, y ∈ GF(p), that satisfy the elliptic curve equation (Eq. 4) together with the additive identity of the group point O known as the point at infinity (Koblitz, 1987):

where, a, b ∈ GF(p) and 4a³+27b² ≠ 0 mod p.

The number of points n on an elliptic curve over a finite field GF(q) is defined by Hasse’s theorem (McEliece, 1987). The set of discrete points on an elliptic curve form an abelian group, whose group operation is known as point addition. Elliptic curve point addition is defined according to the chord-tangent process. Point addition over GF(p) is described as follows.

Let P and Q be two distinct points on E defined over GF(p) with Q ≠ p (Q is not the additive inverse of P). The addition of the two points P and Q is the point R (R = P+Q), where, R is the additive inverse of S and S is a third point on E intercepted by the straight line through points P and Q. The additive inverse of a point P = (x, y) ∈ E, over GF(p), is the point -P = (x, -y) which is the reflection of the point P with respect to the x-axis on E.

When P = Q and P ≠ -P the addition of P and Q is the point R (R = 2P), where, R is the additive inverse of S and S is the third point on E intercepted by the straight line tangent to the curve at point P. This operation is referred to as point doubling.

Equation 5 defines the non-supersingular elliptic curve equation for GF(2^m) fields. Only non-supersingular curves over GF(2^m) are considered since supersingular curves are not secure. Supersingular elliptic curves define a special class of curves with some special properties that make them unstable for cryptography (Menezes, 1993).

where, a, b ∈ GF(2^m) and b ≠ 0.

For a non-supersingular elliptic curve E defined over GF(2^m), point addition and point doubling operations are generally computed using the algebraic formulae as follows:

A major operation required by elliptic curve cryptosystems is the point scalar multiplication. The scalar multiplication operation, denoted as kP, where k is an integer and P is a point on the elliptic curve represents the addition of k copies of point P as given by Eq. 6:

Elliptic curve cryptosystems are built over cyclic groups. Each group contains a finite number of n points that can be represented as scalar multiples of a generator point: iP for i = 0, 1, …, n-1, where, P is a generator of the group. The order of point P is n, which implies that nP = O and iP ≠ O for 1<i≤n-1. The order of each point on the group must be dividable by n. Consequently, a point multiplication kQ for k>n can be computed as (k mod n)Q. A good survey has been conducted by Hankerson et al. (2004).

Projective coordinate systems define points over the projective plane as triplets (X, Y, Z). Projective coordinate systems are used to eliminate the number of inversions (Menezes, 1993). For an elliptic curve defined over GF(2^m), many different forms of formulas may be used for point addition and doubling. For the homogeneous coordinate system, an elliptic curve point (x, y) takes the form (x, y) = (X/Z, Y/Z) (Koyama and Tsutuoka, 1992), while, for the Jacobian coordinate system; a point takes the form (x, y) = (X/Z², Y/Z³) (Cohen et al., 1997). The Lopez-Dahab (1998, 1999) coordinate system takes the form (x, y) = (X/Z, Y/Z²). The mixed coordinate system, on the other hand, adds two points where one is given in a certain coordinate system, while the other is given in another coordinate system. The coordinate system of the resulting point may be in a third coordinate system (Cohen et al., 1998).

The finite GF(2^m) field, with characteristic 2, has particular importance in cryptography since, it leads to efficient hardware. Elements of the GF(2^m) field are represented in terms of a basis. Most implementations use either a polynomial basis or a normal basis. Normal basis is more suitable for hardware implementations than polynomial basis since operations are mainly comprised of rotation, shifting and exclusive-ORing which can be efficiently implemented in hardware.

In Elliptic Curve Diffie-Hellman Protocol, the base point P and the elliptic curve equation are public. User’s A private and public keys are k_A and P_A, respectively. User’s A public key is equal to k_AP. User’s B, on the other hand, private and public keys are k_B and P_B, respectively. Similarly, User’s A public key is equal to k_BP. The message to be encrypted is embedded into the x-coordinate of a point on the elliptic curve (P_m = x_m, y_m) (Rosing, 1999). The shared secret key S between two parties A and B is easily calculated by:

Whenever, one of the users need to send a message to the other party, he/she needs to add the shared secret key to the message to produce the ciphertext point P_C which is:

To decrypt the ciphertext point, the secret key is subtracted from the ciphertext point to give the plaintext point P_m as follows:

In elliptic curve ElGamal protocol, on the other hand, for some user to encrypt and send the message point P_m to user A, he/she chooses a random integer l and generates the ciphertext C_m which consists of the following pair of points:

The ciphertext pair of points uses A’s public key, where only user A can decrypt the plaintext using his/her private key. To decrypt the ciphertext C_m, the first point in the pair of C_m, lP is multiplied by A’s private key to get the point k_a(lP). This point is subtracted from the second point of C_m to produce the plaintext point P_m.

The complete decryption operations can be summarized in the following equation:

HARDWARE/SOFTWARE CO-DESIGN

In digital system design, hardware and software were two distinct parts that are designed relatively independently. In general, the role of hardware engineers was to supply general-purpose computing systems. Then, it comes the role of software engineers to program these systems without the need to worry about the details of the low-level architecture of the hardware (Franke and Purvis, 1991).

However, due to the evolution of very high scale integration, new chips are large enough to include complete systems. Nowadays, it is possible to have CPUs, memories and other digital systems in a single chip. The existence of embedded CPUs and complex digital systems raised two classes of problems: (1) the design of the embedded CPU and (2) the design of the software running on these CPUs. In this case, software design becomes a first-class component in chip design. The need for designing both software and hardware in the early stage formed the root of what is called today hardware/software co-design (Wolf, 2003).

The term co-design was first proposed by Franke and Purvis (1991) as a new design approach that combines the hardware and software perspectives from the earliest stages of the design process and exploits the design flexibility and efficient allocation of functions that such an approach offers. The idea of concurrently designing both hardware and software is older than this date. Sommerville (2004) stated that it is becoming increasingly cost-effective to delay decisions about which functions should be implemented in hardware and which functions should be software components, which is a main task of hardware/software co-design.

Co-design can be thought of as a special case of an older approach called concurrent engineering, which is a systematic approach to the integrated, concurrent design of products and their related processes, including manufacture and support. In this context, co-design attempts to better integrate two concurrent activities, namely the design of the hardware and software components of a system (Franke and Purvis, 1991).

The main goal of co-design is to achieve better designs and meet system-level objectives by concurrently designing both hardware and software (Micheli and Gupta, 1997). However, there are many design factors that make the design space exploration of a digital system a difficult task. One factor is the level of programmability. A system can be designed at the application level using general purpose processors programmed using high level languages. It can also be designed at the instruction level. In this case, special processors are designed with Instruction Set Architectures (ISAs) that are optimized for a specific application domain. These kinds of processors are called Application Specific Instruction Processors (ASIPs) (some papers call them semi-custom processors to differentiate them form General-Purpose Processors (GPPs) and custom processors, which are called Application Specific Integrated Circuits (ASICs)) (Vahid, 2003). The software designers then need to use this ISA to program the ASIP. A third option is to program the design in the hardware level, in which a software is used to configure the hardware after it is manufactured. Hence, programmability and reprogrammability can be done for both hardware and software (Micheli and Gupta, 1997).

Another design factor that increases the design space of a system is the implementation feature. This includes the design style (e.g., clocking strategy and operation mode), the manufacturing technology (e.g, CMOC or bipolar) and the integration level (e.g., system components in a single chip (SoC) or different chips) (Micheli and Gupta, 1997). Considering all these factors in the design of a system increases the possibility of different optimal solution (with respect to different design factors).

The evolution of new integrated circuit technologies (FPGA, ASIC, complex systems, embedded systems) also motivates using co-design (Micheli and Gupta, 1997). Co-design can be done by human designers. However, it is unlikely that human designers can optimize all objectives and consider all design factors. This may lead to designs that are lower than the optimal ones. Moreover, detailed-level design performed by humans is often a time-consuming and error-prone task. Therefore, it is better to have some automatic approaches for co-design supported by Computer-Aided Design (CAD) tools (Micheli and Gupta, 1997).

Co-design can be applied to different types of systems and platforms. Examples include stand-alone digital systems, embedded systems and reconfigurable hardware (Micheli and Gupta, 1997). Co-design involves several processes and phases. We can classify them into three main phases.

Modeling: The modeling phase includes identifying system requirements and specification (Franke and Purvis, 1991), refining the specifications and producing a hardware and software model (Micheli and Gupta, 1997). Identifying system requirements and specification of both hardware and software is called co-specification (Ernst, 1998). This means to start with an abstract notation such that each component or module is independent of its final realization in hardware or software (Franke and Purvis, 1991). Capturing all system requirements at the earliest stage restricts the space of possible design options and hence makes specification, design, implementation and verification efforts more straightforward (Franke and Purvis, 1991). One important process of the modeling phase is hardware/software partitioning (or co-partitioning), whose goal is to find those parts of the model best implemented in hardware and those best implemented in software (Micheli and Gupta, 1997). Hardware is targeted for higher performance and software is better for flexibility (Schaumont and Verbauwhede, 2003). Hardware/software partitioning has a first order impact on the cost/performance characteristics of the final design (Micheli and Gupta, 1997). It should be noted here that co-partitioning should be made in the most appropriate manner and not according to conventional wisdom (Franke and Purvis, 1991). After partitioning, scheduling can be loosely defined as assigning an execution start time to each task in a set, where tasks are linked by some relations. The tasks can be elementary (like hardware operations or computer instructions) or can be a group of elementary operations (like software programs) (Micheli and Gupta, 1997). For embedded systems. The modeling style can be homogeneous or heterogeneous (Micheli and Gupta, 1997). In homogeneous modeling, a modeling language (e.g., the C programming language) or a graphical formalism (e.g., state charts) is used to represent both the hardware and software portions. Then, hardware/software partitioning is applied to the model. Partitioning can be decided by the designer, with a successive refinement and annotation of the initial model, or determined by a CAD tool. In heterogeneous modeling, the hardware/software partition is often outlined by the model itself, because hardware and software components may be expressed in the corresponding languages. Nevertheless, system designers may want to explore alternative implementations of some components.

Validation: Validation is the process of achieving a reasonable level of confidence that the system will work as designed. It has two main goals: (1) to insure the correct functionality of the designed system and (2) that the required performance levels are achieved in the implementation of a system model (Micheli and Gupta, 1997). Validation (also known as co-verification) could be achieved by co-simulation, in which the software component is simulated as running on or communicating with the hardware component (Ernst, 1998).

Implementation: Implementation means the physical realization of hardware and software. When both components are implemented concurrently, it is called co-synthesis, although it may involve hardware synthesis and software compilation (Micheli and Gupta, 1997).

There exists a number of frameworks for hardware/software co-design of FPGA systems. Tham and Maskell (2006) mentioned and compared a number of these frameworks. Some of these frameworks focus only on the co-simulation step of the co-design process. Other frameworks need manual translation of software codes into HDLs for hardware implementation. A software-oriented methodology is presented by Tham and Maskell (2006) that uses SystemC to model both software and hardware parts and then use a tool called SystemCrafter to translate the hardware part into HDL. Another methodology is presented by Jussel and Sullivan (2003) and Sullivan (2002) where, Handel-C is used as the modeling language. This methodology consists of four main steps: software coding, software profiling, function partitioning and co-simulation and hardware/software co-synthesis.

HARDWARE/SOFTWARE CO-DESIGN IMPLEMENTATIONS OF ELLIPTIC CURVE CRYPTOSYSTEMS

Janssens et al. (2001) presented the first hardware/software co-design of a GF(2^m) elliptic curve cryptosystem. The proposed design by Janssens et al. (2001) performs scalar multiplication using a software controller written in C. Point operations and field arithmetic, on the other hand, are implemented in hardware. The presented hardware/software co-design in (Janssens et al. 2001) has been implemented on an Atmel FPSLIC FPGA with m = 8, 16, 72, 192 bits. The FPSLIC incorporates an AVR micro-controller, memory, peripherals and a small FPGA on the same chip. The finite field operations are implemented on the FPGA, with the elliptic curve operations on the micro-controller. The data bus between the micro-controller and the FPGA logic is only 8 bits wide, creating a severe bottleneck. A block diagram of the processor can be shown in Fig. 1.

Zeng et al. (2002) presented a GF(2²⁰⁹) hardware/software co-design of an elliptic curve cryptosystem according to the partitioning schemes proposed by Janssens et al. (2001). An 8-bit embedded micro-controller IP core is used as a software controller by Zeng et al. (2002). The hardware part, on the other hand, has been synthesized based on 0.35 μm standard cell library. The proposed deign by Zeng et al. (2002) was the first VLSI hardware/software co-design of an elliptic curve cryptosystem. The finite field arithmetic is implemented using normal basis.

Ernst et al. (2002) presented three hardware/software co-design implementations of a GF(2¹¹³) elliptic curve cryptosystem on an Atmel AT94K40 FPGA. These implementations include: a pure software implementation of the whole elliptic curve cryptosystem, an implementation that uses a hardware multiplier and an implementation that implements the field arithmetic on hardware.

Fig. 1:	The block diagram of the processor of Janssens et al. (2001)

Fig. 2:	The datapath of the ECC of Cheung et al. (2005)

Cheung et al. (2005) proposed four partitioning schemes. Two of these schemes were proposed already by Ernst et al. (2002). The four partitioning schemes presented by Cheung et al. (2005) include: a pure software implementation scheme, a scheme that uses a hardware multiplier, a scheme that uses a hardware inverter and a scheme that implements point multiplication in hardware. The four proposed partitioning schemes were implemented on the Xilinx ML310 board containing a XC2VP30 FPGA chip with m = 113, 162, 270 bits using normal basis. A diagram of the datapath of the system can be shown in Fig. 2.

Koschuch et al. (2006) have co-designed an elliptic curve cryptosystem over binary extension fields using the Dalton 8051 as host controller which executes the software part. The hardware part consists of an Elliptic Curve Acceleration Unit (ECAU) and an interface with Direct Memory Access (DMA) to enable fast data transfer between the ECAU and the external RAM (XRAM) attached to the 8051 microcontroller as can be shown in Fig. 3.

Fig. 3:	The block diagram of the system of Koschuch et al. (2006)

Fig. 4:	The block diagram of the design of Batina et al. (2006)

Batina et al. (2006) investigated three methodologies on two different platforms: 8051 micro-controller connected to an FPGA and an AVR micro-controller connected to an FPGA. The first methodology implements only the finite field multiplication on the FPGA. The second implements all finite field arithmetic on the FPGA. The third implements all finite field and point operations on the FPGA. The point operations are accomplished via micro-code. A block diagram of the hardware architecture can be seen in Fig. 4.

Recently, Ramsey (2008) investigated the implementation of elliptic curve scalar multiplication on Hybrid FPGA. C code executing on a Power PC processor performed complex elliptic curve arithmetic algorithms. This C code is interfaced with a finite field processor placed in reconfigurable fabric surrounding the processor.

The presented hardware/software co-design by Ramsey (2008) has been implemented on a Xilinx Virtex4 Hybrid FPGA with m = 163, 233, 283, 409, 571 bits using normal basis.