The Wiener's attack, named after cryptologist Michael J. Wiener, is a type of cryptographic attack against RSA. The attack uses the continued fraction method to expose the private key d when d is small.
Contents
Background on RSA
Before we discuss how Wiener's attack works, we will first briefly explain how RSA works. For more details see the main entry on the RSA cryptosystem.
Let Alice and Bob be two 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 primes p and q. Then he calculates the RSA modulus N = pq. This RSA modulus is made public together with the encryption exponent e. N and e form the public key pair (e,N). By making this information public, anyone can encrypt messages to Bob. The decryption exponent d satisfies
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
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
Using the Chinese Remainder Theorem: Suppose one chooses d such that both
1. First compute
2. Use the Chinese Remainder Theorem to compute the unique value of
How Wiener's attack works
Since
there exists an integer K such that
Define
Defining
Divided by
So,
By using simple algebraic manipulations and identities, a guess can be checked for accuracy.
Wiener's theorem
Let
Given
Example
Suppose that the public keys are
The attack shall determine
By using Wiener's Theorem and continued fractions to approximate
According to the continued fractions expansion of
We can verify that the first convergent does not produce a factorization of
Now, if we solve the equation
then we find the roots which are
Notice that, for the modulus
Proof of Wiener's theorem
The proof is based on approximations using continued fractions.
Since
Hence,
Using
Now,
Since
Since
From (1) and (2), we can conclude that
It is a theorem that if the condition above is satisfied, then