Continued Fraction Low Exponent Attack Efficiency Logn

ScientificWorldJournal. 2014; 2014: 650537.

On the Improvement of Wiener Attack on RSA with Small Private Exponent

Mu-En Wu

¹Department of Mathematics, Soochow University, Taipei, Taiwan

Chien-Ming Chen

²School of Computer Science and Technology, Shenzhen Graduate School, Harbin Institute of Technology, Shenzhen, China

³Shenzhen Key Laboratory of Internet Information Collaboration, Shenzhen, China

Yue-Hsun Lin

⁴CyLab, Carnegie Mellon University, Pittsburgh, PA 15213, USA

Hung-Min Sun

⁵Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan

Received 2014 Feb 7; Accepted 2014 Feb 27.

Abstract

RSA system is based on the hardness of the integer factorization problem (IFP). Given an RSA modulus N = pq, it is difficult to determine the prime factors p and q efficiently. One of the most famous short exponent attacks on RSA is the Wiener attack. In 1997, Verheul and van Tilborg use an exhaustive search to extend the boundary of the Wiener attack. Their result shows that the cost of exhaustive search is 2r + 8 bits when extending the Weiner's boundary r bits. In this paper, we first reduce the cost of exhaustive search from 2r + 8 bits to 2r + 2 bits. Then, we propose a method named EPF. With EPF, the cost of exhaustive search is further reduced to 2r − 6 bits when we extend Weiner's boundary r bits. It means that our result is 2¹⁴ times faster than Verheul and van Tilborg's result. Besides, the security boundary is extended 7 bits.

1. Introduction

During the past 30 years, RSA [1] has been one of the most popular public-key cryptosystems worldwide. It has been widely used in several applications [2–4]. The security of RSA is often based on the hardness of the integer factorization problem (IFP), which remains a well-studied problem [5, 6]. Current RSA standards suggest that an RSA modulus N should be at least 1024 bits long. Using the best-known factoring algorithms, the expected workload of factoring a 1024 bit modulus is 2⁸⁰, which is currently believed to be infeasible. However, although the use of a large RSA modulus achieves a high security level, the encryption and decryption procedures involve heavy exponential modular multiplications, which make RSA inefficient. Therefore, many approaches have been investigated for speeding-up the RSA encryption (or signature-verification) and RSA decryption (or signature-signing) [7–12]. Furthermore, since the signing task is often executed by lightweight devices, such as smart cards, mobile phones, or PDAs, the research on speeding-up signature-signing is more practical and important.

The most popular method for reducing the signing time is to apply a small private exponent d since the complexity of signing depends on the bit-length of d. In order to achieve this goal, the order of choosing e and d is exchanged. d is first chosen in the RSA-key generation algorithm, and the corresponding public exponent e satisfying ed ≡ 1(mod⁡φ(N)) is then calculated. These RSA variants are called RSA-Small-d. Nevertheless, the variants of RSA-Small-d have the security flaws [13–18]. In fact, instances of RSA with d < N ^1/4 can be efficiently broken by Wiener attack [16]. Besides, Boneh and Durfee's lattice-based attack [19] indicated that an instance of RSA-Small-d with d < N ^0.292 should be considered to be an unsafe system.

In 1997, Verheul and van Tilborg [20] used an exhaustive search to further extend the boundary of the Wiener attack. Suppose r = log⁡₂⁡d − log⁡₂⁡N ^1/4; their result shows that an exhaustive search for 2r + 8 bits is required to extend the Wiener's boundary r bits. Assume that an exhaustive search for 64 bits is feasible in terms of current computational abilities; solving r for the equation "2r + 8 = 64" yields r = 28, which implies that the boundary of the Wiener attack should be raised up to N ^1/42²⁸.

In this paper, we attempt to reduce the cost of exhaustive search of Verheul and van Tilborg's result. We propose an approach to reduce the cost of exhaustive search when we desire to extend Wiener's boundary. This approach includes two steps.

Step 1 —

We investigate a method for searching as many MSBs (most significant bits) of p + q as possible, which is equivalent to estimating p + q as accurately as possible. In this step, to extend Wiener's boundary r bits, an exhaustive search requires 2r + 2 bits. It means that our result is better than Verheul and van Tilborg's cost, which requires an exhaustive search for 2r + 8 bits.

Step 2 —

We develop an approach, called "Estimated Prime Factor (EPF)," to estimate p + q, and then we derive two integers p _E and q _E, which are the estimations of p and q, respectively. Using EPF, the first 8 MSBs of p + q can be determined. This result is more accurate than the traditional estimation, which estimates p + q by $2 \sqrt{N}$ . Applying EPF can further reduce the cost of exhaustive search. More specifically, to extend Wiener's boundary r bits, an exhaustive search requires 2r − 6 bits. As compared to Verheul and van Tilborg's result, which requires an exhaustive search for 2r + 8 bits, the security boundary is extended 7 bits.

1.1. Our Contribution

The contributions of this paper are summarized as follows.

We first reduce the cost of exhaustive search from 2r + 8 (Verheul and van Tilborg's result) bits to 2r + 2 bits when we extend Wiener's boundary r bits. It means that exhaustive search is 2⁶ times faster in Step 1. Besides, the security boundary is extended 3 bits.
We propose a novel approach, named EPF, for estimating the prime factors of N. With EPF, the cost of the exhaustive search for 2r + 2 bits (mentioned in contribution (1)) is further reduced to 2r − 6 bits. Compared with Verheul and van Tilborg's result, exhaustive search is 2¹⁴ times faster. Besides, the security boundary is extended 7 bits.

1.2. Organization

The remainder of this paper is organized as follows. Section 2 presents the preliminaries of this paper. Section 3 describes Step 1 of our approach. In Section 4, we propose the EPF to estimate the prime factors of an RSA modulus. Next, Step 2 of our approach which is applying EPF is proposed in Section 5. Finally, we present our conclusions and future works in Section 6.

2. Preliminary

In this section, we introduce the preliminaries of this paper which include RSA and its variants and the Wiener attack.

2.1. RSA and Its Variants

The RSA cryptosystem [1] consists of three parts, RSA-key generation, encryption, and decryption which are described as follows.

2.1.1. RSA-Key Generation, Encryption, and Decryption

The RSA-key generation outputs the RSA key: (N, e, d). First, randomly choose two large prime numbers p and q and compute N = pq, where N is called RSA modulus. Secondly, let e, called public exponent, be a randomly chosen integer such that gcd (e, φ(N)) = 1, where φ(·) is Euler's phi function. Then, let d, called private exponent, be the multiplicative inverse modulo φ(N) (i.e., ed ≡ 1 (mod⁡φ(N))). The pair (e, N) is the public key and the pair (d, N) is the private key.

From the key relation ed ≡ 1 (mod⁡φ(N)), there exists a unique positive integer k satisfying

We call (1) as the RSA-key equation. To encrypt a plaintext message M ∈ ℤ _N, compute C ≡ M ^e(mod⁡N). The result C is called the ciphertext of M. To execute RSA decryption, a ciphertext C ∈ ℤ _N is decrypted by raising it to the dth power modulo N. From Lagrange's theorem, it follows that

$\begin{matrix} C^{d} (\underset{}{\mod} N) = M^{e d} (\underset{}{\mod} N) \equiv M (\mod N) = M . \end{matrix}$

(2)

Usually, one often selects e as small as possible due to the reason of efficient encryption (or signature-verification). The smallest e is suggested to be 2³² + 1 rather than 2¹⁶ + 1 while a known affine relation between two messages exists [21]. We call the RSA system with small public exponent e as "RSA-Small-e." On the other hand, since the cost of decryption (or signature-signing) can be significantly reduced when the private exponent d is much smaller than φ(N), in order to simply reduce the decryption (or signature-signing) time, one can select a small private exponent d first in RSA-key generation. Such variant is called RSA-Small-d, which is shown in the following.

2.1.2. RSA-Small-d

Generating instances of RSA with a small private exponent is easy with the observation that the RSA-key equation (1) is symmetric with respect to the public and private exponents. We simply follow the same key generation of original RSA but exchange the choosing order of public and private exponents.

One of the drawbacks of RSA-Small-d is its inefficient encryption. Since the public exponent e in RSA-Small-d is always computed as the inverse of d modulo φ(N), it is expected with high probability that e will be almost the same size as φ(N). In conclusion, RSA-Small-d saves the decryption (or signature) cost while the encryption cost remains large.

2.2. The Wiener Attack

One of the most famous short exponent attacks on RSA is the Wiener attack. Boneh and Durfee [22] showed in 1990 that RSA-Small-d should be considered insecure when d < N ^1/4. He achieved the attack through the technique of continued fractions. In the following paragraph, we briefly introduce the continued fractions and the Weiner attack. The details can be referenced in [16].

Definition 1 (continued fractions) —

For any positive real number α, define α = ξ ₀, a _i = ⌊ξ _i⌋, ξ _i+1 = 1/(ξ _i − a _i) for i = 0, 1, 2, …. Then α can be expanded into the following form:

α _i =a ₀ + 1/(a ₁ + 1/(a ₂ + 1/(a ₃ + 1/ ⋯ ))).

(3)

The form of (3) is called the continued fraction expression of α. For simplicity, we write (3) to be α = (a ₀, a ₁, a ₂,…). In addition, denote α _i = (a ₀, a ₁,…, a _i) as the ith convergent of the continued fraction expansion of α, which means

α _i =a ₀ + 1/(a ₁ + 1/(a ₂ + 1/( ⋯ + 1/a _i))).

(4)

If α is a rational number, then the process of computing its continued fraction expression, see (3), will cease in some index k. That is, α = α _k. If α is irrational, then the process will go on unceasingly.

Theorem 2 —

Denote h _i/k _i as the fraction form of (4); that is, h _i/k _i = α _i, where h _i and k _i are positive integers. Then, h _i and k _i can be calculated by defining h ₋₂ = 0, k ₋₂ = 1, h ₋₁ = 1, and k ₋₁ = 0. And h _i = a _i h _i−1 + h _i−2 and k _i = a _i k _i−1 + k _i−2, for i ≥ 0.

Following the notations in Theorem 2, we have Corollary 3.

Corollary —

For any i ≥ 1,

$\begin{matrix} | α - \frac{h_{i + 1}}{k_{i + 1}} | < | α - \frac{h_{i}}{k_{i}} | . \end{matrix}$

(5)

Furthermore, if α is an irrational number, then lim⁡_i→∞ h _i/k _i = α.

Theorem 4 —

If a real number α and a reduced fraction a/b satisfy

then a/b equals to one of the convergents of the continued fraction expression of α.

2.2.1. The Wiener Attack.

The Wiener attack [16] is based on approximations using continued fractions to find the private exponent of RSA-Small-d in polynomial time if d < N ^1/4, where p and q are of the same bit-length. Note that the RSA-key equation, ed = 1 + k · φ(N), can be rewritten as

which is similar to the form of the left-hand side of (6). In order to apply Theorem 4, we replace e/φ(N) of (7) by e/N, which is known for everyone, and set the difference between e/N and k/d to be smaller than 1/2d ²; that is,

Therefore, according to Theorem 4, k/d can be found by computing one of the convergents of the continued fraction expression of e/N.

The security boundary of the Wiener attack is deduced from the sufficient condition for (8). Since $p \approx q \approx \sqrt{N}$ and k ≈ d, the left-hand side of (8) is simplified to

$\begin{matrix} | \frac{e}{N} - \frac{k}{d} | = \frac{k (p + q - 1) - 1}{N d} \approx \frac{2 \sqrt{N}}{N} = \frac{2}{\sqrt{N}} . \end{matrix}$

(9)

Hence, (8) is transformed to

which gives the security boundary of the Wiener attack (after ignoring the constant term):

2.3. Verheul and van Tilborg's Extension

The Wiener attack works very well and efficiently when the private exponent d < N ^1/4. However, what about if the bit-length of d is slightly larger than the bit-length of N ^1/4? In 1997, Verheul and van Tilborg [20] proposed a technique to solve this problem by performing an exhaustive search for 2r + 8 bits, where r = log⁡₂ d − log⁡₂ N ^1/4 means that the bit-length of d is longer than the bit-length of N ^1/4 by r bits.

Verheul and van Tilborg observed that k/d in (8) can be represented as follows:

$\begin{matrix} \frac{k}{d} = \frac{_{p_{j + 1}} U + {(U Δ + V)}_{p_{j}}}{_{q_{j + 1}} U + {(U Δ + V)}_{q_{j}}}, \end{matrix}$

(12)

where p _i/q _i is the ith convergent of the continued fraction expression of e/N, Δ = 1 or 2, and U and V are two unknown integers with upper bounds as follows:

log⁡₂ U ≤r + 4, log⁡₂ V ≤r + 4.

(13)

Since Δ is a small integer, we can omit its uncertainty. The unknown parts of (12) are about 2r + 8 bits, which give the result of Verheul and van Tilborg's extension: extending Wiener's boundary by r bits requires an exhaustive search for about 2r + 8 bits.

Assume that an exhaustive search for 64 bits is feasible in terms of the current computational capabilities. Solving r for the equation "2r + 8 = 64" yields r = 28, which implies that Wiener's boundary can be extended 28 bits over the bit-length of N ^1/4. Therefore, RSA-Small-d with d < N ^1/42²⁸ can be totally broken by continued fraction attack plus the cost of performing an exhaustive search for 64 bits. In Section 3, we show that, in order to extend Wiener's boundary by r bits, it requires only an exhaustive search for 2r + 2 bits, rather than that from Verheul and van Tilborg's extension for cost, which requires an exhaustive search for 2r + 8 bits.

3. Reducing the Cost of Exhaustive Search to 2r + 2 Bits

Our approach contains two steps which are described in Sections 3 and 5, respectively. In this section, we investigate a method for searching as many MSBs (most significant bits) of p + q as possible, which is equivalent to estimating p + q as accurately as possible. With this method, we can reduce the cost of exhaustive search from 2r + 8 bits (Verheul and van Tilborg's extension) to 2r + 2 bits when we extend Wiener's boundary r bits.

Let A be the estimation of p + q. Throughout this paper, we assume A < p + q. Thus φ(N) = (N + 1)−(p + q) is estimated as (N + 1) − A, which implies

Applying (14) to the Wiener attack, that is, replacing e/N of (8) by e/((N + 1) − A), we have

Note that if A = p + q, then (15) always holds for any d because

$\begin{matrix} | \frac{e}{N + 1 - (p + q)} - \frac{k}{d} | = | \frac{e d - k (N + 1 - (p + q))}{(N + 1 - (p + q)) d} | \\ = \frac{1}{φ (N) d} < \frac{1}{2 d^{2}} . \end{matrix}$

(16)

Simplifying (15) yields

$\begin{matrix} | \frac{e}{N + 1 - A} - \frac{k}{d} | = | \frac{e d - k (N + 1 - A)}{(N + 1 - A) d} | \\ = \frac{k [(p + q) - A] - 1}{(N + 1 - A) d} < \frac{1}{2 d^{2}}, \end{matrix}$

(17)

which is

2d k[(p +q) −A] − 2d <N + 1 −A.

(18)

Solving d in (18), we get the upper bound of the private exponent:

According to the above inequality, we know that the smaller the difference between p + q and A, the higher the upper bound of d. Consequently, in order to extend the security boundary of RSA-Small-d, we attempt to estimate A as precisely as possible such that p + q − A becomes small. Equation (19) also shows that the complexity of further extending Wiener's boundary can be reduced to the complexity of estimating the MSBs of p + q. The relation is shown in the following.

Rearranging (18) we have

2d k(p +q − 1) − 2d <N + (2d k − 1)(A − 1).

(20)

Denote Λ as the difference between p + q and A. That is, Λ = p + q − A. Replacing A in (20) by p + q − Λ conducts

$\begin{matrix} 2 d k (p + q - 1) - 2 d < N + (2 d k - 1) ((p + q - Λ) - 1) \\ = 2 d k (p + q - 1) \\ + φ (N) - Λ (2 d k - 1) . \end{matrix}$

(21)

In (21), eliminating 2dk(p + q − 1) in both sides we get

Λ(2d k − 1) − 2d <φ(N).

(22)

Now we consider the bit-length of each side. Assume that the bit-length of d is n/4 + r bits, which is longer than Wiener's boundary by r bits. Due to the key generation of RSA-Small-d, the parameter k is almost the same size as d with a high probability; that is, log⁡₂ k ≈ log⁡₂ d. In addition, we perform an exhaustive search for the first s MSBs of p + q. Thus the difference between p + q and A can be reduced to (n/2 + 1) − s bits; that is, log⁡₂Λ ≈ (n/2 + 1) − s. Consequently, The term Λ · 2dk, which dominates the size in the left-hand side of (22), is about ((n/2 + 1) − s) + 1 + 2 × (n/4 + r) bits long and the sufficient condition of (22) is

$\begin{matrix} \underset{for Λ}{\underset{︸}{((n / 2 + 1) - s)}} + \underset{for 2 d k}{\underset{︸}{1 + 2 \times (n / 4 + r)}} < n, \end{matrix}$

(23)

which is simplified to

Equation (24) gives the following conclusion. In order to extend Wiener's boundary by r bits, we have to perform an exhaustive search for the first 2r + 2 MSBs ofp + q, where r = log⁡₂ d − log⁡₂ N ^1/4. This result is better than that of Verheul and van Tilborg's cost [20], which requires an exhaustive search for 2r + 8 bits. Therefore, assume that an exhaustive search for 64 bits is feasible in terms of current computational abilities. Solving r for

yields r = 31, which means that RSA-Small-d is insecure when d < N ^1/42³¹.

4. Estimated Prime Factor (EPF)

In this section, a novel approach called Estimated Prime Factor (EPF), which is used to estimate the prime factors of an RSA modulus N, is proposed.

4.1. EPF

Without loss of generality, we assume that q < p < 2q, where N = pq. Denote D _p and D _q as the distances between $\sqrt{N}$ & p and q & $\sqrt{N}$ , respectively. That is,

Applying (26) to N = pq yields

Eliminating N in both sides of (27) we have

which leads to

Equation (30) is quite interesting because the irrational fraction $1 / \sqrt{N}$ reveals partial information of D _p − D _q and D _p · D _q. Note that with D _p − D _q and D _p · D _q we can compute D _p + D _q by

(D _p+D _q)² = (D _p−D _q)² + 4D _p D _q

(31)

and solve D _p and D _q as follows:

$\begin{matrix} D_{p} = \frac{D_{p} + D_{q}}{2} + \frac{D_{p} - D_{q}}{2}, \\ D_{q} = \frac{D_{p} + D_{q}}{2} - \frac{D_{p} - D_{q}}{2} . \end{matrix}$

(32)

Now we use continued fractions to construct a rational sequence to approximate $1 / \sqrt{N}$ . Suppose that the ith convergent of the continued fraction expansion of $1 / \sqrt{N}$ is h _i/k _i. According to Theorem 2, we know that

Since the sizes of h _i and k _i grow with increase of the index i (see Theorem 2), there exists an index t such that

We use h _t and k _t as the estimations of D _p − D _q and D _p D _q, respectively, instead of using the larger ones. That is,

h _t ≈D _p −D _q,k _t ≈D _p D _q.

(35)

From (31), D _p + D _q is estimated as

And thus D _p and D _q are estimated as

$\begin{matrix} D_{p} \approx \frac{\sqrt{h_{t}^{2} + 4 k_{t}} + h_{t}}{2}, D_{q} \approx \frac{\sqrt{h_{t}^{2} + 4 k_{t}} - h_{t}}{2} . \end{matrix}$

(37)

Finally, we define the estimated prime factors of N as

$\begin{matrix} p_{E} : = ⌈ \sqrt{N} + \frac{\sqrt{h_{t}^{2} + 4 k_{t}} + h_{t}}{2} ⌉, \\ q_{E} : = ⌊ \sqrt{N} - \frac{\sqrt{h_{t}^{2} + 4 k_{t}} - h_{t}}{2} ⌋ . \end{matrix}$

(38)

4.2. Theoretical Estimation and Experimental Result on Searching the Index t

The process of computing the convergent of the continued fraction expression of $1 / \sqrt{N}$ should be ceased at the index t satisfying (34). Thus, we have to estimate the size of D _p − D _q in order to determine the index t. Since D _p < p and D _q < q, h _t should not be set larger than n/2 bits at least. Next, we investigate the method to estimate the index t theoretically and experimentally.

4.2.1. Theoretical Estimation

From the definitions of D _p and D _q in (26), we have

which is equivalent to

$\begin{matrix} \log_{2} (D_{p} - D_{q}) = 2 \log_{2} (\sqrt{p} - \sqrt{q}) . \end{matrix}$

(40)

Equation (40) shows that the bit-length of D _p − D _q is twice the bit-length of $\sqrt{p} - \sqrt{q}$ . Consider the following problem.

Problem. Randomly select two prime numbers p and q of n/2 bits; what is the expected value of the number of MSBs of $\sqrt{p}$ and $\sqrt{q}$ that are identical?

From our theoretical estimation, the expected value is about 2.6, and it is almost independent of the bit-length of N. This implies that, for any two randomly selected prime numbers p and q of n/2 bits each, the first 2.6 MSBs of $\sqrt{p}$ and $\sqrt{q}$ are identical on average. Consequently, according to (40), the size of D _p − D _q is expected to be 2 × (n/4 − 2.6) = n/2 − 5.2 bits, which increases linearly with the bit-length of N.

4.2.2. Experimental Results

Table 1 shows the experimental results for the index t in EPF. Suppose that p and q are two randomly generated prime numbers of n/2 bits each; we then compute log⁡₂(D _p − D _q), log⁡₂(h _t), and log⁡₂(h _t+1), which denote the bit-lengths of D _p − D _q, h _t, and h _t+1, respectively. Each block in the table is evaluated from the average value of 1000 experimental instances. As can be observed from the first row, the bit-length of D _p − D _q is approximately equal to (n/2 − 7) bits long for all n and is greater than that of h _t by at least 1 bit on average. This result is slightly different from the result in the previous version at ACNS'07 [23] due to the reason of using different samples in the experiments. Note that in this paper we implement EPF with uniformly distributed samples which are more objective. Moreover, the values of log⁡₂(D _p − D _q) in Table 1 are slightly smaller than the theoretical estimation n/2 − 5.2 bits; the reason may be that we ignore the usage of prime-counting function π(·) in the calculation. However, the values in Table 1 actually increase linearly with the bit-length of N.

Table 1

The improvement of EPF on p + q, where p and q are balanced.

n	512	1024	2048
log₂⁡(D _p − D _q)	248.476	504.626	1016.551

t (in average)	146.229	295.772	594.103
log₂⁡(h _t)	247.161	503.04	1015.201
log₂⁡(h _t+1)	250.12	506.21	1018.14

In EPF, we simply estimate the value of D _p − D _q, which is, however, smaller than the actual value. On the other hand, up to now, there is no theory to justify the difference between the bit-lengths of h _t and D _p − D _q; in fact, this would be an interesting subject of inquiry.

4.3. Accuracy and Further Improvement

We demonstrate the accuracy of EPF in Table 2. Each entry in the table is the data averaged over 1000 samples. The first row shows the difference of the bit-length between p + q and its estimation by using $2 \sqrt{N}$ . The second row shows the difference of the bit-length between p + q and its estimation by using EPF. As can be seen in Table 2, using p _E + q _E as the estimation is more accurate than using $2 \sqrt{N}$ at least one bit on average. This result shows that EPF is better than the traditional estimation method.

Table 2

The improvement of EPF on p + q, where p and q are balanced.

Balanced Modulus N = pq	n = 512	n = 1024	n = 2048
$\log_{2} ((p + q) - 2 \sqrt{N})$	248.476	504.626	1016.551
log₂⁡((p + q) − (p _E + q _E))	247.185	503.294	1015.248

To further raise the accuracy rate of EPF, we may employ the properties of continued fractions. According to Theorem 2, we know that

h _t+1 =a _t h _t +h _t−1,k _t+1 =a _t k _t +k _t−1,

(41)

where a _t is the tth component of the continued fraction expression of $1 / \sqrt{N}$ (see Definition in Section 2.2). Consequently, for any real number λ ∈ [1, a _t], we have

h _t <λ h _t +h _t−1 <h _t+1,k _t <λ k _t +k _t−1 <k _t+1.

(42)

Since D _p − D _q and D _p · D _q are also in the intervals (h _t, h _t+1) and (k _t, k _t+1), respectively, λh _t + h _t−1 and λk _t + k _t−1 might be better estimations of D _p − D _q and D _p · D _q. Hence, an interesting question would be how to find a suitable value of λ that yields better estimations of D _p − D _q and D _p · D _q. Note that, from the properties of continued fractions, we have

$\begin{matrix} \frac{h_{t + 1}}{k_{t + 1}} > \frac{1}{\sqrt{N}} > \frac{h_{t}}{k_{t}} if t is old, \\ \frac{h_{t + 1}}{k_{t + 1}} < \frac{1}{\sqrt{N}} < \frac{h_{t}}{k_{t}} if t is even . \end{matrix}$

(43)

Equation (43) implies that there exists an irrational number λ ₁, such that

$\begin{matrix} \frac{λ_{1} h_{t} + h_{t - 1}}{λ_{1} k_{t} + k_{t - 1}} = \frac{1}{\sqrt{N}} . \end{matrix}$

(44)

To find an appropriate number λ, one method could be to choose λ, which is very close to λ ₁, which might yield better estimations of D _p − D _q and D _p · D _q. However, we leave this concept as the subject of future work on EPF.

5. Applying EPF to Reduce the Cost of Exhaustive Search to 2r − 6 Bits

In this section, we apply EPF proposed in Section 4 to further reduce the cost of exhaustive search.

From the results of Section 3, the security boundary of RSA-Small-d depends on the known MSBs of p + q. In EPF, the experimental results show that the 1st to the 8th MSB of p + q, denoted as MSB_1^∼8(p + q), can be correctly determined with high probability (see Table 2). Consequently, setting p _E + q _E = 2^(n/2+1)−8 A ₁ + A ₂, where A ₂ < 2^n/2−7, then

(A ₁)₂ = MSB_1^∼8(p +q),

(45)

where (A ₁)₂ denotes the binary representation of A ₁. Setting Λ = (p + q) − (p _E + q _E), (45) also shows that Λ is about (n/2 + 1) − 8 bits long. Hence, representing (22) according to the bit-length of the items, Λ, d, k, and φ(N) yields

$\begin{matrix} ((\frac{n}{2} + 1) - 8) + 1 + 2 (\frac{n}{4} + r) < n . \end{matrix}$

(46)

Moreover, by performing an exhaustive search for s bits after the 8th MSB of p + q, that is, MSB_9^∼8+s(p + q), we can further reduce the size of Λ to (n/2 + 1) − (8 + s) bits. This implies that the 1st to the (8 + s)th MSB of p + q can be correctly determined and the size of Λ is reduced to (n/2 + 1) − (8 + s) bits. Hence, (46) is revised to

$\begin{matrix} (\frac{n}{2} + 1) - (8 + s) + 1 + 2 (\frac{n}{4} + r) < n, \end{matrix}$

(47)

which is simplified to

Equation (48) is the improved result when applying EPF to the method presented in Section 3. As a conclusion, extending Wiener's boundary by r bits requires only an exhaustive search for 2r − 6 bits, which results in a lower computational cost than that with Verheul and van Tilborg's extension. We summarize the improvements in each type of attack in Table 3.

Table 3

The improvement between each attack.

Attacks	Boundary	Complexity
Wiener Attack	d < N ^1/4	Polynomial time
V-T Extension	d < N ^1/42^r	Exhaustive search for U and V of 2r + 8 bits (see (13))
Proposed Improvement (Step 1)	d < N ^1/42^r	Exhaustive search for 2r + 2 bits (see (24))
Applying EPF (Step 2)	d < N ^1/42^r	Exhaustive search for 2r − 6 bits (see (48))

With the progress of technology, the ability of machines to perform exhaustive searches will only increase. Figure 1 shows the relations between the security boundaries of the extensions of the Wiener attack and machines with different computational abilities. The symbol s denotes the required number of bits for an exhaustive search to extend Wiener's boundary, and the symbol |d| denotes the upper bound of the insecure private exponent. In terms of the current computational capabilities, an exhaustive search for 64 bits is feasible. Hence, the lines L1, L2 andL3 yield the improvements of 28 bits, 31 bits, and 35 bits, respectively, over Wiener's boundary. The boundaries of the extensions of the Wiener attack (see V-T. Ext., Ext. W., and EPF in Figure 1) can be raised to 284 bits, 287 bits, and 291 bits, respectively, when the RSA modulus N is 1024 bits long. Furthermore, if an exhaustive search for 80 bits is feasible, the upper bound of the extension of the Wiener attack through EPF is raised to N ^1/42⁴³, which is 299 bits when N is 1024 bits long (see L3: EPF). This result is comparable to the boundary of the lattice attack proposed by Boneh and Durfee [19], which has a best upper bound, but heuristic, at the present. Note that there is no guaranty that a heuristic algorithm can output the solution. One may concern whether the assumption that an exhaustive search for 80 bits is feasible or not. In the opinion of current development, it will not be a difficult task to achieve such computational capability in the near future. According to Moore's Law, computers will double in speed approximately every 18 months, which further supports our assumption. Moreover, paralleling techniques and special-purpose machines can help in speeding-up the computation.

An external file that holds a picture, illustration, etc. Object name is TSWJ2014-650537.001.jpg

The boundaries of the extensions of the Wiener attack under different computational capabilities, where 256 and 299 are the boundaries of the Wiener attack (W. Attack) and Boneh and Durfee's attack (B-D. Attack), respectively. L1, L2, and L3 denote the boundaries of Verheul and Tilborg's extension (V-T. Ext.) (see [20]), the extension of the Wiener attack (Step 1) (Ext. W.) (see (24)), and the extension of the Wiener attack through EPF (EPF) (see (48)).

6. Conclusion and Future Works

With the rapid growth of different network environments such as wireless sensor networks [24–27], security is normally the most concerned issue. In this paper, we propose a method, called EPF, to estimate the prime factors of an RSA modulus. With EPF, the cost of exhaustive search can further reduce to 2r − 6 bits. It means that the cost is 2¹⁴ times faster than Verheul and van Tilborg's result and the security boundary is extended 7 bits. It should be noted that their method for an exhaustive search is heuristic since this method is based on the results of distribution of small partial quotient in the continued fraction expansions.

An interesting problem in EPF is whether there exists a deterministic algorithm for finding an index t satisfying h _t < D _p − D _q < h _t+1. In this paper, we use the theoretical estimation to determine the index t. The success rate is 85.1% according to our experiments. Now, another question arises—how to increase the success rate of the process of finding the index t when the deterministic algorithm is not developed. In addition, the other researchable question is how to improve the accuracy rate of MSBs of p _E + q _E, which brings a greater contributive effort of EPF.

We should point out that EPF can be applied to Dujella's refinement [14] and the generalized Wiener attack [18]. Moreover, we foresee that EPF could be applied to other cryptogrammic aspects, especially to the attacks for cryptosystems based on the integer factorization problem (IFP). For example, the lattice technique is commonly used for the cryptanalysis of RSA [17, 28–30] or for the attacks on RSA with small exponents [15, 18, 19, 21, 22, 31, 32]. We expect EPF to be a supportive tool for assisting the lattice technique to increase the effort on the cryptanalysis of RSA. As a conclusion, we would like to point out that with the continuous improvements in computational capability, the security levels are expected to be higher with the assistance of EPF, and the security analysis should be considered more carefully.

Acknowledgments

The authors would like to thank the anonymous reviewers for their valuable comments and suggestions, which certainly led to improvements of this paper. Chien-Ming Chen was partially supported by the Shenzhen Peacock Project, China, under Contract no. KQC201109020055A and the Shenzhen Strategic Emerging Industries Program under Grant no. ZDSY20120613125016389. Hung-Min Sun was partially supported by the National Science Council, Taiwan, under Grant NSC 100-2628-E-007-018-MY3.

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

1. Rivest R, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM. 1978;21(2):120–126. [Google Scholar]

2. Patsakis C. Number theoretic SETUPs for RSA like factoring based algorithms. Journal of Information Hiding and Multimedia Signal Processing. 2012;3(2):191–204. [Google Scholar]

3. Kong Q, Li P, Ma Y. On the feasibility and security of image secret sharing scheme to identify cheaters. Journal of Information Hiding and Multimedia Signal Processing. 2013;4(4):2073–4212. [Google Scholar]

4. Peng N, Luo G, Qin K, Chen A. Query-biased preview over outsourced and encrypted data. The Scientific World Journal. 2013;2013:13 pages.860621 [PMC free article] [PubMed] [Google Scholar]

5. Lenstra H., Jr. Factoring integers with elliptic curves. Annals of Mathematics. 1987;126(3):649–673. [Google Scholar]

6. Pollard J. Theorems on factorization and primality testing. Mathematical Proceedings of the Cambridge Philosophical Society. 1974;76(3):521–528. [Google Scholar]

7. Boneh D, Shacham H. Fast variants of RSA. CryptoBytes. 2002;5(1):1–9. [Google Scholar]

8. Galbraith S, Heneghan C, McKee J. Information Security and Privacy. Vol. 3574. Berlin, Germany: Springer; 2005. Tunable balancing of RSA; pp. 280–292. (Lecture Notes in Computer Science). [Google Scholar]

9. Hinek M. Topics in Cryptology-CT-RSA 2006. Vol. 3860. Berlin, Germany: Springer; 2006. Another look at small RSA exponents; pp. 82–98. (Lecture Notes in Computer Science). [Google Scholar]

10. Sun H, Yang W, Laih C. Advances in Cryptology-ASIACRYPT '99. Vol. 1716. Berlin, Germany: Springer; 1999. On the design of RSA with short secret exponent; pp. 150–164. (Lecture Notes in Computer Science). [Google Scholar]

11. Sun H, Yang C. Public Key Cryptography-PKC 2005. Vol. 3386. Berlin, Germany: Springer; 2005. RSA with balanced short exponents and its application to entity authentication; pp. 199–215. (Lecture Notes in Computer Science). [Google Scholar]

12. Vanstone S, Zuccherato R. Short RSA keys and their generation. Journal of Cryptology. 1995;8(2):101–114. [Google Scholar]

13. Boneh D, Rivest R, Shamir A, et al. Twenty years of attacks on the RSA cryptosystem. Notices of the American Mathematical Society. 1999;46(2):203–213. [Google Scholar]

14. Dujella A. Continued fractions and RSA with small secret exponent. Tatra Mountains Mathematical Publications. 2004;29:101–112. [Google Scholar]

15. Jochemsz E, de Weger B. Information Security. Vol. 4176. Berlin, Germany: Springer; 2006. A partial key exposure attack on RSA using a 2-dimensional lattice; pp. 203–216. (Lecture Notes in Computer Science). [Google Scholar]

16. Wiener MJ. Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory. 1990;36(3):553–558. [Google Scholar]

17. de Weger B. Cryptanalysis of RSA with small prime difference. Applicable Algebra in Engineering, Communications and Computing. 2002;13(1):17–28. [Google Scholar]

18. Blömer J, May A. Public Key Cryptography-PKC 2004. Vol. 2947. Berlin, Germany: Springer; 2004. A generalized Wiener attack on RSA; pp. 1–13. (Lecture Notes in Computer Science). [Google Scholar]

19. Boneh D, Durfee G. Advances in Cryptology-EUROCRYPT '99. Vol. 1592. Berlin, Germany: Springer; 1999. Cryptanalysis of RSA with private key d less than N ^0.292 ; pp. 1–11. (Lecture Notes in Computer Science). [Google Scholar]

20. Verheul E, van Tilborg H. Cryptanalysis of "less short" RSA secret exponents. Applicable Algebra in Engineering, Communications and Computing. 1997;8(5):425–435. [Google Scholar]

21. Coppersmith D, Franklin M, Patarin J, Reiter M. Advances in Cryptology-EUROCRYPT '96. Vol. 1070. Berlin, Germany: Springer; 1996. Low-exponent RSA with related messages; pp. 1–9. (Lecture Notes in Computer Science). [Google Scholar]

22. Boneh D, Durfee G. Cryptanalysis of RSA with private key d less than d less than N ^0.292 . IEEE Transactions on Information Theory. 2000;46(4):1339–1349. [Google Scholar]

23. Sun HM, Wu ME, Chen YH. Applied Cryptography and Network Security. Vol. 4521. Berlin, Germany: Springer; 2007. Estimating the prime-factors of an rsa modulus and an extension of the wiener attack; pp. 116–128. (Lecture Notes in Computer Science). [Google Scholar]

24. Chen CM, Lin YH, Chen YH, Sun HM. SASHIMI: secure aggregation via successively hierarchical inspecting of message integrity on WSN. Journal of Information Hiding and Multimedia Signal Processing. 2013;4(1):57–72. [Google Scholar]

25. Chen CM, Lin YH, Lin YC, Sun HM. RCDA: recoverable concealed data aggregation for data integrity in wireless sensor networks. IEEE Transactions on Parallel and Distributed Systems. 2012;23(4):727–734. [Google Scholar]

26. Sun H-M, Chen C-M, Hsiao Y-C. An efficient countermeasure to the selective forwarding attack in wireless sensor networks. Proceedings of the IEEE Region 10 Conference (TENCON '07); November 2007; Taipei, Taiwan. IEEE; pp. 1–4. [Google Scholar]

27. Wei-Chi K, Chien-Ming C, Hui-Lung L. Cryptanalysis of a variant of Peyravian-Zunic's password authentication scheme. IEICE Transactions on Communications. 2003;86(5):1682–1684. [Google Scholar]

28. Coppersmith D. Advances in Cryptology-EUROCRYPT '96. Vol. 1070. Berlin, Germany: Springer; 1996. Finding a small root of a bivariate integer equation; factoring with high bits known; pp. 178–189. (Lecture Notes in Computer Science). [Google Scholar]

29. Coppersmith D. Advances in Cryptology-EUROCRYPT '96. Vol. 1070. Berlin, Germany: Springer; 1996. Finding a small root of a univariate modular equation; pp. 155–165. (Lecture Notes in Computer Science). [Google Scholar]

30. Sun H, Wu M, Ting W, Hinek M. Dual RSA and its security analysis. IEEE Transactions on Information Theory. 2007;53(8):2922–2933. [Google Scholar]

31. Bleichenbacher D, May A. Public Key Cryptography-PKC 2006. Vol. 3958. Berlin, Germany: Springer; 2006. New attacks on RSA with small secret CRT-exponents; pp. 1–13. (Lecture Notes in Computer Science). [Google Scholar]

32. Boneh D, Durfee G, Frankel Y. Advances in Cryptology-ASIACRYPT '98. Vol. 1514. Berlin, Germany: Springer; 1998. An attack on RSA given a small fraction of the private key bits; pp. 25–34. (Lecture Notes in Computer Science). [Google Scholar]

Articles from The Scientific World Journal are provided here courtesy of Hindawi Limited

wayhilin1986.blogspot.com

Source: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3985315/

Way Hilin1986