Asma Chaouch
email: asma-chaouch@univ-tln.fr

Laurent-Stéphane Didier
email: didier@univ-tln.fr

Yssouf Fangan

Nadia El Dosso
email: dosso@univ-tln.fr

Belgacem Mrabet

Bouraoui Bouallegue

Ouni

Dosso

Nadia El Mrabet
email: nadia.el-mrabet@emse.fr

Belgacem Bouallegue
email: belgacem_bouallegue@yahoo.fr

Bouraoui Ouni
email: ouni_bouraoui@yahoo.fr

Two hardware implementations for modular multiplication in the AMNS: Sequential and semi-parallel

Keywords: Modular multiplication, Hardware implementation, FPGA, Adapted modular number system

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.

Introduction

Nowadays, cryptography primitives are implemented for miscellaneous uses and the efficiency of their implementation on small embedded system devices is important. Most of the public key cryptographic protocols involve modular arithmetic; indeed. This family of cryptosystem which includes RSA Rivest et al. (1978b) and elliptic curve cryptography (ECC) Hankerson and [START_REF] Hankerson | Elliptic curve cryptography[END_REF], relies on it A. [START_REF] Menezes | Handbook of applied cryptography[END_REF]. Hence, the most efficient is the modular arithmetic implementation, the most reduced is the execution time. The most critical operation is the modular multiplication. Many algorithms for the binary representation have been proposed in the literature [START_REF] Barrett | Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor[END_REF]; [START_REF] Montgomery | Modular multiplication without trial division[END_REF]; [START_REF] Taylor | Large moduli multipliers for signal processing[END_REF]; [START_REF] Blakely | A computer algorithm for calculating the product ab modulo m[END_REF]; [START_REF] Takagi | A radix-4 modular multiplication hardware algorithm for modular exponentiation[END_REF].

Beside the algorithmic solutions, it is possible to improve their efficiency by choosing unusual number representations. In [START_REF] Bajard | Modular number systems: Beyond the mersenne family[END_REF], a new number system called the Adapted Modular Number System (AMNS) is proposed in order to speed-up the modular operations. Its main characteristic is that its elements are polynomials with small coefficients. In [START_REF] Didier | Efficient modular operations using the Adapted Modular Number System[END_REF] the theoretical background of AMNS present with a software implementation of the modular multiplication in this system. They show how to build an efficient AMNS that allows modular multiplications that can be more efficient than the classical Montgomery modular multiplication.

In this paper, we present a FPGA architecture for modular multiplication using AMNS and analyze its behavior. This paper gives guidelines to the material fitting of such a structure, namely two methods are presented and a suitable material model is identified. In order to evaluate the performances and the costs (in number of slices register and DSP blocks) of our architectures, we compare our results with the state of the art of modular multiplications in binary, signed-digits and RNS representation. Various architectures have been built for the finite field F p , where p is a prime integer, to provide a scalable implementation on FPGA. Our results are very promising as our implementations provide the most efficient modular multiplication compared to binary implementations with the same size of the modulus p and on the same FPGA target (see Table 8). The work presented is done in continuation of [START_REF] Chaouch | Hardware optimization on fpga for the modular multiplication in the amns representation[END_REF].

The paper is organized as follows. In Section 2, we present the background of the modular multiplication and the AMNS. We describe our hardware architectures in section 3 and in section 4. Our results and a comparison with the state of the art are presented in section 5 and in Section 6. We conclude in section 7.

The Adapted Modular Number System

The Adapted Modular Number System (AMNS) is a number system that was introduced in [START_REF] Bajard | Modular number systems: Beyond the mersenne family[END_REF], in order to speed-up modular arithmetic. The main characteristic of the AMNS is that its elements are polynomials. This characteristic gives to the AMNS many advantages for both efficiency and safety. In [START_REF] Didier | Efficient modular operations using the Adapted Modular Number System[END_REF], the authors give a method to generate many AMNS for any prime integer in order to perform modular operations efficiently. They present software implementation results which highlight that the AMNS allows to perform modular multiplication more efficiently than well known libraries like GNU-MP and OpenSSL. In this section, we give an overview of this number system and of modular operations in it.

In this paper, we do not deal with the generation process of the AMNS, since it requires a consequent mathematical background that is out of the scope of this article and is quite long. See [START_REF] Bajard | Modular number systems: Beyond the mersenne family[END_REF]; [START_REF] Didier | Efficient modular operations using the Adapted Modular Number System[END_REF]. The authors of [START_REF] Didier | Efficient modular operations using the Adapted Modular Number System[END_REF] provide an implementation of the AMNS generation process5 that uses SageMath library [START_REF] Stein | Sagemath[END_REF]. In the same location, there is also a C code generator. Given all the parameters of an AMNS, this generator outputs a software implementation in C language that allows to efficiently perform arithmetic operations in that AMNS.

The AMNS is a subclass of the Modular Number System (MNS). So, we start by first presenting the MNS.

Definition 1. Let p 3 be a prime integer. A modular number system (MNS) is defined by a tuple B = (p, n, γ, ρ), such that for every integer 0 x < p, there exists a vector V = (v 0 , . . . , v n-1 ) such that:

x ≡ n-1 i=0 v i γ i (mod p) , with |v i | < ρ, ρ ≈ p 1/n , and 0 < γ < p.
In this case, we say that the polynomial

V (X) = v 0 +v 1 X +• • •+v n-1 X n-1 is a representation of x in B and we denote V ≡ x B .
For a MNS to be an AMNS, the parameter γ should meet a requirement which is essential for arithmetic operations.

Definition 2. An Adapted Modular Number System (AMNS) is defined by a tuple B = (p, n, γ, ρ, E) such that (p, n, γ, ρ) is a MNS and γ is a root modulo p of the polynomial E(X) = X n -λ, with λ a very small nonzero integer (for instance, λ = ±1, ±2 or ±3).

Example 1. Let p = 19. The tuple B = (19, 3, 7, 2, E), with E(X) = X 3 -1, is an AMNS. Indeed, Table 1 gives a representation of each element of Z/19Z. This shows that the tuple B = (19, 3, 7, 2) is a MNS. Moreover, we have γ n = 7 3 ≡ 1 (mod 19), which is very small.

0 1 2 3 4 0 1 -X 2 -X + 1 X 2 -X -1 X 2 -X 5 6 7 8 9 X 2 -X + 1 X -1 X X + 1 -X 2 + 1 10 11 12 13 14 X 2 -1 X 2 X 2 + 1 -X + 1 -X 2 + X -1 15 16 17 18 -X 2 + X -X 2 + X + 1 X 2 + X -1 -1
It can be checked in Table 1 that any representation A of an element a ∈ Z/19Z is such that: deg(A) < 3, A ∞ < 2 and A(γ) ≡ a (mod p). For instance, γ 2 -γ + 1 = 49 -7 + 1 = 43 ≡ 5 mod 19 shows that X 2 -X + 1 is a representation of 5 in B.
Like in usual number systems, the main arithmetic operations in the AMNS are the addition and the multiplication. Since elements are polynomials in the AMNS, the addition (resp. the multiplication) is an addition (resp. the multiplication) of polynomials. However, additional operations have to be done in order to obtain the result in the AMNS. This is explained by the following: Let x, y ∈ Z/pZ be two integers. Let V ≡ x B and W ≡ y B be their representations in B. The polynomial T = V W satisfies T (γ) ≡ xy (mod p). However, T might not be a valid representation of xy in B, because its degree could be greater than or equal to n. To keep the degree lower than n, the product V W has to be computed modulo the polynomial E. This operation is called the external reduction. Notice that since E(γ) ≡ 0 (mod p) and T = V W (mod E), we have T (γ) ≡ xy (mod p) and deg(T ) < n.

Even if deg(T ) < n, T might not be a representation of xy (mod p) in B, because its coefficients could be greater than or equal to ρ. To have the result in B, a specific primitive called the internal reduction has to be applied.

The same reasoning can be applied for the addition, S = V + W satisfies S(γ) ≡ (x + y) (mod p) and deg(S) < n. Here also, S might not be a valid representation in B, since its coefficients could be greater than or equal to ρ. Hence, the same internal reduction might be required to retrieve the result in B.

Some notations and conventions.

Before presenting the arithmetic operations with the reduction methods, we need to establish some notations and conventions for simplicity and consistency. For consistency, we assume that p 3 and n, γ, ρ 1.

Let Z n [X] be the set of polynomials in Z[X] of degree smaller than n:

Z n [X] = {C ∈ Z[X], such that: deg(C) < n}. If V ∈ Z n [X] is a polynomial, we assume that V (X) = v 0 + v 1 X + • • • + v n-1 X n-1 .

The external reduction.

The external reduction is a polynomial modular reduction. The goal of this operation is to keep the degree of the AMNS representations lower than n. Let C ∈ Z[X] be a polynomial. The external reduction consists in computing a polynomial C such that:

C ∈ Z n [X] and C (γ) ≡ C(γ) (mod p).
The Euclidean division of C by E computes Q and C so that:

C = Q × E + C , with deg(C ) < n and Q ∈ Z[X]
. Since E(γ) ≡ 0 (mod p), one has C (γ) ≡ C(γ) (mod p). So, the external reduction is done as: C = C mod E. The polynomial E is called the external reduction polynomial.

Let A ∈ Z n [X] and B ∈ Z n [X]. Let C = AB be a polynomial. Then, deg(C) < 2n -1. Since E(X) = X n -λ, with λ very small, the external reduction can be done very efficiently. The function RedExt (Algorithm 1) proposed by [START_REF] Plantard | Arithmétique modulaire pour la cryptographie[END_REF] can be used to perform this operation.

Algorithm 1 RedExt -External reduction [START_REF] Plantard | Arithmétique modulaire pour la cryptographie[END_REF]

Require: C ∈ Z[X] with deg(C) < 2n -1 and E(X) = X n -λ Ensure: C ∈ Z n [X], such that C = C mod E 1: for i = 0 . . . n -2 do 2: c i ← c i + λc n+i 3: end for 4: c n-1 ← c n-1 5: return C # C = (c 0 , . . . , c n-1 )
Remark 1. In [START_REF] Bajard | Modular number systems: Beyond the mersenne family[END_REF], the authors show that the output C of Algorithm 1 is such that:

C ∞ < n|λ| A ∞ B ∞ ,
with C = AB and A, B ∈ Z n [X]; cf. Section 3 of that paper.

The internal reduction.

The aim of the internal reduction is to ensure that the coefficients of polynomials are lower (in absolute value) than ρ. Let C ∈ Z n [X] be a polynomial, with C ∞ ρ. This operation consists in computing a polynomial S such that S ∈ B and S(γ) ≡ C (γ) (mod p).

Several methods have been proposed to perform this operation [START_REF] Bajard | Modular number systems: Beyond the mersenne family[END_REF][START_REF] Bajard | Arithmetic operations in the polynomial modular number system[END_REF]; [START_REF] Negre | Efficient modular arithmetic in adapted modular number system using lagrange representation[END_REF]. If the value of the modulus p is not imposed but only its approximate bit-size, then the proposal in [START_REF] Bajard | Modular number systems: Beyond the mersenne family[END_REF] might achieve the best efficiency. However, if the value of p is already given, then the proposal in [START_REF] Negre | Efficient modular arithmetic in adapted modular number system using lagrange representation[END_REF] is currently the best and is the one this paper focuses on.

In [START_REF] Negre | Efficient modular arithmetic in adapted modular number system using lagrange representation[END_REF], Negre and Plantard propose a Montgomerylike reduction method to perform the internal reduction. In their proposal, they combine the multiplication operation with their Montgomery-like internal reduction. In this paper, we split the multiplication process from the internal reduction, because the internal reduction is also essential for other operations like the addition and the conversions from Z/pZ to the AMNS (and vice versa). RedCoeff (Algorithm 2) corresponds to the internal reduction process included in Algorithm 1 of [START_REF] Negre | Efficient modular arithmetic in adapted modular number system using lagrange representation[END_REF].

Algorithm 2 RedCoeff -Coefficient reduction [START_REF] Negre | Efficient modular arithmetic in adapted modular number system using lagrange representation[END_REF] Require:

B = (p, n, γ, ρ, E), C ∈ Z n [X], M ∈ B such that M (γ) ≡ 0 (mod p), φ ∈ N \ {0} and M = -M -1 mod(E, φ). Ensure: S(γ) = C (γ)φ -1 (mod p), with S ∈ Z n [X] 1: Q ← C × M mod (E, φ) 2: R ← (Q × M ) mod E 3: S ← (C + R)/φ 4: return S
Notice that this Montgomery-like reduction method requires three additional parameters: a non-zero integer φ and two polynomials M and M . These polynomials are such that: M ∈ B, M (γ) ≡ 0 (mod p) and M = -M -1 mod(E, φ). The polynomial M is called the internal reduction polynomial.

Since this algorithm involves many reductions modulo φ (line 1) and many exact divisions by φ (line 3), it is necessary to take φ being power of two for this algorithm to be efficient. However, taking φ as a power of two while ensuring the existence of the polynomials M and M is not obvious. In [START_REF] Negre | Efficient modular arithmetic in adapted modular number system using lagrange representation[END_REF], the authors do not provide a generation process which allows that. In El [START_REF] El Mrabet | Efficient multiplication over extension fields[END_REF], El Mrabet and Gama give such a generation process but for the special case E(X) = X n + 1.

In [START_REF] Didier | Efficient modular operations using the Adapted Modular Number System[END_REF], the authors propose a generation process which ensures this requirement for E(X) = X n -λ, with λ ∈ Z \ {0}. In the same paper, they also give a generation process for all the others parameters along with a complete set of algorithms to perform arithmetic and conversion operations in the AMNS. Here, we only present the multiplication algorithm since it is the purpose of this paper. One should read the works done in [START_REF] Didier | Efficient modular operations using the Adapted Modular Number System[END_REF] for more details.

The modular multiplication.

As explained above, the authors in [START_REF] Negre | Efficient modular arithmetic in adapted modular number system using lagrange representation[END_REF] suggest a modular multiplication method which includes the Montgomery-like reduction method. Algorithm 3 corresponds to their proposal, except that it is split here in a set of algorithms.

Algorithm 3 Modular multiplication in AMNS [START_REF] Negre | Efficient modular arithmetic in adapted modular number system using lagrange representation[END_REF] Require:

A ∈ B, B ∈ B and B = (p, n, γ, ρ, E) Ensure: S ∈ B with S(γ) ≡ A(γ)B(γ)φ -1 (mod p) 1: C ← A × B 2: C ← RedExt(C) 3: S ← RedCoeff(C ) 4: return S
In [START_REF] Negre | Efficient modular arithmetic in adapted modular number system using lagrange representation[END_REF], Negre and Plantard show that if the parameters ρ and φ are such that:

ρ 2n|λ| M ∞ and φ 2n|λ|ρ,
then, the output S of the Algorithm 3 is such that S ∞ < ρ (i.e. S ∈ B); cf. Theorem 1 in [START_REF] Negre | Efficient modular arithmetic in adapted modular number system using lagrange representation[END_REF]. This requirement is assumed for φ and ρ in the Algorithm 3.

In [START_REF] Didier | Efficient modular operations using the Adapted Modular Number System[END_REF], the authors prove that it is always possible to generate an AMNS for any prime integer p 3 where the parameter E is such that E(X) = X n -λ, with λ = ±2 i . This makes the internal and the external reductions faster since these operations involve many multiplications by λ. As already mentioned, φ should be a power of two; i.e. φ = 2 t , with t ∈ N \ {0}. Let's consider a k-bit processor architecture, then the basic arithmetic computations are performed on k-bit words. The cost of the modular multiplication is given in Table 2 with λ = ±2 i and φ = 2 t . This cost is expressed as a function of the number of k-bit integer multiplications, additions and shifts. In that table, M and A respectively denote the multiplication and the addition of two k-bit integers. We also denote respectively S y l and S y r a left shift and a right shift of y bits.

Simple polynomial multiplication

n 2 M + (2n 2 -4n + 2)A External reduction 2(n -1)A + (n -1)S i l Internal reduction 2n 2 M + (3n 2 -n)A + nS t r Total cost 3n 2 M + (5n 2 -3n)A + (n -1)S i l + nS t r
Table 2: Theoretical cost of the modular multiplication, where E(X) = X n ± 2 i and φ = 2 t .

2.5. Some advantages of the AMNS.

Compared to the classical (binary) representation, the AMNS has many advantages. First, none of the algorithms for arithmetic operations in the AMNS has a conditional branching. This property is an advantage for efficiency and is also very helpful against side channel attacks, like the Simple Power Analysis (SPA) attack. Second, because the AMNS elements are polynomials, their coefficients are independent and there is no carry propagation to deal with, when performing arithmetic operations.

Finally, because its elements are polynomials, arithmetic operations in the AMNS can be very efficiently parallelized.

Methodologies for hardware implementation

In our modular multiplication we use the AMNS (Adapted modular number system) algorithm. Due to its regularity and simplicity, this algorithms can be easily implemented in the DSP slices of FPGAs.

Most of the proposed solutions in the literature use complex and expensive algorithms to release these data dependencies and improve computing performance in multipliers implanted. Due to the complexity of these algorithms, the corresponding fast modular multipliers often consume a significant amount of FPGA hardware resources. Thus, we can find in the literature examples of FPGA implementations of modular multipliers within ECC cryptosystems using several hundred DSP slices (see for example H. [START_REF] Alrimeih | Fast and flexible hardware support for ecc over multiple standard prime fields[END_REF]). We believe that such a consumption of resources is not reasonable for material implementations of embedded cryptosystems. We have therefore decided to propose a different solution based on architectural optimization rather than algorithms.

Our constraint is to implement a hight level security of cryptographic (128 or 256, 512 and 1024) in FPGA, knowing that the hardwired control units are not big enough for cryptographic sizes. In our target FPGAs, DSP slices are 18 × 25 bits units. Then processing each F p element would require many parallel BRAMs and DSP slices. But using many BRAMs is useless since the number of intermediate F p elements is small in ECC and HECC (up to 10 and 20 respectively). To allow hardware design having an efficient area and frequency on FPGA, we decompose k-bit elements into a a set of w-bit words so that w is a multiple of 18. The choice can reduce the number of slice DSP used in the design. We denote n the number of coefficient of w-bit necessary for each operand with k = nw.

The system model

Our hardware implementation of the modular multiplication in AMNS is based on the algorithm 3. This algorithm can be expanded as follows:

Algorithm 4 Modular multiplication in AMNS -Main steps Require: A ∈ B, B ∈ B and B = (p, n, γ, ρ, E) Ensure: S ∈ B C ← A × B C ← C mod E Q ← C × M mod (E, 2 r ) R ← ((Q × M )) mod E S ← (C + R)/2 r (1) (2) (3) (4) (5)
We remind that the inputs A, B and C are polynomials of degree n -1. Thus, the polynomial A has n coefficients noted a i for i ∈ {0, • • • , n}. The polynomial M is the internal reduction polynomial and the modular inverse of its opposite modulo (E, 2 r ) is M . Note that for efficiency reasons, we choose φ = 2 r . The external reduction polynomial E is a sparse polynomial of the form E(X) = X n -λ. The polynomials C, C and R are intermediate polynomials. This algorithm produces the output polynomial S being the result of the modular multiplication.

The coefficients of the inputs A, B, C and the constants M and M are stored in the memory. The result is written back in the same memory. The structure of our architecture is given in Fig. 1. In this figure, the AMNS Multiple-Coefficient operator, processes the steps (1), ( 2), ( 3), ( 4) and ( 5 We detail the several steps processed in the AMNS Multiple-Coefficient unit for n = 4.

We can directly computes C = A × B mod E as follows:

• c 0 = a 0 b 0 + λ(a 1 b 3 + a 2 b 2 + a 3 b 1 ), • c 1 = a 0 b 1 + a 1 b 0 + λ(a 2 b 3 + a 3 b 2 ), • c 2 = a 0 b 2 + a 1 b 1 + a 2 b 0 + λ(a 3 b 3 ), • c 3 = a 0 b 3 + a 1 b 2 + a 2 b 1 + a 3 b 0 .
Note that this step combine the polynomial multiplication (1) and the polynomial reduction (2). Indeed, the external reduction polynomial E = X n -λ is a sparse polynomial which property is X n mod E = λ. Thus the product C = A × B and the reduction C = C mod E can be combine. The polynomial multiplication is usually implemented using a multiplier-accumulator (MAC operator) with a fixed operation data width (e.g., 36 bits).

The second step computes Q = C × M mod (E, 2 r ) as follows :

• Q 0 = c 0 m 0 + c 1 m 3 + c 2 m 2 + c 3 m 1 , • Q 1 = c 0 m 1 + c 1 m 0 + c 2 m 3 + c 3 m 2 , • Q 2 = c 0 m 2 + c 1 m 1 + c 2 m 0 + c 3 m 3 , • Q 3 = c 0 m 3 + c 1 m 2 + c 2 m 1 + c 3 m 0 .
The third step computes R = ((Q × M )) mod E:

• R 0 = q 0 m 0 + q 1 m 3 + q 2 m 2 + q 3 m 1 , • R 1 = q 0 m 1 + q 1 m 0 + q 2 m 3 + q 3 m 2 , • R 2 = q 0 m 2 + q 1 m 1 + q 2 m 0 + q 3 m 3 , • R 3 = q 0 m 3 + q 1 m 2 + q 2 m 1 + q 3 m 0 .
The last step is simply S = (C +R)/2 r . Thus the modular multiplication is processed through four states, such that the final result S is available at state five. This is illustrated in Fig. 2

Hardware Implementation

In this section, we present two architectures that can be used for computing a modular multiplication in the AMNS on FPGA.

The first is a sequential architecture, which is easy to realize because the arithmetic operations are performed in the order described in Fig. 3. A preliminary analysis shows that the sequential architecture uses fewer slices registers than the semi-parallel architecture but requires more clock cycles for completing the modular multiplication in the AMNS. The second architecture is semi-parallel architecture which aims to execute the most arithmetic operations in the same cycle to have a fast design.

In Section 4.1, we present our sequential architecture while our semiparallel architecture is presented presented in section 4.2.

Sequential architecture

In this design the steps described in section 3.1 are scheduled as shown in figure 3. This figure is an example of the scheduling of a modular multiplication in AMNS, which inputs A and B have four 36-bits coefficients and the modulus p is a 128-bit integer.

In figure 1 the AMNS Multiple-Coefficient block executes the foregoing algorithm as follows. It inputs the loop variables i and j from the control state machine and supplies them to the memory as its address input. The The steps (1), ( 3) and (4) requires n states in order to be computed, while the steps (2) and ( 5) are performed in one state.

The Fig. 4, Fig. 5, Fig. 6 and Fig. 7 shows the parts of the AMNS Multiple-Coefficient block that computes steps (1) and ( 2), (3), ( 4) and (5). While these figures do not show it, the AMNS Multiplication architecture includes a 36 -bit wide single port memory, which allows either read or write access to a single address in one clock cycle. This memory stores the input values A, B, M and M for computation as well as receives the output value S. It also serves as temporary storage for intermediate variables C , R and Q.

The computation of step ( 1) and ( 2) is illustrated in figure 4. Each 72-bit coefficient of C is computed with a 36-bit inputs MAC operator. For instance, for a 128-bit precision architecture, four MAC operators are required at this step. Such a data-path requires 3 DSP blocks for each MAC operator. Each MAC performs a multiplication of coefficients of A and B taken from memory and accumulates the result. The final value is stored in the C i registers that can output serially the result. It has to be remarked that the step (3) which used C has to be computed modulo(E,φ). Thus, in this example, only 40 bits of the coefficients c i are needed at the next step.

The architecture of the module that computes the step (3) of the modular multiplication is similar to the previous module except the size of inputs and outputs (Fig. 5). In this module, each MAC operator inputs one 39bit coefficient of M and one 40-bit coefficient of C . Each MAC operator outputs one 79-bit coefficient of Q, but only 40 bits are kept because step (3) is computed modulo(E,φ). The computation of step ( 4) is illustrated by figure 6. This module is similar to the module displayed in figure 4 except the size of the inputs and the output. Each MAC operator inputs a 36-bit coefficient of M and a coefficient of Q that is serially given. Each module outputs a 76-bit coefficient of R which is stored in a 76-bit register (not displayed in Fig. 6). The final step (5) consists of a 76-bit addition and a shift. The module that computes this step is illustrated in figure 7. Each adder inputs a 72-bit coefficient of C and a 76-bit coefficient of R. The following shift operator corresponds to the division in step (5). In this example the divisor is 2 40 . The 36 bit coefficient of the result S are stored back to the memory. The data path consists of eight internal registers, a counter and a comparator. The controller remains in the state S 0 until the START instruction is set. When the START signal is set, the a i and b i registers are loaded with input values, the C 00 , C 10 , C 20 , C 30 registers and the counter are reset. The different states are summarized in table 3. The remaining states work as follows:

• In the state S 1 , S 2 , S 3 and S 4 the FSM machine execute the steps ( 1) and ( 2) of the algorithm.

• S 1 , S 2 , S 3 and S 4 are waiting to validate the DON E_C signal. Once the coefficients of the polynomial C are charged in the BRAM register, the FSM change to the next state.

• In the state S 5 , S 6 , S 7 and S 8 are waiting to validate the DON E_Q signal. They computes the step (3) in the algorithm. Once the coefficients the polynomial Q are charged in the BRAM register, the FSM change to the next state.

• S 9 , S 10 , S 11 and S 12 control the computation of the step (4) of the algorithm. They are waiting to validate the DON E_R signal. Once the FSM machine generates the coefficients of the polynomial R and charges them in the BRAM register, the FSM change to the next state.

• In the state S 13 is waiting to validate the DON E_S signal. It computes the last step of the algorithm.

Steps Transition Condition Initialization S 0 reset = done

Steps ( 1) and ( 2)

S 0 → S 1 S 1 → S 2 S 2 → S 3 S 3 → S 4 DON E_C = 1 DON E_C = 1
Step (3)

S 4 → S 5 S 5 → S 6 S 6 → S 7 S 7 → S 8 DON E_Q = 1
Step ( 4)

S 8 → S 9 S 9 → S 10 S 10 → S 11 S 11 → S 12 DON E_R = 1
Step (5) S 12 → S 13 DON E_S = 1

Our semi-parallel architecture

We present in this section our semi-parallel architecture which aim is to execute the maximum of intermediate operations in parallel in order to minimize the number of cycles. As an example, we describe in Fig. 9 a scheduling of the steps of the algorithm 3, with n = 4 and w = 36.

It appears that it is not necessary to wait for the end of the computation of the last coefficient of C in step (1) before to start the computation of the step (2) (Alg.4). Indeed, at step 1, we compute in parallel the terms that have to be added in order to get c 0 . Thus, the computation of the coefficients C 0 starts at step 2 (Fig. 9). It is possible to observe the same thing with step (2) and step (3) and with step (4) and step (5).

As a consequence, our semi-parallel architecture is composed of 4 modules as detailed in Fig. 10,Fig. 11,Fig. 12 and Fig. 13. Each of them, take in charge one or two steps of Alg. 3. These modules are:

• Fig. 10: The multiplication a i ×b j is done through the cell M U LT IP LIER.

The cell ADDER collects the products and computes give c i . 1) and ( 2) with w = 36 and a 128-bit modulus p coefficient of C . This coefficient is input serially. Each operator output a coefficient of Q that is written back serially to the memory. The module operator in Fig. 12 computes the step (4). It is composed of multipliers that input the coefficients of M and Q. The multipliers are designed to perform the calculation of (40 -bits × 36 -bit integers) and output 76-bit integers. The result is stored in the R i -Reg registers that are input to the adder which computes one 76-bit coefficient of R. The output is connected to a demultiplexer which outputs all the computed coefficients of R.

The last module (Fig. 13) computes the last step of the modular multiplication in AMNS. It is composed of 76-Addershift operators that input the 72-bit coefficients of C and the 76-bit coefficients of R. In this step a division by 2 r is performed. Thus, only the 36 most significant bits of the sum are output.

Main controller (MC)

. This design is controlled by a synchronous finite state machine (FSM). For w = 36 and a modulus p of 128 bits, the FSM controlling our semi-parallel architecture is illustrated in Fig. 14. It is composed of 11 states, the state S 0 being the starting state. In this FSM, each state requires two cycles to be completed, except the final state which is executed in only one cycle. This leads to a total cost of 21 cycles. The data path of this Once the START signal is set, the inputs a i and b i are loaded, the C 00 , C 10 , C 20 , C 30 registers and the counter are reset. The FSM loops while the DONE is not set. The machine advances to the next state once it is triggered by a valid transition.

• The first state is an initial state S 0 . During this state, the coefficients a i and b i are loaded into the registers.

• Once the states S 1 , S 2 , S 3 and S 4 are completed, DON E_C signal is set. These state permits the computations of the coefficients of the • In the state S 1 the FSM machine use an MAC operator to execute equation ( 1) and (2) of the algorithm 4. In this state the machine compute the coefficient c 0 of the polynomial C .

• In the state S 2 the machine compute the second coefficient c 1 of C . In parallel it starts the computation the coefficient q 0 of polynomial Q.

Once the coefficients value of the polynomial q 0 and c 1 are charged in the BRAM register, the FSM change to the next state. This corresponds to the step (5).

• The state S 10 sets the DON E_s 3 signal. It compute the fourth coefficient of the polynomial S by using an adder operator and a shift operator.

Experimental results

We completely implemented and validated our semi-parallel and the sequential architectures for AMNS on FPGA. We choosed two different families of FPGA, in order to confirm our results with two different technologies. Our designs have been described in VHDL language, synthetized, placed and routed with ISE 14.7 tools for Xilinx FPGA and Quartus II 12.1 for Intel-Altera FPGA using the default synthesis option The results are given for 4 FPGA families:

• two low cost FPGA: Aria II GX (EP2A6x45DF2915) and Zynq xc7 (z010-3g400),

• two high performance FPGA: Virtex 6 (X6vlx 75 t-3ff484) and Cyclone V (5cgXFC7DF 31 C8ES)

Below, we report the results for a modular multiplication with different coefficient sizes w and for different size of p: 128, 256, and 512 bits for FPGA that are large enough. Here we report the maximum operating frequency of the architectures, the number of cycles require to completed the modular multiplication, the total time of the computation, the number of DSP blcks and LUT needed in the implementation. In Tab. 4 and 5 respectively, we give a report of the results of our semiparallel architecture for Xilinx and Intel-Altera FPGA after placement and routing. The results of the implementations of our sequential architectures are reported in figure 6 and7.

Family

As expected, the semi-parallel architecture records the most efficient speed of execution while the sequential design achieves the smallest area.

We observe that Xilinx FPGA provides fastest computations for modular multiplication in AMNS representation compared to the Altera Family.

Family

Comparison with the state of the art

To our knowledge our implementation is the first VHDL implementation of a FPGA architecture of a modular multiplication using AMNS as a number system. We compared our design to some previously published works:

• The first design we are comparing to is detailed in [START_REF] Ors | Hardware implementation of a montgomery modular multiplier in a systolic array[END_REF]. It is a systolic architecture for Montgomery Modular multiplication and uses binary numbers.

• The second design is also a systolic architecture that is based on the CIOS Montgomery modular multiplication by [START_REF] Mrabet | A systolic hardware architectures of montgomery modular multiplication for public key cryptosystems[END_REF]. It also make use of binary numbers.

• The third design is detailed in [START_REF] Bigou | Single base modular multiplication for efficient hardware rns implementations of ecc[END_REF]. Its originality is that it uses Residue Number Systems (RNS) as an integer number system. This architecture is based on cox-rower components introduced in [START_REF] Kawamura | Cox-rower architecture for fast parallel montgomery multiplication[END_REF].

• The design published in [START_REF] Rezai | High-throughput modular multiplication and exponentiation algorithms using multibit-scan-multibit-shift technique[END_REF] uses carry-save representation in the intermediate results.

• The systolic architecture described in [START_REF] Rezai | High-performance scalable architecture for modular multiplication using a new digit-serial computation[END_REF] uses the binary signed digits representation in order to minimize the number of non-zero partial product in the modular multiplication.

• Similarly the architecture presented in Rezai and Keshavarzi (2015) make use of a binary signed digits. Comparing FPGA design is a challenging task because the technologies used are heterogeneous. In this comparison we detailed the number of slices, the number of DSP blocks, the number of cycles needed to complete the modular multiplication and the total delay. Some architectures uses DSP blocks, while some others use only LUT blocks. For the sake of comparison, we unified the measure of the area by calculating an estimate value of LU T eq = nLU T + (nDSP × r), where nLU T is the number of LUT slices, nDSP is the number of DSP blocks and r is the ratio of number of LUTs by the number of DSP blocks available on the target device. Thus the is Area-Delay Product (ADP) is computed as follows: LU T eq × T ime(µs). It appears that our designs faster than the other designs for 256-bit moduli as well for 1024 moduli. As a consequence, the throughput is the highest for all moduli size. This is mainly due to the number of DSP blocks that greatly increase the speed of the architecture, at the price of the area. Compared to the design described in [START_REF] Ors | Hardware implementation of a montgomery modular multiplier in a systolic array[END_REF], our architectures are up to 23 times faster and a ADP up to 1.6 times smaller.

Compared to the architecture of [START_REF] Mrabet | A systolic hardware architectures of montgomery modular multiplication for public key cryptosystems[END_REF] which is a systolic hardware architectures of Montgomery modular multiplication, our design is a bit faster with a better throughput and a bit higher.

The design of [START_REF] Bigou | Single base modular multiplication for efficient hardware rns implementations of ecc[END_REF] is an original design that make use of Residue Number Systems as number system. Compared to this architecture, our designs remain faster but larger. The throughput of our architecture is is higher.

Considering the comparison with the modular multiplication architectures described in [START_REF] Rezai | High-performance scalable architecture for modular multiplication using a new digit-serial computation[END_REF]), ) [START_REF] Rezai | High-throughput modular multiplication and exponentiation algorithms using multibit-scan-multibit-shift technique[END_REF]) and [START_REF] Rezai | Compact sd: A new encoding algorithm and its application in multiplication[END_REF]), our sequential design is faster at the cost of a larger number of slices. We can see that the throughput achieved by these implementations is significantly smaller than what we are able to achieve with our proposed semi-parallel and sequential implementations.

Regardless to the size of the modulus p both our sequential and semi-parallel designs have an interesting property: the number of cycle is independent from the size of the modulus.

Architecture

Conclusion and future works

In this paper, we present a fast hardware architecture that realizes a modular multiplication over large prime characteristic finite fields F p , which uses AMNS representations in order to speed up modular multiplication. We propose two hardware architectures: a semi-parallel architecture and a sequential one. Our semi-parallel architecture provides the fastest implementations. As we propose the first hardware implementation of the modular multiplication in AMNS, we compare our results with existing modular multiplication like systolic CIOS, systolic architectures using carry-save or signed digit representations for the intermediate results and arcitecture designed for the RNS modular multiplication. The comparison of our results with the state of the art highlight that we propose the fastest implementation of modular multiplication for large field application with the highest throughput.

For future work, we prospect to optimize the semi-parallel structure to reduce the area size. We would like to implement a full ECC scalar multiplication using the modular arithmetic in AMNS.

  ) of the AMNS multiplication algorithm. It reads the coefficient of each input value a i , b j , m j and m j out of the memory, processes the intermediate results C , Q, R, S and store them in dedicated local registers. This allows C , Q and R to be used in the AMNS Multiple-Coefficient operator as intermediate values that are input for the next cycle. The register dedicated to S supplies the result to the memory. This unit is controlled with a finite state machine.

Figure 1 :

 1 Figure 1: System architecture

Figure 2 :

 2 Figure 2: Illustration of modular multiplication operations in AMNS. The notation "*" represents mod (E), and "**" represents mod (E, φ)

Figure 3 :

 3 Figure 3: Scheduling of the sequential architecture

Figure 4 :

 4 Figure 4: Sequential architecture, computation of step (1) and (2)

Figure 5 :

 5 Figure 5: Sequential architecture, computation of step (3)

Figure 6 :

 6 Figure 6: Sequential architecture, computation of step (4)

Figure 7 :

 7 Figure 7: Sequential architecture, computation of step (5)

Figure 8 :

 8 Figure 8: Finite state machine for w = 36 and a 128-bit modulus p -Sequential architecture

Figure 10 :

 10 Figure 10: Semi-parallel architecture, computation of step (1) and (2) with w = 36 and a 128-bit modulus p

Figure 11 :

 11 Figure 11: Semi-parallel architecture, computation of step (3) with w = 36 and a 128-bit modulus p

Figure 14 :

 14 Figure 14: Finite state machine for the optimal architecture with w = 36 and a modulus p of 128 bits

Figure 12 :

 12 Figure 12: Semi-parallel architecture, computation of step (4) with w = 36 and a 128-bit modulus p

Figure 13 :•

 13 Figure 13: Semi-parallel architecture, computation of step (5) with w = 36 and a 128-bit modulus p

Figure 15 :

 15 Figure 15: Speed test results

Figure 16 :

 16 Figure 16: ADP and throughput results

Table 1 :

 1

The elements of Z/19Z in B =

(19, 3, 7, 2)

Table 3 :

 3 State transition table of the FSM

•

  The state S 3 , S 4 and S 5 aim to validate the DON E_q 1 , DON E_q 2 , DON E_q 3 , DON E_c 2 , DON E_c 3 signals. The FSM use eight MAC operators in each state to execute step (3). Once all the coefficients of the polynomial Q are generated, the FSM moves to the next state.• The state S 6 validate the DON E_r 0 signal. It computes step (4),

Table 4 :

 4 Semi parallel architecture results on Xilinx FPGA

	Family		Intel -Altera
	FPGA	Aria II	Cyclone V
	p size bit 128	256	128	256	512
	w bit	36		36		72
	Fq(Mhz) 218.2 194.4 157.1 106.4 101.6
	Cycles	19	33	19	33	33
	Time µs 0.087 0.169	0.12 0.309 0.324
	DSP	70	128	40	80	112
	LUT	1722	4173	1201 2747 14670

Table 5 :

 5 Semi parallel architecture results on Intel-Altera FPGA

Table 6 :

 6 Sequential architecture results on Xilinx FPGA

	Family			Altera
	FPGA	Aria II	Cyclone V
	p size bit 128	256	128	256	512
	w bit	36		36		72
	Fq(Mhz) 237.3 213.3 157.2 123.4	82.7
	Cycles	23	47	23	47	47
	Time µs 0.096	0.22	0.146 0.38	0.568
	DSP	42	80	28	52	112
	LUT	1267	2423	679	1304 14283

Table 7 :

 7 Sequential architecture results on Intel-Altera FPGA

Table 10 :

 10 Comparison of ADP and throughput result for 1024-bit modulus p..

		FPGA	Area (LU T eq )	Time (µs)	ADP	Through-put (Mb/s)
	Semi-parallel	V7	124151	0.43	53384	2381.39
	Sequential	V7	55667	0.598	33288	1712.37
	Rezai and Keshavarzi (2014)	V5	6105	0.883	5390	1159.6
	Rezai and Keshavarzi (2016)	V6	1125	2.56	2880	356
	Rezai and Keshavarzi (2015)	V5	6091	0.851	5180	1203.3

https://github.com/arithPMNS/generalisation_amns

• Fig. 12: The multiplication of the coefficients of Q by M mod E generate R.

• Fig. 13: The addition C + R, followed by the exact division by Z r , generates the coefficients of the output S.

The first module in Fig. 10 is in charge of step (1) and (2). The first part of this module is composed of multipliers that compute the product of the 36-bit coefficients of A and B in one cycle. The resulting 72-bit coefficient is stored in the registers.

The second part of this module is composed of an Adder operator which collect the intermediate products and sum them in order to compute one coefficient of C. In this example:

The output of the Adder is connected to a demultiplexer that output the coefficient as soon as its computation is completed. In this example, this module requires 5 cycles for completing the computation. It has to be noted that each state is executed in two clock cycles.

The module in Fig. 11 is designed to compute the step (3) of Alg. 3. It is composed of MAC operators that input a 39-bit coefficient of M and a We present in table 8 the implementation results of our architectures compared to the state of the art for modulus size between 128 and 512 bits. Such a modulus size range targets implementations for ECC [START_REF] Hankerson | Elliptic curve cryptography[END_REF]). We highlight the area, time and throughput results for two sizes of the modulus p. The table 9 show the results for 256-bits moduli. This size targets Elliptic Curve Cryptograhy. In table 10 we show the results for large cryptographic sizes that target RSA algorithm (Rivest et al. (1978a) Our semi-parallel implementation achieves a higher throughput than the sequential. Although the ADP of semi-parallel improve significantly, they do not approach the minimum of ADP in all technologies. The performance of semi-parallel architecture is generally better than sequential architecture.