Wiener's attack

Template:Short description The Wiener's attack, named after cryptologist Michael J. Wiener, is a type of cryptographic attack against RSA. The attack uses continued fraction representation to expose the private key d when d is small.

Background on RSA

Fictional characters Alice and Bob are people who want to communicate securely. More specifically, Alice wants to send a message to Bob which only Bob can read. First Bob chooses two secret primes p and q. Then he calculates the RSA modulus Template:Nowrap. This RSA modulus is made public together with the encryption exponent e. N and e form the public key pair Template:Nowrap. By making this information public, anyone can encrypt messages to Bob. The decryption exponent d satisfies Template:Nowrap, where λ(N) denotes the Carmichael function, though sometimes φ(N), the Euler's totient function, is used (note: this is the order of the multiplicative group (ZTemplate:Px2/Template:Px2NZ)^×, which is not necessarily a cyclic group). The encryption exponent e and λ(N) also must be relatively prime so that there is a modular inverse. The factorization of N and the private key d are kept secret, so that only Bob can decrypt the message. We denote the private key pair as Template:Nowrap. The encryption of the message M is given by Template:Nowrap and the decryption of cipher text C is given by Template:Nowrap (using Fermat's little theorem).

Using the Euclidean algorithm, one can efficiently recover the secret key d if one knows the factorization of N. By having the secret key d, one can efficiently factor the modulus of N.

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 Template:Nowrap.

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 Template:Nowrap for some large of k. When e′ is large enough, i.e. Template:Nowrap, 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 Template:Nowrap and Template:Nowrap are small but d itself is not, then a fast decryption of C can be done as follows:

1. First compute Template:Nowrap and Template:Nowrap.
2. Use the Chinese remainder theorem to compute the unique value of Template:Nowrap that satisfies Template:Nowrap and Template:Nowrap. The result of M satisfies Template:Nowrap as needed. The point is that Wiener's attack does not apply here because the value of Template:Nowrap can be large.Template:Cn

How the attack works

Note that

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

where Template:Nowrap.

Since Template:Nowrap, there exists an integer K such that

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

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

Defining Template:Nowrap and Template:Nowrap, and substituting into the above gives:

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

Divided by dpq:

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

So, Template:Sfrac is slightly smaller than Template:Sfrac, and the former is composed entirely of public information. However, a method of checkingTemplate:Clarify and guess is still required.

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

Wiener's theorem

Let Template:Nowrap with Template:Nowrap. Let Template:Nowrap.

Given Template:Nowrap with Template:Nowrap, the attacker can efficiently recover d.Template:Failed verification

Example

Template:Confusing Suppose that the public keys are Template:Nowrap. 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 Template:Sfrac. Note that this algorithm finds fractions in their lowest terms. We know that

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

According to the continued fractions expansion of Template:Sfrac, all convergents Template:Sfrac are:

$\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 Template:Sfrac yields

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

Now, if we solve the equation

$x^2-((N-\phi (N))+1)x+N=0$

$x^2-((90581-89964)+1)x+90581=0$

$x^2-618x+90581=0$

then we find the roots which are Template:Nowrap. Therefore we have found the factorization

$N=90581=379\times 239=p\times q$.

Notice that, for the modulus Template:Nowrap, Wiener's theorem will work if

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

Proof of Wiener's theorem

The proof is based on approximations using continued fractions.

Since Template:Nowrap, there exists a k such that Template:Nowrap. Therefore

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

Let Template:Nowrap; note that if φ(N) is used instead of λ(N), then the proof can be replaced with Template:Nowrap and φ(N) replaced with λ(N).

Then multiplying by Template:Sfrac,

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

Hence, Template:Sfrac is an approximation of Template:Sfrac. Although the attacker does not know φ(N), he may use N to approximate it. Indeed, since Template:Nowrap and Template:Nowrap, we have:

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

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

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

$\begin{array}{cc}|\frac{e}{N}-\frac{k}{Gd}|& =\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, Template:Nowrap, so Template:Nowrap. Since Template:Nowrap, so Template:Nowrap, then we obtain:

$k\lambda (N)<\lambda (N)d$

$k<d$

Since Template:Nowrap and Template:Nowrap. Hence we obtain:

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

Since Template:Nowrap, Template:Nowrap, then Template:Nowrap, we obtain:

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

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

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

If Template:Nowrap, then Template:Sfrac is a convergent of x, thus Template:Sfrac appears among the convergents of Template:Sfrac. Therefore the algorithm will indeed eventually find Template:Sfrac.

Further reading

• Coppersmith, Don (1996). Low-Exponent RSA with Related Messages. Springer-Verlag Berlin Heidelberg.

• Template:Cite arXiv
• Template:Cite journal
• Python Implementation of Wiener's Attack.
• Template:Cite book