A Generalized Wiener Attack on RSA

A Generalized Wiener Attack on RSA Johannes Blo¨mer, Alexander May Faculty of Computer Science, Electrical Engineering and Mathematics University of Paderborn 33102 Paderborn, Germany {bloemer,alexx}@uni-paderborn.de Abstract. We present an extension of Wiener’s attack on small RSA secret decryption exponents [10]. Wiener showed that every RSA public key tuple (N, e) with e ∈ Z∗φ(N) that satisfies ed − 1 = 0 mod φ(N) for some d < 1 3 N 1 4 yields the factorization of N = pq. Our new method finds p and q in polynomial time for every (N, e) satisfying ex + y = 0 mod φ(N) with x < 1 3 N 1 4 and |y| = O(N− 3 4 ex). In other words, the generalization works for all secret keys d = −xy−1, where x, y are suitably small. We show that the number of these weak keys is at least N 3 4 −ǫ and that the number increases with decreasing prime difference p − q. As an application of our new attack, we present the cryptanalysis of an RSA-type scheme presented by Yen, Kim, Lim and Moon [11, 12]. Our results point out again the warning for crypto- designers to be careful when using the RSA key generation process with special parameters. Keywords: RSA, weak keys, Wiener attack, continued fractions 1 Introduction Let N = pq be an RSA-modulus, where p and q are primes of equal bit-size (wlog p > q). Let e be the public exponent and d be the secret exponent satisfying ed = 1 mod φ(N), where φ(N) is the Euler totient function. We denote by Z∗φ(N) the multiplicative group of invertible integers modulo φ(N). An RSA public key is a tuple (N, e) ∈ Z× Z∗ φ(N). In order to study the security of RSA, many people focus on the difficulty to factor the modulus N without taking into account additional information that may be encoded in the public exponent e. Hence, it is tempting for crypto- designers to construct RSA-type schemes with special public exponents that yield a good performance in encryption/decryption. For example, one might be tempted to use small decryption exponents d in order to speed up the decryp- tion process. Another fast RSA-variant that makes use of special RSA-keys was proposed by Yen, Kim, Lim and Moon [11, 12] in 2001. This YKLM-scheme is designed to counteract the fault-based attack on CRT-RSA of Boneh, DeMillo and Lipton [2]. In 1990, Wiener [10] observed that information encoded in the public ex- ponent e might help to factor N . More precisely, he showed that every public exponent e ∈ Z∗ φ(N) that corresponds to a secret exponent d with d ≤ 13N 1 4 yields the factorization of the modulus in time polynomial in log(N). In 1999, Boneh and Durfee [3] used Coppersmith’s method for finding small roots of modular polynomial equations [4] to improve the bound to d ≤ N0.292. Although the YKLM-scheme uses a special key generation algorithm in order to provide good performance, the secret keys d are not chosen to be small. Therefore, the Wiener attack as well as the Boneh-Durfee attack cannot directly be applied to this RSA-variant. However, in this work we present an extension of Wiener’s approach that leeds to a much larger class of secret keys d which are insecure. Furthermore, we show that the keys which are generated in the YKLM- scheme belong to this larger class, for all reasonable parameter choices of the scheme. As a result, we obtain that the public keys (N, e) in the YKLM-scheme yield the factorization of N in polynomial time. Let us put the cryptanalytic approaches above into a more general framework by defining the notion of weak keys : The results so far show that there are classes of public keys (N, e) where every element in the class yields the factorization of N . One may view the auxiliary input e as a hint how to factor N : Without having e we assume that factoring N is hard, but with the help of e it becomes feasible. In the case of the Wiener attack the class consists of all public key tuples (N, e) where ed− 1 = 0 mod φ(N) with d < 13N 1 4 . We call such a class weak and the elements (N, e) of the weak class are called weak keys. To be more precisely: We define the size of a class of public key tuples by the number of elements (N, e) in the class for every fixed N . Let C be a class of public key tuples (N, e), then sizeC(N) = |{e ∈ Z∗φ(N) | (N, e) ∈ C}|. C is called weak if 1. The size of C is polynomial in N , i.e. sizeC(N) = Ω(N γ) for some γ > 0. 2. There exists a probabilistic algorithm A that on every input (N, e) ∈ C outputs the factorization of N in time polynomial in log(N). Note that the size of a weak class is a function in N which denotes the number of elements that can be factored by the corresponding algorithm A. For example, the size of the class in the Wiener attack is at least N 1 4 −ǫ. Here the ǫ-term comes from the fact that only those d with gcd(d, φ(N)) = 1 define legitimate RSA-keys. Let us give another (trivial) example of a weak class of public keys. Every tuple (N, e) with e = kq, 1 < k < p is a weak key, since the computation gcd(N, e) = q yields the factorization. These are p > N 1 2 many weak keys. Howgrave-Graham [6] observed that even the knowledge of e = kq + r for some 2 unknown r ≤ N 14 suffices to find the factorization of N . This implies the exis- tence of a weak class with size N 3 4 . We think that it is a very natural question to study how many of the possible choices of the public keys are indeed weak keys that should not be used in the design of crypto-systems. For the Wiener attack and the Boneh-Durfee attack it is easy for a crypto-designer to see that a key is weak by inspecting the most significant bits of d. For the extension of Wiener’s attack that we describe in this paper the weakness of the keys is not obvious. One can understand our new result as a warning for crypto-designers to be careful when using keys with a special structure. There is also an imminent danger from weak keys in the case of untrusted servers that create public/secret key pairs: Cre´peau and Slakmon [5] showed how to use weak keys in order to construct malicious RSA systems by encoding information into the public exponent e. Our new class of weak keys is well-suited for the use in such systems and leads to a large variety of new malicious keys. In order to describe our new attack, let us first consider the normal RSA- case, where p− q = Ω(√N). Note that for randomly chosen primes of the same bitsize, the probability that p, q agree in the c most significant bits is roughly 2−(c−1). Hence, we have p− q = Ω(√N) with overwhelming probability. For the case p− q = Ω(√N), we introduce a variant of Wiener’s attack that works for all public keys (N, e) where ex+ y = kφ(N), k ∈ N with 0 < x ≤ 1 3 N 1 4 and |y| = O(N− 34 ex). Notice that our bounds exclude trivial solutions where ex+y = 0, since |y| < ex. The new method works as follows: As in Wiener’s approach, we use the continued fraction algorithm to recover the unknown values x and k. Afterwards, we show that a factorization method due to Coppersmith [4] can be applied: Given half of the most significant bits of p, one can find the factorization of N . Let us compare the new result to Wiener’s attack. Our weak keys have the structure that e−1 = d = −x y mod φ(N), i.e. Wiener’s algorithm is the special case where x = d and y = −1. One should observe that for x of size roughly N 14 as in Wiener’s attack, the parameter e must be of size at least N 3 4 in order to satisfy a relation of the form ex + y = 0 mod φ(N). Thus, |y| can be chosen of size at least x. If e is roughly N , which is normally the case for small d, |y| can even be chosen of size N 1 4 x in the attack. One should expect that for fixed N the number of public keys (N, e) for which our approach applies is roughly the number of tuples (x, y) within the given bounds. This number can be upper bounded by x ·N 14 x ≤ N 34 . In fact, we are able to show that the number of weak keys (N, e) for which our algorithm works is also lower bounded by Ω(N 3 4 −ǫ). It is important to notice that in contrast to the approaches of Wiener and Boneh-Durfee, the secret keys in our attack are not small itself but have a “small decomposition” in x and y. So they might look innocuous to crypto-designers 3 and may be tempting to use in the design of cryto-systems with good encryp- tion/decryption performance. As an example, we show that the public keys (N, e) constructed in the YKLM-scheme can be attacked by our generalization of Wiener’s method. Namely, we can express the secret exponent d in terms of small x and y, which breaks the crypto-system for all reasonable parameter choices. In 2002, de Weger [9] observed that Wiener’s attack can be improved when the prime difference p− q is significantly less than √N . de Weger’s method also applies to our extension of Wiener’s attack. Interestingly, we are able to show that for prime difference p − q = N 14+γ , 0 < γ ≤ 14 there are at least N1−γ−ǫ weak RSA-keys (N, e). It is important to notice that for prime difference p−q = O(N 14 ) an algorithm of Fermat finds the factorization in polynomial time. Thus, our attack has a nice interpolation property towards Fermat’s algorithm: As p− q decreases, the number of weak public keys increases. For γ approaching zero almost all keys are weak, corresponding to the fact that N can be easily factored without any hint that is encoded in e. As a by-product, we get a simple probabilistic factorization algorithm with expected running time O(Nγ+ǫ) comparable to Fermat-Factorization: For a fixed N , choose random e < N and apply our algorithm to each choice (N, e) until (N, e) is a weak key that yields the factorization. Notice that the interpolation property above seems to imply that one cannot improve our approach significantly. On the other hand, there might be different techniques – for example lattice reduction techniques for higher dimensional lattices – that lead to larger classes of weak keys for the prime difference p− q = Ω( √ N). But at the moment this is an open question. The paper is organized as follows: In Section 2, we present our extension of Wiener’s attack. As an application of this method, we present the crytanalysis of the YKLM-scheme in Section 3. In Section 4, we apply the methods of de Weger to our generalized Wiener attack. We conclude the paper by showing in Section 5 that the number of weak RSA-keys (N, e) in our approach is Ω(N 3 4 −ǫ). 2 The generalized Wiener attack Throughout this work we consider RSA-moduli N = pq, where p and q are of the same bit-size (wlog p > q). This implies the inequalities p− q ≤ N 12 and 2N 12 ≤ p+ q ≤ 3N 12 . Furthermore, we have φ(N) = N + 1− (p+ q) > N2 . Our attack makes use of a well-known result due to Coppersmith [4]: Theorem 1 (Coppersmith) Let N = pq be an RSA-modulus, where p and q are of the same bit-size. Suppose we are given an approximation of p with additive error at most N 1 4 . Then N can be factored in time polynomial in logN . 4 We are now able to state our main theorem. Here we consider the normal RSA- case where p− q = Ω(√N). Theorem 2 Let c ≤ 1 and let (N, e) be an RSA public key tuple with N = pq and p− q ≥ cN 12 . Suppose that e ∈ Z∗ φ(N) satisfies an equation ex+ y = kφ(N) with 0 < x ≤ 1 3 N 1 4 and |y| ≤ cN− 34 ex. Then N can be factored in polynomial time. One should notice that the conditions of Theorem 2 imply that ex + y 6= 0, thereby excluding trivial congruences: Since c ≤ 1, we see that |y| < ex. This in turn implies k > 0. Roadmap for the Proof of Theorem 2 – We show that the unknown parameters x, k can be found among the con- vergents of the continued fraction expansion of e N . – From x and k, we compute an approximation of p+ q. – From an approximation of p+ q, we compute an approximation of p− q. – Combining both approximations gives us an approximation of p, which leads to the factorization of N by using Coppersmith’s Theorem. We want to argue that in the following proof we can assume wlog that N ≥ (8 c )4. This condition is equivalent to c ≥ 8N− 14 . If this inequality does not hold then p − q = O(N 14 ) and Fermat’s factorization algorithm yields the factorization of N in polynomial time. Proof: Let us start with the RSA key equation ex+ y = k(N − p− q + 1). (1) Dividing by Nx gives us e N − k x = −k(p+ q − 1) + y Nx . We want to argue that we can assume wlog that gcd(k, x) = 1. Notice that every integer that divides both k and xmust also divide y by equation (1). Thus, we can divide equation (1) by gcd(k, x) which gives us an equation ex′+y′ = 0 mod φ(N) with even smaller parameters x′ and y′. Hence we can assume that k x is a fraction in its lowest terms. By a well-known theorem (see e.g. Theorem 184 in [7]), the fraction k x appears among the convergents of e N if the condition | e N − k x | < 12x2 is satisfied. Thus it remains to show that |k(p + q − 1) + y| < N2x . Let us first find a bound for the parameter k. We know that k = ex+y φ(N) and |y| ≤ cN− 3 4 ex. Since our precondition N ≥ (8 c )4 implies N ≥ 212, we conclude that |y| ≤ 14ex. Therefore, we obtain 3 4 ex φ(N) ≤ k ≤ 5 4 ex φ(N) . (2) 5 Now we are able to estimate k(p+ q − 1) + y ≤ 15 4 ex φ(N) ·N 12 + cN− 34 ex ≤ 15 4 xN 1 2 + xN 1 4 ≤ 4xN 12 , where the last inequality holds for N ≥ 212. Therefore, we have to satisfy the condition 4xN 1 2 < N2x which is equivalent to x < 1√ 8 N 1 4 . This condition holds by our upper bound x ≤ 13N 1 4 . Hence, the fraction k x must be among the convergents of the continued frac- tion expansion of e N . Since there are only O(logN) many convergents, we can apply the following process to each candidate for k and x until our algorithm succeeds. We have to show that the correct k and x yield the factorization of N . Let us write equation (1) as N + 1− ex k = p+ q + y k . Since every parameter on the left hand side is now known to us, we can compute an approximation of p+q up to some unknown error term y k , that can be bounded by |y k | ≤ 43cN 1 4 using inequality (2). Our goal is to find an approximation of p up to some error of size N 1 4 in order to apply Coppersmith’s theorem. Therefore, we transform our approximation of p+ q into an approximation of p− q using the relation p− q = √ (p− q)2 = √ (p+ q)2 − 4N. Let s be our approximation of p+ q with additive error at most 43cN 1 4 . We will show that t = √ s2 − 4N is an approximation of p−q with an additive error that can be bounded by 9N 1 4 . Thus, the term 12 (s+ t) is an approximation of p with error at most ∣∣∣∣12(s+ t)− p ∣∣∣∣ = 12 |s− p− q + t− p+ q| ≤ 1 2 |s− (p+ q)|+ 1 2 |t− (p− q)| ≤ 2 3 cN 1 4 + 9 2 N 1 4 ≤ 6N 14 Define p˜ = 12 (s + t). Then one out of the six values p˜ + (2k + 1)N 1 4 , k = −3,−2,−1, 0, 1, 2 is an approximation of p up to an error of at most N 14 in absolute value. We can apply Coppersmith’s algorithm to all these values. The correct term will then lead to the factorization of N in polynomial time. It remains to show that t = √ s2 − 4N is indeed an approximation of p − q up to some error term that can be bounded by 9N 1 4 . Let us first show that t is well-defined, i.e. s2 − 4N ≥ 0. Observe that s = p+ q + y k satisfies s2 − 4N = (p− q)2 + 2y k (p+ q) + (y k )2 . 6 Therefore, it suffices to show that |2 y k (p + q)| ≤ (p − q)2. Using |y k | ≤ 43cN 1 4 , we obtain |2 y k (p + q)| ≤ 8cN 34 . From our precondition N ≥ (8 c )4, we see that 8 ≤ cN 14 . This immediately implies 8cN 34 ≤ c2N ≤ (p− q)2 as desired. Since N ≥ 212, we know that the error term y k for p + q can be bounded in absolute value by 43cN 1 4 ≤ 12N 1 2 ≤ 14 (p+ q). This implies the inequality s ≤ 5 4 (p+ q). (3) We observe that t− (p− q) = √ s2 − 4N − (p− q) = (s− (p+ q))(s+ (p+ q))√ s2 − 4N + (p− q) . Using the inequalities (3), s− (p+ q) ≤ 43cN 1 4 and p− q ≥ cN 12 finally leads us to the desired bound t− (p− q) ≤ 4 3cN 1 4 · 274 N 1 2 (p− q) ≤ 9N 1 4 . Let us briefly summarize the whole factorization algorithm.' & $ % Algorithm Generalized Wiener Attack INPUT: (N, e), where N = pq and ex+ y = 0 mod φ(N) for some unknown 0 < x ≤ 13N 1 4 and |y| ≤ cN− 34 ex. 1. Compute the continued fraction expansion of e N . 2. For every convergent k x of the expansion: (a) Compute s = N + 1− ex k , t = √ s2 − 4N and p˜ = 12 (s+ t). (b) Apply Coppersmith’s algorithm to the candidates p˜ + (2k + 1)N 1 4 for k = −3,−2, . . . , 2: If Coppersmith’s algorithm outputs the fac- torization of N , then stop. OUTPUT: p, q Since every step in Algorithm Generalized Wiener-Attack can be done in polyno- mial time and the number of convergents is bounded by O(logN), this concludes the proof of Theorem 2. 3 Cryptanalysis of the YKLM-scheme In 2001, Yen, Kim, Lim and Moon [11, 12] presented an RSA-type scheme that was designed to counteract the Bellcore-attack (see [2]). Unfortunately, they 7 need a specialized RSA key generation process in order to make their scheme efficient. Their public key e satisfies a relation with some small parameters that will be described in this section. The efficiency of the YKLM-scheme relies on the fact that these parameters are indeed much smaller than the modulus N . It was raised as an open question by the authors if one can use random public keys e as well in their scheme, thereby maintaining the same performance. We show that the public keys constructed in the YKLM-scheme satisfy the conditions of Theorem 2, i.e. for every public exponent e we have ex + y = 0 mod φ(N) with small x and y. Let us first reconsider the modified key generation algorithm in the YKLM- scheme. RSA Key Generation in the YKLM-scheme Modulus : Choose randomly two primes p and q of the same bit-size and com- pute the product N = pq. Small parameters : Fix a bound B, where B ≪ N . Choose randomly er and r in {1, . . . , B} such that gcd(er, φ(N)) = 1. Compute dr = e−1r mod φ(N). Secret exponent : Compute d = dr + r. If gcd(d, φ(N)) 6= 1, choose different parameters er and r. Public exponent : Compute e = d−1 mod φ(N). Public parameters : Publish the tuple (N, e). The authors pointed out that instead of the public key tuple (N, e) one could even publish the parameters er and r as well, but the following observation shows that the parameters er and r immediately yield the factorization of N . Consider the public key equation ed− 1 = 0 mod φ(N) The secret key d has a decomposition into the unknown part dr and the known parameter r e(dr + r)− 1 = 0 mod φ(N). Multiplication with er removes the unknown parameter dr e(1 + err) − er = 0 mod φ(N). Since every parameter on the left hand side is known, we can compute a multiple kφ(N) of the Euler function e(1 + err)− er = kφ(N) for some k ∈ N. (4) Since e < φ(N), we have that k < (1 + err). Therefore, the bit-length of k is polynomial in the bit-length of N . It is a well-known result that such a multiple kφ(N) yields the factorization of N in probabilistic polynomial time in the bit- length of N (see for example [8]). Certainly, there is no need to publish the small parameters er and r in the YKLM-scheme. On the other hand, we see that by equation (4) one can apply Theorem 2 by setting x = 1 + err and y = −er. This gives us the following corollary from Theorem 2. 8 Corollary 3 Let c ≤ 1 and let (N, e) be a public key tuple constructed by the key generation process in the YKLM-scheme with p− q ≥ cN 12 . Furthermore, let er and r satisfy the conditions 1 + err ≤ 1 3 N 1 4 and er ≤ 1 2 cN 1 4 Then N can be factored in time polynomial in log(N). Proof: In order to be able to apply Theorem 2, it remains to show that 12cN 1 4 ≤ cN− 3 4 e(1 + err). Using equation (4), we conclude that cN− 3 4 e(1 + err) > cN − 3 4φ(N) > 1 2 cN 1 4 , which proves the claim. Since the efficiency of the YKLM-scheme relies on the fact that er and r are very small compared to N , Corollary 3 breaks the YKLM-scheme for all reasonable parameter choices. 4 Generalizing t