# High-performance Elliptic Curve Cryptography by Using the CIOS Method for Modular Multiplication

Amine Mrabet, Nadia El-Mrabet, Ronan Lashermes, Jean-Baptiste Rigaud, Belgacem Bouallegue, Sihem Mesnager, Mohsen Machhout

► To cite this version:

Amine Mrabet, Nadia El-Mrabet, Ronan Lashermes, Jean-Baptiste Rigaud, Belgacem Bouallegue, et al.. High-performance Elliptic Curve Cryptography by Using the CIOS Method for Modular Multiplication. CRiSIS 2016, Sep 2016, Roscoff, France. hal-01383162

HAL Id: hal-01383162

https://inria.hal.science/hal-01383162

Submitted on 18 Oct 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
High-performance Elliptic Curve Cryptography by Using
the CIOS Method for Modular Multiplication

Amine MRABET<fnref n="1" />,<fnref n="3" />,<fnref n="5" />, Nadia EL-MRABET<fnref n="2" />, Ronan LASHERMES<fnref n="7" />, Jean-Baptiste RIGAUD<fnref n="2" />, Belgacem BOUALLEGUE<fnref n="6" />, Sihem MESNAGER<fnref n="1" />,<fnref n="4" /> and Mohsen MACHHOUT<fnref n="3" />

**Abstract** Elliptic Curve Cryptography (ECC) is becoming unavoidable, and should be used for public key protocols. It has gained increasing acceptance in practice due to the significantly smaller bit size of the operands compared to RSA for the same security level. Most protocols based on ECC imply the computation of a scalar multiplication. ECC can be performed in affine, projective, Jacobian or others models of coordinates. The arithmetic in a finite field constitutes the core of ECC Public Key Cryptography. This paper discusses an efficient hardware implementation of scalar multiplication in Jacobian coordinates by using the Coarsely Integrated Operand Scanning method (CIOS) of Montgomery Modular Multiplication (MMM) combined with an effective systolic architecture designed with a two-dimensional array of Processing Elements (PE). As far as we know this is the first implementation of such a design for large prime fields. The proposed architectures are designed for Field Programmable Gate Array (FPGA) platforms. The objective is to reduce the number of clock cycles of the modular multiplication, which implies a good performance for ECC. The presented implementation results focuses on various security levels useful for cryptography. This architecture have been designed in order to use the flexible DSP48 on Xilinx FPGAs. Our architecture for MMM is scalable and depends only on the number and size of words.

**Keywords:** Hardware Implementation, ECC, Modular Multiplication, Montgomery Algorithm, CIOS method, Systolic Architecture, DSP48, FPGA

# 1 Introduction

The search for the most optimised architecture for arithmetic has always fascinated the embedded system world. In recent years this has been especially the case in finite fields for cyber security due to the invention of asymmetric encryption systems based on modular arithmetic operations. Throughout the history of cryptography for embedded systems, there has been a need for efficient architectures for these operations. The implementations must be cost-effective, both in terms of area and latency. Finite field arithmetic is the most important primitive of ECC, pairing and RSA. Since 1976, many

<footnote n="1">¹University of Paris XIII, CNRS, UMR 7539 LAGA - France</footnote>

<footnote n="2">²Ecole des Mines de St-Etienne, SAS-CMP - France</footnote>

<footnote n="3">³University of Monastir EμE Lab - Tunisia</footnote>

<footnote n="4">⁴ Télécom ParisTech</footnote>

<footnote n="5">⁵National Engineering School of Tunis - Tunisia</footnote>

<footnote n="6">⁶King Khalid University - Saudi Arabia</footnote>

<footnote n="7">⁷LHS-PEC TAMIS INRIA-Rennes - France</footnote>
Public Key Cryptosystems (PKC) have been proposed and all these cryptosystems base their security on the difficulty of some mathematical problem. The hardness of this underlying mathematical problem is essential for security. Elliptic Curve Cryptosystems which were proposed by Koblitz [9] and Miller [15], RSA [21] and the Pairing-Based Cryptography[8] are examples of PKCs. All these systems require an efficient finite field multiplication. As a consequence, the development of efficient architecture for modular multiplication has been a very popular subject of research. In 1985, Montgomery has presented a new method for modular multiplication [17]. It's one of the most suitable algorithm for performing modular multiplications in hardware and software implementations. The efficient implementation of the Montgomery Modular Multiplication (MMM) in hardware was considered by many authors [3,6,7,18,19,23]. There is a variety of ways to perform the MMM, considering if multiplication and reduction are separated or integrated. A systolic array architecture [12,24] is one possibility for the implementation of the Montgomery algorithm in hardware, with a design both parallel and pipelined [3,18,19,20,23]. A similar work [20] has been done for binary fields (field characteristic is a power of 2) without having to deal with carry propagation as a consequence. These architectures use a Processing Elements (PE) array where each Processing Element performs arithmetic additions and multiplications. In accordance with the number of words used, the architecture can employ a variable number of PEs. The systolic architecture uses very simple Processing Elements (as in a pipeline). As a consequence, the systolic architecture decreases the needs for logic elements in hardware implementations. Our contribution is to combine a systolic architecture, which is assumed to be the best choice for hardware implementations, with the CIOS method of Montgomery modular multiplication. We optimize the number of clock cycles required to compute a *n*-bit MMM and we reduce the utilization of FPGA resources. We have implemented the modular multiplication in a fixed number of clock cycles. To the best of our knowledge, this is the first time that a hardware or a software multiplier of modular Montgomery multiplication, suitable for various security level, is performed in just 33 clock cycles. Furthermore, as far as we know, our work is the first one dealing with systolic architecture and CIOS method over large prime characteristic finite fields. Using our efficient MMM hardware implementation, we propose an efficient design for ECC operations: point addition and doubling. This paper is organized as follows: Section 2 discusses related state-of-the-art works. Section 3 presents the CIOS method of Montgomery Modular Multiplication algorithm. The proposed architectures and results are presented in Section 4 and Section 5. Finally, the conclusion is drawn in Section 6.

# 2 State of the art

## 2.1 Elliptic Curve Cryptography

The use of elliptic curves in cryptography has been independently introduced by Victor S. Miller [16] and N. Koblitz [10] during the 80s. The main advantage of ECC is that the bit sizes of the key are reduced for the same security level when comparing with a classical RSA algorithm [22]. For instance, at the AES 128-bit security level the key for ECC is
256 bits, while RSA requires a 3072-bit key. The main operation in ECC is the scalar multiplication over the elliptic curve. This scalar multiplication consists in computing $\alpha \times P$, for $\alpha$ an integer and $P$ a point of an elliptic curve. When such an operation is implemented on an embedded system such as a FPGA, it is subject to constraints of area and speed. Efficient scalar multiplication arithmetic is hence a central issue for cryptography. The interested reader is referred to [2] for a good overview of the question.

**ECC preliminaries** Let E be an elliptic curve defined over $\mathbb{F}_p$ with $p > 3$ according to the following short Weierstrass equation:

$$E: y^2 = x^3 + ax + b \qquad (1)$$

where $a, b \in \mathbb{F}_p$ such that $4a^3 + 27b^2 \neq 0$. The elliptic curve $E(\mathbb{F}_p)$ is the set of points $(x, y) \in \mathbb{F}_p^2$ whose coordinates satisfy Equation 1. The rational points of E, augmented with a neutral element O called point at infinity, have an abelian group structure. The associated addition law computes the sum of two points in affine coordinates $P = (x_1, y_1)$ and $Q = (x_2, y_2)$ as $P + Q = (x_3, y_3)$ where: $x_3 = \lambda^2 - x_1 - x_2$ and $y_3 = \lambda(x_1 - x_3) - y_1$ with

$$\lambda = \begin{cases} \frac{y_2 - y_1}{x_2 - x_1} & \text{if } P \neq Q, \\ \frac{3x_1^2 + a}{2y_1} & \text{if } P = Q. \end{cases} \qquad (2)$$

The scalar multiplication of a point P by a natural integer $\alpha$ is denoted $\alpha P$. The discrete logarithm problem is finding the value of $\alpha$, given P and $\alpha P$. The security of ECC is based on the hardness of the discrete logarithm problem. Point addition formulae such as in Equation 2 are based on several operations over $\mathbb{F}_p$ (e.g. multiplication, inversion, addition, and subtraction) which have different computational costs.

**ECC in Jacobian coordinates** In Jacobian coordinates, we use $(x : y : z)$ to represent the affine point $(x/z^2; y/z^3)$. The elliptic curve equation becomes:

$$Y^2 = X^3 + aXZ^4 + bZ^6.$$

Doubling step: we represent the point $Q \in E(\mathbb{F}_p)$ in Jacobian coordinates as $Q = (X_Q, Y_Q, Z_Q)$. The formulae for doubling $T = 2Q = (X_T, Y_T, Z_T)$ can be computed as:

$$X_T = 9X_Q^4 - 8X_QY_Q^2. \quad Y_T = 3X_Q^2(4X_QY_Q - X_T) - 8Y_Q^4. \quad Z_T = 2Y_QZ_Q.$$

Adding step: let $Q = (X_Q, Y_Q, Z_Q)$ and $T = (X_T, Y_T, Z_T) \in E(\mathbb{F}_p)$. Then the point $R = T + Q = (X_R, Y_R, Z_R)$, can be computed as:

$$X_R = (2Y_QZ_T^3 - 2Y_T)^2 - 4(X_QZ_T^2 - X_T)^3 - 8(X_QZ_T^2 - X_T)^2X_T. \\ Y_R = (2Y_QZ_T^3 - 2Y_T)(4(X_QZ_T^2 - X_T)^2X_T - X_R) - 8Y_T(X_QZ_T^2 - XT)^3. \\ Z_R = 2Z_T(X_QZ_T^2 - X_T).$$
<caption>**Algorithm 1: Scalar Multiplication**</caption>

**Input:** $\alpha = (\alpha_n\alpha_{n-1}\dots\alpha_1\alpha_0)_2$ radix 2 decomposition $\in \mathbb{F}_p, P \in E(\mathbb{F}_p)$
**Output:** $\alpha P$
1 $T \leftarrow P$
2 **for** $i = n-1$ **to** 0 **do**
3 $T \leftarrow 2T$
4 **if** $\alpha_i = 1$ **then**
5 $T \leftarrow T + P$
6 **return** $T$

3 Our architecture for MMM (CIOS Method)

The Coarsely Integrated Operand Scanning (CIOS) method presented in Algorithm 2, improves the Montgomery Algorithm by integrating the multiplication and reduction. More specifically, instead of computing the product $a \cdot b$, then reducing the result, this method allows an alternation between iterations of the outer loops for multiplication and reduction. The integers $(p, a$ and $b)$ are seen as lists of $s$ words of size $w$. This algorithm requires an array $T$ of size only $s + 2$ to store the intermediate state. The final result of the CIOS algorithm is composed by the $s + 1$ least significant words of this array at the end.

<caption>**Algorithm 2: CIOS algorithm for Montgomery multiplication [11]**</caption>

**Input:** $p < 2^K, p' = -p^{-1}\mod 2^w, w, s, K = s \cdot w$ :bit length, $R = 2^K, a, b < p$
**Output:** $a \cdot b \cdot R^{-1} \mod p$
1 $T \leftarrow 0$;
2 **for** $i \leftarrow 0$ **to** $s-1$ **do**
3 $C \leftarrow 0$;
4 **for** $j \leftarrow 0$ **to** $s-1$ **do**
5 $\left\lfloor \frac{(C,S) \leftarrow T[j] + a[i] \cdot b[j] + C}{T[j] \leftarrow S} \right\rfloor$ \quad $\alpha$ cell
6 $(C,S) \leftarrow T[s] + C$ \quad $\alpha_f$ cell
7 $T[s] \leftarrow S$
8 $T[s+1] \leftarrow C$
9 $m \leftarrow T[0] \cdot p' \mod 2^w$ \quad $\beta$ cell
10 $(C,S) \leftarrow T[0] + m \cdot p[0]$ \quad $\beta$ cell
11
12 **for** $j \leftarrow 1$ **to** $s-1$ **do**
13 $\left\lfloor \frac{(C,S) \leftarrow T[j] + m \cdot p[j] + C}{T[j-1] \leftarrow S} \right\rfloor$ \quad $\gamma$ cell
14 $(C,S) \leftarrow T[s] + C$ \quad $\gamma_f$ cell
15 $T[s-1] \leftarrow S$
16 $T[s] \leftarrow T[s+1] + C$
17 **return** $T$;
The alternation between multiplications and reductions is possible since the value of *m* (in line 11 of the Algorithm 2) in the *i*th iteration of the outer loop for reduction depends only on the value *T*[0], which is computed by the first iteration of the corresponding inner loop. In order to perform the multiplication, we have modified the CIOS algorithm of [11] and designed this method with a systolic architecture. Indeed, instead of using an array to store the intermediate result, we replace *T* by input and output signals for each Processing Element. As a consequence, our design uses fewer multiplexers decreasing as a consequence the number of slices taken by our design.

# 4 Hardware Implementation

## 4.1 Block DSP in Xilinx FPGAs

Modern FPGA devices like Xilinx Virtex-4, Virtex-5 and Artix-7 as well as Altera Stratix FPGAs have been equipped with arithmetic hardcore extensions to accelerate digital signal processing applications. These DSP blocks can be used to build a more efficient implementation in terms of performance and reduce at the same time the demand for area. DSP blocks can be programmed to perform basic arithmetic functions, multiplication, addition and subtraction of unsigned integers. Figure 1 shows the generic DSP structure in advanced FPGAs. DSP can operate on external input A,B and C as well as on feedback values from P or result PCIN.

<figure><img src="image_2.png" /><figcaption>Figure 1: Structure of DSP block in modern FPGA device.</figcaption></figure>

## 4.2 Proposed Architecture

The idea of our design is to combine the CIOS method for the MMM presented in [11] with a two-dimensional systolic architecture in the model of [13,20,24]. As seen in section 3, the CIOS method is an alternation between iterations of the loops for multiplication and reduction. The concept of the two-dimensional systolic architecture presented in Section 2 combines Processing Elements with local connections, which take external inputs and handle them with a predetermined manner in a pipelined fashion. This new architecture is directly based on the arithmetic operations of the CIOS method
<figure><img src="image_3.png" /><figcaption>Figure 2: data dependency in general systolic architecture.</figcaption></figure>

of Montgomery Algorithm. The arithmetic is performed in a radix-$w$ base ($2^w$). The input operands are processed in $s$ words of $w$ bits. We present many versions of this method. We illustrate our design for $s = 16$ architecture, denoted NW-16 (for Number of Words). We describe it in detail as well as the various Processing Element behaviours. In order to have less states in our Final State Machine (FSM), we divided our Algorithm 2 of Montgomery in five kinds of PEs ($\alpha, \beta, \gamma, \alpha_f, \gamma_f$). Our efficient architecture comes from the fact that the data dependency in the CIOS algorithm allows to perform several operations in parallel. Figure 2 presents the dependency of the different cells. Below we describe precisely each cell. The letters MSW stand for the Most Significant Word and LSW for the Least Significant Word. In our notation the letter $C$ denote the MSW of the result and the letter $S$ the LSW.

### α cell
The α cell corresponds to lines 5 and 6 of Algorithm 2. Its operations are described in Algorithm 3. Notice how registers are embedded into the cell, avoiding in this manner

<caption>**Algorithm 3: α cell**</caption>

Input: $a[i], b[j], C_{In}(= C), S_{In}(= T[j])$
Output: $C_{Out}, S_{Out}$
1 $t1 \leftarrow S_{In} + C_{In}$
2 $t2 \leftarrow a[i] \cdot b[j]$
3 $t3 \leftarrow t2 + t1$
4 $C_{Out} \leftarrow \text{MSW}(t3)$
5 $S_{Out} \leftarrow \text{LSW}(t3)$
6 \return $C_{Out}, S_{Out}$

the usage of an external memory. This cell corresponds to one iteration of the first inner loop. As such it must be used several times in a row (the number of iterations in the inner loop). This chain of α cells is terminated by an αf cell (alpha final) corresponding to lines 7, 8 and 9 of Algorithm 2. Once the first α cell (for each outer loop) is computed, data is available for the β cell (it requires $T[0]$). It is preferable to consume this data as soon as it is available as to minimize memory usage.
**α<sub>f</sub> cell** The α<sub>f</sub> cell corresponds to the end of the first inner loop. It is just an addition as shown in Algorithm 4.

**Algorithm 4: α<sub>f</sub> cell**

**Input:** $C_{In}(= C), S_{In}(= T[s])$

**Output:** $C_{Out}(= T[s+1]), S_{Out}(= T[s])$

1 $t1 \leftarrow S_{In} + C_{In}$

2 $C_{Out} \leftarrow \text{MSW}(t1)$

3 $S_{Out} \leftarrow \text{LSW}(t1)$

4 **return** $C_{Out}, S_{Out}$

**β cell** The β cell is used to compute the *m* value for each outer loop as well as the first special iteration of the second inner loop. Its operations are described in Algorithm 5. Once the β cell computation has been done, it now becomes possible to compute the

**Algorithm 5: β cell**

**Input:** $S_{In}(= T[0]), p', p[0]$

**Output:** $C_{Out}, S_{Out}$

1 $t1 \leftarrow S_{In} \cdot p'$

2 $m \leftarrow \text{LSW}(t1)$

3 $t2 \leftarrow p[0] \cdot m$

4 $t3 \leftarrow S_{In} + t2$

5 $C_{Out} \leftarrow \text{MSW}(t3)$

6 **return** $C_{Out}, m$

second inner loop with γ cells.

**γ cell** The γ cell corresponds to one iteration of the second inner loop. As such these cells must be chained so as to complete the whole second inner loop. For each cell in this chain, the same *m* value is required. Value that is changed for each outer loop iteration (*m* is computed by the β cell). Since a new *m* value may be computed before the end of the γ chain, the value must be propagated along the cells in the same chain. Its operations are described in Algorithm 6.

**Algorithm 6: γ cell**

**Input:** $C_{In}(= C), S_{In}(= T[j]), m, p[j]$

**Output:** $C_{Out}, S_{Out}$

1 $t1 \leftarrow S_{In} + C_{In}$

2 $t2 \leftarrow m \cdot p[j]$

3 $t3 \leftarrow t1 + t2$

4 $C_{Out} \leftarrow \text{MSW}(t3)$

5 $S_{Out} \leftarrow \text{LSW}(t3)$

6 **return** $C_{Out}, S_{Out}, m$
$\gamma_f$ cell Finally, the $\gamma_f$ cell terminate each $\gamma$ cell chain. It consists in two additions as shown in Algorithm 7. The difference with the $\alpha_f$ cell is that in this case both output

<caption>**Algorithm 7: $\gamma_f$ cell**</caption>

**Input:** $C_{In}(= C), S_{1In}(= T[s]), S_{2In}(= T[s+1])$
**Output:** $C_{Out}(= T[s]), S_{Out}(= T[s-1])$
1 $t1 \leftarrow S_{1In} + C_{In}$
2 $t2 \leftarrow \text{MSW}(t1)$
3 $S_{Out} \leftarrow \text{LSW}(t1)$
4 $C_{Out} \leftarrow \text{LSW}(S_{2In} + t2)$
5 **return** $C_{Out}(= T[s]), S_{Out}(= T[s-1])$

values $S$ and $C$ are used in the rest of the computation. $C$ is used by the $\alpha_f$ cell and $S$ by an $\alpha$ cell.

## 4.3 Our architectures

Firstly, we will start with the NW-16 architecture which contains 6 PEs of type alpha and 6 of type gamma. An MMM can be performed with this architecture in 66 clock cycles. Similarly, in order to implement the NW-32 architecture and the NW-64 architecture it is required to double the number of cells each time. We provide a comparison of our architectures at the end of this section.

**NW-16 Architecture** In this architecture, the operands and the modulo are divided in 16 words. The NW-16 architecture is designed in the same way as the NW-32 an NW-64. This example illustrates the scalability of our design. The NW-16 architecture is composed of 15 Processing Elements distributed in a two-dimensional array, where every Processing Elements are responsible for the calculus involving $w$-bit words of the input operands.

The 15 Processing Elements are divided like this: 6 $\alpha$ cells, 1 $\alpha_f$ cell, 1 $\beta$ cell, 6 $\gamma$ cells et 1 $\gamma_f$ cell. As said previously, the number of other PE type ($\alpha_f, \beta, \gamma_f$) remains unchanged whatever the number of words in the design. In order to evaluate the number of clock cycles of the NW-16 architecture, the first parameter is

$$6 = \max\{\text{number of } \alpha \text{ cells, number of } \gamma \text{ cells}\},$$

implying that our algorithm requires to loop $s + 6$ times. We can perform the multiplication with our design in 66 clock cycles since our design requires three states ($66 = 3 \times (s + 6)$). The different results of this architecture for bit-length 256 are given in Table 1.

**Architectures comparison** The Table 2 shows a comparison between the different architectures. The number of clock cycles for every architecture is equal to $3 \times (s + nb)$, such that $nb = \max\{\text{number of } \alpha \text{ cells, number of } \gamma \text{ cells}\}$, implying that our algorithm
<figure><img src="image_4.png" /><figcaption>Figure 3: Proposed Montgomery modular multiplication architecture of NW-16.</figcaption></figure>
<table><caption>Table 1: Implementations of cells and MMM (NW-16).</caption><thead><tr><th>Artix-7</th><th>DSP</th><th>Frequency</th><th>Clock cycles</th></tr></thead><tbody><tr><td>MMM (s=16/K=256)</td><td>29</td><td>146</td><td>66</td></tr><tr><td>α</td><td>2</td><td>379</td><td>1</td></tr><tr><td>γ</td><td>2</td><td>379</td><td>1</td></tr><tr><td>β</td><td>2</td><td>453</td><td>1</td></tr><tr><td>α<sub>f</sub></td><td>1</td><td>460</td><td>1</td></tr><tr><td>γ<sub>f</sub></td><td>2</td><td>443</td><td>1</td></tr></tbody></table>

require to loop $s + nb$ times. It is interesting to notice that all our architectures are scalable and can target the different security levels useful in cryptography.

<table><caption>Table 2: Comparison of our architectures</caption><thead><tr><th>CIOS</th><th>s=8</th><th>s=16</th><th>s=32</th><th>s=64</th></tr></thead><tbody><tr><td>K=256</td><td>32</td><td>16</td><td>8</td><td>4</td></tr><tr><td>K=512</td><td>64</td><td>32</td><td>16</td><td>8</td></tr><tr><td>K=1024</td><td>128</td><td>64</td><td>32</td><td>16</td></tr><tr><td>K=2048</td><td>256</td><td>128</td><td>64</td><td>32</td></tr><tr><td>Clock cycles= 3 × (s + nb)</td><td>33</td><td>66</td><td>132</td><td>264</td></tr><tr><td>Number of cells</td><td>6 +3</td><td>12 +3</td><td>24 +3</td><td>48 +3</td></tr></tbody></table>

## 4.4 ECC implementation

ECC algorithms when implemented in a sequential way have the advantage that the number of finite field arithmetic modules can be reduced to a minimum. For example, only one adder, one multiplier and one subtraction unit (can be an adder) are needed for point addition and doubling. Parallelization between multiplication, addition and subtraction was achieved. We proposed in Figure ?? and Figure ?? the dataflow graphs for point addition and doubling. In this design we use our efficient systolic architecture of
MMM to perform squaring or multiplication. The Table 4 summarizes the implementation
results of the scalar multiplication. We present a results with both NW-8 and NW-16
architectures. To check the correctness of the hardware results, we compare the results
given by the FPGA with sage software implementation.

5 Experimental Results

The Table 3 summarizes the FPGA post-implementation results for the proposed versions
of MMM architectures. We present results for NW-16 architecture. The designs were
described in a hardware description languages (VHDL) and synthesized for Artix-7 and
Virtex-5 Xilinx FPGAs. We present the different results after implementation of bit-
length *k* which are given in Table 3. As it is shown in Table 3, an interesting property
of our design is the fact that the clock cycles are independent from the bit length. This
property gives to our design the advantage of suitability to different security level. In order
to implement the modular Montgomery multiplication for fixed security level, we must
choose the most suitable architecture. The results presented in this work are compared
with the previous work [4,5,18,19] in the Table 3. We can notice that our results are
better than [19] considering every point of comparison i.e. the number of slice and the
number of clock cycles. Considering the number of slices, we recall that [19] used an
external memory to optimize the number of slices used by their algorithms. Considering
the comparison with [18], our design requires less slices and can ran at a better frequency,
without considering the huge progress in the number of clock cycles. Our design performed
the MMM in 66 clock cycles for the 512 and 1024 bit length corresponding to AES-256
and AES-512 security level, while [18] performed the multiplication in 1540 clock cycles
for the AES-256 security level and 3076 for the AES-512 security level.

6 Conclusion

In this paper we have presented an efficient hardware implementation of the CIOS method
of MMM over large prime characteristic finite fields $F_p$. We give the results of our design
after routing and placement using a Artix-7 and Virtex-5 Xilinx FPGAs. Our systolic
implementations is suitable for every implementation implying a modular multiplication,
for example RSA, ECC and pairing-based cryptography. Our architectures and the de-
signs were matched with features of the FPGAs. The NW-16 design presented a good
performance considering latency × area efficiency. This architecture can run for all the
bit length corresponding to classical security levels (128, 256, 512 or 1024 bits) in just
66 clock cycles. Our systolic design using this method CIOS is scalable for any other
number of words. Then we showed that using this multiplier, it is possible to achieve an
efficient scalar multiplication.
Xilinx FPGAs

<table><caption>Table 3: Comparison of our work with state-of-art implementations.</caption><thead><tr><th rowspan="2"></th><th colspan="2">Our works A7</th><th colspan="2">Our works V5</th><th colspan="2">[19] V5</th><th colspan="2">[18] VE</th><th colspan="2">[5] VII</th><th colspan="2">[4] VII</th><th colspan="2">[14] V</th><th colspan="2">[1] K7 and V5</th></tr><tr><th>512</th><th>1024</th><th>512</th><th>1024</th><th>512</th><th>1024</th><th>512</th><th>1024</th><th>1024</th><th>1024</th><th>512</th><th>1024</th><th>512</th><th>K7</th><th>512</th><th>V5</th></tr></thead><tbody><tr><th>Freq</th><td>106</td><td>65</td><td>97</td><td>65</td><td>95</td><td>130</td><td>95.2</td><td>95.6</td><td>116.4</td><td>119</td><td>72.1</td><td>79.2</td><td>176</td><td>123</td><td></td><td></td></tr><tr><th>Cycles</th><td>66</td><td>66</td><td>66</td><td>66</td><td>96</td><td>384</td><td>1540</td><td>3076</td><td>1088</td><td>1167</td><td>-</td><td>-</td><td>66</td><td>66</td><td></td><td></td></tr><tr><th>Speed µs</th><td>0.622</td><td>1.013</td><td>0.680</td><td>1.015</td><td>1.010</td><td>2.953</td><td>16.031</td><td>32.021</td><td>9.34</td><td>9.80</td><td>-</td><td>-</td><td>0.374</td><td>0.536</td><td></td><td></td></tr><tr><th>Slice Reg</th><td>2164</td><td>4208</td><td>3046</td><td>6072</td><td>3876</td><td>6642</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>5076</td><td>4960</td><td></td><td></td></tr><tr><th>Slice LUTs</th><td>1789</td><td>5242</td><td>1781</td><td>5824</td><td>-</td><td>-</td><td>2972</td><td>5706</td><td>9319</td><td>9271</td><td>3125</td><td>6243</td><td>8757</td><td>10877</td><td></td><td></td></tr><tr><th>BRAM</th><td>0</td><td>0</td><td>0</td><td>0</td><td>128</td><td>256</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0</td><td>0</td><td></td><td></td></tr></tbody></table>

<table><caption>Table 4: Implementations of ECC (Jacobian) in Xilinx FPGA.</caption><thead><tr><th></th><th>Slice</th><th>DSPs</th><th>BRAM</th><th>Freq</th><th>Slice FF</th><th>Slice LUT</th></tr></thead><tbody><tr><th>NW-8 (256)</th><td>3745</td><td>33</td><td>12</td><td>98</td><td>8281</td><td>9722</td></tr><tr><th>NW-16 (256)</th><td>3770</td><td>34</td><td>12</td><td>130</td><td>8313</td><td>9255</td></tr><tr><th>NW-8 (512)</th><td>7066</td><td>92</td><td>23</td><td>59</td><td>16500</td><td>20394</td></tr><tr><th>NW-16 (512)</th><td>7116</td><td>60</td><td>23</td><td>74</td><td>16501</td><td>19199</td></tr></tbody></table>
References

[1] Bigou, K., Tisserand, A.: Single base modular multiplication for efficient hardware rns implementations of ecc. In: Conference on Cryptographic Hardware and Embed- ded Systems. p. 123–140 (September 2015)

[2] Hankerson, D., Menezes, A.J., Vanstone, S.: Guide to elliptic curve cryptography. Springer Science & Business Media (2006)

[3] Hariri, A., Reyhani-Masoleh, A.: Bit-serial and bit-parallel montgomery multipli- cation and squaring over gf. IEEE Transactions on Computers 58(10), 1332–1345 (2009)

[4] Harris, D., Krishnamurthy, R., Anders, M., Mathew, S., Hsu, S.: An improved unified scalable radix-2 montgomery multiplier. In: Computer Arithmetic, 2005. ARITH-17 2005. 17th IEEE Symposium on. pp. 172–178 (June 2005)

[5] Huang, M., Gaj, K., El-Ghazawi, T.: New hardware architectures for montgomery modular multiplication algorithm. Computers, IEEE Transactions on 60(7), 923–936 (July 2011)

[6] Huang, M., Gaj, K., Kwon, S., El-Ghazawi, T.: An optimized hardware architec- ture for the montgomery multiplication algorithm. In: Cramer, R. (ed.) Public Key Cryptography – PKC 2008, Lecture Notes in Computer Science, vol. 4939, pp. 214–228. Springer Berlin Heidelberg (2008), http://dx.doi.org/10.1007/ 978-3-540-78440-1_13

[7] Iwamura, K., Matsumoto, T., Imai, H.: Systolic-arrays for modular exponentiation using montgomery method. In: Rueppel, R. (ed.) Advances in Cryptology — EU-ROCRYPT' 92, Lecture Notes in Computer Science, vol. 658, pp. 477–481. Springer Berlin Heidelberg (1993), http://dx.doi.org/10.1007/3-540-47555-9_43

[8] Joux, A.: A one round protocol for tripartite diffie-hellman. Journal of Cryptology 17(4), 263–276 (2004), http://dx.doi.org/10.1007/s00145-004-0312-y

[9] Koblitz, N.: Elliptic curve cryptosystems. Mathematics of Computation 48(177), 203–209 (Jan 1987)

[10] Koblitz, N.: Elliptic curve cryptosystems. Mathematics of computation 48(177), 203–209 (1987)

[11] Koç, C., Acar, T., Kaliski, B.S., J.: Analyzing and comparing montgomery multipli- cation algorithms. Micro, IEEE 16(3), 26–33 (Jun 1996)

[12] Kung, H.: Why systolic architectures? Computer 15(1), 37–46 (Jan 1982)

[13] i Lee, K.: Algorithm and VLSI architecture design for H.264/AVC Inter Frame Coding. Ph.D. thesis, National Cheng Kung University, Tainan, Taiwan (2007)

[14] Manochehri, K., Pourmozafari, S., Sadeghian, B.: Montgomery and rns for rsa hard- ware implementation. Computing and Informatics 29(5), 849–880 (2012)

[15] Miller, V.: Use of elliptic curves in cryptography. In: Williams, H. (ed.) Advances in Cryptology — CRYPTO '85 Proceedings, Lecture Notes in Computer Science, vol. 218, pp. 417–426. Springer Berlin Heidelberg (1986), http://dx.doi.org/10. 1007/3-540-39799-X_31
[16] Miller, V.S.: Use of elliptic curves in cryptography. In: Conference on the Theory and Application of Cryptographic Techniques. pp. 417–426. Springer (1985)

[17] Montgomery, P.L.: Modular multiplication without trial division. Mathematics of Computation 44(170), 519–521 (1985)

[18] Ors, S.B., Batina, L., Preneel, B., Vandewalle, J.: Hardware implementation of a montgomery modular multiplier in a systolic array. In: Parallel and Distributed Processing Symposium, 2003. Proceedings. International. pp. 8–pp. IEEE (2003)

[19] Perin, G., Mesquita, D.G., Martins, J.a.B.: Montgomery modular multiplication on reconfigurable hardware: Systolic versus multiplexed implementation. Int. J. Reconfig. Comput. 2011, 61–610 (Jan 2011), http://dx.doi.org/10.1155/2011/127147

[20] Reymond, G., Murillo, V.: A hardware pipelined architecture of a scalable montgomery modular multiplier over gf(2m). In: 2013 International Conference on Reconfigurable Computing and FPGAs (ReConFig). pp. 1–6 (Dec 2013)

[21] Rivest, R., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM 21, 120–126 (1978)

[22] Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM 21(2), 120–126 (1978)

[23] Tenca, A.F., Koç, Ç.K.: A scalable architecture for montgomery multiplication. In: Koç, Ç.K., Paar, C. (eds.) Cryptographic Hardware and Embedded Systems, First International Workshop, CHES’99, Worcester, MA, USA, August 12-13, 1999, Proceedings. Lecture Notes in Computer Science, vol. 1717, pp. 94–108. Springer (1999), http://dx.doi.org/10.1007/3-540-48059-5_10

[24] Vucha, M., Rajawat, A.: Design and fpga implementation of systolic array architecture for matrix multiplication. International Journal of Computer Applications 26(3), 0975 – 8887 (july 2011)

## A Elliptic curve operations scheduling
<figure><img src="image_5.png" /><figcaption>Figure 4: DFG for the point addition algorithm.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Figure 5: DFG for the point doubling algorithm.</figcaption></figure>