Wiener's attack

Small private key

In the RSA cryptosystem, Bob might tend to use a small value of d, rather than a large random number to improve the RSA decryption performance. However, Wiener's attack shows that choosing a small value for d will result in an insecure system in which an attacker can recover all secret information, i.e., break the RSA system. This break is based on Wiener's theorem, which holds for small values of d. Wiener has proved that the attacker may efficiently find d when d < ⁠1/3⁠ N^1/4.

Wiener's paper also presented some countermeasures against his attack that allow fast decryption. Two techniques are described as follows.

Choosing large public key: Replace e by e′, where e′ = e + k ⋅ λ(N) for some large of k. When e′ is large enough, i.e. e′ > N^3/2, then Wiener's attack cannot be applied regardless of how small d is.

Using the Chinese remainder theorem: Suppose one chooses d such that both d_p ≡ d (mod (p − 1)) and d_q ≡ d (mod (q − 1)) are small but d itself is not, then a fast decryption of C can be done as follows:

1. First compute M_p ≡ C^d_p (mod p) and M_q ≡ C^d_q (mod q).
2. Use the Chinese remainder theorem to compute the unique value of 0 ≤ M < N that satisfies M ≡ M_p (mod p) and M ≡ M_q (mod q. The result of M satisfies M ≡ C^d (mod N) as needed. The point is that Wiener's attack does not apply here because the value of d mod λ(N) can be large.

How the attack works

Note that

${\displaystyle \lambda (N)=\mathrm{lcm}(p-1,q-1)=\frac{(p-1)(q-1)}{G}=\frac{\phi (N)}{G}}$

where G = gcd(p − 1, q − 1).

Since ed ≡ 1 (mod λ(N)), there exists an integer K such that

${\displaystyle ed=K\times \lambda (N)+1}$

${\displaystyle ed=\frac{K}{G}(p-1)(q-1)+1}$

Defining k = ⁠K/gcd(K, G)⁠ and g = ⁠G/gcd(K, G)⁠, and substituting into the above gives:

${\displaystyle ed=\frac{k}{g}(p-1)(q-1)+1}$.

Divided by dpq:

${\displaystyle \frac{e}{pq}=\frac{k}{dg}(1-\delta )}$, where ${\displaystyle \delta =\frac{p+q-1-\frac{g}{k}}{pq}}$.

So, ⁠e/pq⁠ is slightly smaller than ⁠k/dg⁠, and the former is composed entirely of public information. However, a method of checking and guess is still required.

By using simple algebraic manipulations and identities, a guess can be checked for accuracy.

Wiener's theorem

Let N = pq with q < p < 2q. Let d < ⁠1/3⁠ N^1/4.

Given ⟨N, e⟩ with ed ≡ 1 (mod λ(N)), the attacker can efficiently recover d.

Example

Suppose that the public keys are ⟨N, e⟩ = ⟨90581, 17993⟩. The attack should determine d. By using Wiener's theorem and continued fractions to approximate d, first we try to find the continued fractions expansion of ⁠e/N⁠. Note that this algorithm finds fractions in their lowest terms. We know that

${\displaystyle \frac{e}{N}=\frac{17993}{90581}=\frac{1}{5+\frac{1}{29+\cdots +\frac{1}{3}}}=\left[0,5,29,4,1,3,2,4,3\right]}$

According to the continued fractions expansion of ⁠e/N⁠, all convergents ⁠k/d⁠ are:

${\displaystyle \frac{k}{d}=0,\frac{1}{5},\frac{29}{146},\frac{117}{589},\frac{146}{735},\frac{555}{2794},\frac{1256}{6323},\frac{5579}{28086},\frac{17993}{90581}}$

We can verify that the first convergent does not produce a factorization of N. However, the convergent ⁠1/5⁠ yields

${\displaystyle \phi (N)=\frac{ed-1}{k}=\frac{17993\times 5-1}{1}=89964}$

Now, if we solve the equation

${\displaystyle x^2-\left(\left(N-\phi (N)\right)+1\right)x+N=0}$

${\displaystyle x^2-\left(\left(90581-89964\right)+1\right)x+90581=0}$

${\displaystyle x^2-618x+90581=0}$

then we find the roots which are x = 379; 239. Therefore we have found the factorization

${\displaystyle N=90581=379\times 239=p\times q}$.

Notice that, for the modulus N = 90581, Wiener's theorem will work if

${\displaystyle d<\frac{N^{1/4}}{3}\approx 5.7828}$.

Proof of Wiener's theorem

The proof is based on approximations using continued fractions.

Since ed = 1 (mod λ(N)), there exists a k such that ed − kλ(N) = 1. Therefore

${\displaystyle \left|\frac{e}{\lambda (N)}-\frac{k}{d}\right|=\frac{1}{d\lambda (N)}}$.

Let G = gcd(p − 1, q − 1); note that if φ(N) is used instead of λ(N), then the proof can be replaced with G = 1 and φ(N) replaced with λ(N).

Then multiplying by ⁠1/G⁠,

${\displaystyle \left|\frac{e}{\phi (N)}-\frac{k}{Gd}\right|=\frac{1}{d\phi (N)}}$

Hence, ⁠k/Gd⁠ is an approximation of ⁠e/φ(N)⁠. Although the attacker does not know φ(N), he may use N to approximate it. Indeed, since φ(N) = N − p − q + 1 and p + q − 1 < 3√N, we have:

${\displaystyle \left|p+q-1\right|<3\sqrt{N}}$

${\displaystyle \left|N-\phi (N)\right|<3\sqrt{N}}$

Using N in place of φ(N) we obtain:

${\displaystyle \begin{array}{cc}\left|\frac{e}{N}-\frac{k}{Gd}\right|& =\left|\frac{edG-kN}{NGd}\right|\\ & =\left|\frac{edG-k\phi (N)-kN+k\phi (N)}{NGd}\right|\\ & =\left|\frac{1-k(N-\phi (N))}{NGd}\right|\\ & <\left|\frac{-k(N-\phi (N))}{NGd}\right|(\because 0<|N-\phi (N)|)\\ & <\left|\frac{3k\sqrt{N}}{NGd}\right|=\frac{3k\sqrt{N}}{\sqrt{N}\sqrt{N}Gd}\le \frac{3k}{d\sqrt{N}}\end{array}}$

Now, kλ(N) = ed − 1 < ed, so kλ(N) < ed. Since e < λ(N), so kλ(N) < ed < λ(N)d, then we obtain:

${\displaystyle k\lambda (N)<\lambda (N)d}$

${\displaystyle k<d}$

Since k < d and d < ⁠1/3⁠ N^1/4. Hence we obtain:

(1) ${\displaystyle \left|\frac{e}{N}-\frac{k}{Gd}\right|<\frac{1}{d{N}^{\frac{1}{4}}}}$

Since d < ⁠1/3⁠ N^1/4, 2d < 3d, then 2d < 3d < N^1/4, we obtain:

${\displaystyle 2d<N^{1/4}}$, so (2) ${\displaystyle \frac{1}{2d}>\frac{1}{N^{1/4}}}$

From (1) and (2), we can conclude that

${\displaystyle \left|\frac{e}{N}-\frac{k}{Gd}\right|<\frac{3k}{d\sqrt{N}}<\frac{1}{d\cdot 2d}=\frac{1}{2d^2}}$

If |x − ⁠a/b⁠| < ⁠1/2b²⁠, then ⁠a/b⁠ is a convergent of x, thus ⁠k/Gd⁠ appears among the convergents of ⁠e/N⁠. Therefore the algorithm will indeed eventually find ⁠k/Gd⁠.