Jean-Claude Bajard
email: jean-claude.bajard@lip6.fr

Julien Eynard
email: julien.eynard@lip6.fr

Filippo Gandino
email: filippo.gandino@polito.it

Fault Detection in RNS Montgomery Modular Multiplication

Keywords: Residue Number System, Fault Detection, Montgomery Reduction, Base Conversions

Recent studies have demonstrated the importance of protecting the hardware implementations of cryptographic functions against side channel and fault attacks. In last years, very efficient implementations of modular arithmetic have been done in RNS (RSA, ECC, pairings) as well on FPGA as on GPU. Thus the protection of RNS Montgomery modular multiplication is a crucial issue. For that purpose, some techniques have been proposed to protect this RNS operation against side channel analysis. Nevertheless, there are still no effective and generic approaches for the detection of fault injection, which would be additionnally compatible with a leak resistant arithmetic. This paper proposes a new RNS Montgomery multiplication algorithm with fault detection capability. A mathematical analysis demonstrates the validity of the proposed approach. Moreover, an architecture that implements the proposed algorithm is presented. A comparative analysis shows that the introduction of the proposed fault detection technique requires only a limited increase in area.

I. INTRODUCTION

Residue Number Systems (RNS) [START_REF] Garner | The residue number system[END_REF], [START_REF] Szabo | Residue Arithmetic and its application to Computer Technology[END_REF] enable to make computations on large numbers through an arithmetic based on additions, subtractions and multiplications run on small units (i.e. the elements of a chosen RNS base) in a parallel and carry-free way. However, because they are non-positional numeral systems, comparison, division and modular reduction are more difficult to perform. For instance, Bajard et al. [START_REF] Bajard | An RNS Montgomery modular multiplication algorithm[END_REF] propose an algorithm for modular multiplication in RNS (RNSMM) adaptating the classical Montgomery reduction [START_REF] Montgomery | Modular multiplication without trial division[END_REF]. By combining this algorithm with efficient base conversion [START_REF] Shenoy | Fast base extension using a redundant modulus in RNS[END_REF], [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF] fast execution of modular multiplications/exponentiations on large integers, which is of special interest for cryptographic applications, become possible in RNS. For that matter Guillermin et al. [START_REF] Guillermin | A high speed coprocessor for elliptic curve scalar multiplications over Fp[END_REF]- [START_REF] Duquesne | A FPGA pairing implementation using the residue number system[END_REF] show the real effectiveness of RNS for hardware implementation of cryptosystems as RSA, ECC and pairings.

In cryptographic context, RNS also allows to use a leak resistant arithmetic providing a natural protection against side channel analysis such as timing, power and electromagnetic attacks [START_REF] Bajard | Leak resistant arithmetic[END_REF] through randomization of bases between operations. Another kind of dangerous threat is fault attacks, ¦ this author is supported by Direction Générale de l'Armement (DGA - French Ministry of Defence) which are a well-known way to extract informations of cryptosystems. It was initially used by Boneh et al. [START_REF] Boneh | On the importance of checking cryptographic protocols for faults[END_REF] to break RSA-CRT. Because data are scattered across the units, RNS supplies a natural robustness against faults. Indeed it suffices to add a redundant unit to detect any error affecting a single small value. However, standard redundant RNS techniques for fault detection [START_REF] Watson | Self-checked computation using residue arithmetic[END_REF]- [START_REF] Yau | Error correction in redundant residue number systems[END_REF] are feasible as long as no base extension operations and/or overflow appear. In first case, a fault could be propagated to all units of the new base. In second case, the redundant value is not redundancy of RNS data anymore. In the end, the protection of RNS modular multiplication against fault injection appears necessary so as to consolidate interest of RNS arithmetic in cryptography. However, RNSMM algorithms [START_REF] Bajard | An RNS Montgomery modular multiplication algorithm[END_REF], [START_REF] Bajard | Modular multiplication and base extensions in residue number systems[END_REF] contain two consecutive base conversions which are a priori not compliant with standard redundant detection techniques. The goal of the paper is to adapt such standard countermeasures using redundancy to RNS modular multiplication.

In this paper a new algorithm, inserting redundancy into RNS Montgomery multiplication in order to provide efficient and cheap protection against fault attacks in the context of modular exponentiation/elliptic curve point addition, and compliant with a leak resistant arithmetic, is presented and analyzed. A formal analysis proves the detection of any single fault. Beyond theoretical purposes, an architecture resistant to single fault attacks and compliant with previous protections for RNS against side channel attacks is suggested. The architectural design is based on the work presented in [START_REF] Nozaki | Implementation of RSA algorithm based on RNS Montgomery multiplication[END_REF] by Nozaki et al. An analysis based on equivalent gates shows that the area increase required for single fault detection is lower than 3%, and that the total computational time increases by about 1ßÔ2 log 2 ÔexponentÕÕ of the normal delay if the output of RNSMM is required by an RNS implementation that cannot execute the fault detection.

The paper is organized as follows. In section II residue number systems, base extensions and redundancy for error detection are introduced. Section III presents and analyzes an algorithm providing detection of single faults injected during the execution of a RNSMM. Section IV proposes an architecture implementing the present method. A comparison to the only other technique (as far as the authors know) aiming to detect same kind of faults and proposed in [START_REF]A coprocessor for secure and high speed modular arithmetic[END_REF] is discussed. Finally, section V draws conclusions.

II. ABOUT RNS AND FAULT DETECTION

A. Residue Number Systems -Notations

A RNS base B is constituted by n moduli m 1 , . . . , m n and its dynamic range is Ú0, M Ú: Ö0, M Õ Z with

M : n i 1 m i . For i È Ú1, nÛ, M i denotes M
mi , and for any integer x, x i x mi

x mod m i . The Chinese Remainder Theorem [START_REF] Pohst | Algorithmic algebraic number theory[END_REF] applied to base B states that there exists a ring isomorphism ϕ B : ÔZß ÔMÕ , , ¢Õ ÔZß Ôm 1 Õ ¢ . . . ¢ Zß Ôm n Õ , prod , ¢ prod Õ if, and only if, the m i 's are pairwise coprime. So the moduli of a RNS base will be implicitly chosen pairwise coprime. Two main consequences of this theorem may be emphasized for our purpose. Firstly, for any x È Z there is a one-to-one correspondance between x M and x m1 , . . . , x mn ¨B.

x B can denote as well the n-tuple of residues of x in B as x or x M . More generally, tuples of residues and integers will be later merged in some expressions, in order to emphasize some properties. However, in this case the residues will be seen as the unique integer they represent in the dynamic range. Secondly, for every Ôx,

yÕ È Ú0, M Ú 2 , ϕ B Ô x ⊺ y M Õ x 1 ⊺ y 1 m1 , . . . , x n ⊺ y n mn ¨B with ⊺ È Ø , ¡, ¢Ù. And if x M : gcdÔx, M Õ 1 then ϕ B § § x ¡1 § § M ¨ ¡ § § x ¡1 1 § § m1 , . . . , § § x ¡1 n § § mn © B .

B. Base conversions/extensions

Given residues x B of x È Ú0, M Ú, a base extension aims to compute residues of x for new moduli. There are two main types of extension which are summarily described hereafter.

1) Mixed-Radix Conversion (MRC) [2]:

x is transformed from RNS base B to another one by passing through the mixed-radix system (MRS) associated to B. MRS coefficients of x are also an element of Zß Ôm 1 Õ ¢ . . . Zß Ôm n Õ.

2) Chinese Remainder Theorem (CRT) [START_REF] Pohst | Algorithmic algebraic number theory[END_REF]: A classical

way to compute x from x B Ôx 1 , . . . , x n Õ B is x § § § § n i 1 § § x i M ¡1 i § § mi M i § § § § M . ext B ÔxÕ : n i 1 § § x i M ¡1 i § § mi M i is called the "crt-sum" of x B , and k x : Ø extBÔxÕ M Ù its "crt-correction coefficient". Thus x ext B ÔxÕ ¡ k x M . Practically, k x is not recovered through modular reduction of macro quantities like ext B ÔxÕ.
Two methods are now described to get k x .

Shenoy and Kumaresan's method (SK) [START_REF] Shenoy | Fast base extension using a redundant modulus in RNS[END_REF]: they consider the fact that k x È Ú0, nÚ to propose to use an extra redundant modulus m sk n coprime to M . Consequently, if x sk : x m sk is known, one has:

k x k x m sk § § Ôext B ÔxÕ ¡ x sk Õ M ¡1 § § m sk . (1)
In this method, the base is now B Øm sk Ù. Thus, RNS operations handle values in a larger dynamic range Ú0, m sk M Ú.

However, to keep an exact extension of the integer expressed through the residues over B, x sk must remain pure redundancy, i.e. the true dynamic range is still Ú0, M Ú.

Kawamura et al.'s method (KWu, KWc) [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF]: , where trunc function keeps only q most significant bits and set the others to zero, and r is s.t. 2 r¡1 m i 2 r . This approximation of k x is computed by a simple unit called Cox while computations on moduli are performed in cells called Rowers. The problem of approximation is that Cox can return as well k x as k x ¡1. In the last case, the extension returns x M m for a new residue. More precisely, theorem 2 of [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF] proves that this case will occur only for some

Denoting ξ i § § x i M ¡1 i § § mi , the crt-sum is rewritten ext B ÔxÕ n i 1 ξ i M i . Then, k x Ø n i 1 ξi mi Ù.
x ∆ kw M , where ∆ kw È Ú0, 1Ú is an upper-bound of all possible errors, i.e.

0 n i 1 ¡ ξi mi ¡ truncÔξiÕ 2 r © ∆ kw . Thus
if no control is ensured on the size of the input of extension, the result can be not exact. That unexact extension will be denoted KWu. However, theorem 1 of [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF] states that if the input is guaranteed smaller than any quantity Ô1 ¡ α kw Õ M for any α kw È Ú∆ kw , 1Ú, then by adding α kw in Cox to correct the computed crt-correction coefficient the extension is exact. This corrected version is denoted KWc.

C. Redundant RNS and fault detection

The way to use redundancy to detect faults in RNS has been studied by several authors (e.g. [START_REF] Watson | Self-checked computation using residue arithmetic[END_REF]- [START_REF] Yau | Error correction in redundant residue number systems[END_REF], [START_REF] Etzel | Residue number system arithmetic: modern applications in digital signal processing[END_REF]) for many years. By adding a redundant modulus m R to B, the state space is extended to Ú0, M m R Ú, and if m R is large enough any value x affected by a single fault belongs to ÚM, M m R Ú. Then, receiving Ôx B , x mR Õ B ØmRÙ , the usual detection procedure is the computation of x B mR via a base extension, and its comparison to x mR . This is called a consistency check. If Bex denotes the base extension method used for the check (e.g. MRC, SK or KW), then one has to verify if Bex Ôx B Õ ¡ x mR mR is null or not, where xB may contain one faulty residue. Thereafter possible values of errÔxÕ : Bex Ôx B Õ ¡ x are given to supply necessary and sufficient conditions on m R for detecting any single fault.

1) MRC: The case where the check is based on MRC extension has been extensively studied. Trivially, the set of all possible values of errÔxÕ is exactly Û0, M Ú ÔM i ZÕ.

2) CRT: Here, since all residues contribute to the computation k x , a fault could modify it. So the faulty extended value could not be in the original range Ú0, M Ú.

e i ¡νm sk M i mi and x § § ¡e i M ¡1 i § § mi M i . b) KWc: Here it is assumed that x Ô1 ¡ α kw Õ M and x : ϕ ¡1 B Ôx B Õ x eM i È Ú0, M Ú where e ÈÛ ¡ m i , m i Ú. It follows that KWc Ôx B Õ x eM i ¡µM where µ È Ø0, 1Ù. Moreover µ 1 only if Ô1 ¡ α kw Õ M x M , i.e. only if e 0. Then errÔxÕ KWc Ôx B Õ ¡ x reaches at most any value of Û0, M Ú ÔM i ZÕ.
3) Required redundancy to detect single faults: Here is given a sufficient (and necessary) condition on size of m R to detect any single fault through a consistency check based on a MRC, SK or KWc extension. The MRC case has been treated in [START_REF] Watson | Self-checked computation using residue arithmetic[END_REF]- [START_REF] Yau | Error correction in redundant residue number systems[END_REF] for instance. Condition for SK case is, as far as the authors know, supplied for the first time.

Theorem 2.1: Let B Øm R Ù be a redundant RNS, where a modulus m sk is included in B if SK is used for the consistency check. A necessary and sufficient (resp. sufficient) condition to detect any single fault injected on any

tuple of residues Ôx B , x mR Õ expressed in B Øm R Ù through a consistency check based on MRC or SK (resp. KWc) extension is: m È B, m R m ¢ m R M m ¨.
Proof: Previously it has been shown that for MRC, SK and KWc extensions, the faults to be detected have the form g M m where g is in Û0, mÚ. So if such a fault is not detected, it means that there exists an integer γ

verifying g M m γm R . Then Euclide's lemma implies that mR mR M m divides g, and so m R m ¢ m R M m ¨.
This proves the sufficiency for all cases. The necessity is proved by contraposition for MRC case, by exhibiting an undetectable error. The sketch of the proof is similar for the SK extension, by using given constructive examples.

If m R m i ¢ Ôm R M i Õ for any m i in B, the error e § § § mR mR Mi M i M ¡1 i § § § mi ¢M i injected on x 0 will not be detected. Indeed, e mR mR Mi M i m R Mi mR Mi where the first equality uses the hypothesis m R m i ¢ Ôm R M i Õ.
Rem. 1: Due to the approximations in KWc extension, m R could be chosen smaller than some m i 's. However, only the sufficiency is useful for the purpose of section IV.

III. FAULT DETECTION IN RNS MODULAR

MULTIPLICATION

Efficient RNS modular multiplication [START_REF] Bajard | An RNS Montgomery modular multiplication algorithm[END_REF], [START_REF] Bajard | Modular multiplication and base extensions in residue number systems[END_REF] adapts Montgomery reduction to RNS. Because of division by M in classical Montgomery reduction, an auxiliary base B ½ coprime to the main base B is used. Algorithm 1 summarizes the technique. Hypothesis H mrc [START_REF] Bajard | An RNS Montgomery modular multiplication algorithm[END_REF], H sk [START_REF] Bajard | Modular multiplication and base extensions in residue number systems[END_REF] hyp.

Hmrc

H sk H kw Bex 1 MRC crt-sum ext B KWu Bex 2 MRC SK KWc bases M M ½ p 1 m sk M M ½ p 1 M M ½ p 1 m sk È B ½ m R max m i , m ½ i ¨max m sk m i , m ½ i ¨max m i , m ½ i ẍy M p M p 4p 2 M 2p Ôn 1Õ 2 p 4pß Ô1 ¡ ∆ kw Õ M ½ M Ôn 1Õ p 2pß Ô1 ¡ α kw Õ output s 2p s Ôn 1Õ p s 2p
Ô q Bex1 ÔqÕ: extension from B to B ½ ØmRÙ 3: t x ¢rns y rns Ô q ¢rns p in B ½ ØmRÙ 4: s t ¢rns M ¡1 in B ½ ØmRÙ 5: Ô s Bex2 ÔsÕ: extension from B ½ to B ØmRÙ 6: if Ô s m R s m R then 7:
Error detected or H kw [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF] in Fig. 1 (where p is supposed given) reflect versions of RNSMM using different types of base extension for Bex 1 and Bex 2 . Hypothesis on M and M ½ guarantee that t : xy Ô qp, which is a multiple of M and the largest value in the algo., stays in the full dynamic range Ú0, M M ½ Ú. For instance for KW version, theorem 2 of [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF] states that Ô q

Ô1 ∆ kw Õ M . Given H kw , t Ô1 ¡ ∆ kw Õ M Ô1 ∆ kw Õ M 2M p Ô1 ¡ α kw Õ M ½ M . So s t M Ô1 ¡ α kw Õ M ½ and KWc is used for Bex 2 .

A. Adequation of single fault model for RNSMM algo.

The purpose of this discussion is the pertinence of the single fault model in the presence of base extensions, as it is the case in RNSMM algo. If the fault is injected during an extension on a quantity computed in a quotient ring Zß ÔmÕ where m is a modulus of one of the bases concerned by the extension, then the effect is strictly equivalent to a single fault injected either before or after the extension. This consideration is really pertinent because in all base extension techniques previously seen, computations are ran only in such rings (except for Cox; but cf. part III-B4). So a fault injected during a base extension will be considered as a single fault appearing either before or after the extension.

Rem. 2: From hardware point of view, this analysis really depends on chosen architecture and capacities of the attacker, because for instance an attack could be launched during the distribution of the ξ i 's coefficient in new residues. Thus some of them could receive the correct value, and some others a faulty value. Such possibilities must be prevented.

B. Introduction of redundancy -Fault location

Rem. 3: (guideline) As consistency checks require a base extension which is a costly operation, the detection tech-nique should only use the own extensions of RNSMM algo.

Given part III-A about faults during base extension, only five types of error are to be considered in context of RNSMM algo: on a residue in base B before Bex 1 called category 1; on a residue in the second base B ½ called category 2; on a residue in base B after Bex 2 called category 3; and category 4 for faults on extra material for extensions such as m sk channel or Cox. Category 5 concerns faults on redundant residues. Moreover, a fundamental hypothesis is that, given m R , the redundant residues of x, y, and p are part of input of RNSMM algo. This requires that redundant version of the algo. must output s expressed in B B ½ Øm R Ù. Due to independency between residues during parallel RNS operations, as in lines 1, 3 and 4 in algo.1, cat.1 is reduced to faults injected on q before Bex 1 and cat.2 to faults on s before Bex 2 . Cat.3 is obviously the set of single faults injected on Ô s Bex 2 ÔsÕ.

1) Cat.1: A priori a fault on q must be detected with a consistency check using Bex 1 , otherwise the fault would infect all residues of Ô q and the single fault model would become unsuitable. The problem is that, by construction of q § § ¡xyp ¡1 § § M , it is impossible to compute q mR from x, y and p by using only parallel operations. Thus Bex 1 is only used to compute q on B ½ Øm R Ù.

2) Cat.2:

The aim is to obtain

s mR which is equal to § § § § tM ¡1 § § M ½ § §
mR by definition of s. From Ô q mR given by Bex 1 , one now easily has t mR xy Ô qp mR . Then t is expressed over the extended base B B ½ Øm R Ù and t M M ½ . But by construction t is also a multiple of

M , i.e. t Ô0 B , t B ½ ½ ½ Õ B B ½ . So sM § § tM ¡1 § § M ½ M Ô0 B , t B ½ ½ ½ Õ B B ½ , and s mR § § § § tM ¡1 § § M ½ § § mR § § tM ¡1 § §
mR . So by theorem 2.1, a consistency check using Bex 2 will detect faults of category 2.

3) Cat.3: The fault becomes of category 1 as soon as the output is reused as input of algo.1. Otherwise it is possible to use only one more base extension to verify integrity of Ô s, because its redundancy is known (cf. III-C).

4) Cat.4: For KWc, a fault injected directly in the Cox unit is not envisaged, because the essential interest of KW extensions is more practical than theoretical. In practice, either the hardware Cox unit is protected thanks to a standard hardware redundancy (cf. [START_REF]A coprocessor for secure and high speed modular arithmetic[END_REF]), or one can bind one Cox per Rower (cf. [START_REF] Nozaki | Implementation of RSA algorithm based on RNS Montgomery multiplication[END_REF]). In the last case, a fault on a Cox unit is just a fault on the residue computed by the Rower linked to the faulty Cox. However, it is possible to keep only one Cox. In this case, a fault on Cox could add ¨M for Bex 1 or ¨M½ for Bex 2 to the extended value. It would require to use larger bases to avoid overflow, and to deliberately add M to Bex 1 ÔqÕ so as to counteract the possible appearance of Bex 1 ÔqÕ q ¡ M , which is a problem for detection of faults of category 1 (cf. proof of th. 3.1). About SK extension, a fault in extra-channel m sk is easily detected by the consistency check (cf. th. 2.1). 5) Cat.5: Trivially detected. Theorem 3.1: Given any version of redundant RNSMM defined by a set of hypothesis in Fig. 1, it is assumed that at most one single fault of category 1, 2, 4 or 5 is injected during the execution of algorithm 1. Then the fault is injected if, and only if, the consistency check based on Bex 2 and applied to Ôs B ½ ½ ½ , s mR Õ B ½ ØmRÙ fails.

Proof: Detection of faults of cat.2 is ensured by theorem 2.1. It just remains to prove the result for faults of category 1. The consistency check verifies the nullity of s mR ¡ Ô s mR , where s mR is the redundancy of s before Bex 2 and Ô s : Bex 2 Ôs B ½ ½ ½ Õ. Because M is coprime to m R , it is the same to verify if M Ôs mR ¡ Ô sÕ mR 0 when a fault is injected. Considering Ô0, . . . , 0, e i , 0, . . . , 0Õ B affecting q, one has q : ϕ ¡1 B q 1 , . . . , q i¡1 , q i e i mi , q i 1 , . . . , q n ¨B. Then even if t xy Ô qp stays an element of Ú0, M M ½ Ú it is not a multiple of M anymore. Indeed, ϕ B ÔtÕ Ô0, . . . , 0, e i p i , 0, . . . , 0Õ B . It follows that

s mR § § ÔÔ0, . . . , 0, e i p i , 0, . . . , 0Õ B , t B ½ ½ ½ Õ B B ½ M ¡1 § § mR . But Bex 2 only extends s B ½ ½ ½ § § tM ¡1 § § M ½ Ô0 B , t B ½ ½ ½ Õ B B ½ ßM.
s mR § § Ô0 B , t B ½ ½ ½ Õ B B ½ M ¡1 µM ½ § § mR . Finally: M Ôs mR ¡ Ô sÕ mR § § Ôt B , t B ½ ½ ½ Õ B B ½ ¡ Ô0 B , t B ½ ½ ½ Õ B B ½ ¡ µM M ½ § § mR § § Ôt B , 0 B ½ ½ ½ Õ B ¡ δM M ½ ¡ µM M ½ § § mR § § a i M i M ½ § § mR where a i § § e i p i M ¡1 i M ½¡1 § § mi ¡ δm i ¡ µm i and δ È Ø0, 1Ù is such that Ôt B , t B ½ ½ ½ Õ B B ½ Ôt B , 0 B ½ ½ ½ Õ B B ½ Ô0 B , t B ½ ½ ½ Õ B B ½ ¡ δM M ½ . Because m R M i M ½ 1, one
just has to verify that 0 a i m R , i.e. a i mR 0. 1) MRC: Bex 2 exact so µ 0 and 0 a i m i m R .

2) SK: the context is different of the one of theorem 2.1. Indeed, all residues of s B ½ ½ ½ are affected by the fault over q, so SK reconstruction could return s µM ½ with µ any value in Û¡m sk , m sk Ú. Then, with m R max Ôm sk m i Õ, one has

0 a i m sk m i m R .
3) KWc: µ È Ø¡1, 0Ù. Actually δ 0 implies µ 0 and so 0 a i m i . Indeed δ

0 means Ôt B , 0 B ½ ½ ½ Õ B B ½ Ô0 B , t B ½ ½ ½ Õ B B ½ Ôt B , t B ½ ½ ½ Õ B B ½ t. Moreover, hyp. H kw still ensure that t xy Ô qp Ô1 ¡ α kw Õ M M ½ . Then s B ½ ½ ½ Ô0 B , t B ½ ½ ½ Õ B B ½ ßM Ô1 ¡ α kw Õ M ½ , so µ 0.

Rem. 4: Since randomizations of bases in Leak Resistant

Arithmetic technique [START_REF] Bajard | Leak resistant arithmetic[END_REF] only use RNSMM to switch between different Montgomery representations of data, it is compliant with the present detection method.

C. Handling faults of category 3

This case may appear if the integrity of Ô s expressed in B must be ensured and if it will not be used again as input of algo.1. By hypothesis there is at most one fault on it, so Ô s can be s e i M i M . Moreover s mR is given by the last consistency check.

1) H mrc : a standard consistency check applied to ÔÔ s, sÕ B ØmRÙ is possible.

2) H sk : in the same manner, because s sk is also known, a SK extension can be used to verify integrity of data, where a redundancy m R max Ôm i Õ suffices. . In practice, it is highly feasible to have α kw 1 2 . Indeed, by picking up notations of part 5.1 in [START_REF] Kawamura | Cox-rower architecture for fast parallel Montgomery multiplication[END_REF], for given parameters n and r then, if the trunc function keeps at least q most significant bits where q r 2 log 2 ÔnÕ¡log 2 2 r 2 ¡1 ¡ n ¨, then ∆ kw 1 2 . For instance, a 4096 bits level of security requires n 65 and r 64 (rn 4096). Thus, q 8 is sufficient. Hence, in practice one can always have condition 2p Ô1 ¡ α kw Õ M , and a KWc can be used for a consistency check.

IV. ARCHITECTURE

The goal of this section is to present an architecture implementing RNSMM and compliant both with the fault detection approach proposed here, and with the Leak Resistant Arithmetic (LRA) based on the randomization of the RNS bases [START_REF] Bajard | Leak resistant arithmetic[END_REF]. A previous RNS architecture for Montgomery multiplication with Kawamura et al. base extension was proposed in [START_REF] Nozaki | Implementation of RSA algorithm based on RNS Montgomery multiplication[END_REF]. This architecture is composed by a set of n identical arithmetic cells (rowers) that work in parallel and include a modular adder and multiplier unit, a Cox unit, and some memory. An in-depth analysis of the arithmetic cells has been presented in [20], where some other cell architectures have been proposed. In this section, the modifications required to introduce the fault attack protection in the state-of-the-art architectures are analyzed and evaluated.

A. Description of the attacker

The strategy adopted when a fault is detected is at the discretion of the user of the proposed architecture, which simply aims at detecting the fault. A stop of the process in order to avoid any leakage of information is typically a possible choice. The attacker is assumed able to inject one fault. Such type of attack is realistically achieved by a laser shot, that can change a value stored in a register, or temporary change the value of some transistors and lines during a sampling for instance. So the attacker has the ability to hit a specific area in any single cell. Furthermore he could be able to control the moment of the injection.

This paper proposes an architecture resistant against one fault. When an attacker injects several faults, there are two possible scenarios. In first case, they are injected sequentially in different Montgomery multiplications, i.e. at most one fault is injected between two consecutive consistency checks. Then the first fault corresponds to a normal single fault, so this attack is prevented by the proposed approach. In second case, some of them are injected between two consecutive consistency checks. The proposed protection approach can be extended in order to protect against this attack, by increasing the number of redundant moduli.

B. Hardware fault model

Contrary to theoretical faults, hardware faults are defined by size of registers (r bits since 2 r¡1 m j , m ½ j 2 r ) which output ξ i or ξ ½ i in each rower. The model in [START_REF]A coprocessor for secure and high speed modular arithmetic[END_REF] for a fault on ξ i is ξi ξ i e i È Ú0, 2 r Ú. The only problematic case is m i ξi 2 r ( ξi m i is theoretical model). Proposition 4.1: If outputs of rowers are over r bits, then m R 2 r , 4p M and 4p Ô1 ¡ α kw Õ M ½ allow to detect single hardware faults.

Proof: It suffices to consider faults of cat. 1 and 2. Cat.1:

ξ i e i m i f i , f i È Ú0, 2 r ¡ m i Ú Ú0, m i Ú. Denoting q ϕ ¡1 B Ôq 1 , . . . , f i , . . . , q n Õ, the crt-sum with ξi is crt-sum of q plus m i M i M . Because eval Ôf i Õ evalÔ ξi Õ eval Ôf i Õ 1, Cox of Bex 1 can compute k q δ, δ È Ø¡1, 0, 1Ù. δ È Ø¡1, 0Ù is usual in KWu case. δ 1 is not a problem as it just corrects the extra M which appears in crt-sum. Finally, Ô q can contain one extra M . It can be shown that if ∆ kw 1 2
, this extra M is always corrected if the inequality q ∆ kw M holds (which is a necessary condition to have Ô q q M when there is no fault). Thus, one has at least Ô q 2M in all cases, and it suffices to have new conditions 4p M and 3p 1¡α kw M ½ to avoid overflow.

Otherwise 2M

Ô q 3M could happen. In this case, it is sufficient to have 4p

1¡α kw M ½ . Finally, if f i È Ø0, ξ i Ù the fault is corrected, else the theoretical model is suitable. Cat.2: The considered ξ ½ j 's are those of s B ½ ½ ½ . If ξ½ i ξ ½ i e ½ i with e ½ i È Úm ½ i ¡ ξ ½ i , 2 r ¡ ξ ½ i Ú, eval Ôξ ½ i Õ evalÔ ξ½ i Õ evalÔξ ½ i Õ 1 and Cox in Bex 2 could compute k s δ with δ È Ø0, 1Ù. Finally, Bex 2 ÔsÕ n j 1 ξ ½ j M ½ j e ½ i M ½ i ¡ k s M ½ ¡
δM ½ s e ½ i M ½ i ¡ δM ½ . But e ½ i ¡ δm ½ i È Ú¡ξ ½ i , 2 r ¡ ξ ½ i Ú Û ¡ m ½ i , 2 r Ú Û ¡ 2 r , 2 r Ú. If e ½ i m ½
i and δ 1, the fault is corrected, else it is detected.

C. Description of the architecture

The general architecture is presented in Fig. 3. The Kawamura et al.'s architecture requires two modifications to be applied with the proposed fault detection procedure. First, an extra redundant cell is required to detect the fault as explained in the previous sections. The cells treat data expressed over r bits. Hence, by prop.4.1 the chosen redundancy is 2 r . Secondly, a new fault detection unit (FDU) (cf. Fig. 5) is required to check that when a value is propagated to all the cells they indeed receive the same value (cf. rem.2). Such propagation is executed during base extensions. However, it could be avoided by using a round propagation system [START_REF] Nozaki | Implementation of RSA algorithm based on RNS Montgomery multiplication[END_REF], where at each step each cell takes the input of the previous cell, and gives its previous input to the subsequent. In this case, a similar check would be required at the end of the rotation, in order to control that each cell receives again the first input, and so that no fault was injected during the rotation. Each FDU compares the input of two cells, so n ¡ 1 units are required. Furthermore, a FDU is in the redundant cell to apply the consistency check.

LRA [START_REF] Bajard | Leak resistant arithmetic[END_REF] (cf. [START_REF]A coprocessor for secure and high speed modular arithmetic[END_REF] for FPGA implementation) requires an additional unit, the base randomizer, which randomly matches the arithmetic cells with base elements, and distributes data required to calculate the constants matched to the current two random bases. Moreover, the technique requires some small changes in the cells: they will have a different control unit, able to manage the additional operations for the precomputation of the constants (calculated after each randomization), and a different access to the memory, since some data sent by the randomizer unit to the arithmetical cells must be directly stored (e.g. the remainder of 2 r mod m i ), while other values must be processed through additions and multiplications, and then stored.

The redundant cell has two main differences with respect to the standard cells. The first one is the presence of a FDU. It is used for the consistency check of theorem 3.1. The second one is that the modular adder and multiplier subunit does not work with generic modules, but with a power of 2. Fig. 4a and4b show the modular adder and multiplier units used by the standard (a) and redundant (b) cell. The standard modular adder and multiplier is compliant with the cell proposed in [START_REF] Nozaki | Implementation of RSA algorithm based on RNS Montgomery multiplication[END_REF], since the accumulation is performed by the same unit that executes additions and multiplications. However, according to another architectural strategy presented in [20], the accumulation could be executed inside the modular reduction unit. The main difference of the adder and multiplier used in the redundant cell is that the modular reduction subunit is not required. Although the multiplier and adder subunit could be identical to the same subunit used in the other cells, a smaller subunit can be used since one additive input for the accumulation is shorter and the computation of the bits larger than 2 r can be avoided.

D. Fault detection

In the previous sections, the mathematical detection of one fault has been described. In order to design an architecture secure against this attack, it is required that the injection of the fault do not have effects not considered in the analysis.

A fault injected in a cell can only modify its output values. If a fault changes a value during its computation or while it is stored, the effects correspond to the single fault injection analyzed previously. Since there is a Cox per cell, even a fault injected in a Cox unit corresponds to a single fault.

During the base extension all the cells receive an input from each cell. The distribution of these values is executed as follows: the first cell gives its result to all the cells, which use it as an input; all the other cells give their result to the previous cell, which stores it for one cycle. Thus the first cell will distribute them, one per cycle. If a fault affects only a part of the propagation line of the output of the first cell (e.g., it is injected on a buffer), some arithmetic cells could receive the wrong input. In this case, the fault does not correspond to a single fault. However, it can be easily detected through the FDUs, which check that each cell receives the same input.

If during the base extension a fault is injected in a value that must be distributed while it is stored by a cell different from the first, it corresponds to a normal single fault injected before the base extension. Since the same cell works at least for 2 moduli (one per base), the injection of one fault could generate differences on various moduli. In order to avoid this threat, the data of different moduli must be stored in different memories, so the local condition of the fault will avoid the possibility of multiple fault.

A fault in any part of the redundant cell, but not in its fault detection subunit, is simply a fault of category 5 and so is detected by the consistency check. If the fault is injected in a FDU, the unit detects the fault.

E. Evaluation

To evaluate the impact of the fault detection, an analytical study based on equivalent gates has been conducted. The adopted model is shown in Tab.I. To reach a fair evaluation, the same parameters used in [START_REF] Nozaki | Implementation of RSA algorithm based on RNS Montgomery multiplication[END_REF] have been considered: 33 cells, 32 bits per cell, 2 moduli per cell (one per base), 2 r ¡ 2 h m i 2 r , i and h 11; the architecture of standard arithmetic cells is the one of [START_REF] Nozaki | Implementation of RSA algorithm based on RNS Montgomery multiplication[END_REF].

A detailed analysis based on equivalent gates on the RNS arithmetic cell proposed in [START_REF] Nozaki | Implementation of RSA algorithm based on RNS Montgomery multiplication[END_REF] has been presented in [START_REF] Gandino | A general approach for improving RNS Montgomery exponentiation using pre-processing[END_REF]. Tab.II shows the delay of the standard and the new units. The time required by one cycle is determined by the slowest pipeline stage. The modular reduction subunit is the slowest in the standard cell, but it is divided in 2 pipeline stages, so the multiplier and adder subunit has the longest delay. The FDUs have a short delay, so they can execute the check in parallel to the normal work flow, after the cycle in which the data have been computed. Therefore, they neither require additional cycles nor increase the delay. The redundant cell executes the same operations of the standard cells with a shorter delay and with less cycles. Hence, it can works in parallel to the standard cell. Therefore, the fault detection technique proposed in this paper do not affect the delay of an exponentiation. However, as explained previously, if a valid result is requested on both the RNS bases, an additional check is required to detect final faults of cat.3. This final check, if it is not executed during the subsequent operations, requires a base extension, so its delay is less than half of a RNSMM. For example, in a RSA implementation, with a N-bit key and a Montgomery ladder for exponentiation, the increase is less than 1 2¢N with respect to the total delay. The fault detection requires additional components, which increase the total area. The area of the standard and the new units is shown in Tab.III. The largest new unit is the 2 r redundant cell. However, also considering that this cell uses a normal multiplier (without avoiding the column over the r-th bit), it is significantly smaller than a standard one, since it does not need a modular reduction unit. Even the total area of all the additional components is lower than one standard cell. Therefore, the total area increase is lower than 1 33 of the total area, considering that the number of parallel cells is 33. More generally, if the architecture contains n cells, the area increase is about 1 n of the total area. F. Comparison to Guillermin's technique [START_REF]A coprocessor for secure and high speed modular arithmetic[END_REF] Guillermin proposes a method to detect the same kind of faults considered in this paper. However, its approach is valid only in the context of Cox-Rower architecture, while the proposed technique is not limited to a specific architecture. Moreover, when associated to a leak resistant arithmetic, the detection of cat.1 faults is not guaranteed. In [START_REF]A coprocessor for secure and high speed modular arithmetic[END_REF], the detection is achieved by a modified Cox unit which computes a more precise approximation of ξi mi . For an input xy bounded by νp 2 , required conditions on size of bases are: νp M and 3p2 r 2 M ½ . Comparing to νp M and 4p 1¡α kw M ½ for the present architecture, the Guillermin's approach requires to increase base B ½ by at least one extra standard modulus. Thus extra hardware needed is one standard Rower and modified Cox for [START_REF]A coprocessor for secure and high speed modular arithmetic[END_REF], against one redundant Rower only dedicated to 2 modulus and detection units. So, given Tab.III, the present technique needs less extra hardware than [START_REF]A coprocessor for secure and high speed modular arithmetic[END_REF]. Moreover, to add a standard Rower directly impacts computation time of RNSMM. For a 1024 bit RSA-CRT, Guillermin measured that the extra time cost due to his technique is about 5%, for two consecutive 512 bit exponentiations based on Montgomery ladder. So this is two times 1024 executions of RNSMM algorithm. In present technique, the extra delay is less than 1 2¢1024 0.05%. And it is only due to the detection of final faults of category 3 in the output of both exponentiations. Lastly, the present technique can be adapted for detection of several faults by adding more redundant moduli.

V. CONCLUSION

A simple and cheap way to detect single faults injected during a RNS modular multiplication has been presented. The new method has the advantage that no condition is imposed on the choice of bases and base extension techniques, and so is compliant with any RNS Montgomery modular multiplication algorithm. During a base extension, the redundant modulus works in parallel to the cells of the output base. Thus redundant computations and consistency checks do not increase the computation time of a RNS modular

Figure 1 :

 1 Figure 1: Hypothesis for Algorithm 1

Figure 2 :Fig. 2

 22 Figure 2: Categories of fault in RNSMM

  Depending on the chosen set of hypothesis in Fig.1, Bex 2 can be MRC, SK, or KWc. In all cases, Ô s s B ½ ½ ½ µM ½ , where possible values of µ are detailed thereafter. Then Ô

3 )

 3 H kw : one easily shows that 2p 1¡α kw 4p 1¡∆ kw if, and only if, α kw 1 ∆ kw 2

Figure 4 :Figure 5 :

 45 Figure 4: Modular adder and multiplier unit in a standard (a) and redundant (b) cell (a)

  a) SK: SK xB Øm sk Ù ¨È Ú0, m sk M Ú. More precisely two cases can appear (for brevity's and completeness' sake, constructive examples are given but without details). Either the fault affects the redundant residue x sk . In this case, errÔxÕ § § SK xB Øm sk Ù ¨¡ x § § can reach any value in Û0, m sk M Ú ÔMZÕ. Indeed, from eq. (1), by taking x 0 and a fault e sk ¡γM sk with γ any value in Û0, m sk Ú, then errÔxÕ γM . Or the fault is on a residue x i . Here, errÔxÕ reaches any value in the set Û0, m sk M Ú Ôm sk M i ZÕ. For instance, to obtain errÔxÕ γm sk M i with γ any value in Û0, m i Ú, if § § ¡γm sk mi § § ¡γm sk M i mi and x 0. Else, there exists 0 ν mi m sk s.t. ¡γm sk mi νm sk , and one can take

	m sk	0 one can take
	e i

Algorithm 1 :

 1 Redundant RNS modular multiplication Input: coprime bases B and B ½ , mR coprime to B and B ½ , integers p, x and y (expressed in B B ½ ØmRÙ) and base extensions Bex1 and Bex2 verifying hypothesis Hmrc, H sk or H kw Output: s expressed in B B ½ ØmRÙ s.t. s xyM ¡1 Ômod pÕ 1: q Ô¡x ¢rns yÕ ¢rns p ¡1 in B

2:

Table I :

 I Basic logic library in CMOS technology[START_REF] Gajski | Principles of Digital Design[END_REF]

	Gate	Area (transistors)	Delay (Inverter)
	Inverter	2	1
	NAND	4	1.4
	NOR	4	1.4
	XNOR	12	3.2
	NAND3	8	1.8
	NAND4	10	2.2
	REGISTER	15	4.8

Table II :

 II Delay of Considered Units with r 32, k 33, h 11

	Unit	Delay (gates)	Delay (inverters)
	Standard multiplier	15XNOR+4NAND4+15NAND+4NOT+register	86.6
	Standard modular reductor	13XNOR+4NAND4+11NAND+7NOT+register	77.6
	2 r multiplier	15XNOR+4NAND4+9NAND+4NOT+register	78.2
	Fault detection unit	XNOR+2NAND4+NAND	6.6

Table III :

 III Area Cost for the Considered Units with r 32, n 33, h 11 curve point addition. Moreover, the integration in an architecture like Cox-Rower's one implies a limited increase of area and a possible extra delay smaller than 1 2¢log 2 ÔexponentÕ times normal delay.

	Cell	Multiplier adder unit	Modular reduction unit	Cox	Detection Units	Tot.(kilo transistors)
	Standard	992FA+32HA+140XNOR+69NAND4	562FA+51HA+214XNOR+102NAND4	9FA+9register 0	100
		+92NAND3+1623NAND+70NOR	+136NAND3+1357NAND+107NOR
		+1784NOT+70register	+1390NOT+108register
	2 r	992FA+32HA+128XNOR+60NAND4	0	9FA+9register 32XNOR+	63	79
		+80NAND3+1444NAND+64NOR			10NAND4+NAND
		+1704NOT+64register
	Detection	0	0	0	32¢(32XNOR+	16
					10NAND4+NAND)
	exponentiation/elliptic