Gilles Barthe
email: gilles.barthe@imdea.org

François Dupressoir

Pierre-Alain Fouque
email: pierre-alain.fouque@ens.fr

Benjamin Grégoire
email: benjamin.gregoire@inria.fr

Mehdi Tibouchi
email: tibouchi.mehdi@lab.ntt.co.jp

Jean-Christophe Zapalowicz
email: jean-christophe.zapalowicz@inria.fr

Making RSA-PSS Provably Secure Against Non-Random Faults

Keywords: Fault Attacks, PSS, RSA-CRT, Infective countermeasure, Formal Verification, EasyCrypt

RSA-CRT is the most widely used implementation for RSA signatures. However, deterministic and many probabilistic RSA signatures based on CRT are vulnerable to fault attacks. Nevertheless, Coron and Mandal (Asiacrypt 2009) show that the randomized PSS padding protects RSA signatures against random faults. In contrast, Fouque et al. (CHES 2012) show that PSS padding does not protect against certain non-random faults that can be injected in widely used implementations based on the Montgomery modular multiplication.

In this paper, we prove the security of an infective countermeasure against a large class of non-random faults; the proof extends Coron and Mandal's result to a strong model where the adversary can choose the value of the faulty signatures modulo one of the prime factors of the RSA modulus. This fault model is clearly strictly more general than Coron and Mandal's, and it captures most of the non-random faults of Fouque et al. Such non-random faults induce, together with the infective countermeasure, more complex probability distributions than in the original proof; we analyze them using careful estimates of character sums over finite fields. The security proof is formally verified using appropriate extensions of EasyCrypt, and provides the first application of formal verification to provable (i.e. reductionist) security in the context of fault attacks.

Introduction

Signature schemes are among the most widely used constructions in cryptography. Although there is much interest in signature schemes based on elliptic curves, RSA signatures are still widely used. Moreover, many implementations of RSA, including OpenSSL and implementations for embedded devices such as smartcards, use the well-known Chinese Remainder Theorem (CRT) technique for computing modular exponentiations more efficiently: exponentiations using the CRT can be expected to be 4 times faster than those using full-size exponents. However, when unprotected, RSA-CRT is vulnerable to the so-called Bellcore attack, first introduced by Boneh, DeMillo and Lipton [START_REF] Boneh | On the importance of eliminating errors in cryptographic computations[END_REF], and later refined [START_REF] Aumüller | Fault attacks on RSA with CRT: Concrete results and practical countermeasures[END_REF][START_REF] Yen | Permanent fault attack on the parameters of RSA with CRT[END_REF]. An adversary who knows the padded message and can inject a fault in one of the half exponentiations can efficiently factor the public modulus using a single faulty signature and a GCD computation.

Many countermeasures have been proposed to mitigate this vulnerability, including extra computations and sanity checks of intermediate and final results (see [START_REF] Rivain | Securing RSA against fault analysis by double addition chain exponentiation[END_REF]). The simplest such protection is to verify the signature before releasing it. This is reasonably cheap since the public exponent e is usually small. Another approach is to use an extended modulus, as in Shamir's trick [START_REF] Shamir | Improved method and apparatus for protecting public key schemes from timing and fault attacks[END_REF] and its later refinements which also protect CRT recombination using Garner's formula [START_REF] Blömer | A new CRT-RSA algorithm secure against Bellcore attacks[END_REF][START_REF] Ciet | Practical fault countermeasures for Chinese remaindering based cryptosystems[END_REF][START_REF] Vigilant | RSA with CRT: A new cost-effective solution to thwart fault attacks[END_REF][START_REF] Coron | Fault attacks and countermeasures on Vigilant's RSA-CRT algorithm[END_REF]. Finally, redundant exponentiation algorithms [START_REF] Giraud | An RSA implementation resistant to fault attacks and to simple power analysis[END_REF][START_REF] Rivain | Securing RSA against fault analysis by double addition chain exponentiation[END_REF] such as the Montgomery Ladder can be used. Regardless of the approach, RSA-CRT fault countermeasures tend to be rather costly: for example, Rivain's countermeasure [START_REF] Rivain | Securing RSA against fault analysis by double addition chain exponentiation[END_REF][START_REF] Le | On double exponentiation for securing RSA against fault analysis[END_REF] has a stated overhead of 10% compared to an unprotected implementation, and is purportedly more efficient than previous works [START_REF] Giraud | An RSA implementation resistant to fault attacks and to simple power analysis[END_REF][START_REF] Vigilant | RSA with CRT: A new cost-effective solution to thwart fault attacks[END_REF][START_REF] Le | On double exponentiation for securing RSA against fault analysis[END_REF].

Boneh et al.'s original fault attack does not apply to RSA signatures with probabilistic encoding functions, but some extensions of it were proposed to attack randomized ad-hoc padding schemes such as ISO 9796-2 and EMV [START_REF] Coron | Fault attacks on RSA signatures with partially unknown messages[END_REF][START_REF] Coron | Fault attacks against EMV signatures[END_REF]. At Asiacrypt 2009, Coron and Mandal [START_REF] Coron | PSS is secure against random fault attacks[END_REF] paved the way of provable security against side-channel attack in a practical setting by proving that RSA-PSS is secure against random faults in the random oracle model. Injecting a fault on the half-exponentiation modulo the second factor q of N produces a result that can be modeled as uniformly distributed modulo q, and the result of such a fault cannot be used to break RSA-PSS signatures. It is tempting to conclude that using RSA-PSS should enable signers to dispense with costly RSA-CRT countermeasures. However, Fouque et al. [START_REF] Fouque | Attacking RSA-CRT signatures with faults on Montgomery multiplication[END_REF] show that it is possible to break RSA-PSS using certain non-random faults if the result is not checked. Indeed, they obtain a key recovery attack with a few faulty signatures on CRT implementations of RSA-PSS that use the state-of-the-art modular multiplication algorithm of Montgomery [START_REF] Montgomery | Modular multiplication without trial division[END_REF]. Thus, even with PSS, it remains important to check the signature before releasing it.

Infective countermeasures. Checking results before release is a simple and practical security measure, but it is not sufficient by itself, since simple tests can be easily bypassed by flipping the outcome of a comparison [START_REF] Anderson | Low cost attacks on tamper resistant devices[END_REF][START_REF] Trichina | Multi fault laser attacks on protected CRT-RSA[END_REF]. Infective countermeasures are an alternate approach in which results are released all the time, but become gibberish when faulty computations occur: a fault (usually not controlled by the adversary) results in a random value, which consequently makes the faulty signature random. From a security point of view, since faults may not be random, we may not be able to prove that the faulty output is fully random. However, one may ask that the output be independent of secret information even in the presence of non-random faults. Infective countermeasures have been used before by Canetti and Goldwasser [START_REF] Canetti | An efficient threshold public key cryptosystem secure against adaptive chosen ciphertext attack[END_REF] to deal with fault-injecting adversaries when decrypting ciphertexts in a distributed manner. One such countermeasure for RSA-CRT was proposed by Boscher, Handschuh and Trichina [START_REF] Boscher | Fault resistant RSA signatures: Chinese remaindering in both directions[END_REF]. In their technique, the signer computes the signature S and recomputes y ′ = S e mod N to check the signature against the padded message y, before returning S + y ′ p -(y mod p) + y ′ q -(y mod q) if y ′ = y, and an error otherwise. Even if the adversary bypasses the verification y ′ = y, the output signature mixes the fault and correct signature in a non-trivial way. Still, this countermeasure was later attacked by Trichina and Korkikyan [START_REF] Trichina | Multi fault laser attacks on protected CRT-RSA[END_REF] for deterministic padding schemes. We tackle the problem of masking faulty signatures so as to prevent the exploitation of faults and protect validity checks.

Our contributions. In this paper we generalize the fault model from [START_REF] Coron | PSS is secure against random fault attacks[END_REF] and consider a very powerful adversary able to inject non-random faults. More precisely, we let the adversary set the value modulo q of the computed signatures to an arbitrary value of his choice. Clearly, since he could choose that value randomly, the model is strictly more powerful than the one considered by Coron and Mandal. In addition, it captures many other types of faults, such as the "null faults" and "constant faults" introduced by Fouque et al. [START_REF] Fouque | Attacking RSA-CRT signatures with faults on Montgomery multiplication[END_REF]. If such a signatures is directly returned to the adversary, he can clearly factor the modulus, but we consider a simple countermeasure to avoid that problem. The countermeasure, described in Fig. 1, uses infective techniques, mixing additional randomness into faulty signatures in a provably secure way. In practice, we show that our random infection masks faulty signatures enough for us to prove the security of RSA-PSS under the RSA assumption in the random oracle model if enough additional randomness is provided. Concretely, we sample a random value r ′ and add r ′ • (y -y ′ ) to the signature mod N , where y is the original padded message and y ′ is the padded message recovered from the signature. When the signature is computed correctly, (y -y ′ ) is zero and the correct signature is returned. If the signature is faulty, we show that the masked output is statistically close to uniform and hence leaks no secret information. We prove such results in two key lemmas corresponding to [14, Lemmas 1,[START_REF] Anderson | Low cost attacks on tamper resistant devices[END_REF]. Since our faults are non-random, the probability distributions are more complex; we use careful estimates of exponential sums attached to corresponding rational functions to establish their regularity. We only analyze this countermeasure when the validity check is performed in the standard way (by computing the public permutation), but our random infection might also be used to protect other checks such as Rivain's [START_REF] Rivain | Securing RSA against fault analysis by double addition chain exponentiation[END_REF][START_REF] Le | On double exponentiation for securing RSA against fault analysis[END_REF]. A discussion of the faults we model can be found in Section 2.

The second contribution of the paper is a formal proof of security of the countermeasure using EasyCrypt5 , a computer-aided framework that has previously been used to reason about the security of cryptographic constructions-but was never applied to fault attacks and countermeasures. Our proof is the first application of formal verification to provable security against fault attacks, as other works [START_REF] Christofi | Formal verification of a CRT-RSA implementation against fault attacks[END_REF][START_REF] Moro | Formal verification of a software countermeasure against instruction skip attacks[END_REF][START_REF] Rauzy | A formal proof of countermeasures against fault injection attacks on CRT-RSA[END_REF] applying formal verification to fault attacks are focused on proving the correctness of the countermeasures (that is, that the protected ω ← H (m, r)

4: st ← G(ω) ⊕ (r || 0 kg -k 0 ) 5: y ← os2ip(0 || ω || st) 6:
σp ← y dp mod p ⊲ Signature computation 7:

σq ← y dq mod q 8: σ ← (αp • σp + αq • σq) mod N ⊲ αp = q • (q -1 mod p) and similarly for αq 9:

y ′ ← σ e mod N 10:

r ′ ← {0, 1} ρ \{0} ⊲ Infective countermeasure 11: σ ′ ← σ + r ′ • (y -y ′ ) mod N 12: return i2osp(σ ′ )
program either returns the same result as the original program, or fails), but do not provide any provable security guarantees. Apart from increasing our confidence in the effectiveness of the countermeasure, our formal proof reveals a glitch in the proof of Coron and Mandal [START_REF] Coron | PSS is secure against random fault attacks[END_REF], and also paves the way for formally verifying the effectiveness of the countermeasures on standard implementations of PKCS probabilistic signing, in the same way that [START_REF] Almeida | Certified computer-aided cryptography: efficient provably secure machine code from high-level implementations[END_REF] uses an older prototype of EasyCrypt [START_REF] Barthe | Computer-aided security proofs for the working cryptographer[END_REF] to prove security of an implementation of PKCS encryption.

Related work. Christofi et al. [START_REF] Christofi | Formal verification of a CRT-RSA implementation against fault attacks[END_REF] use a combination of program transformation and verification techniques for proving Vigilant's countermeasure for CRT-RSA. They take a source program p and output a program p that contains all possible faulty behaviors of p. Then, they show that the program p either returns a value that matches the value returned by p on the same input, or else returns an error, they conclude that the program is correct for all faults. While it is a natural guarantee to seek, their theorem does not constitute a proof of security in the sense of provable security, but rather a heuristic to validate a countermeasure implementation.

Rauzy and Guilley [START_REF] Rauzy | A formal proof of countermeasures against fault injection attacks on CRT-RSA[END_REF] develop symbolic methods to analyze fault attacks against RSA-CRT implementations. They model arithmetic computations as algebraic expressions, and define a simplification procedure for expressions. Given an expression e (representing the algorithm to be attacked), their tool tests for all possible faulty variants ê of e if the expression gcd(N, e -ê) simplifies to a prime factor of the RSA modulus. If some expression ê is found, then the algorithm is considered insecure. Their tool is useful to find fault attacks on an algorithm, but only provides guarantees of security against a restricted class of attackers. Moreover, it is specialized to deterministic signature schemes and cannot deal with randomized paddings like PSS.

Moro et al. [START_REF] Moro | Formal verification of a software countermeasure against instruction skip attacks[END_REF] focus on the specific class of instruction skip attacks, in which an adversary forces to skip the execution of a targeted instruction. To protect against skip attacks, they transform a program p into a fault-tolerant program p, by providing for each instruction a possible replacement for execution in the presence of instruction skip faults. Using a model checker, they establish the equivalence between executing the instruction without faults and executing the replacement sequence of instructions with instruction skip faults. Their approach is general, and significantly improves resistance against instruction skip attacks. However, it is not suitable for obtaining the strong guarantees required by provable security.

Our results

Instead of considering the many possible faults an adversary could inject in Fig. 1, we give the adversary access to two distinct oracles (Fig. 2) that compute valid signatures (oracle S) and generalize faulty signatures (oracle F ), as justified in Section 2. As discussed, our fault model is independent of the algorithm used to compute modular exponentiation. We therefore use simpler definitions for public and secret key, where a public key pk is composed of a public exponent e and a modulus N , and a secret key sk is composed of a private exponent d and a modulus N .

Throughout the security proof, we consider a fixed k that serves as the size of the modulus and signatures. In particular, we assume that the modulus is balanced, that is

N = p•q is such that 2 k-1 ≤ N < 2 k and 2 k/2-1 ≤ p < q < 2 k/2 .
We also assume that public exponents produced by the key generation algorithm are upper bounded by some constant e max much smaller than 2 k (in practice, 2 16 + 1 is often used). PSS padding is computed using two hash functions H , outputting bitstrings of length k h , and G, producing bitstrings of length k g , where k h + k g + 1 = k. In addition, the padding scheme uses a random salt of length k 0 < k g . For simplicity, we model H as a function from {0, 1} * × {0, 1} k0 to Figure 2 Oracles in our fault model

1: oracle S(m) 2: r ← {0, 1} k 0 3: ω ← H (m, r ) 4: st ← G(ω) ⊕ (r || 0 kg -k 0 ) 5: y ← os2ip(0 || ω || st) 6: σ ← y d mod N 7:
return i2osp(σ)

1: oracle V (m, σ) 2: r ← ⊥ 3: s ← os2ip(σ) 4: if 0 < s < N then 5: y ← s e mod N 6: b || ω || st ← i2osp(y) 7: r || γ ← st ⊕ G(ω) 8: ω ′ ← H (m, r) 9: r = b = 0 ∧ ω = ω ′ ∧ γ = 0 kg -k 0 10: return r 1: oracle F (m, a) 2: r ← {0, 1} k 0 3: ω ← H (m, r) 4: st ← G(ω) ⊕ (r || 0 kg -k 0 ) 5: y ← os2ip(0 || ω || st) 6: σ ← y d mod N 7: r ′ ← {0, 1} ρ \{0} 8: σ ′ ← y d • αp + (a + r ′ • (y -a e )) • αq 9: return i2osp(σ ′ )
{0, 1} k h , and G as a function from {0, 1} k h to {0, 1} kg . This is done without loss of generality. In algorithm and game descriptions, we denote with i2osp and os2ip the conversions between integers and their binary representations. For simplicity, i2osp always produces a bitstring of length k.

We reduce the UF -CMA security of the faulty signature scheme presented in Fig. 2, when the adversary is given access to the faulty signature oracle along with the valid signature oracle and the random oracles H and G, to the one-way security of RSA. We consider a forgery valid even if it was produced by the faulty signature oracle. In the rest of this paper, we use S to denote the valid signature oracle, F to denote the faulty signature oracle, K to denote the RSA key generation algorithm, and V for the PSS verification algorithm. Subscripts identify the game in which a particular oracle appears. We denote with Q X the set of query-response pairs for queries made to oracle X so far.

Figure 3 Initial and Final Games

1: game UF -CMA 2: (e, d , N ) ← K () 3: (m, s) ← A S,F ,H ,G (e, N ) 4: b ← V (m, s) 5: win ← b ∧ (m, s) / ∈ Q S 6:
return win

1: game OW -RSA 2: (e, d , N ) ← K () 3: x * ← [0..N ) 4:
y * ← x * e mod N 5:

x ← I(e, N , y * ) 6:

return x = x *
Theorem 1 (UF -CMA security of protected PSS in the presence of faults). Given a CMA adversary A against the faulty signature scheme (K , S, F , V ) that makes at most q H queries to H , q G queries to G, q S queries to S and q F queries to F , we build a one-way inverter I such that

Pr[UF -CMA : win] ≤ Pr[OW -RSA : x = x * ] + ǫ 0 with ǫ 0 = (q H + q S + q F ) • (q H + q G + q S + q F ) + q G • q F • 3 + 1 2 k h + (q S + q F ) • (2 • q H + q S + q F ) + q H + q S 2 k0 + 1 2 k 2 -1 + q F • (4e 2 max + 1) • k 2 2 ρ-k/2
Remark 1. This theorem allows us to conclude directly with a security claim for PSS when e max is reasonably small (typically 2 16 + 1), ρ ≥ k/2 + 200, and the modulus is not too large (see Remark 2).

Fault model justification. In this section, we justify our fault model, described by oracle F (m, a) in Fig. 2. Our faulty signature oracle computes the correct padded message y, samples r ′ and returns σ ′ = y d • α p + (a + r ′ (y -a e )) • α q with a ∈ Z/qZ chosen by the adversary.

We allow multiple faults to be injected, but only during the RSA-CRT computation (lines 6-7 of the protected signing Fig. 1). More precisely, we consider a scenario where the computation modulo p is correct whereas those modulo q is faulted to result in a constant a chosen by the adversary, i.e. σ f = (y d mod p, a mod q) ∈ Z/pZ × Z/qZ. Then, using our countermeasure we obtain:

σ ′ =σ f + r ′ (y -σ e f ) =y d α p + α q a + r ′ (y -(y d α p + α q a) e ) =y d α p + (a + r ′ (y -a e ))α q .
Our fault model leverages the results of Coron and Mandal in [START_REF] Coron | PSS is secure against random fault attacks[END_REF] who treated the case of random faults against PSS scheme, and those of Fouque et al. [START_REF] Fouque | Attacking RSA-CRT signatures with faults on Montgomery multiplication[END_REF] who proposed various faults: the Null faults (forcing a small register to 0), the Constant faults (forcing a small register to a constant) and the Zero High-Order Bits faults (forcing part of a small register to 0). When applied during the RSA-CRT computations to a precise small register, these faults may allow the adversary to factor the RSA modulus. They apply to any padding scheme, including randomized padding schemes such as PSS.

With our formalization, we take into account the Null faults model, which results in nullifying the signature modulo q, by considering a = 0. Moreover, we cover a more powerful model than the random faults one by giving to the adversary the choice of the value a.

Statistical Lemmas

We need several results on the regularity of the probability distributions related to the infective countermeasure. Recall that the statistical distance between a random variable X on a finite set S and the uniform distribution is defined as:

∆ 1 (X) = 1 2 • s∈S Pr[X = s] - 1 |S| .
We say that X is δ-statistically close to uniform when ∆ 1 (X) ≤ δ.

Our proofs rely on character sums over Z/qZ. We refer to [START_REF] Montgomery | Topics in multiplicative number theory[END_REF] or the full version of this paper [START_REF] Barthe | Making RSA-PSS provably secure against non-random faults[END_REF] for basic properties of Dirichlet characters and character sums. The main statistical result can be stated as follows.

Lemma 1. Consider integer intervals X = [1, X], W = [w 0 , w 0 + W ) whose lengths X, W satisfy X, W < q, and for all t ∈ Z/qZ, denote by T (X , W; t) = XW q • 1 + V (X , W; t) the number of solutions (x, w) ∈ X × W of the congruence xw ≡ t (mod q). Assuming that the Generalized Riemann Hypothesis holds, then for all δ > 0, there exists a constant κ δ > 0 depending only on δ (and not q, X , W) such that:

t∈Z/qZ V (X , W; t) ≤ κ δ q 3/2+δ √ XW .
In particular, the distribution of the products xw mod q is statistically close to uniform in Z/qZ whenever XW ≫ q 1+3δ . Proof. Note first that all elements of X are invertible modulo q, whereas at most one element of W is divisible by q. Denote by W * the number of elements of W which are invertible modulo q, which is thus equal to W or W -1. We then have:

T (X , W; 0) = X • (W -W * ) ≤ X and hence V (X , W; 0) ≤ q W .
On the other hand, for t = 0, we can express T (X , W; t) as a sum over the multiplicative characters modulo q. Indeed, the orthogonality of characters ensures that, for all x, w, we have χ χ(xw)χ(t) = q -1 if xw ≡ t (mod q) and 0 otherwise. Hence:

T (X , W; t) = 1 q -1 χ (x,w)∈X ×W χ(xw)χ(t) = XW * q -1 + 1 q -1 χ =χ0 (x,w)∈X ×W χ(xw)χ(t),
by putting aside the contribution of the trivial character χ 0 . Write that equality as T (X , W; t) = XW * q-1 • 1 + V * (t) . We then have:

V * (t) = 1 XW * χ =χ0 (x,w)∈X ×W χ(xw)χ(t),
and we can express the sum of the squared deviations V * (t)

2 as:

t =0 V * (t) 2 = 1 (XW * ) 2 χ,χ ′ =χ0 x,w,x ′ ,w ′ χ(xw)χ ′ (x ′ w ′ ) t =0 (χχ ′ )(t).
The sum over t on the right-hand side is equal to q -1 if χ = χ ′ and vanishes otherwise, so that:

t =0 V * (t) 2 = q -1 (XW * ) 2 χ =χ0 x,w,x ′ ,w ′ χ(xw)χ ′ (xw) = q -1 (XW * ) 2 χ =χ0 S(χ) 2 ,
where S(χ) = x∈X χ(x) w∈W χ(w). Now since X is an interval of the form [1, X], it is classical that GRH implies, for any δ > 0, x∈X χ(x) ≤ c δ X 1/2 q δ for some constant c δ > 0 (see e.g. [20, Eq. (13.2)]). Hence:

t =0 V * (t) 2 ≤ q -1 (XW * ) 2 • c 2 δ Xq 2δ • χ (w,w ′ )∈W 2 χ(w)χ(w ′ ) ≤ c 2 δ q 2δ (q -1) 2 XW *
by using orthogonality again. Then, the Cauchy-Schwarz inequlity yields:

t =0 V * (t) ≤ c 2 δ q 2+2δ XW * • q -1 ≤ c δ q δ (q -1) 3/2 √ XW .
Finally, observe that for t = 0, we have:

V (X , W; t) = q XW T (X , W; t) -1 = q XW • XW * q -1 • 1 + V * (t) -1 = qW * (q -1)W V * (t) - W -q(W -W * ) (q -1)W .
On the last line, the first term is bounded in absolute value by q q-1 V * (t) , and the second term by q q-1 W . As a result, we get:

t∈Z/qZ V (X , W; t) ≤ q q -1 t =0 V * (t) + q W + V (0) ≤ c δ q 3/2+δ √ XW + 2q W
which yields the stated result for κ δ = c δ + 2, say (as a coarse upper bound). ⊓ ⊔

We now discuss our key statistical lemmas. The first one ensures that the faulty signature σ ′ = y d • α p + a + r ′ (y -a e ) • α q is indistinguishable from a uniform random element in Z/N Z if the nonce r ′ is large enough. We write x instead of r ′ in the rest of this section. Lemma 2. Let N = pq be a k-bit balanced RSA modulus and e the public exponent, 0 ≤ y < 2 k-1 a random integer and x a random nonzero ρ-bit integer. Fix an arbitrary integer a. Assuming that the Generalized Riemann Hypothesis holds, the statistical distance between the distribution of σ ′ = y d • α p + a + x(ya e ) • α q mod N and the uniform distribution modulo N is bounded as:

∆ 1 (σ ′ ) ≤ κ δ q δ N XY ≤ 2k δ • 2 (kδ-ρ)/2
for any δ > 0, with κ δ as in Lemma 1.

Proof. The statistical distance between the distribution of σ ′ and the uniform distribution can be written as:

∆ 1 (σ ′ ) = 1 2 (s,t)∈Z/pZ×Z/qZ Pr (x,y)∈X ×Y σ ′ ≡ s (mod p) σ ′ ≡ t (mod q) - 1 N
where X and Y are the integer intervals [1, X] and [0, Y ) with X = 2 ρ -1 and Y = 2 k-1 respectively. Let us estimate the probability

P (s, t) = Pr (x,y)∈X ×Y σ ′ ≡ s (mod p) σ ′ ≡ t (mod q)
appearing in that equation for some fixed (s, t) ∈ Z/pZ × Z/qZ. We have σ ′ ≡ s (mod p) if and only if y d ≡ s mod p, i.e. y ≡ s e mod p. Hence, the solutions of the first congruence are of the form y = (s e mod p) + pw for w in the integer interval [0, W s ), W s = ⌈ Y -(s e mod p) p ⌉. Then, the second equation, which is equivalent to a + x(y -a e ) ≡ t (mod q), becomes x(pw + (s e mod p) -a e ) ≡ t -a (mod q). This can be written in the form x(w + w 0 ) = t 0 (mod q), with w 0 = (s e mod p)-a e p mod q and t 0 = t-a p mod q. The number of solutions (x, w) is thus T (X , W s ; t 0 ), with W s = [w 0 , w 0 + W s ). Hence:

P (s, t) = 1 XY T X , W s ; t 0 = W s qY + W s qY V X , W s ; t 0 .
Note that W s depends only on s (not on t), and that t → t 0 is a permutation of Z/qZ. Thus, for fixed s, we can sum the previous equation over t ∈ Z/qZ, which gives:

t∈Z/qZ P (s, t) - 1 N ≤ q • W s qY - 1 N + W s qY t∈Z/qZ V X , W s ; t . Now Y /p -1 ≤ W s ≤ Y /p + 1
, so that the first term on the right-hand side is bounded by 1/Y . Thus, Lemma 1 yields: The security proof requires another statistical lemma which ensures that the adversary has a negligible probability of querying the correct value ω ← H (M, r) given a faulty signature. The proof, which uses Lemma 1 in a very similar way as the proof of Lemma 2 (simply replacing the interval Y by a subinterval Y ω ), is given in the full version of this paper [START_REF] Barthe | Making RSA-PSS provably secure against non-random faults[END_REF]. Lemma 3. Let N, e, a, δ, κ δ be as in Lemma 2. Assume that ρ ≥ k h + δk + log 2 (4κ δ ). For any choice of σ ′ ∈ Z/N Z and any k h -bit value ω ′ , the probability that a solution (x, y)

t∈Z/qZ P (s, t) - 1 N ≤ 1 Y + W s qY • κ δ q 3/2+δ √ XW s = κ δ q 1/2+δ
∈ [1, 2 ρ ) × [0, 2 k-1 ) of the equation σ ′ ≡ y d • α p + a + x(y - a e ) • α q (mod N ) satisfies that the most significant k h bits ω ∈ [0, 2 k h ) of y coincides with ω ′ is bounded as: Pr ω = ω ′ |σ ′ ≤ 3 2 k h .
Remark 3. Concretely, this result means that we have to choose ρ larger than k h /2.

Security proof

The sequence of games presented in this Section and formal justifications for all transitions between games are formalized in EasyCrypt. However, Lemmas 2 and 3 are stated as axioms of the formalization. Formally proving these lemmas is outside the scope of this work, as it would first require to formalize at least those properties of additive characters used in our proof.

The hash functions G and H are modelled as random oracles. For clarity, we display the initial definition of H on the left in Fig. 4. The initial definition of G is similar. We assume two global maps h and g are used to build the random oracles. Our proof works mostly by transforming the random oracle H . We therefore display the code for H for each transition, only displaying other oracles when they suffer non-trivial changes.

Game 0. We initially transform both random oracles to keep track of the first caller to make a particular query. It can be either the adversary (Adv), the signature oracle (Sig), or the faulty signature oracle (FSig). Calls made by the experiment when checking the validity of the forgery do not need to tag their query as they are the last queries made to the random oracles and do not need to update its state. We also extend the internal state of H with an additional field for use later in the proof, and currently set to a default value ⊥.

1: oracle H (m, r ) 2: if (m, r) / ∈ dom(h) then 3: h[m, r ] ← {0, 1} k h 4: return h[m, r] 1: oracle H0 (m, r ) 2: if (m, r) / ∈ dom(h) then 3: ω ← {0, 1} k h 4: h[m, r ] ← (ω, c, ⊥) 5: return π1(h[m, r])
Pr[UF -CMA A,K ,S,F ,V : win] = Pr[Game0 : win] Games 1 and 2. In Game 1, we anticipate a call to G on the output of H every time H is called. When H is called by either one of the signing oracles, we return the result of that call to G as well as the result of the current H query, allowing broad simplifications to the signing oracles. In Game 2, we deal with collisions on r and ω values in the signing oracles. In later steps of the proof, we will need the control-flow of the faulty signature oracle to be completely independent from both r and ω, and we modify the oracle to allow these later transformations. Fresh

Figure 5 Games 1 and 2: anticipating calls to G and removing signing collisions

1: oracle H1(c, m, r ) 2: if (m, r) / ∈ dom(h) then 3: ω ← {0, 1} k h 4: h[m, r ] ← (ω, c, ⊥) 5: st ← G(c, ω) 6: else 7: ω ← π1(h[m, r ]) 8: if c = Adv then 9: st ← ⊥ 10: else 11: st ← G(c, ω) 12:
return (ω, st)

1: oracle H2(c, m, r ) 2: if (m, r) / ∈ dom(h) ∨ c = FSig ∨ (c = Sig ∧ π2(h[m, r ]) = FSig) then 3: ω ← {0, 1} k h 4: st ← {0, 1} kg 5: if c = FSig ∨ (m, r ) / ∈ dom(h) then 6: h[m, r ] ← (ω, c, ⊥) 7: if c = FSig ∨ ω / ∈ dom(g) then 8: g[ω] ← (st ⊕ (r || 0 kg -k 0 ), c) 9: else 10: ω ← π1(h[m, r ]) 11: if c = Adv then 12:
st ← ⊥ 13: else 14:

(ω, st) ← ⊥ 15:

return (ω, st)

Pr[Game0 : win] ≤ Pr[Game2 : win] + (q H + qS + qF ) • qS + qF 2 k 0 + qG + q H + qS + qF 2 k h
queries are treated normally. Non-fresh queries made by the signing oracles are resampled as fresh if the previous query had been made by the faulty signature oracle. Non-fresh queries made by the faulty signature oracle are resampled, but not stored into the state. Game 1 is perfectly indistinguishable from Game 0, and Game 2 can be distinguished from Game 1 if either i. (lines 2, 5 and 6) the fresh r used in H -queries made by the signing oracles collides with a previously used r (with probability at most (q S +q F )•(q H +q S +q F )•2 -k0 ); ii. (lines 4, 7 and 8) or the fresh ω used in G-queries made by the signing oracles collides with a previously used ω (with probability at most (q H + q S + q F ) • (q G + q H + q S + q F ) • 2 -k h ). Note that the value stored in g[ω] at line 8 in H 2 is uniformly distributed since st is.

Game 3. Given that H now samples both bitstrings that compose the final padded message, we compute the entire signature in H when called by either one of the signing oracles. We transform the experiment to sample an integer x * and compute y * = x * e mod N to serve as one-way challenge. We embed it in the state when replying to H queries made by the adversary. Everything up to this point has been set up so that the signing oracles can simply use π 3 (h[m, r ]) as the padded message for m with salt r . Game 3 includes this simplification. We introduce additional notation for clarity in the rest of the proof. Consider the function:

f (e,
2: if (m, r) / ∈ dom(h) ∨ c = FSig ∨ (c = Sig ∧ π2(h[m, r ]) = FSig) then 3: σ ← pim (e,N ),y * ,c 0..2 k-1 4: y ← f (e,N ),y * ,c (σ) 5: b || ω || st ← i2osp(y) 6: if c = FSig ∨ (m, r ) / ∈ dom(h) then 7: h[m, r ] ← (ω, c, σ) 8: if c = FSig ∨ ω / ∈ dom(g) then 9: g[ω] ← (st ⊕ (r || 0 kg -k 0 ), c) 10: else 11: ω ← π1(h[m, r ]) 12:
if c = Adv then 13:

st ← ⊥ 14: else 15:

(ω, st) ← ⊥ 16:

return (ω, st)

1: oracle H4(c, m, r ) 2: if (m, r) / ∈ dom(h)∨c = FSig then 3: σ ← pim (e,N ),y * ,c 0..2 k-1 4: y ← f (e,N ),y * ,c (σ) 5: b || ω || st ← i2osp(y) 6: if c = FSig then 7: h[m, r ] ← (ω, c, σ) 8: g[ω] ← (st ⊕ (r || 0 kg -k 0 ), c) 9: else 10: ω ← π1(h[m, r ]) 11: if c = Adv then 12:
st ← ⊥ 13: else 14:

(ω, st) ← ⊥ 15:

return (ω, st)

Pr[Game2 : win] ≤ Pr[Game3 : win] + 2 -k 2 +2
Pr[Game3 : win] ≤ Pr[Game4 : win]

+ q H •q S 2 k 0 + q G •q F •3 2 k h
Game 3 is indistinguishable from Game 2 exactly when x * is invertible. Therefore, the probability that the adversary distinguishes the two games is exactly p+q-1 p•q . We have p + q -1 ≤ 2 k 2 +1 and 2 k-1 ≤ p • q and we can therefore bound the probability of this simulation failing by 2 -k 2 +2 . Since the invertibility of x * is important in some later steps, we in fact let H compute a response only when x * is invertible. In the inverter, since x * is not public, we instead check the invertibility of y * , which is equivalent. For simplicity, we omit discussions regarding this detail in the rest of this section. Game 4. In this game, we stop keeping track of the random oracle queries made by the faulty signature oracle. This is an important step towards being able to apply Lemma 2, which only discusses the statistical distance between two distributions on σ ′ , rather than (ω, σ ′ ). Note that, in Coron and Mandal's proof, Lemma 2 is applied before this transition, in a context in which its premises are not fulfilled. By removing data about random oracle queries, we introduce observable changes in the game's behaviour whenever the adversary queries H with an r that was used previously in a faulty signature query, or whenever the adversary queries G with an ω that was used previously in a faulty signature query. We bound the probability of the adversary guessing an ω value using Lemma 3. Since the view of the adversary does not depend on r values sampled by the faulty signature oracle (see Fig. 7), the probability of the adversary guessing an r value used in generating a faulty signature is easily bounded. Game 5. Our main goal at this stage is to show that faulty signatures are in fact indistinguishable from uniform randomness and can be simulated without using the random oracles. Once this is done, we will be able to resume the proof of security following more standard PSS proofs.

We now use Lemma 2 to completely simulate faulty signature oracle queries. We focus on the faulty signature oracle, inlining and simplifying H knowing that c = FSig. On the left, we display the simplified faulty signature oracle from Game 4 for reference. We make use of elementary properties of the statistical return i2osp(σ ′ )

1: oracle F5 (m, ǫ, a) 2: r ← {0, 1} k 0 3: σ ′ ← [0..N ) 4: return i2osp(σ ′ ) Pr[Game4 : win] ≤ Pr[Game5 : win] + qF • (4e 2 max + 1) • k 2 2 ρ-k/2
distance and Lemma 2 to bound the probability of distinguishing Games 5 and 6. Note that sampling σ in pim (e,N ),y * ,c 0..2 k-1 and applying the public RSA permutation to obtain y is perfectly equivalent to sampling y in 0..2 k-1 . Game 6. With the faulty signature oracle simplified away, we can now focus on simulating the signature oracle. From now on, the c argument to H can no longer be FSig. More generally, it is impossible for any entry in h or g to be tagged with FSig. The signature oracle we have defined at this point is not a valid simulator as it does not run in polynomial time. To ensure that it does, we replace the sampling operation at line 3 in Fig. 6 (right) with the loop displayed on the left of Fig. 8 to sample σ. The adversary can distinguish the two games whenever the loop finishes in a state where y does not start with a 0 bit. At each iteration

= x * ]+ 1 2 k h + q H 2 k 2 -1
of the loop, the σ sampled is invalid with probability at most 1 2 . The probability that all iterations produce an invalid σ is therefore bounded by 1 2 k 0 , since all samples are independent. H 7 may now be queried q H + q S times, allowing us to conclude.

Reduction All the oracles are simulated without using any secret data. We now focus on building an inverter. The adversary can win in two disjoint cases:

either the H -query made by the verification algorithm is fresh (this occurs with probability at most 2 -k h ), -or the H -query made by the verification algorithm was previously made by the adversary. If the query was made by the signature oracle, the forgery cannot be fresh and the adversary cannot win.

In the latter case, the one-way challenge can then be recovered by the inverter shown on the right of Fig. 8. The key observation is that, in case of a successful forgery, we have y = σ e mod N (line 4) and y = y * • u e mod N (by invariant on h). By definition of y * and the morphism and injectivity properties of RSA, we therefore have σ = x * • u. We need to also consider the case where a value u stored in the h map by the adversary is not invertible, which occurs with probability at most q H • 2 -k/2+1 . The final bound is obtained by transitively using the individual transition bounds.

Conclusion

In this paper we have proven the secrurity of an infective countermeasure against the null fault model used in [START_REF] Fouque | Attacking RSA-CRT signatures with faults on Montgomery multiplication[END_REF] and against more powerfull faults than random faults in the sense that we let the adversary chose the value of the result. It would be interesting in the future to take into account faults at each step of the protected algorithm instead of just the CRT-computation step. Moreover it would be a great addition to consider more fault models.

Figure 1

 1 Figure 1 Protected signing algorithm 1: function Sign(sk, pk, m)⊲ sk = (dp, dq , αp, αq , N ), pk = (e, N ) 2:r ← {0, 1} k 0 ⊲ Start of PSS padding 3: ω ← H (m, r) 4: st ← G(ω) ⊕ (r || 0 kg -k 0 ) 5: y ← os2ip(0 || ω || st) 6:σp ← y dp mod p ⊲ Signature computation 7:σq ← y dq mod q 8: σ ← (αp • σp + αq • σq) mod N ⊲ αp = q • (q -1 mod p) and similarly for αq 9:y ′ ← σ e mod N 10:r ′ ← {0, 1} ρ \{0} ⊲ Infective countermeasure 11: σ ′ ← σ + r ′ • (y -y ′ ) mod N 12:return i2osp(σ ′ )

Figure 4

 4 Figure 4 Initial transition: extending state

  N ),y * ,c : σ →    y * • σ e mod N if c = Adv σ e mod N otherwiseFor a set X ⊆ Z/N Z, we denote by pim (e,N ),y * ,c (X) the uniform distribution on the set S = σ ∈ Z/N Z | f (e,N ),y * ,c (σ) ∈ X .

Figure 6

 6 Figure 6 Games 3 and 4: Embedding one-way challenge and oracle queries in F 1: oracle H3(c, m, r )

Figure 7

 7 Figure 7 Game 5: sampling faulty signatures 1: oracle F4(m, ǫ, a) 2: r ← {0, 1} k 0 3: σ ← pim (e,N ),y * ,c 0..2 k-1 4: y ← σ e mod N 5: r ′ ← {0, 1} ρ \0 6: σ ′ ← y d * αp + (a + (ya e )) * αq 7: return i2osp(σ ′ )

Figure 8 1 1:

 81 Figure 8 Game 6 and inverter: sampling σ in polynomial time1: while (!0 ≤ y < 2 k-1 ) ∧ i < k0 do 2: σ ← [0..N ) 3:y ← f (e,N ),y * ,c (σ) 4:i ← i + 1

  Concretely, this result means that, for large enough N , it suffices to take ρ slightly larger than m to obtain a statistical distance of 2 -m .If we do not want to rely on the Riemann Hypothesis, we can obtain an unconditional bound by replacing the use of GRH in Lemma 1 by the Pólya-Vinogradov inequality (or the Burgess bound). However, statistical indistinguishability from uniform then requires somewhat larger values of ρ: at least k/4 + m + o(1) with Pólya-Vinogradov or k/8 + m + o(1) with the Burgess bound.

	P (s, t) -and hence the desired result, since p ≤ 1 N s,t	≤ √	p Y N and Y > X. + κ δ q δ 2N XY	⊓ ⊔
	Remark 2.

XY • p/2 using the coarse upper bound W s /Y ≤ 2/p. Summing further over s, we finally obtain:

https://www.easycrypt.info


Pierre-Alain Fouque

Jean-Christophe Zapalowicz
email: jean-christophe.zapalowicz@inria.fr

Statistical properties of short RSA distribution and their cryptographic applications

Keywords: Exponential Sums, Security Proof for Micali-Schnorr pseudo-random generator, semantic security of RSA padding scheme

In this paper, we study some computational security assumptions involve in two cryptographic applications related to the RSA cryptosystem. To this end, we use exponential sums to bound the statistical distances between these distributions and the uniform distribution. We are interesting studying the k least (or most) significant bits of x e mod N , where N is a RSA modulus when x is restricted to a small part of [0, N ). First of all, we provide the first rigorous evidence that the cryptographic pseudo-random generator proposed by Micali and Schnorr is based on firm foundations. This proof is missing in the original paper and do not cover the parameters chosen by the authors. Consequently, we extend the proof to get a new result closer to the parameters using a recent work of Wooley on exponential sums and we show some limitations of our technique. Finally, we look at the semantic security of the RSA padding scheme called PKCS#1 v1.5 which is still used a lot in practice. We show that parts of the ciphertexts are indistinguisable from uniform bitstrings.

Introduction

The RSA assumption states that given a random value y in Z N , where N is the product of two large primes, it is difficult to compute a e-th root of y, i.e. find x such that y = x e mod N . The RSA problem has been studied by mathematicians and no attack more efficient than factoring the RSA modulus has been found since its discovery. Usually, it is very difficult to prove a computational assumptions such as RSA and cryptographers try to prove that this assumption is at least as difficult than another one for instance factoring. However, some evidence for the non-equivalence of these two hard problems has been provided by Boneh and Venkatesan in [START_REF] Boneh | Breaking rsa may not be equivalent to factoring[END_REF] while the RSA assumption seems to hold.

RSA is a valid cryptographic assumption since on average its difficulty seems to be established thanks to its self-reducibility property. Indeed, it is well-known than if we are able to invert RSA on a non-negligible subset of Z N , then we can invert nearly all values in Z N with high probability. Based on this assumption, cryptographers have proposed and proved that RSA signature and encryption schemes using specific padding function [5,[START_REF] Bellare | Optimal asymmetric encryption[END_REF] are secure in the random oracle model [START_REF] Bellare | Random oracles are practical: A paradigm for designing efficient protocols[END_REF]. The security proof of RSA-OAEP for encryption has been showed to be flawed since, and many reparations have been proposed in [START_REF] Shoup | Oaep reconsidered[END_REF][START_REF] Fujisaki | Rsaoaep is secure under the rsa assumption[END_REF] and checked with computational proof assistant [START_REF] Barthe | Beyond provable security verifiable ind-cca security of oaep[END_REF].

Another direction to assess the security of a computational assumption consists in showing that the values we are looking for are computationally or statistically indistinguishable from the uniform distribution on bitstrings of the same size. Consequently, the best the adversary can do is to guess this value until he finds it. For RSA, it is easy to see that the value x is uniformly distributed if y is. In this paper, we will be interested by the short RSA problem: given y find x such that x e mod N given the promise that x < M N . Coppersmith results [START_REF] Coppersmith | Small solutions to polynomial equations, and low exponent rsa vulnerabilities[END_REF] show that if M = N 1/e , then it is possible in polynomial-time to recover all short values for x using lattice reduction technique. However, we can wonder what is the security of this new assumption when M N 1/e . It is trivial to see that if M = N 1 e + then, by guessing the high order bits of x, in time N times a polynomial in log N , we can invert x. However for larger values of M , the problem seems to be hard. This assumption is made in some standards, such as the standard PKCS#1 v1.5 that is used to protect RSA encryption and we will study it here in a special case. To assess the security of this short RSA assumption, the classical technique consists in studying the distribution of values x e mod N when x < M . This distribution cannot be uniform in Z N since the output is larger than M , but it can be computationally difficult to distinguish it from the uniform distribution in Z N . We will study the short RSA distribution when we consider only some part of the output bits. In this case, it is possible to prove some mathematical statement on the statistical distance between this distribution and the uniform distribution. We will also study the security of the Micali-Schnorr pseudorandom generator. At COCOON 2013, we show some attacks that explain the choice of the parameters proposed by Micali and Schnorr [11]. This generator assumes that the distribution of the least significant bits of x e mod N is indistinguishable from the uniform distribution in {0, 1} k if x < M with M = N 2/e . Our contributions. In the first part of this paper, we will prove the following informal theorem for different values of M . Theorem 1. Let N = pq the product of two large primes and M < N . Let the function f : Z M -→ Z N defined as f (x) = x e mod N . The k least significant bits of f (x) for k < log N are statistically indistinguishable from the uniform distribution on {0, 1} k .

For M √ N , we will show it using classical bounds based on Polya-Vinogradov bounds, and for N 1/e M √ N , we will use more recent results proved by Wooley [START_REF] Td Wooley | Vinogradov's mean value theorem via efficient congruencing[END_REF]. This last bound is very close to be optimal since for M ≤ N 1/e , it is possible in polynomial-time to recover x ≤ M given the k ≥ M least significant bits of f (x) as we explain in [START_REF] Fouque | Time/memory/data tradeoffs for variants of the rsa problem[END_REF]. Indeed, in this case the function f becomes non modular and the problem of retrieving x is quite easy by using Hensel's lifting.

In the second part of this paper, we will show two applications of this theorem. Micali and Schnorr original proof just refers to the first bound M √ N but the proof is missing and they do not give any hint to explain their more aggressive choice of parameters. Indeed, it would be possible to output less bits at each iteration of the generator, but the efficiency of this generator would be less efficient than Blum-Blum-Shub generator [START_REF] Blum | A simple unpredictable pseudorandom number generator[END_REF] for instance. Micali and Schnorr prefer to output more bit and avoid the previous attack when M = N 1/e . Last year, we develop some attacks to go beyond this bound using some time/memory tradeoff techniques which require exponential time complexity. Here, we show that these attacks are also near to be optimal since we can prove the indistinguishability of the random strings. We also explain that the parameters proposed by Micali and Schnorr are closed to be optimal in the special case of e = 3.

Finally, we propose to study the semantic security of the RSA padding called PKCS #1 v1.5 proposed by the RSA Labs. This padding is used in practice in many IETF standards and its security has been studied in [START_REF] Bauer | On the Broadcast and Validity-Checking Security of pkcs#1 v1[END_REF] under some security notions. Here, we study the semantic security, i.e. the most interesting security notion, to assess this assumption as much as we can using mathematical and rigorous statements. This notion means that no bit of the plaintext leaks when we see the ciphertext. In this paper, we will show that no bit of the plaintext leaks when we see some part of the bits of the ciphertext.

Some Mathematical Backgrounds

Statistical Distance. We first define as in [START_REF] Gennaro | An improved pseudo-random generator based on discrete log[END_REF] the statistical distance which allows to measure the distance between two probability distributions, and the notion of statistically indistinguishability. In a security point of view, if the statistical distance between two distributions is negligible, this means that even a powerful and unbounded adversary will not be able to distinguish them. We will denote by U k the uniform distribution on k-bit strings. Definition 1. Let X n and Y n be two arbitrary probability ensembles over a finite set X . We say that X n and Y n have statistical distance δ bounded by ∆(n) if the following holds:

δ = x∈X Prob Xn [x] -Prob Yn [x] ≤ ∆(n).
We say that X n and Y n are statistically indistinguishable if for every polynomial P (•) and for sufficiently large n, ∆(n) ≤ 1/P (n).

In order to bound our desired statistical distance, we will consider the notion of collision probability defined as follows: Definition 2. Let X and X be two independent and identically distributed random variables with values in a finite set X . The collision probability of X, denoted by Col(X) is the probability Pr

[X = X ] = x∈X Pr[X = x] 2 .
Finally, one needs a link between the statistical distance and the collision probability. That is the lemma presented in [START_REF] Shoup | A computational introduction to number theory and algebra[END_REF]: Lemma 1. Let X be a random variable with values in a set X of size |X | and SD(X, U X ) = δ the statistical distance between X and U X , the uniformly distributed variable over X . We have:

2δ ≤ |X | Col(X) -1.
Exponential Sums. Our proofs will bring into play a well-known tool in analytical number theory, that is exponentials sums. Thus it is convenient to use the notation for the following character of Z m :

∀x ∈ Z m , e m (x) = e 2iπx m ∈ C * .
and we recall a notable property about sums of characters:

Theorem 2. m-1 x=0 e m (ax) = 0, if a ≡ 0 mod m, m, if a ≡ 0 mod m.
Weil bound [START_REF] Lidl | Finite Fields[END_REF] allows to bound the exponential sums of the evaluations of a polynomial in term of the degree and the square root of the field: Lemma 2. For any prime p and any polynomial f (X) ∈ F p [X] of degree d ≥ 1 which is not identical to a constant modulo p, the following bound holds:

p x=1 e p (f (x)) < dp 1/2 .
The next lemma is useful to reduce exponentials sums modulo a composite integer N to exponentials sums modulo prime numbers p and q that are involved in the prime decomposition of N = pq: Lemma 3. Let N = pq a RSA modulus with p, q two large prime numbers and let u, v be such that uq = 1 mod p and vp = 1 mod q. Then, for any polynomial f ∈ Z[X] with integer coefficients:

N -1 j=0 e N (f (j)) = p-1 j1=0 e p (uf (j 1 )) q-1 j2=0 e q (vf (j 2 )).
Proof in appendix A.1. Finally let us denote the following exponential sum for any integer a such as gcd(a, N ) = 1 and M < N :

S(a, M ) = 0≤x<M e N (ax e ).
Bounding this sum for different values of M will be at the heart of our proof.

Main Results

In order to prove Theorem 1, we have to estimate the statistical distance between the function lsb k (x e mod N ) for x randomly chosen in Z M and the uniform distribution on {0, 1} k . Then, in function of the values of N, e, k and M , we will be able to show (or not) the statistically indistinguishability of these two probability ensembles. A preliminary and general lemma is considered: Lemma 4. Let N = pq the product of two large primes and M an integer less than N . Let B a bound on S(a, M ) for any integer a such as gcd(a, N ) = 1. The statistical distance between lsb k (x e mod N ) for x randomly chosen in Z M and U k is bounded by:

δ ≤ 2 k N + 2 k/2 B log 1/2 N M .
Proof. Let us denote by X M,e,N,k the random variable whose values are taken in [0, 2 k ) with the following distribution: x is chosen uniformly at random in Z M and we output f (x) = lsb k (x e mod N ). We are interested in bounding the collision probability of this random variable. To count the number of values x and y such that x e mod N and y e mod N share the same k least significant bits, we introduce the following characteristic function:

1(x, y, u) = 1/N × N -1 a=0 e N (a(x e -y e -2 k • u)),
where 1(x, y, u) is equal to 1 if x e -y e = 2 k u mod N and 0 otherwise. By denoting

K = N -1 2 k
, we can evaluate Col(X M,e,N,k ):

Col(X M,e,N,k ) = 1 M 2 × {(x, y) ∈ [0, M -1] 2 | ∃u ≤ K, x e -y e = 2 k • u mod N } , = 1 M 2 N M -1 x=0 M -1 y=0 K u=0 N -1 a=0 e N (a(x e -y e -2 k • u)).
We need to do some modifications to evaluate this collision probability. First note that

M -1 x=0 M -1 y=0 e N (ax e -ay e ) = S(a, M )S(a, M ) = |S(a, M )| 2 .
We thus obtain by considering the case a = 0 and a = 0:

Col(X M,e,N,k ) = K + 1 N + 1 M 2 N N -1 a=1 |S(a, M )| 2 K u=0 e N (-a2 k • u) .
We now focus on the term

N -1 a=1 ( K u=0 e N (-a2 k • u)). We first make a change of variables (a ∈ Z N \ {0} → 2 k a ∈ Z N \ {0}
being a bijection), then use the fact that the sum is a geometric sequence, and finally the inequality sin(y) ≥ 2y/π if 0 ≤ y ≤ π/2. In others words:

N -1 a=1 K u=0 e N (-a2 k • u) = N -1 a=1 K u=0 e N (-a • u) = N -1 a=1 1 -e N (-a(K + 1)) 1 -e N (-a) , = N -1 a=1 sin πa(K+1) N sin( πa N ) = 2 N -1 2 a=1 sin πa(K+1) N sin( πa N ) , ≤ 2
N -1 2 a=1 1 sin( πa N ) ≤ 2 N -1 2 a=1 N a ≤ N log N.
This is a well-known result first proved by Polya and Vinogradov. If we bound the last term uniformly in a S(a, M ) 2 by B 2 , we can finally bound Col(X M,e,N,k ) using the triangular inequality:

Col(X M,e,N,k ) ≤ K + 1 N + 1 M 2 N • N log N • B 2 , ≤ K + 1 N + B 2 log N M 2 .
We now use Lemma 1 to bound the statistical distance δ with the collision probability:

2δ ≤ 2 k (K + 1) N -1 + 2 k/2 B log 1/2 N M .
Note to conclude that K+1 N -1/2 k ≤ 1/N . Indeed:

- 1 N ≤ N -1 2 k • 1 N - 1 2 k ≤ 1+ N -1 2 k • 1 N - 1 2 k ≤ 1 N + N -1 2 k • 1 N - 1 2 k ≤ 1 N .
and consequently (with an omission of a factor 2 for sake of simplicity),

δ ≤ 2 k N + 2 k/2 B log 1/2 N M .
Now that we have this technical lemma, it remains to evaluate the bound B of S(a, M ). Depending on the value of M , this bound will be different. More precisely, we propose a first evaluation where the statistical distance is negligible when M is greater than √ N (see Theorem 3) and a second one with any requirement on M (see Theorem 4). However this second evaluation is clearly bad compared to the first one in the case where M is greater than √ N , and thus is interesting only if M is relatively small.

First Bound when M

√ N

The first method to evaluate B proposes to bound an incomplete exponential sum given the bound of the complete one using another result of Polya and Vinogradov. We obtain a bound on δ which will be small only if the parameter M is sufficiently larger than √ N :

Theorem 3. Let N = pq the product of two large primes and M an integer such as M √ N . The statistical distance between lsb k (x e mod N ) for x randomly chosen in Z M and U k is negligible:

δ ≤ 2 k N + 2 k/2 e 2 √ N log 3/2 N M .
Proof. In order to prove this theorem, we need the following lemma that we prove in Appendix A. Then we consider the Weil bound (see Lemma 2):

x∈Z N e N (ax e ) ≤ ep 1/2 × eq 1/2 ≤ e 2 N 1/2 ,
and finally Lemma 5 gives us the bound on |S(a, M )|, i.e:

|S(a, M )| ≤ e 2 N 1/2 log N.
The replacement of B in Lemma 4 with this evaluation concludes the proof.

Second Bound when M √ N

It remains to treat the case where M is smaller than √ N , specially if one wants to approach the optimal bound, i.e. N 1/e . Even if the following lemma and corollaries do not require anything on the size of M (except that it is less than N obviously), the bounds we find for δ are only interesting for small values of M , meaning M √ N .

Theorem 4. Let N = pq the product of two large primes and M an integer. The statistical distance between lsb k (x e mod N ) for x randomly chosen in Z M and U k is:

δ ≤ 2 k N + 2 k/2 log 3/2 N 1 M + N M e 1 2e(e-1)+1 .
Proof. This result is based on a theorem proved in [START_REF] Td Wooley | Vinogradov's mean value theorem via efficient congruencing[END_REF] which we apply to evaluate S(a, M ). We give here a specific version adapted to our case:

M 1+ (N -1 + M -1 + N • M -e ) σ(e) ,
where σ(e) -1 = 2e(e -1).

According to [START_REF] Td Wooley | Vinogradov's mean value theorem via efficient congruencing[END_REF], the factor M may be replaced by log(2M ), if one increases σ(e) -1 from 2e(e-1) to 2e 2 -2e+1. For the sake of simplicity, we bound log(2M ) by log N (with the weak assumption that M ≤ N/2) and we neglect the term N -1 since it is negligible compared to min(M -1 , N • M -e ). Thus we obtain:

|S(a, M )| M log N (M -1 + N • M -e ) 1
2e(e-1)+1 , and the replacement of B in Lemma 4 with this evaluation concludes the proof.

Since Theorem 4 does not require any assumption of size on M , we want to define this parameter using the optimal bound N 1/e . In other words, we write M as M = N 1/e log c N with c > 0. We propose in this case two corollaries depending on the value of c proved in appendices A.

δ ≤ 2 k N + 2 k/2 (log N ) ceσ(e)-3/2 , with σ -1 (e) = 2e(e -1) + 1.
Note that the statistical distance will be negligible if ceσ(e) -3/2 0, meaning if c

3(e -1) + 3/2e.

δ ≤ 2 k N + 2 k/2 N σ(e)
e (log N ) cσ(e)-3/2

, with σ -1 (e) = 2e(e -1) + 1.

An interesting value of c is c = ( 1 2 -1 e ) log N log log N which represents the case M = √ N . For e = 3, this is the lower bound of c in Corollary 2 and for e > 3 it is included in the defined interval.

Let us give a numerical example for Corollary 1, the most interesting corollary since it treats values of M as close as possible to the optimal bound N 1/e . We consider classical cryptographic parameters for the upper bound of δ, i.e. 2 -80 , and we put e = 3. Suppose that we want to have a negligible statistical distance for k = 160, then a modulus of 4096 bits leads to an impossibility. Indeed, Corollary 1 requires that 7 c < 56 and the result on δ is true for c ≥ 65. However, with a modulus of 8192 bits one obtains the condition 60 ≤ c < 105. In other words, with an input of at least 3511 bits for the function f , the 160 least significant bits of f (x) are statistically indistinguishable from the uniform distribution on {0, 1} 160 .

To conclude, we extend ours theorems and corollaries to another but similar case proved in appendix A.5.

Corollary 3. Let N = pq the product of two large prime integers and M an integer less than N . The results from Theorem 3 and Theorem 4 on the statistical distance between lsb k (x e mod N ) for x randomly chosen in Z M and U k are still valid for msb k (x e mod N ).

4 Applications of these bounds to cryptographic cases

Security of Micali-Schnorr pseudo-random number generator

Micali-Schnorr PRNG. A pseudorandom generator is a deterministic polynomial time algorithm that expands short seeds (made of truly random bits) into longer bit sequences, whose distribution cannot be distinguished from uniformly random bits by a computationally bounded algorithm.

Let (e, N ) a RSA public key with e small compared to log N and x 0 ∈ [0, 2 r ) with 2 r N a secret seed of size r. The Micali-Schnorr pseudorandom generator proposed in [START_REF] Micali | Efficient, perfect polynomial random number generators[END_REF] is defined as follows:

v i = x e i-1 mod N, v i = 2 k x i + w i for i ≥ 1.
At each iteration, this generator outputs the k least significant bits of v i , denoted by w i . In addition, denoting n the size of the modulus N , only x i of size r = n-k, unknown, is reused for the next iteration. Since the generator outputs O(k/ log e) bits per multiplication, one wants k to be as large as possible and e to be as small as possible. This pseudorandom generator is proven secure under the following strong assumption:

Assumption 1 The distribution of x e mod N for random r-bit integers x is indistinguishable by all polynomial-time statistical tests from the uniform distribution of elements of Z * N .

Clearly this assumption cannot be true if one does not restrain the tests to polynomial-time ones only because of the lack of entropy in input. Micali and Schnorr have proposed to use the parameters r = 2n/e and thus k = n(1 -2/e) which are very aggressive parameters in order to raise the efficiency of the generator. However, they just assumed that using these parameters, it may be sufficient for the indistinguishability between the two sets we are focusing on.

Our result. We do not contradict this assumption since our theorems give upper bounds on δ but they can be used to define the sizes of parameters k and r such as the the statistical distance is bounded as desired. Note that we study a single iteration of the generator as in [START_REF] Friedlander | On the distribution of the power generator[END_REF] for example, the consideration of two or more consecutive outputs being a difficult task. The proof of the following corollary is in appendix A.6 Corollary 4. Let (e, N ) a RSA public key with e small compared to log N and d a security parameter such that δ < 2 -d . Let α ∈ (0, 1) such that Micali-Schnorr pseudo-random number generator outputs the (1 -α) log N least significant bits at one iteration. This output is indistinguishable from the uniform distribution on {0,

1} (1-α) log N if α > 2/3 + 2d + 4 log e 3 log N + log log N log N .
Note that Theorem 4 which treats in a relevant way the case α < 1/2, is useless for this application because of the necessarily link between k and M : if M = N α then 2 k N 1-α . Indeed, we start from the following general bound:

δ ≤ 2 k N + 2 k/2 log 3/2 N 1 M + N M e 1 2e(e-1)+1
. By using the same notations for M and 2 k and bounding the right term by 2 -d , we first consider the case N -α < N 1-αe (i.e. 1/M < N/M e ) and neglect the factor 2 (as in the proofs of the corollaries) and the term 2 k N . Thus we obtain α > A(N, e)/B(e) with:

A(N, e) = 3/2 log log N log N + 1 2 + 1 2e(e -1) + 1 + d log N , B(e) = 1 2 + e 2e(e -1) + 1 .
For a fixed e, the function A(N, e)/B(e) is decreasing in N and tends to:

2e(e -1) + 3 2e 2 + 1 , which is larger than 2/3 whatever is the value of the public RSA exponent e ≥ 3.

The same result can be achieved by considering the case N -α > N 1-αe . It is interesting to note that when N tends to infinity, this bound tends to 2/3. In other words we cannot expect to have a positive result of indistinguishability according to our results if one outputs more than (log N )/3 of the least significant bits asymptotically. As concrete example, for N = 2 1024 , e = 3 and d = 80, that gives an input greater than 747 bits (and thus an output lesser than 277 bits).

Semantic Security of PKCS #1 v1.5 encryption

RSA is a well-known asymmetric cryptosystem, first publicized in 1977. Even nowadays it is frequently used in applications where security of digital data is a concern. However the basic RSA encryption process, meaning without any padding of the plaintext, is vulnerable to quite simple or clever attacks (see for example [START_REF] Coppersmith | Low-exponent rsa with related messages[END_REF][START_REF] Håstad | Solving simultaneous modular equations of low degree[END_REF]). The standard PKCS #1 v1.5 proposes a padding which parries a part of these attacks, nevertheless it has been defeated by Bleichenbacher in [START_REF] Bleichenbacher | Chosen ciphertext attacks against protocols based on the rsa encryption standard pkcs #1[END_REF].

PKCS #1 v1.5 encryption. We recall the encryption scheme proposed in the standard PKCS #1 v1.5. By denoting (e, N ) the RSA public key with n the size of the modulus N , a message m of size at most = n -88 is padded as follows:

m padded = 00||02||P S||00||m
with P S the padding string of size r = n --24. Then, m padded is encrypted using the RSA encryption process.

Semantic Security. The semantic security requires that the adversary should not gain any advantage or information from having seen the cipher text resulting from an encryption algorithm. This can be formalized by this concrete definition: Definition 3. An encryption scheme (Enc, Dec) is (t, o, ) semantically secure if for every distribution X over messages, every functions I : {0, 1} m → {0, 1} * and f : {0, 1} m → {0, 1} * (of arbitrary complexity) and every function A of complexity t A ≤ t, there is a function A of complexity ≤ t a + o such that

Pr[A(Enc(K, M ), I(m)) = f (M )] -Pr[A (I(m)) = f (M )] ≤ .
I(m) can be seen as the knowledge of the adversary on the message M , whereas f (M ) represents the knowledge the adversary would learn.

Our result. We are interested by bounding the statistical distance between the function lsb k (P ad(x) e mod N ) for x randomly chosen in Z 2 r and the uniform distribution on {0, 1} k , x being an integer whose binary representation is P S. More precisely we define P ad(x) as P ad(x) = 2 n-16 b + 2 l+8 x + m with b of size 8 and m of size two integer fixed. This application can be viewed as a partial study of the semantic security of PKCS #1 v1.5 encryption because we only give access to the k least significant bits of the ciphertext.

Corollary 5. Let N = pq the product of two large prime integers and M an integer less than N . Let P ad(x) a function defined same as above. The results from Theorem 3 and Theorem 4 on the statistical distance between lsb k (x e mod N ) for x randomly chosen in Z M and the uniform distribution on {0, 1} k are still valid for lsb k (P ad(x) e mod N ).

With a security parameter d = 80, log N = 1024, e = 3 and log M = 872 (we consider the encryption of a symmetric cryptosystem key of size 128), we obtain the condition k < 524.

A Proofs omitted

A.1 Proof of Lemma 3 Lemma 3. Let N = pq a RSA modulus with p, q two large prime numbers and let u, v be such that uq = 1 mod p and vp = 1 mod q. Then, for any polynomial f ∈ Z[X] with integer coefficients:

N -1 j=0 e N (f (j)) = p-1 j1=0
e p (uf (j 1 )) q-1 j2=0 e q (vf (j 2 )).

Proof. Starting from the modular equality uq + vp = 1, one has j = juq + jvp mod N with 0 ≤ j ≤ N -1 and more precisely: j = j 1 uq + j 2 vp mod N, with 0 ≤ j 1 ≤ p -1 and 0 ≤ j 2 ≤ q -1. The binomial theorem implies:

j k = k i=0 k i (j 1 uq) k-i (j 2 vp) i mod N, = (j 1 uq) k + (j 2 vp) k mod N, = uqj k 1 + vpj k 2 mod N,
using the fact that all the monomials contain a factor pq except for the first and the last one in the first equality. Moreover, for k ≥ 1, (uq) k = uq mod N in the second equality since (uq) 2 = uq(1 -vp) = uq mod N and by induction on k. Then, by denoting f (j) = d k=0 a k j k with a k ∈ Z we obtain f (j) = uqf (j 1 ) + vpf (j 2 ) with 0 ≤ j ≤ N -1, 0 ≤ j 1 ≤ p -1, 0 ≤ j 2 ≤ q -1 and thus: Proof. In order to simplify the formula, we consider here that max(1/M, N/M e ) = N/M e and we write (1/M + N/M e ) as N/M e (we will consider that the factor 2 is included in the majoration of log 2M ). Thus we obtain the following bound on δ: Proof. Contrary to the first corollary, we consider here that N/M e ≤ 1/M and we apply the same simplification. We thus obtain a lower bound on c: with u, v ∈ Z such as up + vq = 1 and the Weil bound gives the same result thanks to the degree of the polynomial P ad(x) e equal to e:

x∈Z N e N (aP ad(x) e ) ≤ ep 1/2 × eq 1/2 ≤ e 2 N 1/2 . Thus Theorem 3 is still valid for this application. Finally Theorem 4 is correct with the polynomial P ad(x) e too (see its general form in [START_REF] Td Wooley | Vinogradov's mean value theorem via efficient congruencing[END_REF]).

2 : 5 .

 25 Lemma If for all a ∈ Z * , b ∈ Z and for any polynomialP ∈ Z[X], x∈Z N e N (aP (x))e N (bx) ≤ C, then, for 0 ≤ M ≤ N , 1≤x≤M e N (aP (x)) ≤ C log N.From the notations of Lemma 5, we put P (x) = x e and b = 0 and we evaluate x∈Z N e N (ax e ) using Lemma 3 by denoting u, v ∈ Z such as up + vq = 1: x∈Z N e N (ax e ) = x∈Fp e p (v × ax e ) x∈Fq e q (u × ax e ) .

Theorem 5 .

 5 Let e be an integer with e ≥ 2, and let a/N ∈ R. Suppose that, for some c ∈ Z and N ∈ N with gcd(c, N ) = 1, one has |a/N -c/N | ≤ N -2 and N ≤ M e . Then one has 1≤x≤M e(ax e /N )

3 and A. 4 . 1 .

 41 Corollary Let N = pq the product of two large primes and M an integer such as M = N 1/e log c N and c ≤ 1 e(e-1) log N log log N . The statistical distance between lsb k (x e mod N ) for x randomly chosen in Z M and U k is:

Corollary 2 .

 2 Let N = pq the product of two large primes and M an integer such as M = N 1/e log c N and 1 e(e-1) log N log log N ≤ c < e-1 e log N log log N . The statistical distance between lsb k (x e mod N ) for x randomly chosen in Z M and U k is:

5 Lemma 5 .eCorollary 1 .

 551 (j 2 )/N ). A.2 Proof of Lemma If for all a, b ∈ Z 2 and for any polynomial P ∈ Z[X] with integer coefficients, x∈Z N e N (aP (x))e N (bx) ≤ C then, for 0 ≤ M ≤ N , 1≤x≤M e N (aP (x)) ≤ C log N. Proof. Indeed, we have the following equality: 1≤x≤M e N (aP (x)) = x∈Z N 1 [1,M ] e N (aP (x)) with 1 [1,M ] = 1/N N b=1 M m=1 e N (b(x -m)). Thus, we obtain: 1≤x≤M e N (aP (x)) = 1/N N b=1 x∈Z N e N (aP (x))e N (bx) N (-bm) ≤ C/N × N log N ≤ C log N. A.3 Proof of Corollary 1 Let N = pq the product of two large primes and M an integer such as M = N 1/e log c N and c ≤ 1 e(e-1) log N log log N . The statistical distance between lsb k (x e mod N ) for x randomly chosen in Z M and the uniform distribution on {0, 1} k is: N ) ceσ(e)-3/2 , with σ -1 (e) = 2e(e -1) + 1.

2 Corollary 2 . 2 ,

 222 and one replaces M by M = N 1/e log c N to get the result. Finally, because 1/M ≤ N/M e then we obtain a condition on c: N Let N = pq the product of two large primes and M an integer such as M = N 1/e log c N and 1 e(e-1) log N log log N ≤ c < e-1 e log N log log N . The statistical distance between lsb k (x e mod N ) for x randomly chosen in Z M and the uniform distribution on {0, 1} k is: N ) cσ(e)-3/with σ -1 (e) = 2e(e -1) + 1.

Finally 3 Corollary 3 .ee

 33 c ≥ 1 e(e -1) log N log log N , and the condition M < N implies an upper bound: , one replaces M by M = N 1/e log c N and gets the result. A.5 Proof of Corollary Let N = pq the product of two large prime integers and M an integer less than N . The results from Theorem 3 and Theorem 4 on the statistical distance between lsb k (x e mod N ) for x randomly chosen in Z M and the uniform distribution on {0, 1} k are still valid for msb k (x e mod N ).Proof. Indeed, the single difference appears in the evaluation of Col(X M,e,N,k ):Col(X M,e,N,k ) = 1 M 2 × {(x, y) ∈ [0, M -1] 2 | ∃u ≤ K, x e -y e = u mod N } , N (a(x e -y e -u)), with K still equal to N -1 N (-a • u) ,the rest of the proof remains the same.The analyze of B is quite simple since Lemma 3 implies: x∈Z N e N (aP ad(x) e ) = x∈Fp e p (v × aP ad(x) e ) x∈Fq e q (u × aP ad(x) e ) .

Pierre-Alain Fouque and Jean-Christophe Zapalowicz

A.6 Proof of Corollary 4 Corollary 4. Let (e, N ) a RSA public key with e small compared to log N and d a security parameter such that δ < 2 -d . Let α ∈ (0, 1) such that Micali-Schnorr pseudo-random number generator outputs the (1 -α) log N least significant bits at one iteration. This output is indistinguishable from the uniform distribution on {0,

Since -α/2 < 1 -3 2 α is equivalent to α < 1 and e 2 √ N log 3/2 N is quite large for cryptographic parameters, we will neglect the first term. We bound the statistical distance by 2 -d with d a security parameter and obtain the following condition on α: Proof. The result of Lemma 4 remains valid for this application. Indeed, the characteristic function becomes:

and by denoting M = 2 r , S(a, M ) is now defined as:

e N (aP ad(x) e ).

We still denote by B the bound on S(a, M ) for any integer a and get: