Laurent-Stéphane Didier

Christophe Nègre

Jean-Claude Bajard

] L Dzbt19

T Djath

K Zijlstra

A Tisserand Bigou

Keywords: Addition, soustraction, carré, multiplication, multiplication par des constantes, inversion

On the drawback side, position-related operations such as modular reductions (MRs), divisions and comparisons are di cult since the representation is nonpositional. Indeed, the order of magnitude of operands is more di cult to evaluate than in a positional representation.

1.8 Excerpt of C code for HLS to explain the multiplication of arrays elements on two channels. Each of the components mul0 and mul1 is dedicated to a channel and performs a multiplication of a value received as input by a precomputed value stored internally. The description made in the component prod allows the components mul0 and mul1 to run in parallel. #pragma HLS PIPELINE allows to pipeline the operations within the loop of the component prod. . for various estimations EMM/CMR(2w + 1, w) and numbers n of moduli. .

2.9 Comparison of the time, the numbers of DSPs and slices between HBE c = 2 (from [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF]) solutions and KBE (from [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF]) ones. . . . . . .

3.1 Decomposition of the numbers n of VCs and q of PCs in usual RNS implementations of the ECSM, that is, q = n. In this example, q = n = 16.

Computations related to one VC is performed on each PC. . . . . . . . . .

3.2

Example of decomposition of the numbers n of VCs and q of PCs in RNS implementations of the ECSM when q = 4 and n = 16. Computations related to n/q = 4 VCs are performed on each PC. At a time, each PC deals with one VC, and the 4 VCs are processed one after another. . . . . .

3.3

The architecture for the flexible KBE (adapted from the cox-rower architecture [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF]): example with q = 4 PCs and c = 2. . . . . . . . . . . .

3.4

Structure of the arithmetic processing performed by a rower. The rower performs the operation g Ω (g + a ◊ b + f ) mod m, where m = 2 w ≠ Á (with Á < 2 w/2 ), and a, b, f and g are of size w bits. . . . . . . . . . . . . .

Comparison of FPGA implementation results of the flexible KBE (adapted

from [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF]) for q oe {1, 2, 4, 8, 16} PCs. Finite fields are of 256-bit elements and the width of the PCs is 17 bits. . . . . . . . . . . . . . . . . .

3.6

Example of numbers cycles used by one PC to perform all computations related to the 16/q VCs it handles. The PC sequentially 'uploads' the 16/q VCs. Computations on the same PC are pipelined. In this typical example of loops at lines 1-4 of Algorithm 13, the computations related to the rc = 16 VCs are equally shared by the q PCs in use. At the left figure, q = 2 PCs are used and each PC handles 8 VCs. At the first cycle (top to bottom), computations related to the first VC start. At the next cycle, computations related to the next VC start, and so on until computations related to all 8 VCs (mapped onto the PC) start. Meanwhile, it is possible that the PC has terminated the computations related to the VCs that started earlier. Still, a few cycles are needed by the PC to terminate the remaining computations related to its ongoing VCs, that is, to empty out the pipeline. At the right figure, q = 4 PCs are used and each PC handles 4 VCs. The filling and emptying of the pipeline are similar to the ones at the left figure. . . . . .

LIST OF TABLES

1.1 Some RNS implementations of asymmetric cryptosystems on FPGA from the literature. The size (ı) is the operand size (for example the modulus size for RSA or the size of the underlying field of the curve for ECC). . . . . .

2.1 FPGA implementation results for CMR(2w + 1, w) and EMM operations on a Xilinx XC7Z020 FPGA. . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 HLS implementation results on a XC7Z020 FPGA for HBE c = 2 (from [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF]) and KBE (from [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF]) algorithms for two widths of prime field elements and four RNS channel widths w. . . . . . . . . . . . . . . . .

3.1 HLS implementation results on a XCZU7EV-FFVC1156 FPGA for the flexible KBE (adapted from [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF]) using q oe {1, 2, 4, 8, 16} PCs. Finite fields are of 256-bit elements and the width of the PCs is 17 bits. . . . . .

HLS implementation results

on a XCZU7EV-FFVC1156 FPGA for the flexible HBE (adapted from [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF]) using q oe {2, 4, 8, 16} PCs. Finite fields are of 256-bit elements and the width of the PCs is 17 bits. . . . . .

3.3

Comparison of FPGA implementation results of the flexible HBE (adapted from [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF]) with those of the flexible KBE (adapted from [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF]) for various number of PCs. The flexible HBE is not implemented for one PC. Finite fields are of 256-bit elements and the width of the PCs is 17 bits.105

3.4 Generalized Montgomery curve formulas to curves in short Weierstraß equation [START_REF] Brier | Weierstraß elliptic curves and side-channel attacks[END_REF][START_REF] Izu | A fast parallel elliptic curve multiplication resistant against side channel attacks[END_REF]. The formulas are in projective coordinates. The value x Q denotes the a ne x-coordinate of Q, the input point of Algorithm 15 about the Montgomery ladder. . . . . . . . . . . . . . . . . . . . . . . .

3.5

Steps to compute point addition and doubling formulas from [START_REF] Brier | Weierstraß elliptic curves and side-channel attacks[END_REF][START_REF] Izu | A fast parallel elliptic curve multiplication resistant against side channel attacks[END_REF] reported in Table 3 [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF] . . . . . . . 12 Hierarchical base extension BE MaeM Õ (x) [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF] . . . . . . . . . . . . . . . [START_REF]ESJ +[END_REF] Flexible KBE BE MaeM Õ (x) adapted from [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF]. The function f (v, i) is given by f (v, i) = q c (v ≠ 1) + i. . . . . . . . . . . . . . . . . . . . . . . . . . 14 Flexible HBE BE MaeM Õ (x) adapted from [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF]. The function f (v, i) is given by f (v, i) = q c (v ≠ 1) + i. .

LIST OF ALGORITHMS

INTRODUCTION

Context

Hardware accelerators of asymmetric cryptosystems with flexible utilization of resources are proposed in this thesis. Asymmetric cryptography is used in various applications in order to, among others, securily exchange a secret key, digitally sign documents or authenticate for example, to a server. For instance, the transport layer security (TLS) protocol, used notably in the hypertext transfer protocol secure (HTTPS), relies on asymmetric cryptography for the server/client authentication during the TLS handshake. Asymmetric cryptosystems are implemented in many devices used on a daily basis such as smartphones, personal computers, TV sets and smart cards. These devices have various security requirements to protect the sensitive data they handle. The implementations of the cryptosystems have to be secure and e cient to protect the involved data and to avoid poor performance of the devices.

Computations in current asymmetric cryptosystems involve large operands. For example, operands in RSA [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF] are integers of more than 2000-bit size, and operands in elliptic curve cryptography (ECC) [START_REF] Miller | Use of elliptic curve in cryptography[END_REF][START_REF] Koblitz | Elliptic curve cryptosystems[END_REF] are finite field elements of more than 200-bit size. Therefore, an e cient arithmetic suitable for large operands is needed. The residue number system (RNS) [START_REF] Valach | P evod ísel ze soustavy zbytkov˝ch t íd do polyadické soustavy zm nou m itka periody (the translation of numbers from the system of residual classes to a polyadic system by change of scale of period)[END_REF][START_REF] Garner | The residue number system[END_REF] is a nonpositional number system wherein large operands are represented by their residues over a set (called base) of small coprime moduli m i (a few dozens-bit size). Basic operations such as multiplication, addition and subtraction are independently performed on the small residues. Computations on large operands are then replaced by parallel computations on small operands, leading to faster basic operations. This independence also induces carry-free operations between the moduli [START_REF] Szabo | Residue arithmetic and its applications to computer technology[END_REF]. These advantages recently motivate uses of RNS in implementations of asymmetric cryptosystems; see, for example [NMSK01, SFM + 09, Gui10, BM14].

INTRODUCTION

the modular operations therein. For instance, the main operation in RSA is the modular exponentiation. For ECC applications, the main operation is the elliptic curve scalar multiplication (ECSM), which itself is computed through numerous operations on finite field elements. To reduce the cost of the RNS MR in [START_REF] Posch | Modulo reduction in residue number systems[END_REF], the base extension (BE) proposed in [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF] is used. The BE becomes an important operation in RNS implementations of asymmetric cryptosystems because the cost of the RNS MR is substantially the cost of the two BEs it comprises.

A channel is the hardware support of basic operations on small residues modulo an element m i of the RNS base. In current RNS implementations of asymmetric cryptosystems (see, for example [NMSK01, SFM + 09, Gui10, BM14]), the number of used channels is the number of moduli needed to represent the large operands. The quantity of hardware resources used in implementations is then related to the size of the large operands involved in the computations of asymmetric cryptosystems. The quantity of needed hardware resources becomes a problem whenever it is greater than the one available on the integrated circuit.

Most integrated circuits are primarily used for noncryptographic applications such as signal processing. After taking into account the hardware resources for the primary applications, the remaining hardware resources can be insu cient to implement the desired asymmetric cryptosystem. In such cases, the circuit designer is forced to choose between lowering the performance of the primary applications and reducing the level of security needed to protect the involved data. However, in many domains such as defense or aerospace industries, this choice is not acceptable.

The lack of hardware resources (on an integrated circuit) to implement a desired asymmetric cryptosystem can also occur over time. The recommended levels of security for asymmetric cryptosystems increase over some time. This increase is usually followed by an increase in the sizes of the large operands involved in computations of asymmetric cryptosystems. For instance, the recommended minimal level of security for ECC applications grows recently from 80 bits to 128 bits, resulting in a growth of the minimal size of finite field elements from 160 bits to 256 bits; see, for example [START_REF]Digital signature standard (DSS)[END_REF]ndlsdsd11,[START_REF]Digital signature standard (DSS)[END_REF]. The increase in the sizes of the operands is translated into an increase in the quantity of hardware resources needed for implementing the desired cryptosystem on the same device.

An integrated circuit (reconfigurable) on which is implemented an asymmetric cryptosystem can lack hardware resources for a new implementation of the same cryptosystem but with larger operands that guarantee a greater level of security. To maintain the per-

INTRODUCTION

formance of other applications and upgrade to a greater level of security, the designer has to acquire a new integrated circuit larger than his/her previous one in use. For most designers, this solution is not desirable owing to its financial cost.

Designing hardware accelerators for asymmetric cryptosystems with resource utilization adaptable to the resources available on an integrated circuit is a solution to the mentioned problem. We refer to such accelerators as flexible hardware accelerators. In RNS implementations of asymmetric cryptosystems, such accelerators can be achieved by using fewer channels than normally needed to perform computations on the large operands. In this case, we refer to these fewer channels as physical channels (PCs) to di erenciate them from the in-number normally needed channels that we name virtual channels (VCs).

The work presented in this thesis primarly targets ECC applications. However, some of the contributions are also adaptable to other asymmetric cryptosystems such as RSA.

To evaluate our propositions and compare our solutions with the state-of-the-art ones whenever the latter are existent, we implemented the propositions on field programmable gate arrays (FPGAs) using high-level synthesis (HLS) tools. FPGAs are integrated circuits configurable after manufacture. Their reconfigurability and lower costs (in design complexity and time, financial cost per unit1 ) compared with ASICs2 are reasons that motivate their use for hardware implementations-generally, and particularly in the work presented in this thesis-despite their lower performance (see, for example [START_REF] Sentieys | Architectures reconfigurables FPGA[END_REF]). HLS allows to use a high-level description (for example in C or C++) to automatically describe a register transfer level (RTL) design in a hardware description language (HDL). Compared with HDLs, HLS facilitates fast configurations of FPGAs; more configuration details are handled by the HLS tools.

Contributions

We have investigated two aspects of the BE. The choice of BE as our primary subject of investigation is motivated by the fact that the BE is the most important operation in the ECSM when targeting RNS implementations. One investigated aspect of the BE is its speed. A new BE algorithm with a theoretical cost smaller than that of the state-of-the-art INTRODUCTION algorithm will ultimately result in performance improvements of RNS implementations of the ECSM. The other invertigated aspect is the flexibility of the BE and the translation of the latter to the ECSM. In RNS implementations of the ECSM, the BE is not only the most important operation, but also the most complex one. Implementing a flexible BE is therefore essential in implementing an RNS-flexible ECSM.

The first contribution of this thesis is a new BE algorithm [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF], named hierarchical base extension (HBE). HBE relies on a hierarchical approach for computing the Chinese remainder theorem (CRT). The approach comprises two phases. In the first phase, the input residues are combined by pairs through computations of partial CRTs in the input RNS base. In the second phase, the remaining of the CRT computation is proceeded on the results of these partial CRTs in the output RNS base. The theoretical cost of the HBE algorithm is smaller than that of the BE algorithm proposed in [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF], named KBE (in this thesis) and largely regarded as the state-of-the-art BE. This cost reduction translates to a cost reduction of the RNS MR operation using HBE compared with the one using KBE. To exploit the inherent parallelism of RNS well preserved in the coxrower architecture proposed in [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF], the latter is adapted to support HBE. HLS implementations on FPGA of the two algorithms for various finite field sizes and channel widths show that HBE solutions are always faster and in nearly all cases smaller than KBE ones. The area vs. time trade-o is always in favor of HBE. As a consequence, similar performance improvements are expected in ECSM implementations using HBE compared with the ones using KBE; this expectation is verified in the next contribution.

[DBT19] L. Djath, K. Bigou and A. Tisserand. Hierarchical approach in RNS base extension for asymmetric cryptography. In 26th IEEE Symposium on Computer Arithmetic (ARITH), pages 46-53. IEEE, 2019. DOI: 10.1109/ARITH.2019.00016 Also available from https://hal.archives-ouvertes.fr/hal-02096353

The second contribution of this thesis is two RNS-flexible hardware accelerators for the ECSM on FPGA. The BE operation, either HBE [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF] or KBE [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF], is demonstrated to be flexible. In other words, for a given size of finite field, each of the two BEs can be implemented using a flexible quantity of hardware resources. An architecture is derived for each of the flexible HBE and KBE. The number of PCs in each architecture is flexible. The two BEs are implemented on FPGA with HLS for various numbers of PCs ranging between the divisors of the number of VCs. Implementation solutions show

INTRODUCTION

that when the number of used PCs increases from q to kq with k > 1, the solution time decreases with a factor less than k, regardless of the BE. This observation results from the constancy of the number of wait cycles between pipelined loops independently of the number of used PCs. The solutions with the best area vs. time trade-o s are obtained with implementations using a few PCs. HBE solutions remain faster with better area vs. time trade-o s than KBE ones.

The new flexible architectures are then used to implement two flexible ECSMs, one using HBE [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF] and the other KBE [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF]. These flexible ECSM implementations use adaptable quantities of hardware resources. The used quantities of hardware resources depend on the number of PCs chosen (at design time) for the RNS implementation of the ECSMs. Similarly to the flexible BEs, our flexible ECSM solution time decreases with a factor less than k when the number of used PCs increases from q to kq, regardless of the BE in use. Again, implementations using a few PCs present the best solutions in area vs. time trade-o s. Also, the ECSM solutions using HBE are faster and present better area vs. time trade-o s than the ones using KBE. Last, though comparable in area vs. time trade-o s with the best implementation results from the literature, most of our flexible ECSM solutions are much smaller. Therefore, our flexible ECSM solutions can be implemented on integrated circuits with limited hardware resources. The proposed RNS-flexible architectures can also be used to implement multi-level security hardware accelerators. We plan to submit this contribution in the near future.

The last contribution of this thesis is an auxiliary project started in the early months of the PhD. We studied how to e ciently perform modular multiplications and accumulations (typical operations in RNS implementations of asymmetric cryptosystems) on FPGA using HLS tools. HLS favors fast explorations of di erent parameters for various implementation constraints (for example, loop unrolling). Parameters considered in our study include the size and the shape (arbitrary, specific) of the moduli as well as the type of series (with and without intermediate MR) for the modular operations. The report of this study, presented in [START_REF] Djath | Comparaison d'algorithmes de réduction modulaire en HLS sur FPGA[END_REF] in French, is put in Appendix A.

INTRODUCTION

Outline

This thesis comprises three chapters. In the first chapter, we detail the context of this thesis, namely ECC. The ECSM and computations involved in its computation are also introduced. Besides ECC in the first chapter, we present the RNS and its inherent properties as well as a survey of BEs and RNS MRs. The first and the second contributions of this thesis are respectively presented in the second and the third chapters.

Chapter 1

STATE OF THE ART

Asymmetric Cryptography

Overview of Asymmetric Cryptography

Asymmetric cryptography is based on the idea of publicizing a key. In asymmetric cryptography, each individual possesses two keys: a private key, and a public key usually computed from the private one. The private key is known only by its owner while the public key is revealed.

The safety of revealing the public key without giving information about the private key is associated with the hardness of inverting one-way functions. A function f : x ' ae f (x) is one way if computing f (x) from x is easy while computing x from f (x) is hard. Easy means computing f (x) from x can be performed in polynomial time. Hard means succeeding in computing x from f (x) in polynomial time for all attempting probabilistic algorithms is extremely unlikely. However, proving the hardness of inverting functions is di cult in itself. In practice, functions largely regarded as computationally di cult to invert are used. A practical way to view the hardness: If computing x from f (x) takes considerable amount of time (say, hundreds of years) with the best known algorithms and a huge computation power, then the function f is largely regarded as hard to invert.

In asymmetric cryptography, the hardness should only exists for an eavesdropper. An authorized individual should be able to e ciently compute x from f (x). This ability is usually provided by a trap door that the authorized individual possesses. For instance, the private key of the authorized individual is used as the trap door in an asymmetric cryptosystem.

Applications of asymmetric cryptography include key exchange [START_REF] Di | New directions in cryptography[END_REF] and digital signature [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF][START_REF]A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF]. Applications of asymmetric cryptography are used in many practical contexts such as in establishing secure communications with an e-commerce website or in authenticating to a server.

STATE OF THE ART

Di e-Hellman key-exchange protocol and the RSA cryptosystem, two notable advancements in asymmetric cryptography, are presented in the following subsections. Elliptic curve cryptography (ECC) is then described.

Di e-Hellman Key-Exchange Protocol [DH76]

The safety of the Di e-Hellman key-exchange protocol [START_REF] Di | New directions in cryptography[END_REF] is based on the assumption that the discrete logarithm problem (DLP) in finite field is computationally di cult for well chosen parameters. The parameters to consider include, among others the size of the field, and tailored properties against known attacks such as the Pohlig-Hellman attack [START_REF] Pohlig | An improved algorithm for computing logarithms over GF(p) and its cryptographic significance[END_REF]. Current recommended sizes are a few thousands bits (say, 2048 or 3072 bits); see for example [START_REF]Digital signature standard (DSS)[END_REF].

Let p be a prime, g be a primitive element of the finite field F p . The DLP can be stated: Knowing n = g x mod p, find x. The function f : x ' ae n = g x mod p can be viewed as a one-way function associated with the DLP. Two individuals, Alice and Bob, want to share a common key over a network. The Di e-Hellman key-exchange protocol [START_REF] Di | New directions in cryptography[END_REF] is described in Algorithm 1. At the end of the exchange Alice and Bob have a common secret key

K AB = K BA since n x A B mod p = n x B
A mod p = g x A x B mod p. An eavesdropper has to solve the DLP if he/she intends to recover the secret operands x A or x B from n A or n B . Besides, computing the shared key K AB from n A or n B without knowledge of respectively x B or x A involves solving the DLP.

Algorithm 1: Di e-Hellman key-exchange protocol [START_REF] Di | New directions in cryptography[END_REF].

Input: p a prime, and g a primitive element of F p Output: Alice and Bob have a common key K AB = K BA = g x A x B mod p 1 Alice chooses a random number x A oe F p and keeps it secret 2 Alice computes n A = g x A mod p and sends it to Bob 3 Bob chooses a random number x B oe F p and keeps it secret 4 Bob computes n B = g x B mod p and sends it to Alice 5 Alice receives n B and computes

K AB = n x A B mod p 6 Bob receives n A and computes K BA = n x B A mod p 1.1. ASYMMETRIC CRYPTOGRAPHY

RSA Cryptosystem [RSA78]

The RSA cryptosystem [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF] was the first published work allowing two individuals to exchange a message over a network using a pair of keys (private and public). In RSA, the safety of keeping secret the private key in spite of revealing the public key relies on the considered di culty of factoring large integers.

The problem of the factorization can be put: Knowing an integer n, factorize n. The function f : (p, q) ' ae n = p ◊ q can be viewed as a one-way function associated with the problem of the factorization.

Computing n is straightforward (through a multiplication algorithm) but computing p and q from n requires considerably more e ort. In practice, an attacker has to factorize a number n of a few thousands bits. For example, the recommended sizes for the RSA modulus n in [START_REF]Digital signature standard (DSS)[END_REF] are 1024, 2048 and 3072 bits.

Alice wants to generate her private key (d, n) and her public key (e, n). The simplified procedure is presented in Algorithm 2. For an eavesdropper, computing the decryption key d from the encryption key e requires to factor n.

Bob wants to send a message (also called plaintext) m, 0 AE m AE n ≠ 1 to Alice. Bob gets the public key (e, n) of Alice. The encryption and decryption procedures are described in Algorithm 3.

At the end, Alice gets m since c d mod n = (m e ) d mod n = m. An eavesdropper who gets the ciphertext c has to solve the following problem: Find the eth root of c mod n. This problem is also considered to be computationally di cult. By assumption, the eavesdropper does not possess the decryption key d of Alice. Strictly speaking, an eavesdropper able to solve one of the factorization problem and the eth root mod n problem can recover the plaintext m.

Algorithm 2: Private-and public-key generation in RSA [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF].

Output: private key (d, n) and public key (e, n) 1 Alice chooses two random large primes p and q and computes n = pq 2 Alice chooses a random large integer d coprime with (p ≠ 1)(q ≠ 1) 3 Alice computes e, the inverse of d mod (p ≠ 1)(q ≠ 1) 4 Alice keeps (d, n) secret and publicizes (e, n)

Elliptic Curve Cryptography Elliptic Curves

Part "Elliptic Curves" of the current subsection is a synthesis of basic concepts on elliptic curves from [START_REF] Husemöller | Elliptic Curves[END_REF][START_REF] Cohen | Handbook of Elliptic and Hyperelliptic Curve Cryptography[END_REF][START_REF] Silverman | The Arithmetic of Elliptic Curves[END_REF] useful in the work presented in this thesis.

An elliptic curve is a nonsingular cubic curve along with a stated base point. In this thesis the following simplified definition is considered, though restrictive on the characteristic of the underlying field of the curve.

Definition 1 (Elliptic Curve). Let K be a field of characteristic " = 2, 3. An elliptic curve E K defined over K is the set of elements (x, y) oe K 2 satisfying the equation

E K : y 2 = x 3 + ax + b (1.1)
where a, b oe K are such that ≠16(4a 3 + 27b 2 ) " = 0.

The quantity = ≠16(4a 3 + 27b 2 ) is the discriminant of Equation 1.1 and " = 0 conveys the nonsingularity of the curve E K . The elements of the elliptic curve E K are called points. Figure 1.1 depicts the points of an elliptic curve defined over the finite fields F 1021 and F 16381 .

Equation 1.1 is the short Weierstraß equation of an elliptic curve. The generalized Weierstraß equation of an elliptic curve defined over a field of arbitrary characteristic can be found in [START_REF] Husemöller | Elliptic Curves[END_REF][START_REF] Cohen | Handbook of Elliptic and Hyperelliptic Curve Cryptography[END_REF][START_REF] Silverman | The Arithmetic of Elliptic Curves[END_REF], and is presented in Appendix B.

Two points Q and Q Õ of an elliptic curve E K can be added by drawing a line (QQ Õ ) through them and taking the symmetric (in relation to the x-axis) of the third point of intersection between the line (QQ Õ ) and the curve E K . The point addition of Q and Q Õ is denoted Q+Q Õ . The addition of Q and Q is referred to as point doubling and denoted [2]Q. The construction of the point [2]Q is similar to that of the point Q+Q Õ , the tangent at Q to the curve replacing the line (QQ Õ ). Constructions of point addition and doubling are illustrated on the curve E R :

1.1. ASYMMETRIC CRYPTOGRAPHY E F 1021 : y 2 = x 3 ≠ 3x + 3. E F 16381 : y 2 = x 3 ≠ 3x + 3.
y 2 = x 3 ≠ 3x + 3 in Figure 1.2. Point addition Q+Q Õ and point doubling [2]Q are also obtained through formulas Y _ ] _ [ x Q+Q Õ = ⁄ 2 ≠ x Q ≠ x Q Õ y Q+Q Õ = ⁄(x Q ≠ x Q+Q Õ ) ≠ y Q and Y _ ] _ [ x [2]Q = µ 2 ≠ 2x Q y [2]Q = µ(x Q ≠ x [2]Q ) ≠ y Q (1.2) where ⁄ = y Q ≠ y Q Õ x Q ≠ x Q Õ and µ = 3x 2 Q + a 2y Q .
Formulas in Equation 1.2 include divisions (for the introduced values 1 ⁄ and µ). In general, divisions are di cult to perform. A solution to avoid computing the inherent divisions of Equation 1.2 is to homogenize the equation of the curve E K , that is, to express it in projectives coordinates. By substituting x = X/Z and y = Y/Z into Equation 1.1 we obtain

E K : Y 2 Z = X 3 + aXZ 2 + bZ 3 . (1.3)
Using projective coordinates to express the formulas in Equation 1.2 yields

Y _ _ _ _ ] _ _ _ _ [ X Q+Q Õ = BC Y Q+Q Õ = A(X Q Z Q Õ B 2 ≠ C) ≠ Y Q Z Q Õ B 3 Z Q+Q Õ = Z Q Z Q Õ B 3 and Y _ _ _ _ ] _ _ _ _ [ X [2]Q = 2F H Y [2]Q = E(4G ≠ H) ≠ 8Y 2 Q F 2 Z [2]Q = 8F 3
(1.4)

1. The values ⁄ and µ are the slopes of the line (QQ Õ ) and the tangent at Q to the curve E K respectively.

STATE OF THE ART

Point addition on the curve

E R : y 2 = x 3 ≠ 3x + 3.
Point doubling on the curve where

E R : y 2 = x 3 ≠ 3x + 3.
A = Y Q Õ Z Q ≠ Y Q Z Q Õ , B = X Q Õ Z Q ≠ X Q Z Q Õ , C = Z Q Z Q Õ A 2 ≠ (X Q Õ Z Q + X Q Z Q Õ )B 2 ; E = 3X 2 Q + aZ 2 Q , F = Y Q Z Q , G = X Q Y 2 Q Z Q , H = E 2 ≠ 8G.
Besides projective coordinates, there exist other systems of coordinates wherein the computation of the inherent divisions of Equation 1.2 can be avoided. The reader is referred to [START_REF] Cohen | Handbook of Elliptic and Hyperelliptic Curve Cryptography[END_REF] for a presentation of some of these systems of coordinates and the formulas of point addition and doubling within them.

The point O = (0 : 1 : 0) is the base point (also called point at infinity) expressed in projective coordinates.

Lemma 1 (Group Law on Elliptic Curve). Let E K be an elliptic curve defined over a field K. The points of E K provided with the operation + is a group of neutral element the point O.

A proof of Lemma 1 can be found in [START_REF] Silverman | The Arithmetic of Elliptic Curves[END_REF].

Definition 2 (Elliptic Curve Scalar Multiplication). Let E K be an elliptic curve 1.1. ASYMMETRIC CRYPTOGRAPHY defined over a field K. The elliptic curve scalar multiplication (ECSM) is the function

f : (Z + \{0}) ◊ E K ae E K (u, Q) ' ae [u]Q = Q + Q + • • • + Q ¸˚˙ű terms .
Definition 2 of the ECSM is generalized to all u oe Z by writing

[u]Q = Y _ _ _ _ ] _ _ _ _ [ O if u = 0 Q + Q + • • • + Q if u > 0 (≠Q) + (≠Q) + • • • + (≠Q) otherwise,
where the point ≠Q is the symmetric of the point Q in relation to the x-axis.

In the following, ECC is presented through the lens of the elliptic curve discrete logarithm problem (ECDLP).

Elliptic Curve Discrete Logarithm Problem

Let E Fq be an elliptic curve defined over a finite field F q , and Q a point of E Fq of order v. The ECDLP is stated: Knowing the point [u]Q of the curve E Fq (and the point Q), find the unique scalar u, 0 AE u AE v ≠ 1 by which the point Q is multiplied. The function

f Q : u ' ae [u]Q
can be viewed as a one-way function associated with the ECDLP. Computing [u]Q from u is easily performed using one of the various state-of-the-art algorithms (for example double and add in [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]) while computing u from [u]Q is di cult for well-chosen parameters. The involved parameters are the underlying finite field of the curve and the curve itself.

When choosing the underlying finite field F q of the curve E Fq the aim is to have a field on which the arithmetic is e cient while the curve still ensures a good level of security (meaning the ECDLP should be hard to solve). Several types of fields (prime fields, fields of prime characteristic, binary fields, etc.) have been studied and some fields have been standardized; see, for example the ones in [ndlsdsd11] (from ANSSI2 ) and in [START_REF]Digital signature standard (DSS)[END_REF] (from NIST3 ). The reader should bear in mind that regardless of the type of fields from which is selected the underlying finite field F q , the cardinality q of F q should never be small. The theorem of Hasse says that the cardinality ˘EFq of the curve is bounded as follows:

q + 1 ≠ 2 Ô q AE ˘EFq AE q + 1 + 2 Ô q.
(1.5)

If q is small, then ˘EFq is small. The consequence is that the ECDLP on such a curve E Fq can be solved through exhaustive search attack.

Choosing the curve is tricky and two types of attacks on the ECDLP have to be considered when doing so. The first type consists of attacks on arbitrary curves such as the Pohlig-Hellman attack [START_REF] Pohlig | An improved algorithm for computing logarithms over GF(p) and its cryptographic significance[END_REF] and the Pollard Rho method [START_REF] Pollard | Monte Carlo methods for index computation (mod p)[END_REF]. The Pohlig-Hellman attack is performed by computing u modulo each prime factor (raised to its maximum power within the prime decomposition) of ˘EFq and recovering u through the Chinese remainder theorem (CRT). The u-modulo-prime-factor step becomes easy if the mentioned prime factors are small. Choosing the curve such that v, the order of the point Q and hence a factor of ˘EFq , be a large prime prevents this attack. The Pollard rho method can be viewed as a randomized equivalent of the baby-step giant-step method. Despite its e ectiveness, the Pollard Rho method still runs in exponential time.

The second type of attacks is about attacks on specific curves. Examples of these attacks are the Menezes-Okamoto-Vanstone attack [START_REF] Menezes | Reducing elliptic curve logarithms to logarithms in a finite field[END_REF] and the Frey-Rück attack [START_REF] Frey | A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves[END_REF] which exploit the fact that, under some circumstances, the ECDLP can be reduced to the DLP in some extension field F q l (of the underlying field F q of the curve). The DLP in the extension field can be solved if l is small. Examples of curves subject to these attacks are supersingular curves and curves E Fq of cardinality q ≠ 1. These attacks are prevented by choosing the curves such that v is not a factor of q l ≠ 1 for all small l. Menezes [START_REF] Menezes | Evaluation of security level of cryptography: The elliptic curve discrete logarithm problem (ECDLP)[END_REF] suggested that, when v > 2 160 , checking this condition for 1 AE l AE 20 is enough. Another example of attacks on specific curve is the attack on curves E Fp of cardinality p for which authors of [START_REF] Semaev | Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p[END_REF] and [START_REF] Satoh | Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves[END_REF] prove that the ECDLP can be solved in polynomial time. This attack is prevented by ensuring the cardinality of the curve is not p when choosing the curve.

The idea of ECC, proposed in [START_REF] Miller | Use of elliptic curve in cryptography[END_REF][START_REF] Koblitz | Elliptic curve cryptosystems[END_REF], is to use asymmetric cryptographic applications based on the ECDLP. The preference of the ECDLP to the DLP (in finite field) is motivated by the fact that there is no known algorithm solving the ECDLP for general cases in sub-exponential time, contrary to the DLP in finite field (for example, the index calculus). An inherent consequence is that the cryptographic operands in ECC are smaller than the ones in asymmetric cryptographic applications based on the DLP for the same level of security. For example, the elliptic curve digital signature algorithm (ECDSA4 ) with public-key size of 256 bits is considered providing roughly the same level of security (approximately 128 bits of security) as the digital signature algorithm (DSA5 ) with public-key size of at least 2048 bits; see [START_REF]Digital signature standard (DSS)[END_REF] for recommendations on parameter sizes for signature algorithms based on the DLP and the ECDLP.

Protocols of asymmetric cryptographic applications (key exchange, digital signature, public-key encryption) based on the DLP are adaptable to elliptic curves. As an example, Algorithm 4 describes the elliptic curve version (ECDH) [START_REF] Miller | Use of elliptic curve in cryptography[END_REF] of the Di e-Hellman key-exchange protocol presented in Subsection 1.1.1. An eavesdropper who gets [u A ]Q or [u B ]Q has to solve the ECDLP to recover the (secret) scalars u A or u B . Moreover, solving the ECDLP is a crucial part of forging the agreed key

[u A u B ]Q from [u A ]Q or [u B ]Q without knowledge of u A or u B .
Algorithm 4: Elliptic curve version of the Di e-Hellman key-exchange protocol [START_REF] Miller | Use of elliptic curve in cryptography[END_REF].

Input: E Fq is an elliptic curve defined over F q , and Q a point of E Fq of order v Output: Alice and Bob have a common key

[u A u B ]Q = [u A ]([u B ]Q) = [u B ]([u A ]Q) = [u B u A ]Q 1 Alice chooses a random number u A , 0 AE u A AE v ≠ 1
]Q and computes [u A ]([u B ]Q) = [u A u B ]Q 6 Bob receives [u A ]Q and computes [u B ]([u A ]Q) = [u B u A ]Q
In the remaining of this thesis we assume the curve is defined over a prime field F p . Our assumption is motivated by the fact that in practice, curves over prime fields have proven to be more resistant (to attacks) than curves defined over other fields. Among others, curves defined over binary fields have been subject to attacks; see, for example [START_REF] Gaudry | Constructive and destructive facets of weil descent on elliptic curves[END_REF][START_REF] Galbraith | Extending the GHS weil descent attack[END_REF][START_REF] Hess | The GHS attack revisited[END_REF][START_REF] Menezes | Weak fields for ECC[END_REF].

Computations Involved in an ECSM

The ECSM results from several point doublings and additions (operations in E Fq ), which in turn are obtained through operations in the finite field F p . This hierarchical description is presented in Figure 1.3. There exist several algorithms in the literature to compute the ECSM. The elementary double-and-add algorithm (see, for example [HMV04, p. 97]) is presented in Algorithm 5. The double-and-add algorithm is an elliptic curve adaptation of the square-and-multiply algorithm for exponentiation (for example x 5 = ((1 2 ◊ x) 2 ) 2 ◊ x). Other algorithms for exponentiation such as the sliding window method have also been adapted to elliptic curves. The reader is referred to [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF] for some of these algorithms.

+, , ⇥, 1 DBL, ADD [u]Q Computations in F p Computations in E Fp
Algorithm 6 presents the Montgomery ladder [START_REF] Montgomery | Speeding the pollard and elliptic curve methods of factorization[END_REF] which was initially proposed for curves of equations of the form by 2 = x 3 + ax 2 + x. Thanks to [START_REF] Brier | Weierstraß elliptic curves and side-channel attacks[END_REF][START_REF] Izu | A fast parallel elliptic curve multiplication resistant against side channel attacks[END_REF], the use of this algorithm has been extended to curves of equation in short Weierstraß form. The use of Algorithm 6 presents two major advantages. First, the Y -coordinate (in projective Algorithm 5: Double-and-add algorithm (see, for example [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]).

Input: Q a point of the elliptic curve E Fp u an integer written in binary representation as u s≠1 u s≠2 ...u 0 Output: R =

[u]Q 1 R Ω O 2 for i Ω s ≠ 1 to 0 do 3 R Ω [2]R 4 if u i = 1 then 5 R Ω R + Q 6 return R 36 1.1. ASYMMETRIC CRYPTOGRAPHY
Algorithm 6: Montgomery ladder algorithm [START_REF] Montgomery | Speeding the pollard and elliptic curve methods of factorization[END_REF].

Input: Q a point of the elliptic curve E Fp u an integer written in binary representation as u s≠1 u s≠2 ...u 0 Output:

Q 1 = [u]Q 1 Q 1 Ω O; Q 2 Ω Q 2 for i Ω s ≠ 1 to 0 do 3 if u i = 0 then 4 Q 1 Ω [2]Q 1 ; Q 2 Ω Q 1 + Q 2 5 else 6 Q 2 Ω [2]Q 2 ; Q 1 Ω Q 1 + Q 2 7 return Q 1
system of coordinates) does not need to be computed during the ECSM. Therefore, the cost of the algorithm is reduced. Note that the Y -coordinate can be recovered at the end of the algorithm if necessary. Second, regardless of the bit of the scalar u, a point doubling and a point addition are performed. In other words, the number, the type and the order of operations are the same regardless of the value of the bit of u. This constancy of the number, the type and the order of operations per bit of u constitutes an advantage in terms of protection against some side-channel attacks such as simple power analysis (SPA).

Point doublings and additions are computed through formulas elaborated depending on the parameters of the curve (underlying field, curve equation) and the system of coordinates in use. The reader is referred to [START_REF] Cohen | Handbook of Elliptic and Hyperelliptic Curve Cryptography[END_REF] for some of these formulas. Regardless of the chosen formulas, they involve operations in F p . Therefore, using an e cient arithmetic in F p is crucial in computing the ECSM.

In the work presented in this thesis, we choose to use the residue number system (RNS) to perform operations in F p because RNS provides several e ciency advantages described in Subsection 1.3.2. The hierarchical description of ECSM computations in Figure 1.3 is extended by adding an extra layer at its basis; see Figure 1.4. The contributions of this thesis reside in this extra layer about computations in F p using RNS.

The existence of operations in F p implies a need for e cient modular reductions (MRs). Some MR algorithms from the literature are presented before delving into RNS.

Modular Reduction

Computations of point doublings and additions, useful in ECSM computations involve numerous MRs since operands are in finite fields. For example, over a finite field F p of 256-bit elements, one ECSM requires a few thousands mod p reductions. Therefore, it is crucial to ensure MRs are e cient. In this section some MR algorithms from the literature are presented.

Montgomery Reduction

Montgomery [START_REF] Montgomery | Modular multiplication without trial division[END_REF] introduces a MR algorithm that avoids computing the costly naive division. The idea is to use an auxiliary number r by which the MR and the division are straightforward. For example, in binary representation, mod 2 l reduction and (integer) division by 2 l are respectively performed by selecting the l least significant bits (LSBs) and by taking all the bits except these l LSBs of the considered numbers. The MR idea is described in Algorithm 7. Note that the output of the algorithm on input x is xr ≠1 mod p and not x mod p.

Besides its e ciency, Algorithm 7 is consistent with multiplications and additions/subtractions. Indeed,

xr ≠1 ◊ x Õ r ≠1 = (xx Õ r ≠1 )r ≠1 mod p and xr ≠1 + x Õ r ≠1 = (x + x Õ )r ≠1 mod p.
In other words, there is a correspondence between the product and the sum/di erence of operands in the input space on one hand, and the product and the sum/di erence of operands in the output space on the other hand. Owing to this correspondence in

≠ pp Õ = 1 Output: y = xr ≠1 mod p < 2p 1 z Ω (x mod r)p Õ mod r 2 t Ω x + zp 3 y Ω t/r
addition to its e ciency, Algorithm 7 is suitable for protocols of asymmetric cryptography applications where numerous modular multiplications (MMs) and additions/subtractions are needed, in particular for protocols of ECC applications. If successive MMs have to be performed, for example in the case of a modular exponentiation or a progressive modular accumulation of products, another way to exploit this correspondence is to repeatedly input the products in the form (xr mod p)(x Õ r mod p) instead of xx Õ to Algorithm 7. The repeated outputs will be of the form xx Õ r mod p, that is, in the same space as the input factors. Hence, the change of space is avoided between successive MMs. In such cases, the changes of spaces only happen before the start (x ae xr mod p) and after the end (xr mod p ae x) of the successive MMs.

Another remark on Algorithm 7 is the range of its output: If x is inputted, the output is xr ≠1 mod p < 2p. In successive MMs, an intermediate product x may grow in such a way that x no longer verifies the input condition x < pr for the next run of Algorithm 7. Usually, the auxiliary number r is adjusted beforehand to prevent this situation for happening. A typical example: Suppose a modular exponentiation on elements of F p is being performed using Algorithm 7 for the reduction, with p < r < 2p. During the modular exponentiation, it may occur that an output y 1 of Algorithm 7 is such that p < y 1 < 2p. In such a case and for an element y 2 oe F p , the product x = y 1 ◊ y 2 cannot be guaranteed to be less than pr, which is the input condition of Algorithm 7. For our typical example, taking (beforehand) r such that r > 2p ensures that this input condition remains true during the whole modular exponentiation.

Barrett Reduction

Barrett [START_REF] Barrett | Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor[END_REF] proposes an algorithm to perform the modular reduction by approximating the quotient of the integer division. Let p and x < p 2 be numbers. The aim is to compute

STATE OF THE ART

x mod p. The quotient of the integer division Âx/pÊ is approximated by

E 7 x 2 w 8 p Õ 2 w F , where p Õ = E 2 2w p F . Since x mod p = x ≠ p E x p F , the idea is to compute x = x ≠ p E 7 x 2 w 8 p Õ 2 w F .
(1.6)

The computed value x < 3p [START_REF] Barrett | Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor[END_REF]. The value x mod p is recovered from x through at most two subtractions of p.

On Pseudo-Mersenne Numbers

Numbers of the form p = 2 w ≠ c where 0 AE c < 2 w/2 are said to be pseudo-Mersenne, in reference to Mersenne numbers (of the form p = 2 w ≠ 1). Reductions modulo pseudo-Mersenne numbers are e ciently performed. The main idea is to exploit the form of these numbers and use bit selection and multiplication by a small constant to perform the reduction. Let x be a number of binary size 2w (say, the product of two numbers of size w). Start by remarking that x can be written

x = x 1 ◊ 2 w + x 0 , (1.7)
where x 0 and x 1 are less than 2 w . Note also that 2 w © c (mod p). Therefore,

x mod p © x 1 c + x 0 (mod p).
(1.8)

The number x = x 1 c + x 0 is of at most 3n/2 bits and can be rewritten similarly to Equation 1.7 into x = x1 ◊ 2 w + x0 .

(1.9)

The binary size of x0 is w while that of x1 is at most w/2. From the congruence at Equation 1.8 and the equality at Equation 1.9, is deduced

x mod p © x1 c + x0 (mod p).
(1.10)

RESIDUE NUMBER SYSTEM

The number x1 c+ x0 is of at most n+1 bits. The possible last reduction modp is performed by at most one subtraction of p.

In the general case where the target operations are in arbitrary fields, this algorithm cannot be used for reductions in these fields.

Residue Number System

Overview of the Residue Number System

This subsection presents a simplified description of RNS, first proposed in [START_REF] Valach | P evod ísel ze soustavy zbytkov˝ch t íd do polyadické soustavy zm nou m itka periody (the translation of numbers from the system of residual classes to a polyadic system by change of scale of period)[END_REF][START_REF] Garner | The residue number system[END_REF]. The reader interested in more details about RNS is referred to [START_REF] Szabo | Residue arithmetic and its applications to computer technology[END_REF]. The concept of congruence will be used throughout the remaining of this thesis, and therefore introduced at the start.

Definition 3 (Congruence). Let m > 0 be an integer. Two integers x and y are congruent modulo m if x ≠ y is a multiple of m. We write

x © y (mod m) (1.11)
and we say that y is the residue of x modulo m. The integer m is called the modulus.

This definition still holds when the modulus m < 0. In the remaining of this document all the moduli are assumed positive for convenience.

The Residue Number System [Val56, Gar59]

In RNS, numbers are represented by their residues over a set M = {m 1 , . . . , m n } of moduli m i . The moduli m i are selected pairwise coprime and the set M they compose is called an RNS base.

Example 1. To represent the number 117 in the RNS base {5, 6, 7}, we compute the residues of 117 modulo 5, 6 and 7 respectively.

117 © 2 (mod 5) 117 © 3 (mod 6) 117 © 5 (mod 7)

The tuple (2, 3, 5) is the RNS representation of the number 117 in the base {5, 6, 7}.

STATE OF THE ART

In practice, the sizes of the moduli used for RNS implementations of ECC applications are typical sizes of DSP slices or machines words, that is, in [10, 64] bits.

RNS can be viewed as a number system where large numbers (a few hundreds of bits) are transformed into a set of small numbers (a few dozen bits). Computations on large numbers are then replaced by computations on small numbers, the latter being usually performed in parallel.

For RNS to be well defined as a number system it is crucial that the moduli m i (elements of the RNS base) be pairwise coprime. By well defined we mean there is a oneon-one correspondence between numbers in [0, r n i=1 m i ≠ 1] and their RNS representation. Otherwise, some representations will not correspond to any number in [0,

r n i=1 m i ≠ 1].
Moreover, in such case at least two (more precisely, gcd(m 1 , . . . , m n )) numbers will have the same RNS representation.

Example 2. Let suppose in Example 1 that 5, 6, and 8 were chosen as moduli. These moduli are not pairwise coprime since gcd(6, 8) = 2. The representation (1, 4, 3) does not correspond to any number in [0, 239]. Besides, the numbers 117 and 237 have the same representation (2, 3, 5).

We ease the notation of the congruence by writing y = |x| m to say that x © y (mod m). Definition 4. Let M = {m 1 , . . . , m n } be an RNS base. A number x is represented in RNS according to the base M by the tuple

(x m 1 , . . . , x mn ),
where

x m i = |x| m i for i = 1, . . . , n.
Whenever there is no ambiguity on the RNS base in which x is represented, the notation of the RNS representation of x is further simplified by simply writing (x 1 , . . . , x n ).

Arithmetic Operations in RNS

Let M = {m 1 , . . . , m n } be an RNS base and M = r n i=1 m i . Let ù stands for any of the operations ◊, + or ≠ with operands in RNS representation. Let x, y be two integers represented in RNS according to the base M by (x 1 , . . . , x n ) and (y 1 , . . . , y n ) respectively.

RESIDUE NUMBER SYSTEM

Let also assume the result of multiplication, addition and subtraction of x and y is less than M . The RNS computation of the multiplication, addition and subtraction between x and y is performed by

(x 1 , . . . , x n ) ù (y 1 , . . . , y n ) = (|x 1 ù y 1 | m 1 , . . . , |x n ù y n | mn ).
(1.12)

If y is coprime with M , then the notation ù is extended to include division and Equation 1.12 still holds.

Example 3. The numbers 117 and 68 are represented in RNS according to the base {5, 6, 7} by (2, 3, 5) and (3, 2, 5) respectively. The number 185, sum of 117 and 68, is represented by

(|2 + 3| 5 , |3 + 2| 6 , |5 + 5| 7 ) = (0, 5, 3).

Conversion from Positional Number System to RNS and Vice Versa

Knowing how to convert numbers from positional system to RNS and vice versa is justified by the fact that the use of positional systems is widespread. For instance, most digital systems use the weighted number system of radix 2. A case where the conversions become handy is when one of two (or more) individuals in a network uses the RNS while the other(s) a positional system. An RNS-to-positional or the reverse conversion has to be performed for each exchange.

The conversion of a number from positional representation to RNS is performed by computing the residues of this number over the moduli of the RNS base. The reader can recognize this method in Example 1.

A number represented in RNS is converted into a positional system by using the Chinese remainder theorem (CRT) presented in Theorem 2.

Theorem 2 (Chinese Remainder Theorem). Let m 1 , . . . , m n be n positive integers that are pairwise coprime. The system of congruences

Y _ _ _ _ _ _ _ _ ] _ _ _ _ _ _ _ _ [ x 1 = |x| m 1 x 2 = |x| m 2 . . . x n = |x| mn (1.13) has a unique solution modulo M = n Ÿ i=1 m i .

STATE OF THE ART

This solution is given by

x = - - - - - n ÿ i=1 |x i M i ≠1 | m i M i - - - - - M , (1.14)
where

M i = M m i for i = 1, . . . , n.
Theorem 2 about the CRT is proven in Appendix C.

The CRT is also used to perform base extensions, that is, conversions from one RNS base to another; see Subsection 1.3.3.

RNS Inherent Properties and Complexity Measurement

RNS Inherent Properties

In RNS, the basic operations multiplication, addition and subtraction are held independently on each modulus of the RNS base. This independence means the mentioned computations are carry-free between the channels. Consequently, multiplications, additions and subtractions can be performed in parallel.

RNS is a nonpositional representation system, that means, the value of a number does not change if its residues in a given base are reordered di erently. We emphasize that a reordering of the residues, if done, must be followed by a similar reordering in the used RNS base. For example, (2, 3, 5) in the RNS base {5, 6, 7} and (3, 2, 5) in the (same but reordered) RNS base {6, 5, 7} represent the exact same number 117. However, in the RNS base {5, 6, 7} the tuple (3, 2, 5) represents the number 68.

The major drawback of RNS is the di culty to perform position-related operations such as comparisons, divisions by integers not coprime with the range M of the RNS base, and MRs. This di culty results from that of evaluating the order of magnitude of operands in nonpositional representation systems. For example, comparisons are di cult because we cannot just rely on the position of digits (as in a usual positional system) of two (or more) integers in RNS to compare them. An alternative is to convert the to-becompared integers into a positional system such as mixed-radix system (MRS) before the comparison. These conversions are costly as we see in Subsection 1.3.3. Exact divisions by integers not coprime with M are also di cult in RNS for the same reason. Exact divisions by such integers might require to convert those integers to their positional representation before performing the divisions. As mentioned, those conversions are costly. Another way to perform divisions the reader might think of is to subtract

1.3. RESIDUE NUMBER SYSTEM
the divisor iteratively. However this method requires a comparison per subtraction to determine the end of the division process. As explained, the comparisons are di cult.

Another di cult operation in RNS is the mod p reduction, where p is a (large) integer not coprime with the range M of the RNS base. Since operations in protocols of asymmetric cryptographic applications are usually performed in rings or fields, the mod p reduction is a crucial operation. Some ways to perform MRs from the literature are presented in Section 1.2.

How Complexity is Measured?

Deciding on a complexity unit is always tricky, and even more when hardware aspects are involved in addition to theoretical ones. It is critical to choose the metric of the input size and define what the basic operations are. The input size is the number of residues, which is the same as the number of moduli of the considered RNS base. The size itself of the moduli is almost hidden in the complexity. In hardware implementations, it is common to choose the size of the moduli such that the residues (operands of the various RNS computations) fit in the multipliers embedded in the DSP slices 6 . We consider our basic operations to be modular multiplications, additions and subtractions, the modulus being an element of the RNS base. For a historical interest, we point out that Szabo and Tanaka [ST67, pp. 140-150] reported mixed-radix conversion as a basic operation besides multiplication, addition and subtraction. The reason behind including mixed-radix conversion is that the latter is used in sign-determination related operations such as relative-magnitude determination. In most asymmetric cryptography applications and particularly in ECC applications, we are not interested in sign determination.

Complexity-unit candidates for asymmetric cryptosystems in RNS are elementary modular multiplication (EMM) and elementary modular addition (EMA). An EMM and an EMA are respectively a modular multiplication and a modular addition/subtraction in a channel. The EMM is more significant than the EMA within the cost of RNS computations because the elementary multiplication (without the modular reduction step) usually costs more than the elementary addition while the modular reduction algorithm costs the same in EMM as in EMA at worst. Besides, additions are usually performed by adders/accumulators located next to the multipliers embedded in the DSP slices. Examples of references where the complexity is expressed in terms of the number of EMMs include 6. DSP slices stand for digital signal processing slices.

STATE OF THE ART

[KKSS00, BDK01, GLP + 12, BT15].

Base Extension

A base extension (BE) is a conversion of a number x from its representation in an RNS base M = {m 1 , . . . , m n } to its representation in another RNS base

M Õ = {m Õ 1 , . . . , m Õ n Õ }. The notation BE MaeM Õ (x) indicates the computation of the residues (x m Õ 1 , . . . , x m Õ n Õ ) of a number x in M Õ , knowing the residues (x m 1 , . . . , x mn ) of x in M.
An intuitive approach would be to convert x from the RNS base M to its positional representation using the CRT (formula given in Equation 1.14), then convert x from its positional representation to the RNS base M Õ . However, this approach is troublesome owing to the variable sizes of the operands. Therefore, the conversion to positional representation is usually avoided.

Base extensions (BEs) from the literature can be classified in two major types: the ones that go through a representation in MRS, therefore requiring an RNS-to-MRS conversion, and the others that use the CRT formula (without converting the number into a positional representation). These two types of base extension are presented hereafter.

Base Extensions Requiring an RNS-to-MRS Conversion

Definition 5 (Mixed-radix system; from [ST67, pp. 41-47]). Let M = {m 1 , . . . , m n } be a set of numbers not necessarily coprime. A number x is said to be represented in MRS according to the radices

m i if x = x n n≠1 Ÿ i=1 m i + x n≠1 n≠2 Ÿ i=1 m i + • • • + x 2 m 1 + x 1 (1.15)
The tuple (x 1 , . . . , x n ) is the MRS representation of x in the MRS base M.

BEs using an RNS-to-MRS conversion comprise two parts: a conversion of x from the RNS base M to the associated MRS base M, and a conversion of x from the MRS base

M to the RNS base M Õ .
The earliest algorithm converting a number x from RNS to MRS appeared in [START_REF] Valach | P evod ísel ze soustavy zbytkov˝ch t íd do polyadické soustavy zm nou m itka periody (the translation of numbers from the system of residual classes to a polyadic system by change of scale of period)[END_REF] according to [ST67, pp. 41-51], and in [START_REF] Garner | The residue number system[END_REF]. Let M = {m 1 , . . . , m n } be an RNS base (the moduli m i are coprime), and (x 1 , . . . , x n ) be the RNS representation of x in M. Let (x 1 , . . . , x n ) denote the MRS representation of x in M. Their idea of the RNS-to-MRS conversion (that is, (x 1 , . . . , x n ) into (x 1 , . . . , x n )) is described hereafter.

RESIDUE NUMBER SYSTEM

Let start with the MRS representation of x in

M x = x n n≠1 Ÿ i=1 m i + x n≠1 n≠2 Ÿ i=1 m i + • • • + x 3 m 1 m 2 + x 2 m 1 + x 1 .
(1.16)

By reducing modulo m 1 the left and the right side of Equation 1.16 we obtain x 1 = x 1 (since x 1 = |x| m 1 ). Next, substracting x 1 = x 1 from each side of Equation 1.16 and multiplying the consequent results by m 1 ≠1 yield

(x ≠ x 1 )m 1 ≠1 = x n n≠1 Ÿ i=2 m i + x n≠1 n≠2 Ÿ i=2 m i + • • • + x 3 m 2 + x 2 .
(1.17)

By reducing the left and the right side of Equation 1.17 we obtain

x 2 = |(x ≠ x 1 )m 1 ≠1 | m 2 .
This process is repeated until all the MRS digits x i of x are computed. Algorithm 8 summarizes the idea.

Algorithm 8: RNS-to-MRS conversion algorithm [START_REF] Valach | P evod ísel ze soustavy zbytkov˝ch t íd do polyadické soustavy zm nou m itka periody (the translation of numbers from the system of residual classes to a polyadic system by change of scale of period)[END_REF][START_REF] Garner | The residue number system[END_REF].

Input: x 1 , . . . , x n Output: x 1 , . . . , x n 1 Precomputations: |m ≠1 j | m i , for all i, 2 AE i AE n and j, 1 AE j AE i ≠ 1 2 x 1 = x 1 3 for i Ω 2 to n do 4 x i Ω x i 5 for j Ω 1 to i ≠ 1 do 6 x i Ω |(x i ≠ x j )m ≠1 j | m i
The reader can remark that computations in Algorithm 8 are performed mod m i . Therefore, the MRS possesses the advantage over other positional systems that the size of the operands remains the same during the conversion from RNS.

The second part of the BE, namely the conversion of x from the MRS base M to the RNS base M Õ , is equivalent to computing, for all j = 1, . . . , n,

- - - - - x n n≠1 Ÿ i=1 m i + x n≠1 n≠2 Ÿ i=1 m i + • • • + x 2 m 1 + x 1 - - - - - m Õ j .
(1.18)

At least two ways to perfom this conversion exist. One way is reported in [START_REF] Szabo | Residue arithmetic and its applications to computer technology[END_REF] where the authors exemplify the idea with one modulus of M Õ . Let assume this modulus is m Õ 1 . The idea of the conversion of x from M to {m Õ 1 } is to run Algorithm 8 on inputs

STATE OF THE ART

x m 1 , . . . , x mn , 0 (in {m 1 , . . . , m n } fi {m Õ 1 }) while maintaining the same bounds for the loop of Algorithm 8, that is, i from 2 to n. The RNS digit x m Õ 1 is solution of an equation mod m Õ 1 of the first degree as its only unknown variable; the other variables of the equation are the digit in {m Õ 1 } outputted by the run of Algorithm 8 and some precomputations. This method can be used to perform the conversion from M to M Õ by one run of Algorithm 8 on inputs x m 1 , . . . , x mn , 0, . . . , 0 (in {m 1 , . . . , m n }fi{m Õ 1 , . . . , m Õ n }) while the bounds of the loop of Algorithm 8 are kept the same (i from 2 to n). Each RNS digit x m Õ j is solution of an equation of the first degree mod m Õ j as its only unknown variable. However, this method requires the number of simultaneously-running inputs to be equal to the sum of the sizes of the two RNS bases M and M Õ . When targeting hardware implementations, this method leads to a used hardware resources twice the ones needed by the cox-rower architecture [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF] (see below in Part "Base Extension Using the CRT formula") without a gain in time.

Another way to perform the MRS-to-RNS conversion is to compute Equation 1.18 directly. For example, authors of [START_REF] Bajard | Selected RNS bases for modular multiplication[END_REF] proceed this way and prove that the computation at Equation 1.18 can be performed through shifts and additions/substractions if the selected moduli m i and m Õ j are pseudo-Mersenne numbers 2 w ≠ c with c of small Hamming weight. However, their method involves a lot of data dependencies between the channels, and hence hinders the ability to exploit the inherent parallelism of RNS. In the work presented in this thesis, we are interested in preserving as much as possible the inherent parallelism of RNS. Therefore, the base architecture selected for this thesis is the coxrower [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF] (see below in Part "Base Extension Using the CRT formula") because it exploits the inherent parallelism of RNS. In other words, the architectures implemented in the work presented in this thesis are adaptations of the cox-rower architecture.

Overall, the presented BE using the RNS-to-MRS conversion costs n(3n + 1) 2 EMMs.

To summarize, the two notable properties of the BE using conversions through MRS are the fact that the RNS-to-MRS conversion is sequential accross the moduli of M on one hand, and either the need for twice the size of an RNS base in area or the involvement of a lot of data dependencies on the other hand.

Base Extension Using the CRT Formula

Let M = {m 1 , . . . , m n } and M Õ = {m Õ 1 , . . . , m Õ n } be two RNS bases, (x m 1 , . . . , x mn ) and (x m Õ 1 , . . . , x m Õ n ) the RNS representations of a number x in M and M Õ respectively. We

RESIDUE NUMBER SYSTEM

recall the CRT formula:

x = - - - - - n ÿ i=1 |x m i M i ≠1 | m i M i - - - - - M , (1.19)
where

M i = M m i for i = 1, . . . , n.
From Definition 3 of congruence, there is an integer h such that

x = A n ÿ i=1 |x m i M i ≠1 | m i M i B ≠ hM. (1.20)
The main idea of BEs using the CRT is to compute the integer h or its approximation and use the obtained result in the computation of the various x m Õ j by reducing each side of Equation 1.20 modulo m Õ j , for j = 1, . . . , n. The earliest BE using the CRT is proposed in [START_REF] Shenoy | Fast base extension using a redundant modulus in RNS[END_REF]. The idea is to add to M an extra modulus m n+1 Ø n wherein h = |h| m n+1 is computed using the fact that h < n and

|h| m n+1 = - - - - - M ≠1 A n ÿ i=1 |x m i M i ≠1 | m i M i ≠ x B- - - - - m n+1
.

(1.21)

The integer h in Equation 1.20 can also be computed by approximation, in which case there is no need for an extra modulus. Posch and Posch [START_REF] Posch | Base extension using a convolution sum in residue number systems[END_REF] provide an algorithm which computes an approximation of

h = E n ÿ i=1 |x m i M i ≠1 | m i m i F , (1.22)
and introduce for x the bound [0, (1 ≠ ' max )M [ (where ' max π 1) in order for the approximation to be exact. Kawamura et al. [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF] propose to compute

h = E n ÿ i=1 trunc(|x m i M i ≠1 | m i ) 2 w + ‡ F (1.23)
which is an approximation of h, w being the binary size of the moduli m i and ‡ a chosen value to counteract the error in the approximation. The function trunc approximates

|x m i M i ≠1
| m i by its t most significant bits (MSB), t < w, the w ≠ t remaining bits put at 0. Algorithm 9 describes their BE. Under conditions specified in Theorem 1 and Theorem 2 in [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF], the value of h computed in Algorithm 9 is respectively h on one hand, either h or h ≠ 1 on the other hand. In the RNS MR algorithm from [START_REF] Posch | Modulo reduction in residue number systems[END_REF] where two BEs are performed, these theorems help decide on the input value of ‡ to get the correct reduction results.

Algorithm 9: Base extension BE MaeM Õ (x) [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF].

Input: (x m 1 , . . . , x mn ), ‡ Precomp.:

|M ≠1 i | m i , for all i, 1 AE i AE n |M i | m Õ j , for all i, 1 AE i AE n and j, 1 AE j AE n | ≠ M | m Õ j , for all j, 1 AE j AE n Output: (x m Õ 1 , . . . , x m Õ n ) 1 for i Ω 1 to n parallel do 2 ' x m i Ω - - - - - x m i ◊ |M ≠1 i | m i - - - - - m i 3 for i Ω 1 to n do 4 ‡ Ω ‡ + trunc(' xm i ) 2 w 5 h i Ω Â ‡Ê 6 ‡ Ω ‡ ≠ h i 7 for j Ω 1 to n parallel do 8 x m Õ j Ω - - - - - x m Õ j + ' x m i ◊ |M i | m Õ j + h i ◊ | ≠ M | m Õ j - - - - - m Õ j
Algorithm 9 costs n 2 + n EMMs. Our count does not include the multiplications

h i ◊ | ≠ M | m Õ j since they are selections between 0 or | ≠ M | m Õ j (the bit h i being 0 or 1).
Operations from lines 4-6 are also not included in the cost because they are e ciently performed using the small accumulator on t bits (usually, t oe [4, 8]) called the cox [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF].

The cox-rower architecture proposed in [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF] and adapted to ECC in [START_REF] Guillermin | A high speed coprocessor for elliptic curve scalar multiplications over F p[END_REF] is presented in Figure 1.5. Computations at line 2 of Algorithm 9 are performed in parallel by the n rowers. The large multiplexer outputs the results of these computations by the left and right buses. The right bus broadcasts these results to the various rowers which now perform computations at line 8 of Algorithm 9 in parallel. The left bus transfers the results of the computations at line 2 to the cox unit which performs computations at lines 4-6 of Algorithm 9 and send their results to the various rowers where line 8 are being performed.

BEs using the CRT possess the advantage over BEs using an RNS-to-MRS conversion of finishing in n + 1 steps while using n (or n + 1 moduli for [START_REF] Shenoy | Fast base extension using a redundant modulus in RNS[END_REF]) channels. The notable advantage of Algorithm 9 is that the main computations, at lines 2 and 8, are performed in parallel. Unlike in Algorithm 8, there is no carry from one modulus to another in these crucial steps. Hence, Algorithm 9 exploits the inherent independence (in RNS) of multiplication, addition and subtraction among the moduli.

RNS Modular Reduction

The importance of MRs at the field level is mentioned in Section 1.2. Moreover, RNS by definition introduces MRs at another level, the various reductions mod m i . In this section we present some algorithms from the literature that e ciently perform the RNS MRs.

RNS Montgomery Reduction

The e ciency of the Montgomery reduction presented in Algorithm 7 motivates Posch and Posch [START_REF] Posch | Modulo reduction in residue number systems[END_REF] and later Kawamura et al. [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF] to propose an RNS adapted version of the algorithm. Their algorithm is presented in Algorithm 10. Let M and M Õ be two RNS bases such that each modulus of M Õ is coprime with all moduli of M. Let also assume x < MM Õ (for example, the product of two numbers). It is important that x be represented in the two bases because of its range.

Since the reduction mod M is easy in the RNS base M, the auxiliary number r for the Montgomery reduction in RNS is chosen to be M (the RNS equivalent of the 2 l for binary representation). By saying reduction mod M is easy in the base M, we mean the residues Algorithm 10: RNS Montgomery reduction algorithm [START_REF] Posch | Modulo reduction in residue number systems[END_REF].

Input:

x M , x M Õ Precomp.: p M Õ , (≠p ≠1 ) M , (M ≠1 ) M Õ Output: s M and s M Õ where s = (xM ≠1 ) mod p 1 q M Ω x M ◊ (≠p ≠1 ) M 2 q M Õ Ω BE MaeM Õ (q M ) 3 r M Õ Ω x M Õ + q M Õ ◊ p M Õ 4 s M Õ Ω r M Õ ◊ (M ≠1 ) M Õ 5 s M Ω BE M Õ aeM (s M Õ )
(in M) of a number remain unchanged when this number is taken modulo M . However, the RNS division by M cannot be performed in base M because M as the product of the various m i is not coprime with them, hence not invertible mod m i . The BE at line 2 allows to go from the base M to the base M Õ wherein the RNS division by M can be performed. This RNS division is only possible if the moduli of M Õ are coprime with the ones of M (this has been assumed). The second BE (line 5 of Algorithm 10) returns the result of the division by M back to the base M. This BE is also necessary for having the MR result in the two bases. Lines 1, 3 and 4 of Algorithm 10 are the RNS equivalents of lines 1, 2 and 3 of Algorithm 7 respectively. Algorithm 10 costs 2n 2 + 5n EMMs. This cost can be improved, for example by combining some precomputations and reducing the number of times the input residues are multiplied by these precomputations [GLP + 12, Gui10]. Gandino et al. [GLP + 12] improve the cost to 2n 2 + 2n EMMs by further reorganizing some internal computations.

RNS Barrett Reduction

The RNS Barrett reduction idea [START_REF] Schinianakis | An RNS modular multiplication algorithm[END_REF] is to use RNS to compute

x = x ≠ p E 7 x 2 w 8 p Õ 2 w F .
( of a computed o set value if divisibility is not possible, and a multiplication by the precomputed inverse of 2 w over the moduli of the RNS base besides an additional modulus.

In the overall complexity, these operations introduce a parameter that depends on the number of cycles taken by a MM, making di cult the comparison to other algorithms. Nevertheless, the authors will later acknowledge in [START_REF] Schinianakis | An RNS barrett modular multiplication architecture[END_REF] (wherein an architecture to support their algorithm is proposed) that the proposed algorithm require more EMMs than RNS Montgomery reduction.

On Pseudo-Mersenne Numbers and RNS

In Subsection 1.2.3 we mention that the algorithm tailored for pseudo-Mersenne cannot be used for reductions in arbitrary fields. However, moduli m i of the RNS base can be chosen to be small pseudo-Mersenne numbers to speed the various computations mod m i , regardless of the modular reduction algorithm used at the field level.

Field Programmable Gate Arrays

Field Programmable Gate Arrays (FPGAs) are used for many hardware implementations of asymmetric cryptosystems in the literature. FPGAs are presented in this section as well as some RNS implementations of asymmetric cryptosystems from the literature. Highlevel synthesis (HLS), as the chosen tool in this thesis to assist in the implementation on FPGAs, is also introduced.

Overview of FPGAs

Some of the material in this subsection is a synthesis of the introduction to FPGAs from [START_REF] Sentieys | Architectures reconfigurables FPGA[END_REF]. The used vocabulary is from Xilinx FPGAs because their 7-series devices constitute our implementation target. Similar concepts are available for FPGAs from other manufacturers under other names.

FPGAs are integrated circuits whose functionalities are programmable after manufacture. The functionality of an FPGA is programmed with the design; the FPGA is said to be configured. FPGAs are usually reconfigurable. They serve in many applications such as signal processing, computer vision and hardware security.

An FPGA can be described as a matrix of configurable logic blocks (CLBs). The CLBs usually comprise fast memories with low capacity called look-up tables (LUTs) combined with flip-flops (FFs) and a small multiplexer. A LUT allows to carry out combinatorial functions such as 4-input bits or 6-input bits to 1-output bit functions depending on the number of its inputs (4-input LUT or 6-input LUT respectively). A common view of a CLB can be found in [START_REF] Sentieys | Architectures reconfigurables FPGA[END_REF]. Interconnects are programmable and they link the CLBs to each other as well as to other elements of the FPGA. Figure 1.6 presents a simplified view of an FPGA.

Other elements such as block RAMs (BRAMs) for data storage, digital signal processing (DSP) slices for arithmetic processing, digital clock manager (DCM) and input/output (I/O) pins are usually present in the modern FPGAs. One of the most complex element in modern FPGAs is probably the DSP slice which comprises a multiplier and an accumulator, and can perform elementary arithmetic functions. For example, in the Xilinx 7-series FPGAs used for our implementations, the DSP slice (DSP48E1) embeds a 18 ◊ 25 multiplier in 2's complement and a 48-bit accumulator. multipliers and accumulators that are best implemented in dedicated DSP slices. All 7 series FPGAs have many dedicated, full-custom, low-power DSP slices, combining high speed with small size while retaining system design flexibility. The DSP slices enhance the speed and efficiency of many applications beyond digital signal processing, such as wide dynamic bus shifters, memory address generators, wide bus multiplexers, and memory-mapped I/O registers. The basic functionality of the DSP48E1 slice is shown in Figure 1-1. For complete details, refer to Figure 2 the user guide [START_REF]Xilinx. 7 series DSP48E1 slice user guide (UG479)[END_REF] for more details about this DSP slice.

The implementation on FPGAs is commonly performed using computer-aided design (CAD) tools and is described as follows. First, the functionality of the FPGA is implemented in a hardware description language (HDL), allowing to describe the desired architecture at a register-transfer level (RTL). It is also possible to describe the functionality of the FPGA in a high-level language such as C, C++ or SystemC. In this case, an HLS tool is used to automatically generate the HDL description of the RTL from the description in high-level language. In the work presented in this thesis, we describe the functionality in C and use Vivado HLS 2019.2 from Xilinx as HLS tool. Second, the CAD tool converts the HDL description of the RTL into a configuration stream, usually called bitstream. Last, the generated bitstream is used to configure the various elements of the FPGA, notably the CLBs, and the interconnects which will route the signal between the CLBs, and between the CLBs and other elements of the FPGA.

FPGAs present numerous advantages, notably their (re)configurability, compared with other integrated circuits such as application-specific integrated circuits (ASICs). Besides, the financial cost per unit and the time to market of FPGAs are lower than the ones of ASICs because ASIC designs usually require a large design team, complex and costly tools, considerable design and manufacture time [START_REF] Sentieys | Architectures reconfigurables FPGA[END_REF]. However, the FPGA performance is lower (lower speed and more power consumption) than the ASIC one due mainly to the programmable interconnects (and their layout) which ensure FPGA configurations. Still, FPGAs remain performant for applications they are used in. To summarize, FPGAs provide good hardware performance in addition to being configurable.

Some RNS Implementations of Asymmetric Cryptosystems on FPGA from the Literature

RNS implementations of asymmetric cryptosystems have gained interest in the two latest decades. Table 1.1 presents some of these implementations on FPGA from the literature. In references reported in Tabe 1.1, most authors implemented the core operation of the cryptosystem, for example the modular exponentiation for RSA or the ECSM for ECC. The ECSM solution by Bajard and Merkiche [START_REF] Bajard | Double level Montgomery cox-rower architecture, new bounds[END_REF] is currently the fastest one among RNS implementations of the ECSM over an underlying finite field of 256-bit elements. However, several parameters have to be considered for a fair comparison of FPGA implementations, causing the comparison to be di cult. An important parameter to consider is the FPGA technology. The same code is likely to give better implementation results on a recent FPGA than an older one (say, 10 or more years older FPGA). Besides, the area metrics such as the number of DSPs cannot be directly compared if the multipliers embedded in the DSPs do not handle the same input size. For example, DSPs embedding 9 ◊ 9 multipliers cannot be fairly compared in number to the ones embedding 18 ◊ 25 multiplier in 2's complement. Also, the number of combinatorial functions implementable by a 6-input LUT is greater than the one implementable by a 4-input LUT. Therefore, the numbers of slices are di cult to compare between two implementations using di erent technologies of FPGA (the slices comprise LUTs among other elements). We see in Chapter 3 that we compare our implementation results with the ones from the literature for FPGA technologies which are the closest to ours.

Another parameter to consider in the comparison is the chosen algorithm for computing the core operation. For example, a sliding window (without any protection) is likely to be faster than a double-and-add or a Montgomery ladder. For ECC, the type of the underlying field (binary, prime, etc.) and if prime field, the form of the prime (pseudo-Mersenne or arbitrary) are also parameters to consider. The protection of the implementation, if any, is also to be considered in the comparison because there exists an extra cost if the implementation is protected. In addition, the extra cost is dependent on the type of protection (for example against SPA or DPA 7 ). Overall, comparison of FPGA implementations of cryptosystems are tricky and the reported performance results are insu cient in themselves to make a fair comparison.

1.4. FIELD PROGRAMMABLE GATE ARRAYS
To close this subsection, we mention that many RNS implementations (for example [NMSK01, Gui10, BM14, BT15]) are based on adaptations of the cox-rower architecture by Kawamura et al. [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF] because the latter exploits the inherent parallelism of RNS. The architectures implemented in our contributions at Chapters 2 and 3 are also adapted from the cox-rower.

7. DPA stands for di erential power analysis.

High-Level Synthesis

HLS allows to automatically generate a register-transfer level (RTL) design described in a hardware description language (HDL) from a high-level description (usually in C, C++ or SystemC). The behavioral specification (for example the C code) and the implementation constraints (for example loop pipelining) are inputted to HLS which automatically generates the HDL description of the RTL and outputs the performance estimations of this desciption.

The main advantage of HLS is the reduction of the design time since HLS allows to focus mainly on the functionality; the consequence is a gain in productivity for designers. Besides, HLS favors fast explorations of the design space for di erent parameters and constraints. However, one should not expect HLS to automatically explore the design space without any guidance and provide excellent results. Our experiments suggest that the coding style of the high-level description has to be as close as possible to a behavioral specification in HDL in order to guide HLS to achieve decent results compared with a handwritten HDL description.

Figure 1.8 presents an excerpt of C code for HLS (as a toy example) to perform multiplications of arrays, element by element. There are 2N multiplications to be performed and two channels are used. Each channel is the hardware support of N multiplications, and the channels run in parallel. Each function describes a component. The component prod allows to perform the 2N multiplications and calls the components mul0 and mul1 for this purpose. Each of mul0 and mul1 is associated with a channel and performs one multiplication between a precomputed multiplicand (stored internally) and an input multiplier. The data types word and dword 8 represent unsigned integers of respective sizes 8 and 16 bits. The multiplicand and the multiplier are of data type word, and the output product is of data type dword. Attention should be paid to cast the type of the multiplicand and the multiplier to dword in the writing of the multiplication (lines 11 and 15). The reason behind this need for casting is that in C programming, a product of two values of data 8. The types word and dword are not built-in data types of C programming and the sizes 8 and 16 bits are specific to the example in Figure 1.8. The data types to use in an implementation have to be specified by the designer regarding the size of the manipulated data and should not be limited to usual types and related sizes of C programming (such as 16 or 32 bits for an int or an unsigned int depending on the platform). For example, choosing the data type word to represent unsigned integers of size 17 bits allows to fully exploit the 18 ◊ 25 multipliers in 2's complement embedded in the DSP slices of Xilinx 7-series FPGAs (asymmetric widths for DSP operands are not considered in this thesis). The product of two numbers of data type word is a number of data type dword, the latter representing in this case unsigned integers of size 34 bits. ) ) ; 1 6 . } Figure 1.8 -Excerpt of C code for HLS to explain the multiplication of arrays elements on two channels. Each of the components mul0 and mul1 is dedicated to a channel and performs a multiplication of a value received as input by a precomputed value stored internally. The description made in the component prod allows the components mul0 and mul1 to run in parallel. #pragma HLS PIPELINE allows to pipeline the operations within the loop of the component prod.

type word is a value of data type word. Last, the loop at line 3 is pipelined by adding the adequate directive (line 4) to achieve a better throughput.

Conclusion

In this chapter, we presented ECC which is the context of this thesis. The ECSM, as the core operation in protocols of ECC applications, has been described and examples of state-of-the-art algorithms to compute it have been stated. We also described the RNS, the number system we choose to perform the ECSM because of its exploitable inherent advantages. The crucial operation BE has been presented. In particular, the state-ofthe-art BE proposed in [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF] has been introduced, with which we compare the first contribution of this thesis in the next chapter. We also introduced FPGAs as well as HLS which we use to implement on FPGA our RNS solutions presented in the following Chapter 2

HIERARCHICAL BASE EXTENSION

Modular reductions (MRs) are an important part of computations of the elliptic curve scalar multiplication (ECSM), the core operation in protocols of ECC applications. In RNS implementations of the ECSM, the cost of an MR is substantially the cost of the two base extensions (BE) composing it. Therefore, the BE is a crucial operation in RNS implementations for ECC.

In this chapter, we present our BE [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF] which uses a hierarchical approach for computing the CRT formula. The main idea is to combine two (three or four) residues of a given number (the input of the BE) in one base to form super-residues, and then proceed with the computation of the CRT formula on these super-residues in the other base.

Much of the material presented in this chapter comes from [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF], a paper we presented at ARITH-261 in June 2019. We draw the attention of the reader to the fact that the implementations, that provide the results presented in this chapter, were perfomed using Vivado HLS 2019.2, on the contrary to Vivado HLS 2017.4 for implementation results in [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF]. The implementation codes and optimization files as well as the target FPGA are exactly the same in this chapter as in [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF]. These re-implementations are solely motivated by updating the results presented in [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF].

Additional notations used throughout the rest of the thesis are introduced in Section 2.1. The BE by Kawamura et al. (KBE) [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF], largely regarded as the state-of-the-art BE, and its associated cox-rower architecture are detailed in Section 2.2. Then, we present our hierarchical base extension (HBE) [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF] in Section 2.3, along with a comparison of the theoretical cost of HBE with that of KBE. We also describe an architecture, adapted from the cox-rower, to support HBE. In Section 2.4 the benefit from using HBE instead of KBE in RNS modular multiplications is evaluated. Implementation results of HBE and KBE are presented in Section 2.5. This chapter is concluded in Section 2.6.

Notations

RNS bases and residues (of a number) are represented in two dimensions. Two reasons motivate the preference of the two-dimension notations to the common one-dimension notations. We want to better exhibit the hierarchy of the computations toward the CRT and show the intermediate results that we name super-residues.

• An RNS base M of n = r ◊ c moduli is written M = Y _ _ _ ] _ _ _ [ m 1,1 . . . m 1,c . . . . . . . . . m r,1 . . . m r,c Z _ _ _ _ _ _ \ .
Let i, j be integers such that 1 AE i AE r and 1 AE j AE c.

• M = r Ÿ i=1 c Ÿ j=1 m i,j . • M i,j = M m i,j . • M (i) = c Ÿ j=1 m i,j . The M (i) , 1 AE i AE r, are called super-moduli. • M (i) = M M (i) . • m (i) i,j = M (i) m i,j . • A number x is represented in the RNS base M by x M = Q c c c a x m 1,1 . . . x m 1,c . . . . . . . . . x m r,1 . . . x mr,c R d d d b
, where x m i,j = |x| m i,j .

Kawamura Base Extension

In this section the BE proposed by Kawamura et al. [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF] and mentioned in Subsection 1.3.3 is detailed using the two-dimension notations introduced in Section 2.1.

Overview of KBE

The Chinese remainder theorem (CRT) formula, mentioned in Theorem 2 (Chapter 1), is recalled. Let M and M Õ be two RNS bases, x M and x M Õ the RNS representations of a

2.2. KAWAMURA BASE EXTENSION base M x m 1,1 x m 1,2 x m 1,3 x m 1,4 x m r,c 1 x m r,c base M 0 x m 0 1,1 x m 0 1,2 x m 0 1,3 x m 0 1,4 x m 0 r,c 1 x m 0 r,c 1 Figure 2.1 -Simplified description of KBE.
number x in M and M Õ respectively. The number x is given by:

x = - - - - - - r ÿ i=1 c ÿ j=1 - - -x m i,j M ≠1 i,j - - - m i,j M i,j - - - - - - M , (2.1) = Q a r ÿ i=1 c ÿ j=1 - - -x m i,j M ≠1 i,j - - - m i,j M i,j R b ≠ hM. (2.2)
Like most BEs based on the CRT, the idea of KBE is to compute the CRT formula of Equation 2.2 in the base M Õ . Figure 2.1 depicts a simplified description of the CRT computation in KBE. The computation of the CRT is performed on all input residues in each modulus of the output RNS base. In other words, for every output residue x m Õ k,l computed, all input residues x m i,j are multiplied by some precomputed values (not represented in Figure 2.1) and accumulated modulo the corresponding modulus of the output RNS base. The main contribution of [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF] is that the integer h in Equation 2.2 can be approximated by the integer h in Equation 2.3, and the term hM can be subtracted iteratively from the results of the CRT in every modulus m Õ k,l of the output RNS base.

h = W W W U r ÿ i=1 c ÿ j=1 trunc(|x m i,j M ≠1 i,j | m i,j ) 2 w + ‡ X X X V (2.3)

KBE Algorithm

Description of KBE Algorithm Using a Two-Dimension Notation

Algorithm 11 is Algorithm 9 of KBE [KKSS00] (Subsection 1.3.3) rewritten using the twodimension notations presented in Section 2.1. Since r and c are chosen such that n = rc, we replace loops bounded by n with nested loops bounded by r and c. The computations performed within the various loops of Algorithm 9 remain unchanged in Algorithm 11; the various indices are adjusted to take into account the two-dimension notations.

The term

q r i=1 q c j=1 |x m i,j M ≠1 i,j | m i,j M i,j of Equation 2.
2 is computed at line 3 and within line 11 of Algorithm 11. The correctness of x M Õ depends on the accuracy of h, the approximation of h. The value of h is computed in lines 6-8 of Algorithm 11; h is the sum of the bits h i,j computed at line 7. The function trunc approximates |x m i,j M ≠1 i,j | m i,j by its t most significant bits (MSBs), t < w, the w ≠ t remaining bits set to 0. In practice, the function trunc selects the t MSBs of |x m i,j M ≠1 i,j | m i,j and the denominator 2 w is replaced by 2 t . Choosing t oe [4, 8] is usually su cient for RNS implementations of ECC applications.

Validation of KBE

Theorems 3 and 4, from [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF], provide conditions that ensure the approximation h (in Equation 2.3) is h or at worst h ≠ 1. Two values d and e are defined below before presenting the theorems.

Definition 6 (from [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF]). The values d and e are given by

d = max 1AEiAEr, 1AEjAEc A ' x m i,j ≠ trunc(' x m i,j ) m i,j
B and e = max 1AEiAEr, 1AEjAEc

3 2 w ≠ m i,j 2 w 4 . Theorem 3 (from [KKSS00]). If 0 AE rc(d + e) AE ‡ < 1 and 0 AE x < (1 ≠ ‡)M , then h = h. Theorem 4 (from [KKSS00]). If ‡ = 0, 0 AE rc(d + e) < 1 and 0 AE x < M, then h = h or h = h ≠ 1.
The approximation of ' x m i,j and m i,j by respectively trunc(' x m i,j ) and 2 w introduces an error upperly bounded by rc(d + e). From Theorem 3, the output of KBE is exact if the base M is chosen such that rc(d + e) AE ‡ < 1 and x < (1 ≠ ‡)M . In practice, Algorithm 11: Kawamura base extension BE MaeM Õ (x) adapted from [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF] Input: x m i,j for all i, 1 AE i AE r and j, 1 AE j AE c; ‡ = 0 or 0.5 Precomp.:

|M ≠1 i,j | m i,j , |M i,j | m Õ k,l , | ≠ M | m Õ k,l , for all i, 1 AE i AE r; j, 1 AE j AE c; k, 1 AE k AE r; l, 1 AE l AE c Output: x m Õ k,l for all k, 1 AE k AE r and l, 1 AE l AE c 1 for i Ω 1 to r parallel do 2 for j Ω 1 to c parallel do 3 ' x m i,j Ω - - - - - x m i,j ◊ |M ≠1 i,j | m i,j - - - - - m i,j 4 for i Ω 1 to r do 5 for j Ω 1 to c do 6 ‡ Ω ‡ + trunc(' xm i,j ) 2 w 7 h i,j Ω Â ‡Ê 8 ‡ Ω ‡ ≠ h i,j 9 for k Ω 1 to r parallel do 10 for l Ω 1 to c parallel do 11 x m Õ k,l Ω - - - - - x m Õ k,l + ' x m i,j ◊ |M i,j | m Õ k,l + h i,j ◊ | ≠ M | m Õ k,l - - - - - m Õ k,l
we use ‡ = 0.5. From Thorem 4, the output of KBE is x M Õ or (x + M ) M Õ (that is, x or

x + M in the base M Õ ) if ‡ = 0, rc(d + e) < 1 and x < M. Two BEs are used in the RNS Montgomery reduction algorithm [START_REF] Posch | Modulo reduction in residue number systems[END_REF][START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF]. The first of the two BEs can be inexact because the correctness of the result mod p is not impacted. The second BE must be exact for the result mod p to be correct. Therefore, it is common to choose RNS bases such that conditions of Theorems 4 and 3 are respectively satisfied for the first and the second BE.

Cost of KBE

Line 3 of Algorithm 11 is performed rc times. The cost of lines 6-8 is negligible because these lines are e ciently performed by a small accumulator on t bits (usually, t oe [4, 8]). This accumulator is called the cox unit; see Subsection 2.2.3. Line 11 is performed r 2 c 2 times. In total, Algorithm 11 costs r 2 c 2 + rc EMMs, which is equal to the n 2 + n EMMs for the cost of KBE [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF] mentioned in the state of the art (Subsection 1.3.3).

The Cox-Rower Architecture

Kawamura et al. [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF] provide the cox-rower architecture to perform KBE. This architecture (or its variant) has been used to e ciently implement the RSA (for example [START_REF] Nozaki | Implementation of RSA algorithm based on RNS montgomery multiplication[END_REF]) and the ECSM (for example, [START_REF] Guillermin | A high speed coprocessor for elliptic curve scalar multiplications over F p[END_REF][START_REF] Bajard | Double level Montgomery cox-rower architecture, new bounds[END_REF]). Figure 2.2 presents a twodimension-notation version of the cox-rower in [START_REF] Guillermin | A high speed coprocessor for elliptic curve scalar multiplications over F p[END_REF], adapted from [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF].

There is one rower per channel, dedicated to computations over one modulus per RNS base. Each rower embeds a multiplier and an accumulator, and is able to perform computations of the form g Ω (g + a ◊ b + f ) mod m i,j or mod m Õ i,j , where the operands a, b, f and g are of size the width w of the channels. All rowers run in parallel. The execution of KBE using the cox-rower architecture is described as follows. The precomputations are held in the memory. The multiplications in base M at line 3 of Algorithm 11 are performed in the rowers. These multiplications are not represented in the simplified description of KBE in Figure 2.1. The large multiplexer receives the results of these multiplications from the rowers and outputs two buses (left and right). The right bus broadcasts the results to the rowers in order to proceed with the computation of the CRT in base M Õ (line 11 of Algorithm 11). This broadcast of each result to the various rowers corresponds to the arrows in the simplifed description of KBE presented in Figure 2.1. The left bus transfers the results (of the multiplications) to the cox unit which computes the bits h i,j (lines 6-8 of Algorithm 11). The cox then sends the bits h i,j (0 or 1) to the various rowers. Once received in the rowers, these bits activate the subtraction of 0 or M in the rowers. These subtractions correspond to adding

h i,j ◊ | ≠ M | m Õ k,l (in line 11 of Algorithm 11).

Hierarchical Base Extension

In [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF] we proposed a hierarchical approach to perform the BE operation.

Hierarchical approaches are not new in RNS. For example, RNS can be used recursively when inside-channel computations are performed in a small RNS base; see [Yas92, HRdH + 18]. The performance using this method is not improved significantly compared with using traditional RNS methods. However, this method presents additional properties related to protection against some physical attacks.

Authors of [START_REF] Skavantzos | Implementation issues of the two-level residue number system with pairs of conjugate moduli[END_REF][START_REF] Tomczak | Hierarchical residue number systems with small moduli and simple converters[END_REF] propose to use RNS bases of three or four moduli, where some of these moduli are factorizable into smaller ones. They target signal processing applications, wherein the used integers (of a few dozens of bits) are smaller than in asymmetric cryptography applications. For this approach to lead to e cient implementations of asymmetric cryptosystems, the MR must be e cient in the (sub)channels using these moduli and their factorizations. Our proposed idea in [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF] is a hierarchical approach for computing the BE (through a CRT computation and we target cryptographic applications) rather than an RNS hierarchical representation.

Hierarchical approaches with partial CRTs are proposed in [START_REF] Bostan | Tellegen's principle into practice[END_REF][START_REF] Van Der Hoeven | Fast Chinese remaindering in practice[END_REF] to improve the performance of the CRT computation in an RNS-to-positional conversion. To our knowledge, HBE [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF] is the first BE that uses a hierarchical approach for full RNS computations.

Overview of HBE

The main idea of HBE can be described in two phases: First, we combine the input residues per group of c (that is, per row) through computations of small and partial CRTs in the base M. The results of these partial-CRT computations are named super-residues. These combinations are depicted with some simplifications in Figure 2.3 for c = 2. The residues x m i,1 and x m i,2 (in blue) are combined into the super-residues '

x M (i) (in blue). In the second phase, we proceed with the computation of the CRT on these super-residues in the base M Õ . In Figure 2.3, this phase is simplified into the arrows going from the super-residues '

x M (i) (in blue) to the residues x m Õ i,j (in orange).

base M

x m 1,1 x m 1,2 x m 2,1 x m 2,2 x m r,1 x m r,2 base M 0 x m 0 1,1 x m 0 1,2 x m 0 2,1 x m 0 2,2 x m 0 r,1 x m 0 r,2 b x M (1) b x M (2) b x M (r) 1 Figure 2.3 -Simplified description of HBE c = 2.

HBE Algorithm Desription of the Algorithm

HBE is presented in Algorithm 12. Like KBE and generally BEs based on the CRT, HBE computes the CRT formula of Equation 2.2 in the RNS base M Õ . Lines 1-3 are the same in Algorithm 12 as in Algorithm 11. Lines 4-7 correspond to the computation of partial CRTs on each row, resulting in the super-residues ' x M (i) (one super-residue per row). The super-residues are not reduced at this step. Therefore, '

x M (i) < cM (i) for all i, 1 AE i AE r. Lines 9-11 of Algorithm 12 of HBE are an adaptation of lines 6-8 of Algorithm 11 of KBE. This time, the values h i are of size 1 + Álog 2 cË bits. Under conditions of Theorems 3 and 4 initially specified for KBE, we prove that the approximation of h Algorithm 12: Hierarchical base extension BE MaeM Õ (x) [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF] Input: x m i,j for all i, 1 AE i AE r and j, 1 AE j AE c; ‡ = 0 or 0.5 Precomp.:

|M ≠1 i,j | m i,j , |M i,j | m Õ k,l , | ≠ M | m Õ k,l , for all i, 1 AE i AE r; j, 1 AE j AE c; k, 1 AE k AE r; l, 1 AE l AE c Output: x m Õ k,l for all k, 1 AE k AE r and l, 1 AE l AE c 1 for i Ω 1 to r parallel do 2 for j Ω 1 to c parallel do 3 ' x m i,j Ω - - - - - x m i,j ◊ |M ≠1 i,j | m i,j - - - - - m i,j 4 for i Ω 1 to r parallel do 5 ' x M (i) Ω 0 6 for j Ω 1 to c do 7 ' x M (i) Ω ' x M (i) + ' x m i,j ◊ m (i) i,j
(without modular reduction)

8 for i Ω 1 to r do 9 ‡ Ω ‡ + trunc(' x M (i) ) 2 w◊c 10 h i Ω Â ‡Ê 11 ‡ Ω ‡ ≠ h i 12 for k Ω 1 to r parallel do 13 for l Ω 1 to c parallel do 14 ' x m Õ k,l,i Ω |' x M (i) | m Õ k,l 15 x m Õ k,l Ω - - - - -x m Õ k,l + ' x m Õ k,l,i ◊ - - -M (i) - - - m Õ k,l + h i ◊ | ≠ M | m Õ k,l - - - - - m Õ k,l
reaches the same result, that is,

q n i=1 h i = h or h ≠ 1.
The proof is provided in the part "Validation of HBE" below.

Lines 14 and 15 are the most costly lines of Algorithm 12 since they are performed x M (i) , multiplying the results of line 14 by M (i) is su cient to get the CRT computed at line 15.

To summarize, the input residues are combined per row through partial CRTs to get the super-residues. Then the computation of the CRT in the output base is proceeded on the super-residues with an approximation similar to that of KBE [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF]. The main computation (lines 14 and 15 of Algorithm 12) of HBE is performed r 2 c times while that of KBE (line 11 of Algorithm 11) is perfomed r 2 c 2 times. However, HBE introduces w ◊ (c ≠ 1)w bit multiplications (line 7 of Algorithm 12) and reductions of cw + Álog 2 cË bits by w-bit integers (line 14 of Algorithm 12).

The first three lines of Algorithm 11 of KBE can be hidden in the computation of the RNS MR from [START_REF] Posch | Modulo reduction in residue number systems[END_REF] by combining some precomputations of Algorithm 11 of KBE with some of Algorithm 10 of the RNS MR; see [GLP + 12, Gui10, KKSY18]. As a result, the implementation of the RNS MR is made faster. Algorithm 12 of HBE is also compatible with this optimization.

We choose c oe {2, 3, 4} small for RNS implementations of ECC applications to keep the inherent parallelism of RNS as much as possible. The case c = 2 reveals some simplifications, notably in the architecture; see Subsection 2.3.3.

Validation of HBE

The CRT formula is recalled.

x = Q a r ÿ i=1 c ÿ j=1 - - -x m i,j M ≠1 i,j - - - m i,j M i,j R b ≠ hM.
(2.4)

To validate HBE presented in Algorithm 12, we start by proving that the term in parentheses in Equation 2.4 is computed within the execution of Algorithm 12. We then discuss the correctness of h approximated by computing the values h i in Algorithm 12.

The term in parentheses in Equation 2.4 is

s x = r ÿ i=1 c ÿ j=1 - - -x m i,j M ≠1 i,j - - - m i,j M i,j = r ÿ i=1 c ÿ j=1 ' x m i,j M i,j = r ÿ i=1 c ÿ j=1 ' x m i,j M m i,j = r ÿ i=1 c ÿ j=1 ' x m i,j M (i) m i,j ◊ M M (i) = r ÿ i=1 Q a c ÿ j=1 ' x m i,j m (i) i,j R b M (i) = r ÿ i=1 ' x M (i) ◊ M (i) (2.5)
The reader can recognize that Equation 2.5 is computed (mod m Õ k,l ) at line 14 and the first two terms at line 15 of Algorithm 12.

Theorems 3 and 4 from [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF] give an upper bound for the error made by approximating h by h, using Algorithm 11 of KBE. Since trunc(' x m i,j ) AE '

x m i,j and 2 w > m i,j for all i, 1 AE i AE r and j, 1 AE j AE c, we obtain

r ÿ i=1 c ÿ j=1 trunc(' x m i,j ) 2 w < r ÿ i=1 c ÿ j=1 ' x m i,j m i,j
.

(2.6)

Besides, from the proofs of Theorems 3 and 4 in [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF],

r ÿ i=1 c ÿ j=1 ' x m i,j m i,j ≠ r ÿ i=1 c ÿ j=1 trunc(' x m i,j ) 2 w < rc(d + e).
(2.7)

Our discussion of the correctness of h for HBE with c oe {2, 3, 4} is built upon Theorems 3 and 4 from [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF] with respect to KBE. Clearly, if the base M is chosen verifying Theorems 3 and 4 for KBE, then M can be used for HBE, c oe {2, 3, 4}.

Let assume m 1,1 < m 1,j for all j, 2 AE j AE c, and m 1,j < m i,j for all i, 2 AE i AE r and j, 1 AE j AE c. One can rearrange the moduli in the two-dimension notation of the base M to get these inequalities.

With respect to Algorithm 12 of HBE, let the values d Õ M (i) , e Õ M (i) , d Õ and e Õ be defined by

d Õ M (i) = ' x M (i) ≠ trunc(' x M (i) ) M (i) , e Õ M (i) = 2 cw ≠ M (i) 2 cw and d Õ = max 1AEiAEr (d Õ M (i) ) , e Õ = max 1AEiAEr (e Õ M (i) ) .
The function trunc now approximates ' x M (i) (of cw +Álog 2 cË bits) by its t+Álog 2 cË MSBs, the 2w≠t remaining bits set to 0. The super-modulus M (i) is approximated by 2 cw . To ease the notation and improve the clarity of the argument, we assume c = 2-the arguments for the cases c = 3, 4 being analogous to that of c = 2. From this assumption, the function trunc approximates '

x M (i) by its t + 1 MSBs, and the super-modulus

M (i) is approximated by 2 2w . The introduced values d Õ M (i) , e Õ M (i) , d Õ and e Õ are rewritten d Õ M (i) = ' x M (i) ≠ trunc(' x M (i) ) M (i) , e Õ M (i) = 2 2w ≠ M (i) 2 2w
(2.8) and

d Õ = ' x M (1) ≠ trunc(' x M (1) ) M (1) , e Õ = 2 2w ≠ M (1) 2 2w .
(2.9)

Remark 1 (On d and d Õ values). The various ' x m i,j and ' x M (i) as well as their truncated values cannot be predicted in the numerator of d in Definition 6 and that of d Õ in Equation 2.9. Therefore, we assume the upper bounds

d = 2 w≠t ≠ 1 m 1,1 , d Õ = 2 2w≠t ≠ 1 M (1) .
(2.10)

We want to prove that

r ÿ i=1 trunc(' x M (i) ) 2 2w < r ÿ i=1 2 ÿ j=1 ' x m i,j m i,j
(2.11) and

r ÿ i=1 2 ÿ j=1 ' x m i,j m i,j ≠ r ÿ i=1 trunc(' x M (i) ) 2 2w < 2r(d + e).
(2.12)

For all i, 1 AE i AE r, 2 ÿ j=1 ' x m i,j m i,j = ' x m i,1 m i,2 + ' x m i,2 m i,1 m i,1 m i,2 = ' x M (i) M (i) . Since trunc(' x M (i) ) AE '
x M (i) and 2 2w > M (i) , we obtain for all i, 1 AE i AE r,

trunc(' x M (i) ) 2 2w < 2 ÿ j=1 ' x m i,j m i,j
, and consequently

r ÿ i=1 trunc(' x M (i) ) 2 2w < r ÿ i=1 2 ÿ j=1 ' x m i,j m i,j
, which is Equation 2.11.

Let us bound

r ÿ i=1 2 ÿ j=1 ' x m i,j m i,j ≠ r ÿ i=1 trunc(' x M (i) ) 2 2w .
From Equation 2.8, we do have on one hand trunc(' x

M (i) ) = ' x M (i) ≠ M (i) ◊ d Õ M (i)
, and on the other hand e Õ M (i) = 1 ≠

M (i) 2 2w , which implies 1 ≠ e Õ M (i) = M (i) 2 2w , that is, 1 2 2w = 1 ≠ e Õ M (i)
M (i) .

HIERARCHICAL BASE EXTENSION

We get

r ÿ i=1 trunc(' x M (i) ) 2 2w = r ÿ i=1 1 ' x M (i) ≠ M (i) ◊ d Õ M (i) 2 ◊ 1 ≠ e Õ M (i) M (i) = r ÿ i=1 ' x M (i) M (i) ≠ r ÿ i=1 e Õ M (i) ' x M (i) M (i) ≠ r ÿ i=1 (1 ≠ e Õ M (i) ) d Õ M (i) = r ÿ i=1 ' x M (i) M (i) ≠ r ÿ i=1 e Õ M (i) ' x M (i) M (i) ≠ r ÿ i=1 M (i) 2 2w d Õ M (i) .
(2.13)

The terms at the right of the equal sign in Equation 2.13 verify

r ÿ i=1 ' x M (i) M (i) = r ÿ i=1 2 ÿ j=1 ' x m i,j m i,j ; r ÿ i=1 e Õ M (i) ' x M (i) M (i) < 2re Õ because ' x M (i) M (i) < 2, and e Õ M (i) AE e Õ by definition; r ÿ i=1 M (i) 2 2w d Õ M (i) < rd Õ because M (i) 2 2w < 1, and d Õ M (i) AE d Õ by definition.
It follows from Equation 2.13 that

r ÿ i=1 trunc(' x M (i) ) 2 2w > r ÿ i=1 2 ÿ j=1 ' x m i,j m i,j ≠ 2re Õ ≠ rd Õ , that is, r ÿ i=1 2 ÿ j=1 ' x m i,j m i,j ≠ r ÿ i=1 trunc(' x M (i) ) 2 2w < 2re Õ + rd Õ . (2.14)
Proving e Õ + 2 ≠1 d Õ < e + d su ces to get Equation 2.12 from Equation 2.14. We have

d ≠ 2 ≠1 d Õ = 2 w≠t ≠ 1 m 1,1 ≠ 2 ≠1 (2 2w≠t ≠ 1) M (1) = m 1,2 (2 w≠t ≠ 1) ≠ 2 ≠1 (2 2w≠t ≠ 1) M (1) (recall M (1) = m 1,1 ◊ m 1,2 ) (2.15) and e Õ ≠ e = 2 2w ≠ M (1) 2 2w ≠ 2 w ≠ m 1,1
2 w (to get the value of e from Definition 6, use the fact that ' i, j, m 1,1 AE m i,j )

= 1 ≠ M (1) 2 2w ≠ 3 1 ≠ m 1,1 2 w 4 = m 1,1 2 w ≠ M (1) 2 2w = m 1,1 ◊ 2 w ≠ M (1) 2 2w = m 1,1 (2 w ≠ m 1,2 ) 2 2w = m 1,1 ◊ Á 1,2 2 2w (2.16)
From Equations 2.15 and 2.16, we obtain

d ≠ 2 ≠1 d e Õ ≠ e = m 1,2 (2 w≠t ≠ 1) ≠ 2 ≠1 (2 2w≠t ≠ 1) M (1) ◊ 2 2w m 1,1 ◊ Á 1,2 = m 1,2 (2 w≠t ≠ 1) ≠ 2 ≠1 (2 2w≠t ≠ 1) m 1,1 ◊ Á 1,2 ◊ 2 2w M (1)
(2.17)

Lemma 5. If t < w 2 ≠ 1 then m 1,2 (2 w≠t ≠ 1) ≠ 2 ≠1 (2 2w≠t ≠ 1) m 1,1 ◊ Á 1,2 > 1. Proof. The inequality m 1,2 > m 1,1 implies m 1,2 Ø m 1,1 + 1 and Á 1,2 AE Á 1,1 ≠ 1, which leads to m 1,2 1 2 w≠t ≠ 1 2 ≠ 2 ≠1 1 2 2w≠t ≠ 1 2 Ø (m 1,1 + 1) 1 2 w≠t ≠ 1 2 ≠ 2 ≠1 1 2 2w≠t ≠ 1 2 and m 1,1 ◊ Á 1,2 AE m 1,1 (Á 1,1 ≠ 1) . Subsequently, m 1,2 (2 w≠t ≠ 1) ≠ 2 ≠1 (2 2w≠t ≠ 1) m 1,1 ◊ Á 1,2 Ø (m 1,1 + 1) (2 w≠t ≠ 1) ≠ 2 ≠1 (2 2w≠t ≠ 1) m 1,1 (Á 1,1 ≠ 1)
.

(2.18)

We have

(m 1,1 + 1)(2 w≠t ≠ 1) ≠ 2 ≠1 (2 2w≠t ≠ 1) ≠ m 1,1 (Á 1,1 ≠ 1) = m 1,1 ◊ 2 w≠t + 2 w≠t ≠ m 1,1 ≠ 1 ≠ 2 2w≠t≠1 + 2 ≠1 ≠ m 1,1 (Á 1,1 ≠ 1) = (m 1,1 ◊ 2 w≠t ≠ 2 2w≠t≠1 ) + (2 w≠t + 2 ≠1 ) ≠ (m 1,1 ◊ Á 1,1 + 1). (2.19)
The first term at the right of the equal sign in Equation 2.19 verifies

m 1,1 ◊ 2 w≠t ≠ 2 2w≠t≠1 > 2 2w≠t≠1 ≠ 2 3w 2 ≠t
.

(2.20)

Indeed, Á 1,1 < 2 w 2 implies ≠Á 1,1 > ≠2 w 2 , which leads to m 1,1 = 2 w ≠ Á 1,1 > 2 w ≠ 2 w 2
, and subsequently

m 1,1 ◊ 2 w≠t > 2 w≠t 1 2 w ≠ 2 w 2 2 = 2 2w≠t ≠ 2 3w 2 ≠t = 2 ◊ 2 2w≠t≠1 ≠ 2 3w 2 ≠t . It follows that m 1,1 ◊ 2 w≠t ≠ 2 2w≠t≠1 > 2 2w≠t≠1 ≠ 2 3w 2 ≠t .
The third term at the right of the equal sign in Equation 2.19 verifies

2 2w≠t≠1 ≠ 2 3w 2 ≠t > m 1,1 ◊ Á 1,1 + 1 = m 1,1 (Á 1,1 + m ≠1 1,1 ). (2.21) Indeed, 2 2w≠t≠1 ≠ 2 3w 2 ≠t can be rewritten 2 2w≠t≠1 ≠ 2 3w 2 ≠t = 2 w ◊ 2 w 2 ◊ 2 ≠t 1 2 w 2 ≠1 ≠ 1 2 , (2.22)
where the factors of the right of the equal sign verify inequalities detailed as follows.

• The factor 2 w in Equation 2.22 verifies

2 w > m 1,1 . • The factor 2 w 2 in Equation 2.22 verifies 2 w 2 > Á 1,1 + m ≠1 1,1 . This inequality comes from 2 w 2 Ø Á 1,1 + 1 (since Á 1,1 < 2 w 2 ) and Á 1,1 + 1 > Á 1,1 + m ≠1 1,1 (since m ≠1 1,1 < 1, due to the fact that the size w of m 1,1 is in [10, 64], that is, m 1,1 > 1). • The factor 2 ≠t 1 2 w 2 ≠1 ≠ 1 2 in Equation 2.22 verifies 2 ≠t 1 2 w 2 ≠1 ≠ 1 2 Ø 1. Since t < w 2 ≠ 1, we have 2 t < 2 w 2 ≠1 , which implies 2 t AE 2 w 2 ≠1
≠ 1, and consequently

1 AE 2 ≠t 1 2 w 2 ≠1 ≠ 1 2 .
From Equations 2.20 and 2.21, we obtain

m 1,1 ◊ 2 w≠t ≠ 2 2w≠t≠1 > m 1,1 ◊ Á 1,1 + 1, which implies (m 1,1 ◊ 2 w≠t ≠ 2 2w≠t≠1 ) ≠ (m 1,1 ◊ Á 1,1 + 1) > 0.
It follows, a fortiori, that

(m 1,1 ◊ 2 w≠t ≠ 2 2w≠t≠1 ) + (2 w≠t + 2 ≠1 ) ≠ (m 1,1 ◊ Á 1,1 + 1) > 0.
Considering Equation 2.19, we get

(m 1,1 + 1)(2 w≠t ≠ 1) ≠ 2 ≠1 (2 2w≠t ≠ 1) ≠ m 1,1 (Á 1,1 ≠ 1) > 0, that is, (m 1,1 + 1) (2 w≠t ≠ 1) ≠ 2 ≠1 (2 2w≠t ≠ 1) m 1,1 (Á 1,1 ≠ 1) > 1.
From Equation 2.18 we then obtain

m 1,2 (2 w≠t ≠ 1) ≠ 2 ≠1 (2 2w≠t ≠ 1) m 1,1 ◊ Á 1,2 > 1.
In practice, the condition t < w 2 ≠ 1 of Lemma 5 is verified for RNS implementations of asymmetric cryptosystems where w is usually in [10,64]. For w Ø 11 we can always find t in [4, 8] verifying this condition. For w = 10, it su ces to take t = 3 to ensure this condition. It follows from Lemma 5 that

m 1,2 (2 w≠t ≠ 1) ≠ 2 ≠1 (2 2w≠t ≠ 1) m 1,1 ◊ Á 1,2 > 1. Since 2 2w
M (1) > 1, Equation 2.17 then implies

d ≠ 2 ≠1 d Õ e Õ ≠ e > 1. It follows that d ≠ 2 ≠1 d Õ > e Õ ≠ e, that is, e Õ + 2 ≠1 d Õ < e + d (2.23)
We conclude from Equations 2.14 and 2.23 that

r ÿ i=1 2 ÿ j=1 ' x m i,j m i,j ≠ r ÿ i=1 trunc(' x M (i) ) 2 2w < 2r(e + d), (2.24)
which is Equation 2.12.

Cost of HBE

Some operands at lines 7 and 14 of Algorithm 12 are of size greater than the width w of the channels. At line 7, there is a product of w-bit and (c ≠ 1)w-bit integers as well as an accumulation of cw-bit integers. The result of line 7, a (cw + Álog 2 cË)-bit integer, is reduced modulo a w bit integer at line 14. We introduce three additional notations to represent the cost of these operations. Our goal is to compare the cost of these operations to the usual metric, namely EMM. From there, we can fairly evaluate the HBE cost against the KBE one.

• CMUL(w, w Õ ): cost of a multiplication of a w-bit integer by a w Õ -bit integer.

• CADD(w, w Õ ): cost of an addition/subtraction of a w-bit integer to a w Õ -bit integer.

• CMR(w, w Õ ): cost of a w-bit integer mod a w Õ -bit integer reduction. Similarly to Algorithm 11 of KBE, lines 1-3 of Algorithm 12 of HBE cost rc EMMs. Lines 4-7 cost rc(CMUL(w, (c ≠ 1)w) + CADD(cw, cw)). As for the cost of lines 6-8 of Algorithm 11 of KBE, the cost of lines 9-11 of Algorithm 12 of HBE is not counted. Indeed, the cost of these lines is negligible since the operations at these lines are performed e ciently by the cox unit, a small accumulator of t + Álog 2 cË bits. Finally, lines 14 and 15 are operated r 2 c times. Line 14 costs r 2 c CMR(cw + Álog 2 cË, w). Line 15 costs r 2 c(EMM + 2CADD(w, w)).

Overall, Algorithm 12 of HBE costs In DSP slices of modern FPGAs, additions are usually hidden in the pipeline computing the multiplications. Therefore, we concentrate the cost on the modular multiplications, similarly to most works in the literature. With this simplification, we obtain for the cost of HBE 2r 2 (EMM + CMR(2w + 1, w)) + 2r (EMM + CMUL(w, w)) .

Overestimating a CMUL(w, w) to be equal to an EMM, we obtain that HBE (c = 2) costs

2r 2 EMM + 2r 2 CMR(2w + 1, w) + 4r EMM, that is, n 2 2 EMM + n 2 2 CMR(2w + 1, w) + 2n EMM. (2.26)
Recall that KBE costs

n 2 EMM + n EMM.
(2.27)

The comparison of the HBE (c = 2) cost with the KBE one is made di cult by the presence of the term n 2 2 CMR(2w+1, w) in Equation 2.26. HBE (c = 2) may cost less than KBE if CMR(2w + 1, w) π EMM. In order to compare a CMR(2w + 1, w) with an EMM, we implemented the two operations on a Xilinx XCV7020 FPGA (using Vivado HLS 2019.2) for various widths w of channels. The implementation results are reported in Table 2.1. In most cases, an EMM costs about twice a CMR(2w + 1, w) in time and/or in area. Therefore, we estimate EMM/4 AE CMR(2w + 1, w) AE EMM/2.

Estimating one EMM to be in {2, 3, 4} CMR(2w + 1, w), we evaluate the theoretical cost ratio HBE (c = 2) / KBE of one BE for various numbers n of moduli. The result of this evaluation is shown in Figure 2.4. The theoretical cost reduction of HBE (c = 2) against KBE is up to 35% using these estimations.

A Cox-Rower Architecture Adapted for HBE

The cox-rower architecture [KKSS00], initially designed for KBE, has been adapted for HBE to exploit its e ciency. The adapted architecture for c = 2 is presented in Figure 2.5.

Algorithm 12 of HBE consists of three primary (groups of) loops. The first and the third loops can be performed on the HBE architecture (Figure 2.5) as well as on the KBE one (the original cox-rower at Figure 2.2) since computations within these loops (except those about the h i ) run in parallel on the rc = n channels. If c > 2, the architecture has to be adapted to support reductions of integers larger than 2w + 1 bits. The second loop performs in parallel r = n/c accumulations of products. Therefore, the value of c is inversely related to the quality of the parallelism. For c = 2, the lost in parallelism is slight because r = n/2 accumulations of products are performed in parallel. The size of the accumulator of the second loop is cw+Álog 2 cË. For c = 2, the value of the accumulator can be easily reduced in the third loop, with a reduction similar to the one performed in the third loop of KBE algorithm.

The cox unit for HBE is now a small accumulator of size t + Álog 2 cË bits, unlike in the original cox-rower architecture for KBE [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF] where the corresponding small accumulator is of size t bits. For c = 2, the size of the small accumulator is t + 1. The output h i of the cox is of 2-bit size in HBE c = 2. The value h i sent to the various

APPLICATION TO RNS MODULAR MULTIPLICATIONS

rowers now activates the subtractions of 0, M , 2M and 3M in the rowers (line 15 of Algorithm 12).

The behavior of the HBE c = 2 architecture is described as follows. The precomputations are held in the memory, as in the original cox-rower. The 2r multiplications of lines 1-3 of Algorithm 12 are performed by the 2r rowers running in parallel. These multiplications are not represented in the simplified description of HBE in Figure 2.3. The super-residues are computed through 2r multiplications and additions, r operations running in parallel at a time. This step corresponds to the arrows from x m i,1 and x m i,2 (in blue) to '

x M (i) (in blue) in the simplifed description of HBE c = 2 presented in Figure 2.3. The super-residues are broadcasted to the channels to perform lines 14 and 15 of Algorithm 12 of HBE. This broadcast is operated by the two right buses at the output of the large multiplexer. We use two buses to be able to employ one of them to broadcast w-bit results when necessary, for example the '

x m i,j computed at line 3 of Algorithm 12. The broadcast of the super-residues to the various rowers corresponds to the arrows from the ' x M (i) (in blue) to all the x m Õ i,j in (orange) in the simplifed description of HBE c = 2 presented in Figure 2.3. The left bus at the output of the large multiplexer transfers the w +1 MSBs of the various super-residues to the cox unit. At its turn, the cox unit computes the values h i and sends them to the various rowers to execute the subtractions at line 15 of Algorithm 12.

Application to RNS Modular Multiplications

The modular reduction (MR) is performed numerous times during an elliptic curve scalar multiplication (ECSM). The cost of Algorithm 10 about the RNS MR from [START_REF] Posch | Modulo reduction in residue number systems[END_REF], is mainly the cost of the two BEs comprised in the algorithm. Two KBEs cost 2n 2 +2n EMMs while the RNS MR costs 2n 2 + 5n EMMs. The cost of the RNS MR drops to 2n 2 + 2n when optimizations of Gandino et al. [GLP + 12] (combination of precomputations and reordering of internal operations) are applied. One RNS modular multiplication (MM) costs 2n 2 + 4n EMMs (2n EMMs for the multiplications in the two RNS bases and 2n 2 + 2n EMMs for the RNS MR). When KBE is replaced with HBE (c = 2) in the RNS MM, the cost of the latter drops to 3n 2 2 + 6n and 5n 2 4 + 6n with the assumptions 1 EMM = 2 and 4 CMR(2w + 1, w) respectively. CMR(2w + 1, w). For a typical example, if we target a finite field F p of 256-bit elements for ECC and use channels of 17-bit width (to fit into the hardwired integer multipliers embedded in the Xilinx DSP slices; see Section 2.5), we need n = 16 moduli for each RNS base. In such an example, HBE leads to a 17-27% gain in the theoretical cost of the RNS MM compared with KBE.

The theoretical cost ratio HBE/KBE for one RNS MM using another approach for ECC [BT15, BT16] is also evaluated. The proposed idea in [START_REF] Bigou | Single base modular multiplication for e cient hardware rns implementations of ecc[END_REF], and generalized in [START_REF] Bigou | Hybrid position-residue number system[END_REF], is to use p with properties similar to pseudo-Mersenne and blend RNS with a polynomial representation of small degree d. We refer to MM algorithms in [START_REF] Bigou | Single base modular multiplication for e cient hardware rns implementations of ecc[END_REF] and [START_REF] Bigou | Hybrid position-residue number system[END_REF] for various estimations EMM/CMR(2w + 1, w) and numbers n of moduli.

FPGA Implementation Results

We implemented Algorithm 12 of HBE (for c = 2) and Algorithm 11 of KBE [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF] on a XC7Z020 FPGA from Xilinx using Vivado HLS 2019.2. The same environment and optimization e ort (for example, loop pipelining) were used for the implementation of the two BE algorithms to fairly compare them. The implementation of the two algorithms is also motivated by the lack of results for standalone BE implementations in the literature.

We use high-level synthesis (HLS) to reduce the design time of the two BEs and explore several implementation parameters such as the number and the width of the RNS channels. However, we were unable to use HLS to allocate a memory per channel as described in Figures 2.2 and 2.5 of KBE and HBE architectures respectively. A memory containing all the precomputations and feeding all the channels has been used instead. With this method, the parallelism of the channels is limited by the number of their accesses per cycle to the memory. Nevertheless, this situation does not negate the fairness of our comparison since the two BE implementations are both subject to the situation. Allocating a memory per channel will improve the results of the two BE implementations. For instance, in Chapter 3 where we were able to appropriately allocate a memory per channel, the results of the BE implementations show significant improvements (see BE results for F p of 256-bit elements and channel width w of 17 bits in Table 2.2, and the BE results for 16 physical channels (PCs) in Table 3.3-the FPGAs are both from the Xilinx 7-series family though being di erent).

The RNS bases are selected for underlying finite fields F p (of ECC) of 256-and 384bit elements. The number n of RNS channels is the smallest even integer such that nw > log 2 p (because c = 2 must divide n). The widths w of the RNS channels examined are 17, 20, 24 and 28 bits. The hardwired integer multipliers embedded in the DSP slices in Xilinx FPGAs support 18 ◊ 18 and 18 ◊ 25 bit multiplications in 2's complement. The DSP slices are fully exploited with 17-bit operands for unsigned integers; see [START_REF]Xilinx. Vivado design suite user guide high-level synthesis (UG902)[END_REF][START_REF]Xilinx. 7 series DSP48E1 slice user guide (UG479)[END_REF]. In our implementations, we do not use asymmetric widths for the DSP operands (for example, 17 ◊ 24 bits).

The implementation results are reported in Table 2.2. The "time" stands for the product of the period and the number of cycles to compute the BE. The time, the numbers of DSPs and slices of the two algorithms are plotted in Figure 2.9. HBE solutions are faster and smaller than KBE solutions in most instances. For example, for F p of 256-bit elements and channels of 24-bit width, HBE is 20% faster, 19% smaller in DSPs and 6% smaller

Conclusion

In this chapter, we have presented the hierarchical base extension (HBE) [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF]. HBE operates partial computations of small CRTs on the input residues to form super-residues in the input RNS base, and proceed with the CRT on these super-residues in the output RNS base. On the design of the RNS bases, HBE does not introduce additional constraints compared with the state-of-the-art base extension (KBE) [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF]. HBE shows a gain of up to 35% in the theoretical cost compared with KBE.

We have also presented the architecture proposed to support HBE c = 2 [DBT19] inpired by the cox-rower architecture for KBE [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF]. The inherent parallelism of RNS is maintained with a slightly deeper pipeline at the rower level. FPGA implementations using HLS tools demonstrate that HBE solutions are faster (up to 20%), and in nearly all cases smaller (up to 23%) than KBE. The area vs. time trade-o is always in favor of HBE.

In the next chapter flexible ECSMs using HBE (c = 2) and KBE are implemented and their results compared.

Perpective

We intend to study other types of decompositions (for example, c = 3, 4) and design architectures to support the inherent optimizations of these decompositions.

Chapter 3

RNS-FLEXIBLE HARDWARE ACCELERATORS FOR ECC

Elliptic curve cryptography (ECC) serves widely in digital communications where asymmetric cryptography is needed. The elliptic curve scalar multiplication (ECSM) is the core operation in protocols of ECC applications. Two bases of n moduli are needed in RNS implementations of the ECSM. For each base, the number n of moduli is chosen so that the range1 of the base is greater than the size of the underlying finite field of the curve. A virtual channel (VC) is associated with one modulus per RNS base. Therefore, the RNS implementations of the ECSM require n VCs. Physical channels (PCs) are hardware supports of the RNS computations. In current RNS implementations of the ECSM, the used number q of PCs is equal to the number n of VCs; see, for example [NMSK01, SFM + 09, Gui10, BM14]. In other words, each PC is the hardware support of RNS computations over one modulus per RNS base. RNS-flexible implementations of the ECSM are proposed in this chapter. The flexibility is to say that the ECSM is implemented using q PCs, q varying between all divisors of n.

In the literature of hardware implementations of ECC over prime fields, the term flexibility embodies two meanings that are di erent from the one given in this chapter. The first meaning concerns hardware implementations able of supporting two di erent asymmetric cryptosystems such as ECC and RSA (for example [START_REF] Batina | Flexible hardware design for RSA and elliptic curve cryptosystems[END_REF]) or ECC and hyperelliptic curve cryptography (HECC) (for example [START_REF] Batina | Flexible hardware architectures for curve-based cryptography[END_REF]). The second meaning concerns hardware implementations of ECC with two or more underlying prime fields; see, for example [START_REF] Orlando | A scalable GF(p) elliptic curve processor architecture for programmable hardware[END_REF][START_REF] Alrimeih | Fast and flexible hardware support for ECC over multiple standard prime fields[END_REF].

The meaning of the term flexibility in this chapter is di erent from the ones mentioned above and is put this way: For a given underlying prime field, the ECSM is implemented using an adaptable (that is, flexible) quantity of hardware resources. The flexibility of the hardware-resource quantity is achieved by using q PCs, where q is a divisor of n.

PC 1,1 PC 1,2 PC 1,3 PC 1,4 PC 2,1 PC 2,2 PC 2,3 PC 2,4 PC 3,1 PC 3,2 PC 3,3 PC 3,4 PC 4,1 PC 4,2 PC 4,4 PC 4,4 1
The q = 16 PCs run in parallel.

PC i,j

VC i,j 1 One VC is mapped onto each PC.

Figure 3.1 -Decomposition of the numbers n of VCs and q of PCs in usual RNS implementations of the ECSM, that is, q = n. In this example, q = n = 16. Computations related to one VC is performed on each PC.

PC 1,1 PC 1,2 PC 1,3 PC 1,4
The q = 4 PCs run in parallel. The number n of VCs does not change when using fewer PCs. That means n/q VCs are mapped onto each PC. Let consider a typical example of a prime field of 256-bit elements and two RNS bases of 16 moduli, each of size 17 bits. 16 VCs are needed to cover the full size of the field. The ECSM can be implemented using q oe {1, 2, 4, 8, 16} PCs. Figure 3.1 depicts the decomposition of the numbers of VCs and PCs in usual RNS The adaptability of the hardware-resource quantity used for the flexible ECSM implementation makes the latter particularly suitable for integrated circuits with limited hardware resources. Besides, the RNS flexibility of the ECSM implementation provides circuit designers with several hardware resources vs. performance trade-o s to choose from. This chapter is organized as follows. Additional notations are introduced in Section 3.1. The flexibility of the BE by Kawamura et al. (KBE) [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF] and the hierarchical base extension (HBE) [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF] is shown in Sections 3.2 and 3.3 respectively. Then, the flexible ECSM is presented in Section 3.4. The chapter is concluded in Section 3.5.

Notations and Definitions

Definitions and additional notations are introduced besides the two-dimension notations presented in Chapter 2.

• The number n of VCs is equal to the number of moduli per RNS base. This number is the same independently of the performed flexible implementation. Let us recall that n = rc.

• The number of PCs used for a specific implementation of the BE or the ECSM is denoted q, q being a divisor of the number n of VCs (hence q AE n). The number q of PCs varies with the performed flexible implementation.

• The term flexibility means an adaptable number q of PCs can be used to implement a BE (either KBE or HBE) or an ECSM. If n is a perfect power, that is, n = s a , then our RNS implementation can be performed on q oe {1, s, s 2 , . . . , s a } PCs.

Flexible Kawamura Base Extension

This section presents how we implemented the flexible KBE. We first show that Algorithm 11 of KBE [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF] can be adapted to run on a flexible number q of PCs. Then, the adaptation of the cox-rower architecture [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF] to use q PCs is presented. FPGA implementations using high-level synthesis (HLS) are presented at last.

Algorithmical Description of the Flexible KBE

Algorithm 13 describes the mapping of the rc VCs onto the q PCs from Algorithm 11 of KBE. Triple nested loops bounded by rc/q, q/c and c at lines 1-3 and 10-12 in Algorithm 13 now replace the double nested loops bounded by r and c at lines 1-2 and 9-10 in Algorithm 11. The nested loops bounded by q/c and c at lines 2-3 and 11-12 of Algorithm 13 describe the q PCs running in parallel. The loops bounded by rc/q at lines 1 and 10 describe the mapping of rc/q VCs onto each of the q PCs, one VC at a time.

The computations performed within the various loops of Algorithm 13 and Algorithm 11 are the same. Lines 5-9 of Algorithm 13 are exactly lines 4-8 of Algorithm 11 and correspond to the computations performed by the cox unit. These lines are not a ected by the new description (q PCs are used instead of rc PCs) because the behavior of the cox is independent of the number of PCs.

Architecture of the Flexible KBE

The architecture of the flexible KBE is adapted from the cox-rower architecture [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF]. Figure 3.3 depicts the architecture of the flexible KBE for q = 4 PCs. Each memory i,j (i = 1, 2 and j = 1, 2 in our example) stores the precomputations corresponding to rc/q VCs. An additional signal (not represented in Figure 3.3) indicates the running VC on the PC at a time. There is one rower per PC, dedicated to computations over rc/q moduli per RNS base, one at a time. The computations performed by the rowers are of the form g Ω (g + a ◊ b + f ) mod m i,j or mod m Õ i,j as in the original cox-rower, with the operands a, b, f and g being of size the width w of the PCs. The arithmetic processing performed by the rower is depicted in Figure 3.4. The first multiplier and adder allow to perform g +a◊b+f , the value of g being added only when an accumulation is being performed (for example line 13 of Algorithm 13). The remaining multipliers and adders allow to reduce mod m i,j or mod m Õ i,j the result of g + a ◊ b + f using the reduction method specific to Algorithm 13: Flexible KBE BE MaeM Õ (x) adapted from [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF]. The function f (v, i) is given by f (v, i) = q c (v ≠ 1) + i. Input: x m i,j for all i, 1 AE i AE r and j, 1 AE j AE c; ‡ = 0 or 0.5 Precomp.:

|M ≠1 i,j | m i,j , |M i,j | m Õ k,l , | ≠ M | m Õ k,l , for all i, k, 1 AE i, k AE r and j, l, 1 AE j, l AE c Output: x m Õ k,l for all k, 1 AE k AE r and l, 1 AE l AE c 1 for v Ω 1 to rc/q do 2 for i Ω 1 to q/c parallel do 3 for j Ω 1 to c parallel do 4 ' x m f (v,i),j Ω - - - - - x m f (v,i),j ◊ - - -M ≠1 f (v,i),j - - - m f (v,i),j - - - - - m f (v,i),j 5 for i Ω 1 to r do 6 for j Ω 1 to c do 7 ‡ Ω ‡ + trunc(' xm i,j ) 2 w 8 h i,j Ω Â ‡Ê 9 ‡ Ω ‡ ≠ h i,j 10 for v Ω 1 to rc/q do 11 for k Ω 1 to q/c parallel do 12 for l Ω 1 to c parallel do 13 x m Õ f (v,k),l Ω - - - - -x m Õ f (v,k),l + ' x m i,j ◊ |M i,j | m Õ f (v,k),l + h i,j ◊ | ≠ M | m Õ f (v,k),l - - - - - m Õ f (v,k),l
pseudo-Mersenne numbers described in Subsection 1.2.3.

The execution of KBE using the flexible architecture is described as follows. The rc multiplications in base M at line 4 of Algorithm 13 are performed by the q rowers running in parallel. Each rower is in charge of rc/q multiplications, one at a time. Similarly to the original cox-rower, the large multiplexer receives the results of the multiplications from the rowers and outputs two buses (left and right). The right bus broadcasts the results inputted to the large multiplexer to the q rowers in order to proceed with the computation of the CRT in base M Õ , with q executions of line 13 (Algorithm 13) at a time. The left bus transfers the results inputted to the large multiplexer to the cox unit which computes the rc bits h i,j and sends them to the q rowers, q bits h i,j at a time, for subtraction of 0 or M .

CTRL rower 1,1 memory 1,1 PC 1,1 rower 1,2 memory 1,2 PC 1,2 rower 2,1 memory 2,1 PC 2,1 rower 2,2

FPGA Implementation Results

Implementation Environment

We implemented Algorithm 13 on a XCZU7EV-FFVC1156 FPGA from Xilinx using Vivado HLS 2019.2. The finite field F p is of 256-bit elements. The PCs are chosen to be 17-bit wide in order to fully exploit the DSP slices in Xilinx FPGAs. Let us recall that the hardwired integer multipliers embedded in the DSP slices in Xilinx FPGAs support 18 ◊ 18 and 18 ◊ 25 bit multiplications in 2's complement. Asymmetric widths for the DSP operands are not supported in implementations leading to results presented in this 94 ≠ Á (with Á < 2 w/2 ), and a, b, f and g are of size w bits. chapter, similarly to the ones in Chapter 2. Each RNS base needs 16 moduli to represent the elements of F p since the size of the moduli is the width of the PCs (17 bits). Algorithm 13 was implemented for all q oe {1, 2, 4, 8, 16} PCs using the same environment and optimization e ort.

Utilization of Hardware Resources

The FPGA implementation results are reported in Table 3.1. The hardware resources and the performance vary depending on the number of PCs used for the flexible KBE implementation. The variations of hardware resources and performance in relation to the increase of the number of PCs are presented in Figure 3.5. The base of comparison taken in this figure is the implementation results for one PC. The numbers of DSPs and BRAMs increase linearly with the number of PCs. In other words, an increase of the number of PCs from q to kq induces an increase with the same factor k in the numbers of DSPs and BRAMs. For example, the KBE implementation with 4 PCs is performed using 12 DSPs, which is 4 ◊ 3 DSPs, the implementation with one PC using 3 DSPs. On the other hand, the number of slices increases less than linearly with the number of PCs, that is, the increase factor is less than k when the number of PCs is increased from q to kq. For example, an increase of the number of PCs from q = 1 to q = 4 results in an increase factor of only 2.1 in the number of slices (107 and 223 slices for q = 1 and 4 PCs respectively).

Number of Cycles and Time Analyses

Let consider the example of the first (group of) loop bounded by 16 (16 VCs corresponding to the 16 moduli per base) in Algorithm 13. Each PC handles 16/q VCs (q PCs are used). Figure 3.6 shows the number of cycles needed by a PC to perform all computations related to the 16/q VCs it handles. For q = 2 and 4, each PC handles 8 and 4 VCs respectively, and runs them one after another. These number of VCs are represented by the 8 columns at the left and 4 columns at the right in Figure 3.6. The 6 boxes of each column symbolize the number of cycles needed by a PC to perform all computations related to one VC. These 6 cycles are typical value of the pipeline depth for our implementation of the arithmetic processing (performed by the rower) presented in Figure 3.4. The loop is pipelined. Hence, at each cycle, the operations related to a new VC starts on the PC; this is symbolized by the one-box height gap between the columns in each of the left and right figures (in Figure 3.6).

For the left figure in Figure 3.6, after 8 cycles (from top to bottom), the computations related to the 8 VCs on one PC have all started. We name these cycles operation cycles Figure 3.5 -Comparison of FPGA implementation results of the flexible KBE (adapted from [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF]) for q oe {1, 2, 4, 8, 16} PCs. Finite fields are of 256-bit elements and the width of the PCs is 17 bits. and their number OC. Therefore, OC = 8. The reader can see that at the right figure in Figure 3.6, OC = 4. Additional cycles are needed by the PC to terminate all computations on its ongoing VCs. These cycles are named wait cycles and their number is denoted WC. In Figure 3.6, WC = 5 in the left and the right figures. This case is the worst scenario, that is, the case where the next loop cannot start until all computations (related to all the VCs) of the current loop are teminated. Ideally, we want WC = 0 because it leads to the minimal value of the total number of cycles for the implementation. However, in our HLS implementations, the achieved WC for the di erent loops are always > 0 though usually better than the worst case.

When the number of PCs increased from q to kq, the OC decreases with a factor k, but the WC remains the same regardless of the number of PCs used. This constancy of the WC prevents the implementations from achieving a reduction with a factor k in the total number of cycles. Consequently, this number of cycles decreases less than linearly, that is, the decrease factor is less than k when the number of PCs increases from q to kq. For example, using q = 4 PCs instead of one PC decreases the number of cycles by a factor of 3.2 (88 cycles for four PCs and 280 cycles for one PC).

The "time" is the product of the period and the number of cycles (to compute the BE), similarly to Section 2.5. The periods achieved by the implementations on the various numbers q of PCs are relatively close. Therefore, the less-than-linear decrease in the total number of cycles (when the number of PCs increases linearly) results in a less-than-linear decrease in the time.

FLEXIBLE HIERARCHICAL BASE EXTENSION

Flexible Hierarchical Base Extension

A description of how we implemented the flexible HBE is presented in this section, similarly to Section 3.2 about the flexible KBE. In addition, the flexible HBE solutions are compared with the flexible KBE ones.

Algorithmical Description of the Flexible HBE

Algorithm 14 presents the mapping of the rc VCs onto the q PCs from Algorithm 12 of HBE. Triple nested loops bounded by rc/q, q/c and c at lines 1-3 and 14-16 in Algorithm 14 replace double nested loops bounded by r and c at lines 1-2 and 12-13 in Algorithm 12. Within these triple loops, the inner loops bounded by q/c and c at lines 2-3 and 15-16 describe the q PCs running in parallel. The outer loops bounded by rc/q at lines 1 and 14 describe the mapping of rc/q VCs on each PC, one VC at a time. For the computation of the super-residues, double nested loops bounded by rc/q and q/c at lines 5 and 6 of Algorithm 14 replace the single loop bounded by r at line 4 of Algorithm 12. The super-residues are now computed by q/c parallel executions of lines 7-9 (of Algorithm 14) at a time, rc/q times. Lines 10-13 of Algorithm 14 remain unchanged regarding lines 8-11 of Algorithm 12 because computations at these lines are not a ected by the change of the number of PCs from rc to q. Indeed, these computations are performed by the cox unit which is independent of the number of used PCs, as in Algorithm 13 of the flexible KBE.

Architecture of the Flexible HBE

The architecture of the flexible HBE is adapted from that of HBE (c = 2) (presented in Subsection 2.3.3) to use q PCs, q being a divisor of rc. Each PC supports rc/q VCs. Figure 3.7 depicts the architecture of the HBE for q = 4 PCs. The number of rowers is reduced to the desired number q of PCs, one rower per PC. The computation of the super-residues involves an accumulation without reduction; see lines 5-9 of Algorithm 14. To be able to perform these accumulations, we split the arithmetic processing performed by the rower of KBE (in Figure 3.4) into two parts: an upper and a lower part. The upper part, depicted in Figure 3.8, performs the operation G Ω G + a ◊ b + f , that is, without reduction. G is of size at most 2w + 1 bits; a, b and f are of size the width w of the PCs. In addition to operations at lines 1-4, 10-16 and 18 in Algorithm 14 which are existent in Algorithm 14: Flexible HBE BE MaeM Õ (x) adapted from [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF]. The function

f (v, i) is given by f (v, i) = q c (v ≠ 1) + i. Input: x m i,j for all i, 1 AE i AE r and j, 1 AE j AE c; ‡ = 0 or 0.5 Precomp.: |M ≠1 i,j | m i,j , |M i,j | m Õ k,l , | ≠ M | m Õ k,l , for all i, k, 1 AE i, k AE r and j, l, 1 AE j, l AE c Output: x m Õ k,l for all k, 1 AE k AE r and l, 1 AE l AE c 1 for v Ω 1 to rc/q do 2 for i Ω 1 to q/c parallel do 3 for j Ω 1 to c parallel do 4 ' x m f (v,i),j Ω - - - - - x m f (v,i),j ◊ - - -M ≠1 f (v,i),j - - - m f (v,i),j - - - - - m f (v,i),j 5 for v Ω 1 to rc/q do 6 for i Ω 1 to q/c parallel do 7 ' x M (f (v,i)) Ω 0 8 for j Ω 1 to c do 9 ' x M (f (v,i)) Ω ' x M (f (v,i)) + ' x m f (v,i), j ◊ m (f (v,i)) f (v,i),j
(without modular reduction)

10 for i Ω 1 to r do 11 ‡ Ω ‡ + trunc(' x M (i) ) 2 w◊c 12 h i Ω Â ‡Ê 13 ‡ Ω ‡ ≠ h i 14 for v Ω 1 to rc/q do 15 for k Ω 1 to q/c parallel do 16 for l Ω 1 to c parallel do 17 ' x m Õ f (v,k),l,i Ω |' x M (i) | m Õ f (v,k),l 18 x m Õ f (v,k),l Ω - - - - -x m Õ f (v,k),l + ' x m Õ f (v,k),l,i ◊ - - -M (i) - - - m Õ f (v,k),l + h i ◊ | ≠ M | m Õ f (v,k),l - - - - - m Õ f (v,k),l
Algorithm 13 of the flexible KBE, the upper part is able to perform the computation of the super-residus. In our HLS implementations, the upper part is carried out by one DSP. The lower part, depicted in Figure 3.9, performs the operation g Ω G mod m, where

FLEXIBLE HIERARCHICAL BASE EXTENSION

CTRL m = 2 w ≠ Á and G is of size at most 2w + 1 bits. At lines 4 and 18 of Algorithm 14, the lower part is used after the upper part in order to perform the needed reduction. At line 17, the lower part is used alone (without the upper part) since only the modular reduction is needed at this line. At line 9 of Algorithm 14 where the super-residues are computed, the lower part is not used to avoid performing a modular reduction. In our HLS implementations, the lower part is carried out by one DSP at the expense of some extra slices.

rower 1,1 memory 1,1 PC 1,1 rower 1,2 memory 1,2 PC 1,2 rower 2,1 memory 2,1 PC 2,1 rower 2,2 memory
The behavior of the architecture of the flexible HBE is similar to that of HBE and is described as follows. Line 4 of Algorithm 14 is performed on the q PCs, q parallel computations at a time, rc/q times. Then, the super-residues are computed through the rc multiplications and additions, q/c operations running in parallel at a time. The superresidues are broadcasted to the rowers by the two right buses at the output of the large ≠ Á (with Á < 2 w/2 ), g is of size w bits, and G of size at most 2w + 1 bits. multiplexer, similarly to the broadcast in HBE architecture (see Subsection 2.3.3). The left bus sends the super-residues values to the cox unit which computes the values h i and send them to the rowers for the subtractions at line 18 (0, M , 2M and 3M when c = 2). The rc computations of lines 17 and 18 of Algorithm 14 are performed on the q PCs, q parallel computations at a time, rc/q times.

FLEXIBLE HIERARCHICAL BASE EXTENSION

FPGA Implementation Results

Implementation Environment

The flexible HBE (c = 2) was implemented with the same environment and optimization e ort as the flexible KBE was (Subsection 3.2.3). The considered finite field F p is also of 256-bit elements and the PCs 17-bit wide. Algorithm 14 of the flexible HBE was implemented using q oe {2, 4, 8, 16} PCs. Owing to the architecture of HBE, the number of PCs needs to be greater or equal to c (the super-residues are formed by combining c residues). Therefore, using one PC for the implementation of the flexible HBE (c = 2) was not possible.

Utilization of Hardware Resources and Time

The FPGA implementation results are reported in Table 3.2. Figure 3.10 depicts the evolution of the numbers of DSPs, BRAMs, slices and cycles, and the time. The base of comparison is the implementation results obtained for q = 2 PCs (the flexible HBE cannot be implemented for q = 1 PC). An increase in the number of PCs from q to kq results in an increase of factor k in the numbers of DSPs and BRAMs. For example, HBE solution with four PCs uses 8 DSPs and 4 BRAMs, which is twice the number of DSPs and BRAMs used by HBE solution with two PCs (4 DSPs and 2 BRAMs). The number of slices increases less than linearly in relation to the increase of the number of PCs. Similarly to the flexible KBE and for the same reason (WC > 0; see Subsection 3.2.3), the number of cycles of the flexible HBE solutions decreases less than linearly in relation to the increase of the number of PCs. This less-than-linear decrease in the number of Table 3.2 -HLS implementation results on a XCZU7EV-FFVC1156 FPGA for the flexible HBE (adapted from [DBT19]) using q oe {2, 4, 8, 16} PCs. Finite fields are of 256-bit elements and the width of the PCs is 17 bits. same for the two BEs. For all q oe {2, 4, 8, 16}, HBE is 33% smaller than KBE in DSPs. However, in most cases, HBE solutions require more slices than KBE ones; this is due to the fact that only one DSP is used in our HLS implementations of the lower part of the arithmetic processing performed by the rower at Figure 3.9 (see Subsection 3.3.2). For example, for q = 4 PCs, the HBE solution costs 23% more slices than the KBE one. This extra cost in slices amounts to 35% for q = 8 PCs. Note also that for q = 16 PCs, the HBE solution is 2% smaller in slices besides being 33% smaller in DSPs and 9% faster than the KBE one. Overall, the extra costs in slices of HBE solutions are well compensated by the gains in DSPs. Besides, HBE solutions are faster than KBE ones for all q oe {2, 4, 8, 16} PCs.

When increasing the number of PCs from q to kq, the decrease factor in the number of cycles of HBE is smaller than that of KBE. For example, by using four PCs instead of two (that is, double the number of PCs), the number of cycles of the HBE solution is reduced by 35% while that of the KBE solution is reduced by 42%. This result is to be expected since in Algorithm 14 of HBE an additional (group of) loop is introduced (compared with KBE)-the loop for the computation of the super-residues-, resulting in an augmentation of the total WC. The consequence is that the gain in time of HBE compared with KBE decreases as the number of PCs increases. In other words, the fewer PCs are used, the greater is the time gain of HBE solutions compared with KBE ones. Nevertheless, HBE solutions remain faster than KBE ones for all considered numbers of PCs.

RNS-FLEXIBLE HARDWARE ACCELERATORS FOR ECC

q = 1 q = 2 q = 4 q = 8 q = 16 200 400 600 800 1000 time (ns) KBE HBE q = 1 q = 2 q = 4 q = 8 q = 16 50 100 150 200 250 nb. cycles KBE HBE q = 1 q = 2 q = 4 q = 8 q = 16 0 8 16 24 32 40 48 nb. DSPs KBE HBE q = 1 q = 2 q = 4 q = 8 q = 16 0

Flexible Elliptic Curve Scalar Multiplication

This section presents how we implemented the flexible ECSMs from the flexible BEs presented in the two previous sections. First, the main steps between the ECSM and the BE are described. Then, FPGA implementation results of the flexible ECSMs using KBE and HBE are presented. The results of the two flexible ECSMs (with KBE and HBE) are compared with each other, and with FPGA implementation results of the ECSM from the literature.

BE mod p reduction DBL, ADD {(+, , ⇥) mod p} [u]Q 1 Figure 3
.12 -Hierarchical description of RNS computations of the ECSM. The ECSM is computed from a few hundreds point doublings and additions. If Algorithm 15 of the Mongomery ladder [START_REF] Montgomery | Speeding the pollard and elliptic curve methods of factorization[END_REF] is used, each iteration of its loop requires two dozens basic operations and a dozen RNS mod p reductions. Each mod p reduction is made of two BEs and a few basic operations. The cost of the ECSM is mainly driven by that of the mod p reduction, which is itself driven by that of the BEs.

Overview of the Flexible ECSM

Hierarchy of the ECSM

The RNS computation of the ECSM is performed through operations that are presented in an hierarchical way in Figure 3.12. From top to bottom, the RNS computation of the ECSM defined over F p requires an ECSM algorithm, point addition and doubling formulas, an e cient RNS MR algorithm (for the mod p reduction), and a BE algorithm.

The chosen algorithm for computing the ECSM in this thesis is the Montgomery ladder [START_REF] Montgomery | Speeding the pollard and elliptic curve methods of factorization[END_REF], recalled in Algorithm 15. At each bit of the scalar, a point doubling and addition are performed. In other words, the arithmetic operations at each iteration are the same regardless of the value of the scalar bit. The constancy of the number of operations is an advantage in terms of computation protection 2 . There is an extra cost attached to Montgomery ladder compared with other ECSM algorithms such as the double-andadd algorithm. This extra cost is due to the fact that a point doubling and addition are performed at each iteration. The number of point doublings and additions needed to perform an ECSM depends on the bit size of the underlying finite field of the curve. In the current standards (see, for example [ndlsdsd11, oST13]), a few hundreds point doublings Algorithm 15: Montgomery ladder algorithm [START_REF] Montgomery | Speeding the pollard and elliptic curve methods of factorization[END_REF] Input: Q a point of the elliptic curve E Fp u an integer written in binary representation as u s≠1 u s≠2 ...u 0 Output:

Q 1 = [u]Q 1 Q 1 Ω O; Q 2 Ω Q 2 for i Ω s ≠ 1 to 0 do 3 if u i = 0 then 4 Q 1 Ω [2]Q 1 ; Q 2 Ω Q 1 + Q 2 5 else 6 Q 2 Ω [2]Q 2 ; Q 1 Ω Q 1 + Q 2 7 return Q 1 Table 3.4 -Generalized
Q 1 + Q 2 [2]Q 1 X Q 1 +Q 2 = ≠4bZ Q 1 Z Q 2 (X Q 1 Z Q 2 + X Q 2 Z Q 1 ) +(X Q 1 X Q 2 ≠ aZ Q 1 Z Q 2 ) 2 Z Q 1 +Q 2 = x Q (X Q 1 Z Q 2 ≠ X Q 2 Z Q 1 ) 2 X [2]Q 1 = (X Q 1 2 ≠ aZ Q 1 2 ) 2 ≠ 8bX Q 1 Z Q 1 3 Z [2]Q 1 = 4Z Q 1 (X Q 1 3 + aX Q 1 Z Q 1 2 + bZ Q 1 3 )
Table 3.5 -Steps to compute point addition and doubling formulas from [START_REF] Brier | Weierstraß elliptic curves and side-channel attacks[END_REF][START_REF] Izu | A fast parallel elliptic curve multiplication resistant against side channel attacks[END_REF] reported in Table 3.4.

Q 1 + Q 2 [2]Q 1 R = X Q 1 Z Q 2 + X Q 2 Z Q 1 E = 2X Q 1 Z Q 1 S = X Q 1 X Q 2 F = X Q 1 2 L = Z Q 1 Z Q 2 G = Z Q 1 2 D = RL H = ≠4bG J = R 2 ≠ 4SL I = aG X Q 1 +Q 2 = ≠4bD + (S ≠ aL) 2 X [2]Q 1 = EH + (F ≠ I) 2 Z Q 1 +Q 2 = x Q J Z [2]Q 1 = 2E(F + I) ≠ GH
and additions are needed to perform an ECSM using the Montgomery ladder.

The formulas used for point addition and doubling in our ECSM implementations are from [START_REF] Brier | Weierstraß elliptic curves and side-channel attacks[END_REF][START_REF] Izu | A fast parallel elliptic curve multiplication resistant against side channel attacks[END_REF] (in projective coordinates) because they are applicable to arbitrary curves in short Weierstraß equation. These formulas and the steps to compute them are respectively reported in Tables 3.4 and 3.5. The reader can see from the computation

FLEXIBLE ELLIPTIC CURVE SCALAR MULTIPLICATION

Algorithm 16: RNS Montgomery reduction algorithm [START_REF] Posch | Modulo reduction in residue number systems[END_REF] Input:

x M , x M Õ Precomp.: p M Õ , (≠p ≠1 ) M , (M ≠1 ) M Õ Output: s M and s M Õ where s = (xM ≠1 ) mod p 1 q M Ω x M ◊ (≠p ≠1 ) M 2 q M Õ Ω BE MaeM Õ (q M ) 3 r M Õ Ω x M Õ + q M Õ ◊ p M Õ 4 s M Õ Ω r M Õ ◊ (M ≠1 ) M Õ 5 s M Ω BE M Õ aeM (s M Õ )
steps in Table 3.5 that each iteration of the loop of Algorithm 15 of the Montgomery ladder is made of multiplications, additions and subtractions mod p (the operations are performed in the underlying finite field F p of the curve). The main cost of these operations in RNS comes from the mod p reduction. Indeed, the cost of the RNS mod p reduction is quadratic in EMMs while that of multiplications, additions and subtractions is linear in EMMs; see Section 1.3.

We choose to perform the mod p reduction with the state-of-the-art algorithm from Posch and Posch [START_REF] Posch | Modulo reduction in residue number systems[END_REF], recalled in Algorithm 16. This algorithm comprises two BEs (at lines 2 and 5), and some multiplications and additions (at lines 1, 3 and 4). The cost of Algorithm 16 comes mainly from the two BEs. Some precomputations of Algorithm 16 can be combined with some of the BE algorithm in use, as have shown Gandino et al. [GLP + 12] and Guillermin [START_REF] Guillermin | A high speed coprocessor for elliptic curve scalar multiplications over F p[END_REF]. These combinations allow to reduce the number of multiplications between the input residues and the precomputations. We use these optimizations in our implementations.

In summary, the ECSM can be viewed as composed of BEs and basic operations (multiplications, additions and subtractions) outside the BEs. Therefore, a flexible implementation of the ECSM is performed through flexible BEs and flexible basic operations.

Algorithmical Description

Since the ECSM is made of BEs and basic operations, an algorithmical description of the flexible basic operations is provided in addition to the algorithmical descriptions of the flexible BEs (KBE and HBE) presented in Subsections 3.2.1 and 3.3.1. Let x and y be two large integers. Algorithm 17 describes the RNS computation in base M of s = x ù y using q PCs, where the symbol ù stands for any of the basic operations-multiplication, addition and subtraction. The inner loops bounded by q/c and c at lines 2 and 3 describe see, for example Tables 3.6 and 3.8 for the occupancies of BRAMs in our flexible ECSM implementations. Although using the same hardware resources (in DSPs and BRAMs), the solutions of the flexible ECSMs over F p 1 and F p 2 would not present the same performance. Indeed, the solution of the flexible ECSM over F p 2 would be slower since more computations have to be performed per PC (twice VCs are mapped onto each PC).

The flexible multi-level-security ECSMs were not implemented. The FPGA implementation results presented in the next subsection only concern the flexible ECSMs over a single finite field.

FPGA Implementation Results

We implemented the flexible ECSMs using the same environment as the flexible BEs. The ECSMs using KBE and HBE are respectively called ECSM-KBE and ECSM-HBE. Similarly to the flexible BEs, the considered finite field F p is of 256-bit elements and the PCs are 17-bit wide. Also, the flexible ECSM-KBE was implemented for q oe {1, 2, 4, 8, 16} PCs and the flexible ECSM-HBE for q oe {2, 4, 8, 16} PCs. Similarly to the flexible HBE, the flexible ECSM-HBE was not implemented for q = 1 PC owing to HBE architecture (at least 2 PCs are required to implement HBE c = 2).

Flexible ECSM-KBE

FPGA implementation results of the flexible ECSM-KBE are reported in Table 3.6. The hardware resources and the performance vary depending on the number of PCs used for the implementation. The resource and performance variations in relation to the number of PCs are depicted in Figure 3.13. These variations are similar to the ones observed for the flexible KBE. The numbers of DSPs and BRAMs increase linearly with the number of PCs, that is, they increase with a factor k when the number of PCs increases from q to kq. On the other hand the number of slices increases less than linearly with the number of PCs, that is, it increases with a factor less than k when the number of PCs increases from q to kq. For example, using four PCs instead of one PC causes a 4 times increase in the numbers of DSPs (12 instead of 3) and BRAMs (4 instead of 1) but only a 1.4 times increase in the number of slices (4432 instead of 3120).

The variations of the number of cycles and the time are also similar to the ones observed for the flexible KBE. The number of cycles and the time decrease less than linearly in relation to the increase of the number of PCs. In other words, the number of cycles and the time decrease with a factor less than k when the number of PCs increases from q to kq. As explained for the flexible KBE, the less-than-linear decrease in the number of cycles results from the various WCs being > 0 in our HLS implementations (see Part "Number of Cycles and Time analyses" in Subsection 3.2.3). Since the periods of the implementation solutions (for the various numbers of PCs) are close, the less-than-linear decrease in the number of cycles results in a less-than-linear decrease in the time. For instance, when the number of PCs is increased from one to four, the time decreases by a factor 3.0, from 11.2 ms to 3.7 ms.

One BRAM is allocated to each PC. Each BRAM contains precomputations related to the rc/q VCs that are mapped onto the PC it is allocated to. The total number of precomputations related to all the rc VCs does not vary with the number of PCs. The precomputations are equally shared between the BRAMs of the PCs in a way that each precomputation can be accessed locally, that is, by the rower of the same PC. The more PCs are used, the lesser each BRAM is occupied. The occupancy of one BRAM is reported in Table 3.6 for the various number of used PCs. These occupancies are the ceils of the values computed by the formula nb. stored bits 36000 bits ◊ 100.

(3.1)

The denominator is the BRAM size in the Xilinx 7-series FPGAs, that is, 36 Kb [Xil19a, p. 14] (two RAMs of 18 Kb each). The reader can see that the BRAMs are not fully occupied regardless of the number of PCs.

Since the used hardware resources di er depending on the number of PCs of the

Flexible ECSM-HBE

FPGA implementation results of the flexible ECSM-HBE are reported in Table 3.8. Similarly to the flexible ECSM-KBE, the hardware resources and the performance vary depending on the number of PCs used for the implementation. Figure 3.14 depicts these variations. Similarly to the flexible HBE, the comparison base of the variations is the implementation results obtained for two PCs (ECSM-HBE implementation is not possible for q = 1 PC). Again, the numbers of DSPs and BRAMs increase linearly with the number of PCs while the number of slices increases less than linearly. For instance, using four PCs instead of two PCs results in a 2 times increase in the numbers of DSPs (8 instead of 4) and BRAMs (4 instead of 2) but only a 1.1 times increase in the number of slices (4851 instead of 4307).

Similarly to the flexible BEs and ECSM-KBE, the number of cycles and the time of the flexible ECSM-HBE solutions decrease less than linearly in relation to the increase of the number of PCs. The various WCs > 0 account for the less-than-linear decrease in the number of cycles (see Part "Number of Cycles and Time analyses" in Subsection 3.2.3). At its turn, the less-than-linear decrease in the number of cycles results in a less-than-linear decrease in the time (the periods of the implementation solutions for the various numbers of PCs are close). For example, when the number of PCs increases from two to four PCs, the time decreases by a factor 1.4 (4.3 ms for two PCs and 3.0 ms for four PCs).

One BRAM is allocated to each PC, similarly to the flexible ECSM-KBE. The BRAM of each PC contains precomputations related to the rc/q VCs mapped onto the PC. All 3.8 for the di erent number of used PCs. The BRAM occupancy is computed using the formula at Equation 3.1, similarly to the flexible ECSM-KBE. Again, the BRAMs are also not fully occupied in the flexible ECSM-HBE implementation.

The flexible ECSM-HBE implementation results according to the introduced metrics of area vs time trade-o s are reported in Table 3.9. Similarly to the flexible ECSM-KBE results, the flexible ECSM-HBE trade-o s in DSPs ◊ time and BRAMs ◊ time are better when implementations are performed on fewer PCs. The reverse is true for the slices ◊ time trade-o , except for q = 16 PCs. For q = 16 PCs, the HLS tool uses much more LUTs, leading to much more slices and resulting in a much greater slices ◊ time trade-o (we recall that a slice is made of LUTs, FFs and other logic elements such as a small multiplexer). Overall, the area vs. time trade-o s are better when the ECSM-HBE is implemented with fewer PCs. As for the flexible ECSM-KBE, this result is not surprising since the WCs being > 0 have less impact on the time of on-few-PCs implementations than on that of on-many-PCs implementations.

To summarize, when the number of PCs increases, the hardware resources also increase (linearly in DSPs and BRAMs and less than linearly in slices) while the time decreases less than linearly. The flexible ECSM-HBE solutions have their best area vs. time trade-o s when they are implemented using few PCs. ECSM-HBE solutions are faster than ECSM-KBE ones for all q oe {2, 4, 8, 16} PCs. For example, the ECSM-HBE solution is 19% faster than the ECSM-KBE one for q = 4 PCs. For q = 2 PCs, the gain in time amounts to 31%. The number of used BRAMs remains the same for ECSM-HBE and ECSM-KBE. Similarly to what has been observed for the BEs, ECSM-HBE solutions are 33% smaller than ECSM-KBE ones in DSPs for all q oe {2, 4, 8, 16} PCs. However, there is a small extra cost in slices for ECSM-HBE. For example, ECSM-HBE costs 9% more slices than ECSM-KBE for q = 4 PCs. The maximum extra cost in slices for ESCM-HBE solutions is 23%, reached for q = 2 PCs. Globally, the extra costs in slices for ECSM-HBE solutions are overly compensated by their gains in DSPs, in addition to ECSM-HBE solutions being faster than ECSM-KBE ones for all q oe {2, 4, 8, 16} PCs. Consequently, the area vs. time trade-o s are in favor of the flexible ECSM-HBE for all q oe {2, 4, 8, 16} PCs.

Let us recall that the decrease factor in the number of cycles in HBE is smaller than the one in KBE when the number of PCs increases from q to kq (see Part "Comparison Flexible KBE vs. Flexible HBE" in Subsection 3.3.3). This result induces a decrease factor in the number of cycles in ECSM-HBE solutions smaller than the one in ECSM-KBE solutions when the number of PCs increases. For example, by using four PCs instead of two PCs, the number of cycles of the ECSM-HBE solution is decreased by 36% while that of the ECSM-KBE solution is decreased by 43%. Consequently, the gain in time of ECSM-HBE solutions compared with ECSM-KBE ones decreases when the number of PCs increases. In other words, the fewer the PCs, the greater the gain in time of ECSM-HBE solutions compared with ECSM-KBE ones. Considering that the best area vs. time trade-o s are obtained for ECSM implementations using fewer PCs regardless of the chosen BE, this result can also be put in this way: The better is the area vs. time trade-o of the ECSM for each BE, the faster are ECSM-HBE solutions compared with ECSM-KBE ones.

FLEXIBLE ELLIPTIC CURVE SCALAR MULTIPLICATION

q = 1 q = 2 q = 4 q = 8 q = 16 2 4 6 8 10 time (ms) ECSM-KBE ECSM-HBE q = 1 q = 2 q = 4 q = 8 q = 16 500000 1000000 1500000 2000000 2500000 nb. cycles ECSM-KBE ECSM-HBE q = 1 q = 2 q = 4 q = 8 q = 16 0 8 16 24 32 40 48 nb. DSPs ECSM-KBE ECSM-HBE q = 1 q = 2 q = 4 q = 8 q = 16 0

Comparison with Results from the Literature

Comparing implementations results of various works is always tricky because of the numerous parameters that have to be considered. For the comparison to be relevant, parameters have to be the same or close enough. These parameters include the ECSM algorithm as well as the point doubling and addition formulas, the FPGA and its configuration tool. In our case, for each to-be-compared-with result from the literature, the flexible ECSM-KBE and ECSM-HBE should be implemented on the same FPGA with the same tool using the same formulas in order to enable a fair comparison. This work is not possible in the time frame allowed by the PhD grant. Besides, we choose to use HLS for our FPGA implementations because it enhances fast configurations of FPGAs (by focusing almost exclusively on the functionality), and numerous FPGA implementations are required in our demonstration of the RNS flexibility. The selected HLS tool is not compatible with most of the FPGAs used in ECSM implementations from the literature. Therefore, we select a few implementations results that we consider to be the most significant from the literature and show that our results are comparable with them. The FPGA configurations in all selected references were described using a hardware description language (HDL). Configuring an FPGA using an HDL requires much more time than using HLS.

The papers from the literature chosen for the comparison are the following ones, listed below in reverse chronological order. Our ECSM implementations target arbitrary underlying prime field of the curve, similarly to all selected references except [START_REF] Güneysu | Ultra high performance ecc over nist primes on commercial FPGAs[END_REF].

• The first paper by Bajard and Merkiche [START_REF] Bajard | Double level Montgomery cox-rower architecture, new bounds[END_REF] is instructive for our comparison because the authors use RNS for operations in the underlying finite field and they choose the Montgomery ladder as the ECSM algorithm (the same as we do). The main di erence compared with our work comes from the architecture. The reduction algorithm chosen in their work to perform the mod m i in the various rowers is the Montgomery reduction algorithm [START_REF] Montgomery | Modular multiplication without trial division[END_REF]; this is to support their main contribution: avoiding the constraints related to choosing pseudo-Mersenne for the RNS base moduli. For example, there is not enough pseudo-Mersenne moduli of size 17 bits to form the two bases needed to perform modular operation in an underlying finite field of 521-bit elements. Another advantage of using this paper in our comparison is that their implementation was performed on an FPGA from the Xilinx 7-series FPGAs, as ours. Their ECSM solution is the fastest among the ones using RNS.

• In the second paper, Ma et al. [START_REF] Ma | A high-speed elliptic curve cryptographic processor for generic curves over GF(p)[END_REF] do not use RNS, but usual positional number system for operations in the underlying finite field. The ECSM is computed using the window method with randomized jacobian coordinates, as proposed in [START_REF] Möller | Securing elliptic curve point multiplication against side-channel attacks[END_REF]. The main advantage of using this method is that the ECSM is computed with less iterations compared for example to a Montgomery ladder. Besides, the number of point additions is considerably reduced depending on the chosen size of the window. As far as we know, their solution is currently the fastest one for the ECSM over arbitrary prime field reported in the literature.

• The contribution of Guillermin [Gui10] is also instructive in our comparison because RNS is used for operations on the underlying finite field as well as the Montgomery ladder for the ECSM. Besides, the overall core of the architecture in Figure 3.3 used for the flexible ECSM-KBE implementation comes from this paper, itself adapted from the one in [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF]. However, although the arithmetic operation of the rower is the same in [START_REF] Guillermin | A high speed coprocessor for elliptic curve scalar multiplications over F p[END_REF] and this work, we were unable to manually place the registers for pipeline stages (performed automatically by the HLS tool) as in their arithmetic processing due to limitations of the current HLS tools. In addition, the author uses the point addition and doubling formulas from [START_REF] Bajard | Combining leak-resistant arithmetic for elliptic curves defined over F p and RNS representation[END_REF] whereas we use the ones in [START_REF] Brier | Weierstraß elliptic curves and side-channel attacks[END_REF][START_REF] Izu | A fast parallel elliptic curve multiplication resistant against side channel attacks[END_REF].

• The last paper is by Güneysu and Paar [START_REF] Güneysu | Ultra high performance ecc over nist primes on commercial FPGAs[END_REF]. RNS is not used for operations on the underlying finite field. Besides, the authors target NIST pseudo-Mersenne prime fields and design their operators for this purpose; the mod p reductions are then faster than in arbitrary prime fields. The ECSM was implemented using the double-and-add algorithm. The double-and-add algorithm usually costs less point additions than the Montgomery ladder. For fairly chosen scalars, the gain in point additions is about half the bit size of the underlying finite field of the curve. The authors also estimate the results if the window method were used. To keep a fair comparison with real implementation results from the literature and ours, this estimation is not reported in our comparison. The reported results are from Tables 1 and2 of [START_REF] Güneysu | Ultra high performance ecc over nist primes on commercial FPGAs[END_REF].

Table 3.11 contains our ECSM implementation results and the ones in the mentioned papers from the literature. Since the used hardware resources di er from one implementation to another, the metrics slices ◊ time, DSPs ◊ time and BRAMs ◊ time are added. The added metrics provide a close evaluation of the gain in time when using more area or vice versa. The smaller the value, the better the area vs. time trade-o . The symbol (ı) in the frequency column of Table 3.11 indicates that the frequencies are the ceils of the period inverses for our implementations, and the ceils of the frequencies for the results from the literature.

The area and the area ◊ time trade-o s of our ECSM solutions, the one in [START_REF] Bajard | Double level Montgomery cox-rower architecture, new bounds[END_REF] and the best one in [START_REF] Ma | A high-speed elliptic curve cryptographic processor for generic curves over GF(p)[END_REF] at line 12 of Table 3.11 are plotted in Figure 3.16. We choose to plot the results in these two references because their FPGA technologies are the closests to ours. Since [START_REF] Bajard | Double level Montgomery cox-rower architecture, new bounds[END_REF] and [START_REF] Ma | A high-speed elliptic curve cryptographic processor for generic curves over GF(p)[END_REF] do not target flexible implementations, their implementation results are plotted near ours for q = 16 PCs.

Our ECSM solutions for all q oe {1, 2, 4, 8} are smaller in DSPs and BRAMs than the ones from [START_REF] Bajard | Double level Montgomery cox-rower architecture, new bounds[END_REF] and [START_REF] Ma | A high-speed elliptic curve cryptographic processor for generic curves over GF(p)[END_REF]. This result demonstrates the usefulness of our flexible ESCM-KBE and ECSM-HBE. The gain in area is compensated by a lost in time, leading to mixed results in area ◊ time trade-o s. For example, our ECSM-HBE solutions for 3.4. FLEXIBLE ELLIPTIC CURVE SCALAR MULTIPLICATION q = 1 q = 2 q = 4 q = 8 q = 16 0 q = 1 q = 2 q = 4 q = 8 q = 16 0 q = 1 q = 2 q = 4 q = 8 q = 16 0 area q = 1 q = 2 q = 4 q = 8 q = 16 0 q = 1 q = 2 q = 4 q = 8 q = 16 0 7000 14000 21000 28000 35000 slices × time

ECSM-KBE ECSM-HBE [BM14] [MLPJ13]

q = 1 q = 2 q = 4 q = 8 q = 16 0 [START_REF] Bajard | Double level Montgomery cox-rower architecture, new bounds[END_REF] and the best one in [START_REF] Ma | A high-speed elliptic curve cryptographic processor for generic curves over GF(p)[END_REF]. ECSM implementations from [START_REF] Bajard | Double level Montgomery cox-rower architecture, new bounds[END_REF][START_REF] Ma | A high-speed elliptic curve cryptographic processor for generic curves over GF(p)[END_REF], and generally from the literature, are not flexible. q = 2 PCs are 39% better in DSPs ◊ time trade-o than the ones in [START_REF] Bajard | Double level Montgomery cox-rower architecture, new bounds[END_REF], but 18% not as good as the ones in [START_REF] Ma | A high-speed elliptic curve cryptographic processor for generic curves over GF(p)[END_REF] regarding the same metric. In BRAMs ◊ time trade-o , our ECSM-HBE solutions for q = 2 PCs are 12% better than the ones in [START_REF] Bajard | Double level Montgomery cox-rower architecture, new bounds[END_REF], but 55% not as good as the ones in [START_REF] Ma | A high-speed elliptic curve cryptographic processor for generic curves over GF(p)[END_REF]. Our ECSM solutions are larger in slices than the ones in [START_REF] Bajard | Double level Montgomery cox-rower architecture, new bounds[END_REF][START_REF] Ma | A high-speed elliptic curve cryptographic processor for generic curves over GF(p)[END_REF], resulting in slices ◊ time trade-o s in their favor. Nevertheless, our ECSM-KBE and ECSM-HBE are flexible, and our best ECSM solutions are comparable in area ◊ trade-o s with the best ones from the literature, notably [START_REF] Bajard | Double level Montgomery cox-rower architecture, new bounds[END_REF][START_REF] Ma | A high-speed elliptic curve cryptographic processor for generic curves over GF(p)[END_REF].

The implementations results from [START_REF] Guillermin | A high speed coprocessor for elliptic curve scalar multiplications over F p[END_REF][START_REF] Güneysu | Ultra high performance ecc over nist primes on commercial FPGAs[END_REF] are instructive but the comparison with our results is di cult. The FPGA used in our work is not from the same manufacturer as the one used in [START_REF] Guillermin | A high speed coprocessor for elliptic curve scalar multiplications over F p[END_REF]. Therefore, any conclusion is di cult to draw, for example from the gain in DSPs ◊ time (their DSPs are smaller) or the loss in BRAMs ◊ time. It is also hard to conclude from the results in [START_REF] Güneysu | Ultra high performance ecc over nist primes on commercial FPGAs[END_REF] because they restrict the underlying finite field F p of the curve to be NIST prime fields where the mod p reduction is faster than in arbitrary prime fields; the mod p reduction is costly (approximately two BEs) in our implementations. Nevertheless, it seems safe to assume that the results from [START_REF] Guillermin | A high speed coprocessor for elliptic curve scalar multiplications over F p[END_REF][START_REF] Güneysu | Ultra high performance ecc over nist primes on commercial FPGAs[END_REF] are equivalent to the ones from [START_REF] Bajard | Double level Montgomery cox-rower architecture, new bounds[END_REF][START_REF] Ma | A high-speed elliptic curve cryptographic processor for generic curves over GF(p)[END_REF] with which we compared our results.

Overall, most of our ECSM solutions are smaller than the ones from the literature. The comparison results are mixed in terms of area vs. time trade-o s. Our best ECSM solutions are comparable with the best ones from the literature, in addition to our implementations being flexible.

Conclusion

The RNS flexibility of the BE has been proven in this chapter. We have demonstrated that the BE operation can be implemented using a flexible number of PCs, leading to an adaptable utilization of hardware resources. The flexible architectures allow to choose the desired numbers of DSPs and BRAMs to be used for the implementation; their numbers vary linearly with the number of PCs. HLS implementations of the flexible HBE [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF] and KBE [KKSS00] provide several area vs. time trade-o s for the comparison of the two flexible BEs. HBE solutions are faster with better area vs. time trade-o s in all comparable cases.

We have also shown that the ECSM operation is flexible. The flexible ECSM can be implemented using either the flexible HBE or the flexible KBE. With variations of the numbers of DSPs and BRAMs similar to the ones of the flexible BEs, HLS implementations of the flexible ECSM-HBE and ECSM-KBE also provide several area vs. time trade-o s. ECSM-HBE solutions are always faster and present better area vs. time trade-o s than ECSM-KBE ones.

Although our ECSM solutions are slower than the best ones from the literature (most of our solutions are smaller), our best solutions are comparable with the latter in terms of area vs. trade-o s. For example, our ECSM-HBE solutions are 39% smaller than results in [START_REF] Bajard | Double level Montgomery cox-rower architecture, new bounds[END_REF] but 18% larger than results in [START_REF] Ma | A high-speed elliptic curve cryptographic processor for generic curves over GF(p)[END_REF] in DSPs ◊ time. Our ECSM implementations present the main advantage of being flexible compared with the ones from the literature. Consequently, the ECSM can be implemented so that the quantity of used hardware resources is adaptable and small. Therefore, such implementations can be performed on integrated circuits with limited available hardware resources. Nearly all our solutions are smaller than the ones from the literature, demonstrating the benefit of the flexibility.

CONCLUSION

The work presented in this thesis aims at designing RNS-flexible hardware accelerators for the ECSM operation on FPGA using HLS. In Chapter 1 ECC as the context of this thesis has been presented. We have also presented the ECSM which is the core operation in protocols of ECC applications. The computation of the ECSM over F p involves numerous multiplications, additions and subtractions in F p , and hence numerous mod p reductions. RNS has also been presented in Chapter 1 as well as its advantages such as the independence of multiplications, additions and subtractions between the moduli of an RNS base. Besides, the base extension (BE) has been described and its importance in the RNS mod p reduction has been demonstrated.

Contributions

In Chapter 2 we presented our hierarchical base extension (HBE) proposed in [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF]. HBE proceeds by first computing super-residues which are results of partial CRTs on the residues in the input RNS base. The continuation of the CRT is then carried out on the super-residues in the output RNS base. Compared with the state-of-the-art base extension (KBE) [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF], no additional contraint is needed to form the RNS bases. The theoretical gain introduced by HBE compared with KBE is up to 35%. We also proposed an architecture for HBE [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF], adapted from the cox-rower [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF]. Our architecture preserves the inherent parallelism of RNS with a marginally deeper pipeline than the coxrower. FPGA implementations using HLS show that HBE solutions are always faster (up to 20%), and in nearly all cases smaller (up to 23%) than KBE solutions. HBE solutions present the best area vs. time trade-o in all cases.

In Chapter 3 the flexible HBE and KBE are presented before showing how to use them to obtain flexible ECSMs. We first demonstrated that HBE and KBE are flexible, that is, they can be implemented using a flexible number of PCs. The architectures of HBE [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF] and KBE [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF] are adapted to support this flexibility. The flexibility of the architectures allow us to select the desired numbers of DSPs and BRAMs to be used for the BE implementation. FPGA implementations using HLS show that the flexible HBE solutions are always faster (up to 28%) and 33% smaller in DSPs that the flexible KBE ones. Though most flexible HBE solutions are larger in slices (up to 35%) than the flexible KBE ones, the area vs. time trade-o is in favor of the flexible HBE solutions in all cases.

We showed how to derive flexible ECSMs from the flexible HBE and KBE in the rest of Chapter 3. The derived flexible ECSM-HBE and ECSM-KBE can be implemented using the architectures described for the flexible HBE and KBE respectively. The hardware resources of our flexible ECSMs are adaptable owing to the flexibility of the architectures, similarly to the flexible BEs. FPGA implementations using HLS show that the flexible ECSM-HBE solutions are always faster (up to 31%) and 33% smaller in DSPs than the flexible ECSM-KBE ones. The flexible ECSM-HBE solutions are slightly larger in slices (up to 23%) than the flexible ECSM-KBE ones. Similarly to the flexible BEs, the area vs. time trade-o is always in favor of the flexible ECSM-HBE solutions. For ECSM-HBE solutions and ECSM-KBE ones, the best area vs. time trade-o s are given by implementations with fewer PCs. Compared with the best FPGA implementation results from the literature, nearly all our ECSM-HBE and ECSM-KBE solutions are smaller in DSPs and BRAMs. Although our ECSM solutions are slower than the best ones from the literature (most of our solutions are smaller), the area ◊ time trade-o s of our best solutions are comparable with the latter. For instance, our ECSM-HBE solutions are 39% smaller than the ECSM ones in [START_REF] Bajard | Double level Montgomery cox-rower architecture, new bounds[END_REF] but 18% larger than the ECSM ones in [START_REF] Ma | A high-speed elliptic curve cryptographic processor for generic curves over GF(p)[END_REF] in DSPs ◊ time. The smallness and adaptability of area utilizations in our solutions, obtained thanks to the flexibility, imply that ECSM-HBE and ECSM-KBE can be implemented on integrated circuits with limited available hardware resources.

Perspectives

In Chapter 2 the super-residues in our HBE implementations are results of partial CRTs on c = 2 input residues. The partial CRTs are also possible on other numbers c of input residues. We plan to study the cases c = 3 and 4 and design optimized architectures for HBE.

We mention in Chapter 3 (Subsection 3.4.1) that our flexible ECSM architectures can be used to implement flexible multi-level-security ECSMs. For example, using the same architecture, and hence the same numbers of DSPs and BRAMs, we could implement ECSM-KBE and ECSM-HBE over two di erent finite fields: one of 256-bit elements and the other of 512-bit elements. The number of VCs to be mapped onto each PC for an ECSM over the finite field of 512-bit elements would be twice the one for an ECSM over the finite field of 256-bit elements. We also plan to study this aspect of the flexibility and how to optimize the architectures to support ECSMs over two or more finite fields.

The ECSM algorithm used in our flexible implementations is the Montgomery ladder without any additional protections (for example against DPA). How will behave countermeasures against various side-channel attacks in a context of flexible ECSM implementations is worth a study. d'opérations plus complexes 1 mais sur de plus petites tailles : des centaines de bits pour les courbes elliptiques (ECC) [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF] et hyper-elliptiques (HECC) [START_REF] Cohen | Handbook of Elliptic and Hyperelliptic Curve Cryptography[END_REF] ; ou des dizaines de bits pour la cryptographie post-quantique (PQC) sur des réseaux euclidiens (RE).

La représentation modulaire des nombres, ou RNS pour residue number system [Gar59, ST67, Big14], amène un plus grand parallélisme interne permettant d'accélérer les calculs comme dans RSA et ECC, mais il nécessite un niveau supplémentaire de réductions modulaires. RNS découpe les nombres en petits morceaux dans une base de moduli premiers entre eux deux à deux notés m i . Les calculs s'e ectuent sur les restes modulo les m i dans un canal propre à chaque m i . Ces « petites » réductions modulo chaque m i s'ajoutent aux réductions modulaires à un plus haut niveau sur les nombres complets (p. ex. le modulo p pour des éléments de GF(p)). Dans ce papier, nous nous intéressons seulement aux réductions modulo les m i dans le cadre de l'utilisation de RNS.

Dans le cadre PQC, on utilise des petits corps finis (p. ex. éléments entre 13 et 23 bits) mais pour des calculs sur des polynômes (p. ex. degrés entre 256 et 1024) et des petites matrices (souvent de tailles 2 ◊ 2, 3 ◊ 3 , 4 ◊ 4).

Dans ce papier, nous nous intéressons uniquement aux réductions modulaires pour des tailles de quelques dizaines de bits (pour les moduli de RNS et pour les petits corps utilisés dans PQC-RE). Nous ne traitons pas des réductions pour des plus grands nombres comme ceux utilisés pour RSA et ECC (ceci fera l'objet de travaux futurs).

Les outils actuels de synthèse de circuits n'o rent pas de support très avancé pour la réduction modulaire. Ainsi, nous développons une bibliothèque C dédiée à l'arithmétique modulaire en cryptographie asymétrique utilisable en synthèse de haut niveau (HLS pour high level synthesis). Elle sera distribuée sous licence libre une fois su samment complétée, validée et documentée.

Nous utilisons la HLS pour explorer de nombreux compromis entre les représentations des nombres, les algorithmes de calcul et les architectures matérielles (ce qui est très coûteux en synthèse VHDL ou Verilog). Pour un modulo quelconque (c.-à-d. avec une écriture dense et sans structure comme 5101963 = (10011011101100110001011) 2 ), on utilise principalement les réductions de Montgomery [START_REF] Montgomery | Modular multiplication without trial division[END_REF] et de Barrett [START_REF] Barrett | Communications Authentication and Security Using Public Key Encryption: A Design for Implementation[END_REF]. Pour RE, on utilise plutôt un modulo spécifique avec une décomposition binaire très creuse (comme 8380417 = 2 23 ≠ 2 13 + 1) car la réduction se simplifie beaucoup (voir p. ex. [START_REF] Solinas | Generalized Mersenne numbers[END_REF]). En RNS, on utilise souvent des moduli de la forme m i = 2 w ± c i où w est la taille des mots dans les canaux et les c i des petites constantes, denses, pour des questions de performances (voir p. ex. [START_REF] Crandall | Method and apparatus for public key exchange in a cryptographic system[END_REF]). Ici aussi, cela conduit à des réductions plus e caces que pour des moduli quelconques. En pratique, il y a un compromis entre la forme du modulo, ou des moduli, et le nombre de telles valeurs utilisables. Dans ce papier, nous présentons les résultats de notre bibliothèque pour la réduction modulaire de petits nombres (c.-à-d. d'au plus quelques dizaines de bits, pour RNS ou PQC-RE). Nous comparons expérimentalement l'impact des principaux algorithmes de réduction pour di érentes formes de moduli. Les principaux motifs de calcul de nos applications, utilisés dans ce papier, sont la somme réduite et la somme réduite de produits. Nous évaluons comment se comportent les outils de HLS sur ces motifs de calcul et expérimentons di érentes techniques d'exploration pour di érentes contraintes arithmétiques et architecturales.

Définitions et notations

Pour la suite du papier, nous définissons et utilisons :

m le modulo de taille w bits pouvant avoir plusieurs formes :

-MQ : modulo quelconque avec une écriture dense et sans structure particulière ; -MSC : modulo spécifique à écriture binaire très creuse (p. ex. 3 bits non nuls sur w) ; -MSR : modulo spécifique pour RNS de forme 2 w ± c (où c est petit, c < 2 w/2 ) ; -la réduction modulaire x mod m ou des opérations modulaires (x ù y) mod m avec l'opération ù oe {±, ◊} ; -le motif de calcul: une séquence d'opérations arithmétiques faisant intervenir des réductions modulaires sur des vecteurs de taille N , les motifs étudiés ici sont: -M1 :

q N i=1 x i mod m ; -M2 : q N i=1 x i ◊ y i mod m ;
-deux stratégies sont comparées pour la réduction de séquence d'opérations modulaires :

-RIS : Réduction Intermédiaire Systématique, p. ex.

1 q N i=1 (x i ◊ y i mod m) 2 mod m ;
-RSF : Réduction Seulement à la Fin, p. ex.

1 q N i=1 x i ◊ y i 2
mod m ; -l'opérande de la réduction modulaire peut avoir plusieurs tailles (p. ex. w, w + Álog 2 N Ë, 2w ou 2w + Álog 2 N Ë bits dans nos applications) ; -des données x et y de taille w bits pour les vecteurs des motifs ; -TM le temps total de calcul (en ns) pour obtenir le résultat d'un motif.

Bibliothèque développée

Nous souhaitons aider les concepteurs d'implantations matérielles en cryptographie asymétrique à explorer di érents compromis algorithmes/représentations des nombres/architectures de calcul. Dans ce papier, nous traitons uniquement de la réduction modulo m, un entier d'au plus quelques dizaines de bits, et de son utilisation dans quelques motifs de calcul typiques. Nous travaillons d'abord sur des m « petits » pour PQC et RNS, mais nous compléterons notre bibliothèque pour des moduli plus grands dans l'avenir (p. ex. éléments de GF(p) de quelques centaines de bits). La forme de m influençant beaucoup les algorithmes et les performances, nous avons choisi de supporter :

-des moduli quelconques (MQ), des moduli spécifiques très creux (MSC) utilisés pour PQC et des moduli spécifiques à RNS (MSR) ; -les algorithmes de réduction de Montgomery [START_REF] Montgomery | Modular multiplication without trial division[END_REF] -tout d'abord inclure le fichier parameters.h en ligne 1 afin de « configurer » la bibliothèque pour son application ; -spécifier ses entrées (ici 2 tableaux de N données de taille w bits en word) et ses sorties (ici la somme réduite donc aussi en word) en ligne 4 ; -initialiser l'accumulateur avec la bonne taille en ligne 6 ; -e ectuer son calcul (ici la somme des produits selon la stratégie RSF, donc sans réduction intermédiaire) en lignes 7 et 8 ; -et enfin e ectuer la réduction en appelant la fonction de réduction choisie (ici barrett(res) en ligne 9). L'utilisation est assez simple, puisqu'une fois les spécifications de l'application définies (préparation du fichier parameters.h à partir d'un template fourni), il su t de faire quelques appels de fonctions, utiliser les bons types et éventuellement quelques casts pour s'assurer de la bonne taille des données intermédiaires. Les étiquettes comme acc sur la boucle d'accumulation en ligne 7 du code de la fonction m2_rsf sont utilisées pour spécifier les cibles des directives d'optimisations particulières de l'outil HLS (pipeline, déroulage de boucle, etc.). Nos implantations ont été réalisées avec Vivado HLS 2017.4 [START_REF]Xilinx. Vivado design suite user guide high-level synthesis (UG902)[END_REF] sur un FPGA Artix-7 (xc7a15) de Xilinx. Les résultats présentés ci-dessous ont comme contraintes : une taille de modulo de w oe {13, 17, 23, 30} bits, une taille de vecteurs N oe {10, 20, 40, 100}, une période d'horloge cible de 3 ns et un e ort d'optimisation par défaut (moyen). Nous avons aussi exploré l'impact de directives de pipeline et de déroulage de boucle de l'outil (voir [START_REF]Xilinx. Vivado HLS optimization methodology guide (UG1270)[END_REF]). Nous obtenons ainsi plus de 2400 résultats d'implantations di érentes. Nous présentons ci-dessous un sous-ensemble représentatif pour des raisons de place (d'autres tailles w de modulo dans le cas du motif M2 en version RSF avec N = 20. La figure A.2 présente les résultats pour le meilleur temps de calcul obtenu pour les di érentes combinaisons de directives d'optimisations testées. Pour chaque métrique (temps, surface et compromis surface ◊ temps), les résultats sont normalisés par rapport à la plus grande valeur pour la métrique.

Nous observons que l'algorithme natif utilisé par l'outil HLS lors de l'appel de l'opérateur % est bien moins performant que nos implantations des algorithmes de la littérature. Il n'utilise pas de bloc DSP pour la réduction (uniquement pour l'accumulation des produits q N i=1 x i ◊ y i ), mais il nécessite de nombreux cycles de calcul. Il semble utiliser une boucle avec un nombre d'itérations dépendant de la taille de l'opérande dans nos expérimentations. Il présente donc peu d'intérêt pour nos applications cryptographiques car nos implantations sont toutes bien meilleures.

Les meilleurs résultats obtenus sont clairement pour MSR et MSC. Ceci est parfaitement logique puisque les algorithmes pour les moduli spécifiques utilisent des propriétés particulières permettant de simplifier les calculs (ce qui n'est pas possible pour des MQ). Ainsi, pour des applications RNS, l'algorithme MSR est plus performant que Barrett et Montgomery. Pour PQC, la même conclusion s'impose pour MSC.

Le nombre de cycles d'horloge de nos 4 implantations (Barrett, Montgomery, MSC et MSR) sont proches (et souvent autour de 50% de moins que pour %). Les fréquences obtenues sont proches de la contrainte imposée à l'outil.

Des résultats similaires sont obtenus pour les autres tailles N de vecteurs testées. Notre bibliothèque permet à l'utilisateur d'utiliser le meilleur algorithme de réduction modulaire en fonction du type de modulo utilisé dans son application. Dans le cas d'applications avec des moduli spécifiques, l'utilisation des algorithmes MSC et MSR o re de bien meilleurs résultats. Dans le cas d'applications avec des moduli quelconques, notre bibliothèque confirme que Montgomery est un peu meilleur que Barrett.

Dans la suite, nous ne donnerons plus les résultats pour l'algorithme de réduction natif avec l'opérateur % car il est bien trop lent pour nos applications cryptographiques.

Impact des directives d'optimisation sur la boucle d'accumulation

Nous avons testé plusieurs directives d'optimisation sur la boucle d'accumulation: pipeline correspond au cas où les N itérations sont pipelinées ; unrollk au cas où (N/k) itérations sont e ectuées sur k opérateurs en parallèle. la réduction spécifique de moduli MSR de taille w = 23 bits. Nous comparons di érentes directives de l'outil de synthèse HLS sur la boucle d'accumulation. La première ligne du tableau présente comme référence les résultats sans aucune directive. Chaque produit de la boucle d'accumulation requiert 2 blocs DSP car ils ont 2 opérandes de w = 23 bits, ce qui est plus grand que la taille du multiplieur disponible dans un bloc DSP du FPGA cible (voir [START_REF]Xilinx. Vivado design suite user guide high-level synthesis (UG902)[END_REF][START_REF]Xilinx. 7 series DSP48E1 slice user guide (UG479)[END_REF]). La réduction finale requiert également 2 blocs DSP.

La table A.1 présente les résultats d'implantation du motif M2 RSF avec N = 20 pour

On remarque que les di érentes implantations atteignent quasiment la période cible. En pipelinant, on arrive à diviser par 3 le temps de calcul TM sans changer le nombre de DSP utilisés. On peut encore réduire de

Conclusion

Notre bibliothèque o re un support, assez simple d'utilisation, d'algorithmes de réduction modulaire avancés qui ne sont pas supportés nativement par les outils de HLS actuels.

Elle o re aussi la possibilité de générer des circuits optimisés en temps et en surface pour chaque type de modulo (de forme quelconque ou spécifique). Ceci est particulièrement intéressant pour des applications en cryptographie asymétrique comme ECC en RNS ou PQC.

Nous allons continuer le développement de notre bibliothèque et ajouter d'autres opérations, formes de moduli et motifs de calcul. Nous souhaitons aussi essayer d'autres outils de HLS et fabricants/familles de FPGA.

Dans ce manuscrit de thèse, nous présentons des accélérateurs matériels pour la cryptographie asymétrique avec une utilisation flexible de ressources matérielles. La cryptographie asymétrique est implantée dans de nombreux appareils utilisés au quotidien, comme par exemple les ordinateurs personnels et les téléphones intelligents. Elle sert notamment à échanger des clés secrètes, à signer numériquement des documents, ou encore à s'authentifier par exemple, auprès d'un serveur. Les opérandes dans les cryptosystèmes actuels sont de très grands nombres : par exemple, quelques centaines de bits pour la cryptographie basée sur les courbes elliptiques (ECC) [START_REF] Miller | Use of elliptic curve in cryptography[END_REF][START_REF] Koblitz | Elliptic curve cryptosystems[END_REF] et quelques milliers de bits pour RSA [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF]. Une arithmétique e cace et adaptée aux grands nombres est nécessaire afin d'éviter de trop faibles performances des appareils sur lesquels sont implantés ces cryptosystèmes.

Le système modulaire de représentation des nombres (RNS) [START_REF] Valach | P evod ísel ze soustavy zbytkov˝ch t íd do polyadické soustavy zm nou m itka periody (the translation of numbers from the system of residual classes to a polyadic system by change of scale of period)[END_REF][START_REF] Garner | The residue number system[END_REF] est un système non positionnel dans lequel un grand nombre est représenté par ses restes modulo de petits nombres premiers entre eux deux à deux. L'ensemble de ces petits nombres premiers entre eux constitue une base RNS. Les opérations élémentaires habituelles, à savoir multiplication, addition et soustraction, sont e ectuées entre les petits restes de façon indépendante. Autrement dit, les opérations élémentaires entre de grands nombres sont remplacées par des opérations entre de petits restes. De plus, ces opérations élémentaires peuvent être e ectuées en parallèle. Il n'y a pas de propagation de retenues entre les di érents restes [START_REF] Szabo | Residue arithmetic and its applications to computer technology[END_REF] à cause de l'indépendance des opérations élémentaires entre les restes. E ectuer des opérations élémentaires est donc très e cace en RNS. Ces avantages du RNS ont entraîné ces deux dernières décennies un gain d'intérêt de son usage dans les implantations matérielles de la cryptographie asymétrique. En guise d'exemples, nous citons les travaux [NMSK01, SFM + 09, Gui10, BM14].

Le RNS présente un inconvénient majeur qui est la di culté à e ectuer des réductions modulaires (MR), des divisions et des comparaisons. Cette di culté est due au caractère non positionnel du RNS (l'ordre de grandeur des opérandes est plus di cile à déterminer que dans une représentation positionnelle "classique"). Pourtant, les MR sont nombreuses dans les calculs des cryptosystèmes asymétriques actuels. Par exemple, l'opération de base de RSA est l'exponentiation modulaire. Pour ECC, l'opération de base est la multiplication scalaire (ECSM), qui elle-même se calcule à partir de nombreuses opérations dans des corps finis (ce qui necessite de nombreuses MR). L'extension de base de Kawamura et al. (KBE) [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF] est utilisée dans l'algorithme de MR de l'état de l'art proposé dans [START_REF] Posch | Modulo reduction in residue number systems[END_REF] afin de réduire le coût de ce dernier. L'extension de base (BE) devient une opération cruciale dans les implantations RNS parce que le coût de la MR provient essentiellement du coût des deux BE qui la composent.

Les canaux sont les supports matériels des opérations élémentaires entre les restes modulo les éléments d'une base RNS. Les implantations RNS de la littérature (par exemple, [NMSK01, SFM + 09, Gui10, BM14]) utilisent autant de canaux que d'éléments d'une base nécessaires à la représentation des grandes opérandes. Il en résulte une utilisation d'une quantité de ressources matérielles correspondant à la taille des grandes opérandes. Cette quantité requise constitue un problème dès lors qu'elle est supérieure à celle disponible sur le circuit intégré qu'on veut utiliser. Cette situation peut se présenter lorsque le circuit intégré choisi pour l'implantation du cryptosystème est très petit avec peu de ressources matérielles ou lorsque plusieurs applications non cryptographiques coexistent avec des applications cryptographiques sur un même circuit intégré. En e et, la plupart des circuits intégrés sont principalement utilisés pour des applications non cryptographiques comme par exemple le traitement de signal ou la vision par ordinateur. En tenant compte des ressources matérielles utilisées par ces applications principales, le reste des ressources matérielles sur le circuit intégré peut être insu sant pour implanter le cryptosystème souhaité.

Concevoir des accélérateurs matériels flexibles pour la cryptographie asymétrique permet de résoudre ce problème. Dans ce manuscrit, nous appelons accélérateurs matériels flexibles des accélérateurs matériels dont l'utilisation de ressources matérielles est flexible, c'est-à-dire qui peut être adaptée, pour une même taille des grandes opérandes. On peut donc choisir la quantité de ressources matérielles à utiliser par une implantation d'un cryptosystème asymétrique en fonction de celle disponible sur le circuit intégré. Dans les implantations RNS, de tels accélérateurs peuvent être réalisés en les concevant de façon à ce qu'ils utilisent un nombre de canaux plus petit que celui normalement nécessaire pour les calculs sur les grandes opérandes. Nous appelons canaux physiques (PC) les canaux e ectivement utilisés, et notons q leur nombre. À chaque élément d'une base RNS, nous associons un canal virtuel (VC). Le nombre n de VC est alors le nombre d'éléments nécessaires pour représenter les grandes opérandes.

Contributions

La première contribution de cette thèse est un nouvel algorithme de BE nommé hierarchical base extension (HBE) [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF]. HBE utilise une approche hiérarchique dans le calcul du théorème chinois des restes (CRT). Cette approche se décrit en deux phases. Au cours de la première phase, les restes en entrée sont combinés par paires à l'aide de CRT partiels e ectués dans la base d'entrée. Lors de la seconde phase, la suite du calcul du CRT est e ectuée sur les résultats de ces CRT partiels dans la base de sortie. Le coût théorique de HBE est jusqu'à 35% plus petit que celui de KBE [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF], largement considéré comme la BE de l'état de l'art.

De plus, nous avons proposé une architecture pour HBE [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF]. Cette architecture est adaptée de l'architecture cox-rower de KBE [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF]. Notre architecture préserve le parallélisme naturel du RNS avec un pipeline légèrement plus profond au niveau des rowers. HBE et KBE ont été implantés sur FPGA à l'aide d'outils de synthèse de haut niveau (HLS). Ces implantations visent des tailles de corps typiques de celles utilisées dans les applications de ECC et sont e ectuées pour plusieurs tailles de canaux. Les résultats de ces implantations montrent que HBE est dans tous les cas plus rapide que KBE (jusqu'à 20%), et dans presque tous les cas plus petit (jusqu'à 23%) en surface. HBE présente toujours le meilleur compromis surface/temps. Deux accélérateurs matériels RNS flexibles de l'ECSM constituent la seconde contribution de cette thèse. Dans un premier temps, nous montrons que la BE peut être implantée de façon flexible, et cela pour la BE de l'état de l'art (KBE) [START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF] et la notre (HBE) [START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF]. Les architectures flexibles sont dérivées des architectures de base des deux BE. Le nombre q de PC dans chaque architecture flexible est adaptable, et q est choisi à la conception parmi les diviseurs de n (le nombre de VC). Il en résulte que pour une taille donnée de corps fini, la BE (HBE ou KBE) peut être implantée avec une quantité flexible de ressources matérielles. Le concepteur peut donc choisir le nombre q de PC à utiliser pour une implantation donnée en fonction de la quantité de ressources matérielles dont il dispose sur son circuit intégré. La flexibilité permet d'obtenir plusieurs compromis surface/temps pour l'implantation d'une même opération. HBE et KBE flexibles ont été implantées sur FPGA à l'aide d'outils de HLS. Les résultats d'implantations montrent qu'indépendamment de la BE, lorsque le nombre de PC passe de q à kq, les nombres de DSP et BRAM croissent d'un facteur k. Par contre, le nombre de slices croît d'un facteur plus petit que k. L'augmentation de la surface utilisée induit une diminution du temps, qui décroît d'un facteur plus petit que k. En outre, les résultats de HBE flexible sont plus rapides (jusqu'à 28%) et 33% plus petits en DSP que ceux de KBE flexible, pour un même nombre de PC utilisés. Par contre, les implantations de HBE flexible utilisent plus de slices que celles de KBE flexible (jusqu'à 35%). Toutefois, le compromis surface/temps est toujours en faveur des résultats de HBE flexible.

Dans un second temps, deux ECSM flexibles nommées ECSM-HBE et ECSM-KBE flexibles sont implantées à partir des architectures flexibles des deux BE (HBE et KBE respectivement). Comme pour les BE flexibles, les nombres de DSP et BRAM croissent d'un facteur k lorsque le nombre de PC utilisés passe de q à kq. Aussi, les facteurs de croissance du nombre de slices et de décroissance du temps sont plus petits que k. Les résultats de comparaison des deux ECSM flexibles sont similaires à ceux des deux BE flexibles. Pour un même nombre de PC utilisés, les résultats de ECSM-HBE flexible sont toujours plus rapides (jusqu'à 31%) et 33% plus petits en DSP que ceux de ECSM-KBE flexible. Les résultats de ECSM-HBE flexible sont légèrement plus gros en slices (jusqu'à 23%) que ceux de ECSM-KBE flexible. Comme pour les BE flexibles, les résultats de ECSM-HBE flexible présentent les meilleurs compromis surface/temps. Quoiqu'en compromis surface/temps, nos meilleurs résultats d'implantations sont comparables aux meilleurs résultats de la littérature, la plupart de nos implantations présentent des nombres de DSP et de BRAM bien plus petits. La possibilité d'implanter des ECSM sur des corps de base d'une même taille en utilisant une surface plus petite et adaptable constitue l'apport majeur de la flexibilité.

La troisième contribution de cette thèse est une étude auxiliaire au projet de thèse et rapportée dans [START_REF] Djath | Comparaison d'algorithmes de réduction modulaire en HLS sur FPGA[END_REF]. Le but est d'étudier les meilleures façons d'e ectuer des multiplications modulaires et accumulations sur FPGA à partir d'outils de HLS. Le sujet d'étude est motivé par la présence de nombreuses multiplications modulaires et accumulations dans les implantations RNS des cryptosystèmes asymétriques. Plusieurs paramètres tels que la taille et la forme (générique, spécifique) des moduli ainsi que la stratégie de réduction (réduction intermédiaire ou réduction seulement à la fin) sont étudiés. Nous avons également étudié plusieurs contraintes d'implantation tels que le pipelining et l'unrolling de boucles en fonction des paramètres. Résumé : Les implantations RNS de cryptosystèmes asymétriques actuels utilisent des ressources matérielles correspondant à la taille des opérandes traitées. Dans cette thèse, nous proposons une nouvelle approche dans l'implantation RNS de cryptosystèmes asymétriques qui permet une utilisation flexible de ressources matérielles. Dans un premier temps, un nouvel algorithme d'extension de base est présenté. Les extensions de bases sont, de part leurs coûts, des opérations critiques dans les implantations RNS. Notre nouvel algorithme d'extension de base utilise une approche hiérarchique dans le calcul du théorème chinois des restes. Com-paré à l'algorithme d'extension de base de l'état de l'art, il présente un coût théorique réduit, qui se traduit par un gain en surface et en temps dans nos implantations HLS sur FPGA. Ensuite, nous implantons les deux algorithmes d'extension de base à partir de la nouvelle approche d'implantation RNS. Enfin, des multiplications scalaires utilisant chacune des deux extensions de base sont implantées avec la nouvelle approche. Nos implantations HLS sur FPGA utilisent des ressources matérielles en quantité flexible. De plus, quoique comparables en compromis surface/temps à ceux de l'état de l'art, la plupart de nos résultats sont bien plus petits. Title: RNS-Flexible Hardware Accelerators for High-Security Asymmetric Cryptography Keywords: computer arithmetic, residue number system, flexibility, FPGA hardware implementation.

Abstract: Asymmetric cryptosystems are implemented in RNS using a quantity of hardware resources corresponding to the size of the cryptographic operands. In this thesis we propose a new approach to perform RNS implementations of asymmetric cryptosystems that leads to a flexible utilization of hardware resources. We start with describing a new method to perform base extensions which are crucial operations in RNS implementations of asymmetric cryptosystems. The proposed base-extension method, based on a hierarchical approach for computing the Chinese remainder theorem, introduces a reduc-tion of the theoretical cost. Our FPGA implementations using HLS show an area and time gain compared with the state-of-the-art method. Then, we demonstrate the practicality of our new RNS-implementation approach on the two base-extension methods. Last, elliptic curve scalar multiplications based on the two base-extension methods are implemented using our RNS-implementation approach. Our FPGA implementations use a flexible quantity of hardware resources. Besides, although comparable with state-of-the-art ones in area vs. time trade-offs, most of our solutions are much smaller.

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Kawamura Base Extension . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Overview of KBE . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 KBE Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.3 The Cox-Rower Architecture . . . . . . . . . . . . . . . . . . . . . . 2.3 Hierarchical Base Extension . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 Overview of HBE . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.2 HBE Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.3 A Cox-Rower Architecture Adapted for HBE . . . . . . . . . . . . .2.4 Application to RNS Modular Multiplications . . . . . . . . . . . . . . . . . 2.5 FPGA Implementation Results . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 RNS-Flexible Hardware Accelerators for ECC 3.1 Notations and Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Flexible Kawamura Base Extension . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Algorithmical Description of the Flexible KBE . . . . . . . . . . . . 3.2.2 Architecture of the Flexible KBE . . . . . . . . . . . . . . . . . . . 3.2.3 FPGA Implementation Results . . . . . . . . . . . . . . . . . . . . 3.3 Flexible Hierarchical Base Extension . . . . . . . . . . . . . . . . . . . . . 3.3.1 Algorithmical Description of the Flexible HBE . . . . . . . . . . . . 3.3.2 Architecture of the Flexible HBE . . . . . . . . . . . . . . . . . . . 3.3.3 FPGA Implementation Results . . . . . . . . . . . . . . . . . . . . 3.4 Flexible Elliptic Curve Scalar Multiplication . . . . . . . . . . . . . . . . . 3.4.1 Overview of the Flexible ECSM . . . . . . . . . . . . . . . . . . . . 3.4.2 FPGA Implementation Results . . . . . . . . . . . . . . . . . . . . 3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Example of an elliptic curve defined over two finite fields. . . . . . . . . . . 1.2 Geometric description of point addition and point doubling. . . . . . . . . 1.3 Hierarchical description of computations involved in an ECSM. . . . . . . . 1.4 Hierarchical description of computations involved in an ECSM with RNS as chosen number system. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 The cox-rower architecture in [Gui10], adapted from [KKSS00]. . . . . . . 1.6 Simplified view of an FPGA. . . . . . . . . . . . . . . . . . . . . . . . . . . 1.7 Basic functionalities of the DSP slice in 7-series FPGAs from Xilinx (from [Xil18a]). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3. 7

 7 The flexible architecture for HBE (adapted from the HBE architecture in[START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF], itself inspired by the cox-rower architecture[START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF]): example with q = 4 PCs and c = 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 3.8 Structure of the upper part of the arithmetic processing performed by a rower in the flexible HBE (c = 2). The upper part of the rower performs the operation G Ω G + a ◊ b + f , where a, b and f are of size w bits, andG of size at most 2w + 1 bits. . . . . . . . . . . . . . . . . . . . . . . . . . 102 3.9 Structure of the lower part of the arithmetic processing performed by a rower in the flexible HBE (c = 2). The lower part of the rower performs the operation g Ω G mod m, where m = 2 w ≠ Á (with Á < 2 w/2 ), g is of size w bits, and G of size at most 2w + 1 bits. . . . . . . . . . . . . . . . . 102 3.10 Comparison of FPGA implementation results of the flexible HBE (adapted from [DBT19]) for q oe {2, 4, 8, 16} PCs. Finite fields are of 256-bit elements and the width of the PCs is 17 bits. . . . . . . . . . . . . . . . . . . . . . . 104 3.11 Comparison of the time, the numbers of cycles, DSPs and slices between the flexible HBE solutions and the flexible KBE ones for various numbers of PCs. HBE is not implemented for one PC. . . . . . . . . . . . . . . . . . 106 3.12 Hierarchical description of RNS computations of the ECSM. The ECSM is computed from a few hundreds point doublings and additions. If Algorithm 15 of the Mongomery ladder [Mon87] is used, each iteration of its loop requires two dozens basic operations and a dozen RNS mod p reductions. Each mod p reduction is made of two BEs and a few basic operations. The cost of the ECSM is mainly driven by that of the mod p reduction, which is itself driven by that of the BEs. . . . . . . . . . . . . . . . . . . . . . . . 107 3.13 Comparison of FPGA implementation results of the flexible ECSM-KBE for q oe {1, 2, 4, 8, 16} PCs. Finite fields are of 256-bit elements and the PCs 17-bit wide. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 3.14 Comparison of FPGA implementation results of the flexible ECSM-HBE for q oe {2, 4, 8, 16} PCs. Finite fields are of 256-bit elements and the PCs 17-bit wide. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 3.15 Comparison of the time, the numbers of cycles, DSPs and slices between the flexible ECSM-HBE solutions and the flexible ECSM-KBE ones for various numbers of PCs. ECSM-HBE is not implemented for one PC. . . . 119 LIST OF FIGURES 3.16 Comparison of the area and area ◊ time trade-o s of our ECSM implementations with the one in [BM14] and the best one in [MLPJ13]. ECSM implementations from [BM14, MLPJ13], and generally from the literature, are not flexible. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.1 Extraits de codes C de notre bibliothèque (haut) et de son utilisation (bas). A.2 Comparaison des di érents algorithmes de réduction pour w oe {13, 17, 23, 30} bits pour le motif M2 RSF avec N = 20. . . . . . . . . . . . . . . . . . . . A.3 Impact de la taille N des vecteurs pour MSR avec w = 23. . . . . . . . . .

3. 11

 11 Comparison of our FPGA implementation results of the ECSM with the ones from the literature. . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.1 Impact des directives d'optimisation pour M2 RSF, MSR, w = 23 et N = 20.139 A.2 Impact des stratégies de réduction pour w = 23 et N = 20. . . . . . . . .

Algorithm 3 :

 3 Encryption and decryption procedures in RSA [RSA78]. Input: Bob gets the public key (e, n) of Alice with the intention of sending her a plaintext m Output: Alice recovers m 1 Encryption 2 Bob computes c = m e mod n and sends c to Alice 3 Decryption 4 Alice receives c and computes c d mod n = m

Figure 1 . 1 -

 11 Figure 1.1 -Example of an elliptic curve defined over two finite fields.

Figure 1 . 2 -

 12 Geometric description of point addition and point doubling.

Figure 1

 1 Figure 1.3 -Hierarchical description of computations involved in an ECSM.

Figure 1

 1 Figure 1.4 -Hierarchical description of computations involved in an ECSM with RNS as chosen number system.

Figure 1

 1 Figure 1.5 -The cox-rower architecture in [Gui10], adapted from [KKSS00].

Figure 1

 1 Figure 1.6 -Simplified view of an FPGA.

  Figure 1.7 presents the basic functionalities of this DSP slice. It can perform operations of the form (A + D) ◊ B + C, where A, D, B and C are respectively of size 30, 25, 18 and 48 bits. The reader is referred to 1.4. FIELD PROGRAMMABLE GATE ARRAYS eries DSP48E1 User Guide www.xilinx.com 9 479 (v1.10) March 27, 2018

Figure 1

 1 Figure 1-1: Basic DSP48E1 Slice Functionality

w

  Figure 2.2 -The cox-rower architecture in [Gui10], adapted from [KKSS00].

  r 2 c times. The modular reduction ' x M (i) mod m Õ k,l is performed at line 14. Line 15 of Algorithm 12 corresponds to line 11 of Algorithm 11. Since the factors m (i) i,j are inserted during the computation of the super-residues '

  + CMR(cw + Álog 2 cË, w) + 2 CADD(w, w)) + rc (EMM + CMUL(w, (c ≠ 1)w) + CADD(cw, cw)) .(2.25)Assuming c = 2, we obtain for the cost of HBE 2r 2 (EMM + CMR(2w + 1, w) + 2 CADD(w, w))+ 2r (EMM + CMUL(w, w) + CADD(2w, 2w)) .

Figure 2 . 5 -

 25 Figure 2.5 -Architecture of HBE c = 2.

Figure 2 .

 2 Figure 2.6 depicts the theoretical cost ratio HBE/KBE for one RNS MM using optimizations from [GLP + 12]. The cost is presented for estimating 1 EMM to be in {2, 3, 4}

Figure 2 . 6 -

 26 Figure 2.6 -Theoretical cost ratio HBE/KBE of one RNS MM, with optimizations from [GLP + 12], for various estimations EMM/CMR(2w + 1, w) and numbers n of moduli.

  as HPR d = 2 and HPR d = 4. Figures 2.7 and 2.8 depict theoretical cost ratios HBE/KBE for one RNS MM using HPR d = 2 and HPR d = 4 respectively. Typically, if n = 16, HBE leads to a theoretical cost gain from 8% to 17% in RNS MM with HPR d = 2 compared with KBE. With HPR d = 4 and for n = 16 moduli, the cost gain of HBE is up to 5%.

Figure 2 . 7 -

 27 Figure 2.7 -Theoretical cost ratio HBE/KBE of one RNS MM with HPR d = 2 [BT15] for various estimations EMM/CMR(2w + 1, w) and numbers n of moduli.

Figure 2

 2 Figure 2.8 -Theoretical cost ratio HBE/KBE of one RNS MM with HPR d = 4 [BT16] for various estimations EMM/CMR(2w + 1, w) and numbers n of moduli.

wFF

  Figure 2.9 -Comparison of the time, the numbers of DSPs and slices between HBE c = 2 (from [DBT19]) solutions and KBE (from [KKSS00]) ones.

  VCs are mapped onto each PC.

Figure 3 . 2 -

 32 Figure 3.2 -Example of decomposition of the numbers n of VCs and q of PCs in RNS implementations of the ECSM when q = 4 and n = 16. Computations related to n/q = 4 VCs are performed on each PC. At a time, each PC deals with one VC, and the 4 VCs are processed one after another.

3. 1 .

 1 NOTATIONS AND DEFINITIONS implementations, that is, when 16 PCs are used. The two-dimension notations introduced in Chapter 2 are used. The left figure shows the 16 PCs (in blue) running in parallel. The right figure depicts one VC (in orange) mapped onto its PC. In Figure 3.2, we give an example of decomposition of the numbers of VCs and PCs when 4 PCs are used for the RNS implementation. The 4 PCs (in blue) run in parallel and are shown in the left figure. The right figure shows 4 VCs (in orange) mapped onto their PC. Each PC runs the computations related to its 4 VCs, one VC at a time and one after another.

Figure 3

 3 Figure 3.3 -The architecture for the flexible KBE (adapted from the cox-rower architecture [KKSS00]): example with q = 4 PCs and c = 2.

Figure 3

 3 Figure 3.4 -Structure of the arithmetic processing performed by a rower. The rower performs the operation g Ω (g + a ◊ b + f ) mod m, where m = 2 w≠ Á (with Á < 2 w/2 ), and a, b, f and g are of size w bits.

  computations related to 8 VCs (case q = 2 PCs are used for the implementation). computations related to 4 VCs (case q = 4 PCs are used for the implementation).

Figure 3 . 6 -

 36 Figure3.6 -Example of numbers cycles used by one PC to perform all computations related to the 16/q VCs it handles. The PC sequentially 'uploads' the 16/q VCs. Computations on the same PC are pipelined. In this typical example of loops at lines 1-4 of Algorithm 13, the computations related to the rc = 16 VCs are equally shared by the q PCs in use. At the left figure, q = 2 PCs are used and each PC handles 8 VCs. At the first cycle (top to bottom), computations related to the first VC start. At the next cycle, computations related to the next VC start, and so on until computations related to all 8 VCs (mapped onto the PC) start. Meanwhile, it is possible that the PC has terminated the computations related to the VCs that started earlier. Still, a few cycles are needed by the PC to terminate the remaining computations related to its ongoing VCs, that is, to empty out the pipeline. At the right figure, q = 4 PCs are used and each PC handles 4 VCs. The filling and emptying of the pipeline are similar to the ones at the left figure.

Figure 3 . 7 -

 37 Figure 3.7 -The flexible architecture for HBE (adapted from the HBE architecture in [DBT19], itself inspired by the cox-rower architecture [KKSS00]): example with q = 4 PCs and c = 2.

Figure 3 Figure 3

 33 Figure 3.8 -Structure of the upper part of the arithmetic processing performed by a rower in the flexible HBE (c = 2). The upper part of the rower performs the operation G Ω G + a ◊ b + f , where a, b and f are of size w bits, and G of size at most 2w + 1 bits.

Figure 3

 3 Figure 3.11 -Comparison of the time, the numbers of cycles, DSPs and slices between the flexible HBE solutions and the flexible KBE ones for various numbers of PCs. HBE is not implemented for one PC.

  Montgomery curve formulas to curves in short Weierstraß equation [BJ02, IT02]. The formulas are in projective coordinates. The value x Q denotes the a ne x-coordinate of Q, the input point of Algorithm 15 about the Montgomery ladder.

Figure 3

 3 Figure 3.15 -Comparison of the time, the numbers of cycles, DSPs and slices between the flexible ECSM-HBE solutions and the flexible ECSM-KBE ones for various numbers of PCs. ECSM-HBE is not implemented for one PC.

Figure 3

 3 Figure 3.16 -Comparison of the area and area ◊ time trade-o s of our ECSM implementations with the one in [BM14] and the best one in [MLPJ13]. ECSM implementations from [BM14, MLPJ13], and generally from the literature, are not flexible.

Figure A. 2 -

 2 Figure A.2 -Comparaison des di érents algorithmes de réduction pour w oe {13, 17, 23, 30} bits pour le motif M2 RSF avec N = 20.

Titre:

  Accélérateurs matériels RNS flexibles pour la cryptographie asymétrique à haute sécurité Mot clés : arithmétique des ordinateurs, système modulaire de représentation des nombres, flexibilité, implantation matérielle sur FPGA.

  Theoretical cost ratio HBE/KBE of one RNS MM, with optimizations from [GLP + 12], for various estimations EMM/CMR(2w + 1, w) and numbers n of moduli. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Theoretical cost ratio HBE/KBE of one RNS MM with HPR d = 4 [BT16]

	LIST OF FIGURES
	2.8

. . . . . . . . . . . . . . . . . . . . . . . . 2.1 Simplified description of KBE. . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 The cox-rower architecture in [Gui10], adapted from [KKSS00]. . . . . . . 2.3 Simplified description of HBE c = 2. . . . . . . . . . . . . . . . . . . . . . 2.4 Theoretical cost ratio HBE/KBE of one BE for various estimations EM-M/CMR(2w + 1, w) and numbers n of moduli. . . . . . . . . . . . . . . . . 2.5 Architecture of HBE c = 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 2.7 Theoretical cost ratio HBE/KBE of one RNS MM with HPR d = 2 [BT15] for various estimations EMM/CMR(2w + 1, w) and numbers n of moduli. .

  .4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HLS implementation results on a XCZU7EV-FFVC1156 FPGA for the ECSM-KBE using q oe {1, 2, 4, 8, 16} PCs. Finite fields are of 256-bit elements and the PCs 17-bit wide. . . . . . . . . . . . . . . . . . . . . . . . . 3.7 HLS implementation results of the ECSM-KBE according to introduced metrics of area vs. time trade-o s for q oe {1, 2, 4, 8, 16} PCs. . . . . . . . . 3.8 HLS implementation results on a XCZU7EV-FFVC1156 FPGA for the ECSM-HBE using q oe {2, 4, 8, 16} PCs. Finite fields are of 256-bit elements and the PCs 17-bit wide. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.9 HLS implementation results of the ECSM-HBE according to introduced metrics of area vs. time trade-o s for q oe {2, 4, 8, 16} PCs. . . . . . . . . . 3.10 Comparison of flexible ECSM-HBE solutions with flexible ECSM-KBE ones for the various numbers of PCs. ECSM-HBE is not implemented for one PC.

	LIST OF TABLES
	3.6

1

  Di e-Hellman key-exchange protocol [DH76]. . . . . . . . . . . . . . . . . . 2 Private-and public-key generation in RSA [RSA78]. . . . . . . . . . . . . . 3 Encryption and decryption procedures in RSA [RSA78]. . . . . . . . . . . . 4 Elliptic curve version of the Di e-Hellman key-exchange protocol [Mil85]. .

5 Double-and-add algorithm (see, for example [HMV04]). . . . . . . . . . . . . 6 Montgomery ladder algorithm [Mon87]. . . . . . . . . . . . . . . . . . . . . 7 Montgomery reduction algorithm [Mon85]. . . . . . . . . . . . . . . . . . . . 8 RNS-to-MRS conversion algorithm [Val56, Gar59]. . . . . . . . . . . . . . . 9 Base extension BE MaeM Õ (x) [KKSS00]. . . . . . . . . . . . . . . . . . . . . 10 RNS Montgomery reduction algorithm [PP95]. . . . . . . . . . . . . . . . . 11 Kawamura base extension BE MaeM Õ (x) adapted from

  . . . . . . . . . . . . . . . . . . . . . . . 15 Montgomery ladder algorithm [Mon87] . . . . . . . . . . . . . . . . . . . . . 16 RNS Montgomery reduction algorithm [PP95] . . . . . . . . . . . . . . . . . 17 Flexible basic operation in the RNS base M. The function f (v, i) is given by f (v, i) = q c (v ≠ 1) + i. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	HLS HPR	high-level synthesis modular multiplication algorithm proposed in [BT15, BT16] LIST OF ABBREVIATIONS
	HTTPS hypertext transfer protocol secure
	I/O	input/output
	KBE	Kawamura base extension
	ADD least significant bit elliptic curve point addition ANSSI look-up table Agence nationale de la sécurité des systèmes d'information (France) ASIC modular multiplication application specific integrated circuit BE modular reduction base extension BRAM MRS LSB LUT MM MR mixed-radix system block RAM CAD MSB most significant bit computer-aided design CADD NIST National Institute of Standards and Technology (United States) cost of an addition/subtraction CLB OC number of operation cycles configurable logic block CMUL PC physical channel cost of a multiplication CMR RAM random access memory cost of a modular reduction CRT RNS residue number system Chinese remainder theorem DBL RSA Rivest Shamir Adleman (the cryptosystem proposed in [RSA78]) elliptic curve point doubling DCM RTL register transfer level digital clock manager DLP SPA simple power analysis discrete logarithm problem (in finite fields) DPA TLS transport layer security di erential power analysis DSA VC virtual channel digital signature algorithm VHDL VHSIC hardware description language DSP slice digital signal processing slice ECC VHSIC very high speed integrated circuits elliptic curve cryptography ECDH elliptic curve Di e-Hellman protocol WC number of wait cycles
	ECDLP	elliptic curve discrete logarithm problem
	ECDSA elliptic curve digital signature algorithm
	ECSM	elliptic curve scalar multiplication
	EMA	elementary modular addition
	EMM	elementary modular multiplication
	FF		flip-flop
	FPGA	field programmable gate array
	HBE		hierarchical base extension
	HDL		hardware description language
	HECC	hyperelliptic curve cryptography

and keeps it secret 2 Alice computes [u A ]Q and sends it to Bob 3 Bob chooses a random number u B , 0 AE u B AE v ≠ 1 and keeps it secret 4 Bob computes [u B ]Q and sends it to Alice 5 Alice receives [u B

Table 1 .

 1 1 -Some RNS implementations of asymmetric cryptosystems on FPGA from the literature. The size(ı) is the operand size (for example the modulus size for RSA or the size of the underlying field of the curve for ECC).

	reference	proc./journal	FPGA	cryptosystem	size (ı)
	[CNPQ03]	MWSCAS	Virtex 2	RSA	1024
	[SKS06] [SFM + 09] IEEE TCAS I MELECON	Virtex 2 Pro Virtex E	ECC ECC	160 160, 192, 224, 256
	[Gui10]	CHES	Stratix Stratix II	ECC	160, 192, 256, 384, 512
	[CDF + 11]	CHES	Cyclone II Stratix II & III	Pairings	126, 128, 192
			Virtex 6
	[YFCV12]	Pairing	Virtex 4 Virtex 6	Pairings	126, 128
	[PITM13]	DSD	Spartan 3	RSA	1024
	[ESJ + 13]	IEEE TVLSI	Virtex E Virtex 2 Pro	ECC	160, 192, 224, 256
			Stratix II
	[BM14]	CARDIS	Kintex 7	ECC	256, 521
	[FKSK15]	CS2	Virtex 2 Virtex 5	ECC	192
	[BEMP15]	ARITH	Virtex 5 Kintex 7	Lattice-based cryptography	64, 128
			Spartan 6
	[BT15]	CHES	Virtex 5	ECC	192, 384, 512
			Kintex 7

Table 2 .

 2 1 -FPGA implementation results for CMR(2w + 1, w) and EMM operations on a Xilinx XC7Z020 FPGA.

	operations	CMR(2w + 1, w)		EMM
	w (bits)	17 20 24 28	17	20 24	28
	nb. slices	1	1	24 29	1	23	1	39
	nb. DSPs	2	2	1	1	3	3	4	5
	nb. cycles	1	1	2	2	2	2	2	3
	time (ns) 2.2 2.2 9.3 9.5 10.3 7.8 7.8 18.7

Table 2 .

 2 2 -HLS implementation results on a XC7Z020 FPGA for HBE c = 2 (from[START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF]) and KBE (from[START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF]) algorithms for two widths of prime field elements and four RNS channel widths w.

	F p width (bits)	BE algo. w (bits)	KBE	17	HBE	KBE	20	HBE	KBE	24	HBE	KBE HBE 28
		nb. slices	409		359	962		652	611		575	708	673
		nb. DSPs	51		44	45		39	52		42	77	61
	256	nb. BRAM period (ns)	1 9.7		1 9.8	1 9.8		1 9.5	1 9.6		1 8.4	1 9.9	1 9.6
		nb. cycles	98		91	88		83	89		81	77	71
		time (ns)	950.6		891.8	862.4		788.5	854.4		680.4	762.3 681.6
		nb. slices	458		468	1270		830	1041		994	903	1062
		nb. DSPs	75		64	63		54	76		60	105	81
	384	nb. BRAM period (ns)	1 8.2		1 8.8	1 8.7		1 9.5	1 9.1		1 7.6	1 9.9	1 9.6
		nb. cycles	165		143	140		122	163		132	103	93
		time (ns)	1353.0 1258.4 1218.0 1159.0 1483.3 1003.2 1019.7 892.8

in slices than KBE. The gain in DSPs amounts to 21% for w = 28 bits, in which case the reduction is 11% in computation time and 5% in slices. The only case where HBE costs more than KBE for one of the resource metrics, specifically the number of slices, is for an F p of 384-bit elements and channels of 28-bit width. The lost in slices is 15%. However, this lost in slices is balanced by a 23% gain in DSPs and a 12% gain in computation time, leading to an area vs. time trade-o again in favor of HBE.

Table 3 .

 3 1 -HLS implementation results on a XCZU7EV-FFVC1156 FPGA for the flexible KBE (adapted from [KKSS00]) using q oe {1, 2, 4, 8, 16} PCs. Finite fields are of 256-bit elements and the width of the PCs is 17 bits.

	nb. PCs	1	2	4	8	16
	nb. slices	107	162	223	341	623
	nb. DSPs	3	6	12	24	48
	nb. BRAMs	1	2	4	8	16
	period (ns)	3.9	3.9	4.1	4.6	4.6
	nb. cycles	280	153	88	56	37
	time (ns)	1092 596.7 360.8 257.6 170.2

  Table 3.3 -Comparison of FPGA implementation results of the flexible HBE (adapted from[START_REF] Djath | Hierarchical approach in RNS base extension for asymmetric cryptography[END_REF]) with those of the flexible KBE (adapted from[START_REF] Kawamura | Cox-Rower architecture for fast parallel Montgomery multiplication[END_REF]) for various number of PCs. The flexible HBE is not implemented for one PC. Finite fields are of 256-bit elements and the width of the PCs is 17 bits.

	BE algos.	KBE HBE KBE HBE KBE HBE KBE HBE KBE HBE
	nb. PCs	1		2		4		8		16
	nb. slices	107	-	162	179	223	289	341	526	623	609
	nb. DSPs	3	-	6	4	12	8	24	16	48	32
	nb. BRAMs	1	-	2		4		8		16
	period (ns)	3.9	-	3.9	4.2	4.1	4.2	4.6	4.4	4.6	4.3
	nb. cycles	280	-	153	103	88	67	56	49	37	36
	time (ns)	1092	-	596.7 432.6 360.8 281.4 257.6 215.6 170.2 154.8
			nb. PCs	2	4	8	16
			nb. slices	179	289	526	609
			nb. DSPs	4	8	16	32
		nb. BRAMs	2	4	8	16
			period (ns)	4.2	4.2	4.4	4.3
			nb. cycles	103	67	49	36
			time (ns)	432.6 281.4 215.6 154.8

Table 3 .

 3 6 -HLS implementation results on a XCZU7EV-FFVC1156 FPGA for the ECSM-KBE using q oe {1, 2, 4, 8, 16} PCs. Finite fields are of 256-bit elements and the PCs 17-bit wide.

	nb. PCs	1	2	4	8	16
	nb. slices	3120	3317	4432	5841	13621
	nb. DSPs	3	6	12	24	48
	nb. BRAMs (occupancy)	1 (38%) 2 (19%) 4 (10%) 8 (5%) 16 (3%)
	period (ns)	4.4	4.5	4.7	4.9	5.1
	nb. cycles	2541429 1376748 790575 481648 311713
	time (ms)	11.2	6.2	3.7	2.4	1.6

Table 3 .

 3 7 -HLS implementation results of the ECSM-KBE according to introduced metrics of area vs. time trade-o s for q oe {1, 2, 4, 8, 16} PCs. than linearly in relation to the increase of the number of PCs. This less-than-linear decrease in the time is mainly due to the various WCs being > 0 in the flexible ECSM-KBE implementations. As a result, ECSM-KBE implementations with fewer PCs present the best area vs. time trade-o s.

	nb. PCs	1	2	4	8	16
	DSPs ◊ time slices ◊ time BRAMs ◊ time	33.6 34944 20565.4 16398.4 14018.4 21793.6 37.2 44.4 57.6 76.8 11.2 12.4 14.8 19.2 25.6
	time decreases less

Table 3 .

 3 8 -HLS implementation results on a XCZU7EV-FFVC1156 FPGA for the ECSM-HBE using q oe {2, 4, 8, 16} PCs. Finite fields are of 256-bit elements and the PCs 17-bit wide. HBE computation are equally shared between the BRAMs, regardless of the number of PCs in use. The occupancy of one BRAM is reported in Table

	nb. PCs	2	4	8	16
	nb. slices	4307	4851	6145	14599
	nb. DSPs	4	8	16	32
	nb. BRAMs (occupancy)	2 (14%) 4 (7%) 8 (4%) 16 (2%)
	period (ns)	4.3	4.8	4.9	5.1
	nb. cycles	1002615 637235 444325 305763
	time (ms)	4.3	3.0	2.2	1.5
	precomputations needed for the ECSM-

Table 3 .

 3 10 -Comparison of flexible ECSM-HBE solutions with flexible ECSM-KBE ones for the various numbers of PCs. ECSM-HBE is not implemented for one PC.

	nb. PCs	1		2		4		8		16
	BE algorithms	KBE	HBE	KBE	HBE	KBE	HBE	KBE	HBE	KBE	HBE
	nb. slices	3120	-	3317	4307	4432	4851	5841	6145	13621	14599
	nb. DSPs	3	-	6	4	12	8	24	16	48	32
	nb. BRAMs	1	-	2		4		8		16
	period (ns)	4.4	-	4.5	4.3	4.7	4.8	4.9	4.9	5.1	5.1
	nb. cycles	2541429	-	1376748 1002615 790575 637235 481648 444325 311713 305763
	time (ms)	11.2	-	6.2	4.3	3.7	3.0	2.4	2.2	1.6	1.5

  et deBarrett [Bar84] pour MQ, et des algorithmes spécifiques pour MSC et MSR[START_REF] Crandall | Method and apparatus for public key exchange in a cryptographic system[END_REF][START_REF] Solinas | Generalized Mersenne numbers[END_REF].Nous définissons et utilisons des types de données spécifiques pour chaque taille nécessaire et des macros de transtypage (cast) pour adapter correctement les tailles 2 . Par exemple pour M2 en version RSF (c.-à-d. réduction seulement à la fin), il faut pouvoir réduire l'accumulation des N produits sur 2w + Álog 2 N Ë bits. Pour ce motif, nous avons aussi évalué une réduction intermédiaire systématique (RIS) à chaque itération. La figure A.1 présente un extrait de code C de notre bibliothèque et un exemple de code devant être produit par l'utilisateur. La partie haute de la figure est le code de la réduction modulaire avec l'algorithme de Barrett de la bibliothèque. Les types comme word et sumdword doivent être définis par l'utilisateur selon un « template » fourni avec la bibliothèque. Par exemple, le type word est de taille de w bits (code pour w = 13 : typedef uint13 word;), le type dword est de taille double pour les produits de deux nombres de w bits (code pour w = 13 : typedef uint26 word;), le type sumdword est pour les accumulateurs sur 2w + Álog 2 N Ë bits, etc. L'utilisateur doit aussi définir des macros de transtypage (cast) pour chacun des types définis. Par exemple, la macro W est définie par #define W(x) ((word) (x)). Le template fournit la liste de l'ensemble des macros à définir selon les usages. Toutes ces définitions spécifiques à l'application doivent être codées par l'utilisateur en complétant le template parameters.h inclus en ligne 1. Ce fichier définit aussi la constante N choisie pour les vecteurs.La partie basse de la figure A.1 présente un exemple de code utilisateur pour e ectuer le motif M2 avec la stratégie RSF. L'utilisateur doit :

Nous comparons nos résultats avec l'algorithme « natif » employé par Vivado HLS lors de l'utilisation de l'opérateur % du langage C. Nos résultats montrent qu'il s'agit probablement d'une division euclidienne itérative dont on conserve le reste final

[START_REF] Ercegovac | Digital Arithmetic[END_REF][START_REF] Ercegovac | Division and Square-Root Algorithms: Digit-Recurrence Algorithms and Implementations[END_REF]

. En tout, nous comparons 5 algorithmes de réduction modulaire di érents dans le même cadre.

Toutes nos implantations sont génériques pour des opérandes de taille w bits fixée à la conception. Pour RNS et PQC, w est de quelques dizaines de bits au plus. La taille N des vecteurs dans les motifs est aussi générique. Pour Barrett et Montgomery, il faut précalculer à la conception des constantes internes (p. ex. un inverse modulaire qui dépend de m et de w).

Table A .

 A 28 % et 40 % TM en déroulant avec un facteur 2 et 4 respectivement, au prix d'une augmentation du nombre de DSP utilisés. Au-delà d'un facteur 4, on n'observe plus d'amélioration significative du temps, tout en payant le 2 -Impact des stratégies de réduction pour w = 23 et N = 20.Pour M1, nous donnons uniquement les résultats pour RSF car RIS est toujours bien moins performant (le coût d'une itération de boucle, une addition, est bien trop faible devant celui d'une réduction modulaire). Nous présentons les résultats de M1 RSF pour montrer l'impact de l'itération (par rapport à M2).Pour M2 avec Barrett et Montgomery, RSF est meilleur en compromis surface◊temps (RIS peut être un tout petit plus rapide mais pour une surface plus importante).Globalement RSF est souvent plus e cace que RIS (pour les N et w testés). Mais il nous reste à explorer ce qui se passe pour des N très grands et des w petits (comme c'est le cas pour RE avec p. ex. w = 13 et N oe [256, 1024]). D'autres stratégies intermédiaires sont envisageables, comme réduire de temps en temps de petits accumulateurs partiels. Cela pourrait être intéressant pour des motifs où les calculs dans chaque itération sont plus complexes qu'une seule opération.Enfin, nous analysons l'impact de la taille des vecteurs des motifs sur les performances et les coûts. La figure A.3 présente quelques résultats représentatifs pour l'algorithme de réduction MSR avec w = 23. Nous observons que pour les N testés, le compromis surface◊temps est proche d'une fonction a ne de N (résultat général à toutes nos implantations). Cette croissance a ne avec N permet d'e ectuer des estimations à haut niveau très simplement (avec une marge d'erreur raisonnable).Cependant, la figure A.3 suggère aussi un phénomène bien plus complexe à anticiper (du moins dans l'état actuel de nos connaissances). Ceci est en lien avec les deux dernières lignes de la table A.2 où le motif RIS est plus e cace que RSF. On observe sur la figure A.3 que le temps de calcul et le nombre de cycles du RIS croissent moins vite que ceux de RSF. Le même phénomène est observé pour les compromis surface◊temps, on peut donc en déduire que le gain de RIS sur RSF se fait sur le coût de chaque itération de la boucle d'accumulation. Cependant, d'un point de vue purement arithmétique, RIS calcule s Ω (s + x i ◊ y i ) mod m à chaque itération, contre s Ω (s + x i ◊ y i ) pour RSF, donc RIS e ectue plus de calculs par itération. Nous voyons que l'outil arrive à mieux pipeliner les itérations de RIS que celles de RSF dans certains cas. Il est clair qu'il nous reste du travail pour mieux cerner quand et comment (modification de la structure du code) utiliser les di érentes directives d'optimisation de l'outil HLS.

		algorithme	surface	temps (ns, cycles)	surface◊temps
	motif	et stratégie	slices DSP période cycles TM DSP◊TM slices◊TM
	M1 Montgomery RSF	122	5	2.6	31	81	405	9882
		Barrett RSF	110	1	2.9	58	169	169	18502
		MSC RSF	62	0	2.5	17	43	0	2635
		MSR RSF	66	0	2.6	17	45	0	2970
	M2	Montgomery RIS	194	12	2.6	60	156	1872	30264
		Montgomery RSF	149	7	2.6	64	167	1165	24794
		Barrett RIS	259	12	2.8	53	149	1781	38436
		Barrett RSF	218	10	2.7	52	141	1404	30608
		MSC RIS	403	4	2.7	55	149	594	59846
		MSC RSF	261	4	2.7	47	127	508	33121
		MSR RIS	146	8	2.6	31	81	645	11768
		MSR RSF	167	6	3.2	46	148	884	24583

4.4. Impact de la taille N des vecteurs

According to[START_REF] Sentieys | Architectures reconfigurables FPGA[END_REF], the manufacturing cost of FPGAs is paid o by the numerous clients owing to the large quantity in which they are usually produced. For ASICs 2 to become profitable, they must be produced in extremely large quantity because of the important cost in human resources, equipement, design complexity and time they require.

ASICs stand for application specific integrated circuits.

ANSSI stands for Agence nationale de la sécurité des systèmes d'information (France).

NIST stands for National Institute of Standards and Technology (United States).

The ECDSA is based on the ECDLP.

The DSA is based on the DLP.

ARITH-26 stands for 26th IEEE Symposium on Computer Arithmetic.

2.6. CONCLUSION

The range of an RNS base {m 1 , . . . , m n } is the number M = r n i=1 m i ; see Section 1.3 about RNS.

The computation protection is not su cient for a complete secure implementation. Indeed, other parameters of hardware implementations such as the number of control signals or the storage addresses of iteration results have to be considered. For example, if the storage addresses of the results of an iteration depend on the bit value of the scalar and no further step is taken, then the information leak is likely to di er depending on the bit value of the scalar.

On rappelle que la sémantique du langage C est assez peu mathématique, p. ex. le produit de 2 mots est un mot de même taille que les opérandes.

Remerciements

Ce travail a été financé en partie par le PEC, la DGA et la Région Bretagne. Nous remercions chaleureusement les relecteurs anonymes pour leurs précieuses remarques et corrections.

FLEXIBLE KAWAMURA BASE EXTENSION

) for q oe {2, 4, 8, 16} PCs. Finite fields are of 256-bit elements and the width of the PCs is 17 bits.

cycles is translated into a less-than-linear decrease in the time. For example, the HBE solution with four PCs is only 1.5 faster than the one with two PCs.

Comparison Flexible KBE vs. Flexible HBE

The comparison of the flexible HBE and KBE is reported in Table 3.3. The comparison is performed for q oe {2, 4, 8, 16} PCs. No comparison is possible for q = 1 PC since no implementation result is available for HBE (c = 2) on one PC. In Figure 3.11 are plotted the time, the numbers of cycles, DSPs and slices.

The HBE solution is faster than the KBE one for all q oe {2, 4, 8, 16} PCs. For example, for q = 4 PCs, the HBE solution is 22% faster than the KBE one. The gain in speed reaches 28% for q = 2 PCs. For a given number q of PCs, the number of BRAMs is the the q PCs running in parallel to compute the basic operation. The outer loop bounded by rc/q at line 1 describes the mapping of rc/q VCs on each PC, one VC at a time.

Algorithm 17 is useful in computations of the formulas in Table 3.5 (without the mod p reduction) and in computations of lines 1, 3 and 4 of Algorithm 16 (for the mod p reduction). For RNS computations of basic operations in base M Õ , the same algorithm is used by replacing M with M Õ .

Algorithm 17: Flexible basic operation in the RNS base M. The function f (v, i) is given by f (v, i) = q c (v ≠ 1) + i. Input: x m i,j and y m i,j for all i, 1 AE i AE r and j, 1 AE j AE c Output: s m i,j for all i, 1 AE i AE r and j, 1 AE j AE c 1 for v Ω 1 to rc/q do 2 for i Ω 1 to q/c parallel do

Architecture

The architectures used for the flexible ECSMs are the ones at Figures 3.3 and 3.7 used for the flexible KBE and HBE respectively, depending on the BE used in the flexible ECSM. Additional precomputations related to the RNS MR (Algorithm 16) and the point doubling and addition formulas (curve related values such as ≠a and ≠4b) in Table 3.5 are stored in the memories. The arithmetic processing performed by the rower remains unchanged: the one at Figure 3.4 if the flexible ECSM uses KBE, and the ones at Figures 3.8 and 3.9 if the flexible ECSM uses HBE. The basic-operation computations described in Algorithm 17 are performed using the architecture corresponding to the chosen BE. If KBE is used in the ECSM implementation, the basic operations (outside the BEs) are performed by the architecture at Figure 3.3 with the rower performing the arithmetic processing described in Figure 3.4. If HBE is used in the ECSM implementation, the same basic operations are performed by the architecture at Figure 3.7 with the rower performing the combination of the upper and the lower part of the arithmetic processing depicted in Figures 3.8 and 3.9.

On Flexible Multi-Level-Security ECSMs

Depending on its usage, an application may need two (or more) security levels. For example, the application may need a lower security level for a frequent usage and a higher one for a less frequent usage. In such a situation, two underlying finite fields (of the ECSM), corresponding to the two desired security levels, are needed. The designer is forced to choose between performing two implementations of the ECSMs over the two finite fields (one ECSM per finite field) or one implementation of the ECSM over the largest finite field (to ensure the highest security level by default). In the first case, the two implementations use separate hardware resources, leading to a used quantity of hardware resources greater than the one needed by each implementation. In the second case, the solution frequently uses more time than normally needed (the lower security level is more frequently used by the application). The flexible architectures at Figures 3.7 and 3.3 can be employed to implement the two ECSMs (over the two finite fields) on the same hardware resources with appropriate performance for each ECSM. The term "flexible multi-level-security ECSMs" indicates two (or more) ECSMs over finite fields of di erent sizes can be implemented using the same hardware resources, and this quantity of hardware resources is flexible.

Let us consider the case of two finite fields F p 1 and F p 2 where p 1 and p 2 are two large prime such that the bitsize of p 2 is twice that of p 1 . If n VCs are needed for the flexible ECSM over F p 1 , then 2n VCs can be used for the flexible ECSM over F p 2 (the same width of VCs is considered for the ECSM implementations on F p 1 and F p 2 ). The same architecture can be used to implement the flexible ECSMs over F p 1 and F p 2 by mapping respectively n/q and 2n/q VCs onto each PC. An additional signal, that indicates which one of the flexible ECSM over F p 1 or over F p 2 is being performed, has to be added to the architecture. Mainly, the core of the architecture remains the same, that is, the arithmetic processing performed by each rower is unchanged. For a given number of PCs, this constancy of the architecture core would lead to the same number of DSPs used regardless of the underlying finite field (F p 1 or F p 2 ) of the ECSM.

On the memory of each PC are stored the precomputations needed for the implementation of the ECSM over F p 1 and over F p 2 . If the two sets of precomputations per memory (of each PC) can be stored in a single BRAM, then the solutions of the flexible multi-level-security ECSMs would use the same area (in DSPs and BRAMs) as the solutions of a "single" flexible ECSM (without targeting the multi-level-security aspect). This situation is likely to occur since BRAMs in modern FPGAs have large storage capacities which are usually underexploited in RNS implementations of asymmetric cryptosystems; implementation, we introduce additional metrics to assess the obtained gain in time when increasing hardware resources. These metrics are DSPs ◊ time, slices ◊ time and BRAMs ◊ time, and they provide information about area vs. time trade-o s. The HLS implementation results according to these metrics are reported in Table 3.7. The DSPs ◊ time and BRAMs ◊ time trade-o s are the best (smallest) for q = 1 PC, and increase with the number of PCs while the contrary is observed for the slices ◊ time trade-o (except for q = 16 PCs). Overall, the area vs. time trade-o s are better when a few PCs are used for the ECSM-KBE implementation. This result is to be expected since the WCs being > 0 have lesser impact on the time when the flexible ECSM-KBE implementation is performed on fewer PCs.

RNS-FLEXIBLE HARDWARE ACCELERATORS FOR ECC

In summary, the used hardware resources increase with the number of PCs (linearly for the DSPs and BRAMs and less than linearly for the slices). On the other hand, the

Comparison Flexible ECSM-KBE vs. Flexible ECSM-HBE

In Table 3.10 flexible ECSM-KBE solutions and flexible ECSM-HBE ones, reported respectively in Tables 3.6 and 3.8, are put together. The comparison of the flexible ECSMs is performed for q oe {2, 4, 8, 16} PCs since the ECSM-HBE is not implemented using one PC. In Figure 3.15 are plotted the time, the numbers of cycles, DSPs and slices.

COMPARAISON D'ALGORITHMES DE RÉDUCTION MODULAIRE EN HLS SUR FPGA

This appendix contains the unabridged contribution (in French) from [START_REF] Djath | Comparaison d'algorithmes de réduction modulaire en HLS sur FPGA[END_REF]. Mots-clés : arithmétique modulaire, conception en synthèse de haut niveau, exploration d'architectures et d'algorithmes, circuit FPGA.

Comparaison d'algorithmes de réduction modulaire en HLS sur FPGA

Introduction

Les implantations en cryptographie asymétrique nécessitent un support d'arithmétique modulaire de plus en plus avancé. RSA utilise des carrés et multiplications modulo un nombre de quelques milliers de bits. Les cryptosystèmes actuels nécessitent des séquences Code (de la bibliothèque) pour la réduction modulaire avec l'algorithme de Barrett : résultats pour d'autres contraintes seront disponibles dans la documentation de la bibliothèque). Notre attention portera principalement sur le motif M2, car il est crucial pour RNS et PQC.

Résultats d'implantation

Comparaison des di érents algorithmes de réduction

Nous commençons par comparer les di érents algorithmes de réduction modulaire (le % de Vivado et nos implantations de Barrett

Impact de la stratégie de réduction

Pour un motif nécessitant de nombreuses opérations modulo m, plusieurs stratégies de réduction sont envisageables. Il est possible d'e ectuer une réduction intermédiaire systématique (RIS) à chaque itération ; pour M2 cela correspond au calcul :

Il est possible d'e ectuer une réduction seulement à la fin (RSF) ; pour M2 cela donne :

Dans la version RSF de motifs comme M1 et M2, l'accumulateur doit être plus large pour absorber les retenues de la somme des résultats de chaque itération (avec Álog 2 N Ë bits en plus). Ceci engendre une réduction finale plus coûteuse car son opérande est plus large.

Nous avons implanté les stratégies RIS et RSF pour les motifs M1 et M2 et nos di érents algorithmes de réduction. La table A.2 présente une partie représentative de nos résultats.

GENERALIZED WEIERSTRASS EQUATION OF ELLIPTIC CURVES

Definition 7 (from [START_REF] Cohen | Handbook of Elliptic and Hyperelliptic Curve Cryptography[END_REF]). An elliptic curve E K defined over a field K is given by the Weierstraß equation

where a 1 , a 2 , a 3 , a 4 , a 6 oe K and the values

Appendix C

PROOF OF THE CHINESE REMAINDER THEOREM

In Theorem 2 we presented the Chinese remainder theorem (CRT). The CRT is widespread and a proof of it can be found in most books about elementary number theory; see for example [START_REF] Niven | An Introduction to the Theory of Numbers[END_REF][START_REF] Tattersall | Elementary number theory in nine chapters[END_REF][START_REF] Burton | Elementary Number Theory[END_REF]. We prove the CRT in three steps: For all i, 1 AE i AE n, let C i be a number such that |C i M i | m i = 1. The various C i exist because for all i, 1 AE i AE n, m i is coprime with M i (since m i is coprime with all m j , j " = i and M i = r j" =i m j ). Let us define y = q n i=1 x i C i M i . We do have for all i, |x i C i M i | m i = x i and for all j " = i,

Hence, for all i, y © x i (mod m i ). The number y is a solution of ( ).

• The solution of ( ) is unique modulo M . Let z be another solution of ( ). By definition of z, for all i, |z| m i = x i . Therefore, for all i, |z| m i = |y| m i = x i because y is also a solution of ( ). This equivalence implies, for all i, |z ≠ y| m i = 0 which is equivalent to, for all i, m i divides z ≠ y. We deduce r n i=1 m i divides z ≠ y, that is, M divides z ≠ y. We get |z| M = |y| M . • The value given to x in Theorem 2 is the unique solution of ( ) between 0 and M .

PROOF OF THE CHINESE REMAINDER THEOREM

The number x is one of the solutions of ( ), by definition of ( ). Therefore, x can be written

owing to the uniqueness of the ( )