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.
Background on RSA
editFictional 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 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 ed ≡ 1 (mod
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.[1]
Small private key
editIn 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 N1/4.[2]
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 ⋅
Using the Chinese remainder theorem: Suppose one chooses d such that both dp ≡ d (mod (p − 1)) and dq ≡ d (mod (q − 1)) are small but d itself is not, then a fast decryption of C can be done as follows:
- First compute Mp ≡ Cdp (mod p) and Mq ≡ Cdq (mod q.
- Use the Chinese remainder theorem to compute the unique value of 0 ≤ M < N that satisfies M ≡ Mp (mod p) and M ≡ Mq (mod q. The result of M satisfies M ≡ Cd (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.[3]
How the attack works
editNote that
where G = gcd(p − 1, q − 1).
Since ed ≡ 1 (mod
Defining k = K/gcd(K, G) and g = G/gcd(K, G), and substituting into the above gives:
- .
Divided by dpq:
- , where .
So, e/pq is slightly smaller than k/dg, and the former is composed entirely of public information. However, a method of checking[clarification needed] and guess is still required.
By using simple algebraic manipulations and identities, a guess can be checked for accuracy.[1]
Wiener's theorem
editLet N = pq with q < p < 2q. Let d < 1/3 N1/4.
Given ⟨N, e⟩ with ed ≡ 1 (mod
Example
editThis section may be confusing or unclear to readers. In particular, it assumes ed ≡ 1 (mod |
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
According to the continued fractions expansion of e/N, all convergents k/d are:
We can verify that the first convergent does not produce a factorization of N. However, the convergent 1/5 yields
Now, if we solve the equation
then we find the roots which are x = 379; 239. Therefore we have found the factorization
- .
Notice that, for the modulus N = 90581, Wiener's theorem will work if
- .
Proof of Wiener's theorem
editThe proof is based on approximations using continued fractions.[2][4]
Since ed = 1 (mod
- .
Let G = gcd(p − 1, q − 1); note that if
Then multiplying by 1/G,
Hence, k/Gd is an approximation of e/
Using N in place of
Now, k
Since k < d and d < 1/3 N1/4. Hence we obtain:
- (1)
Since d < 1/3 N1/4, 2d < 3d, then 2d < 3d < N1/4, we obtain:
- , so (2)
From (1) and (2), we can conclude that
If |x − a/b| < 1/2b2, 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.[further explanation needed]
References
edit- ^ a b L. Render, Elaine (2007). Wiener's Attack on Short Secret Exponents.[dead link]
- ^ a b c Boneh, Dan (1999). Twenty Years of attacks on the RSA Cryptosystem. Notices of the American Mathematical Society (AMS) 46 (2).
- ^ Cui, Xiao-lei (2005). Attacks On the RSA Cryptosystem.
- ^ Salah, Imad Khaled; Darwish, Abdullah; Oqeili, Saleh (2006). "Mathematical Attacks on RSA Cryptosystem" (PDF). Journal of Computer Science. 2 (8): 665–671. doi:10.3844/jcssp.2006.665.671.
Further reading
edit- Dujella, Andrej (2004). Continued Fractions and RSA with Small Secret Exponent.
- Wiener, Michael J. (1990). "Cryptanalysis of short RSA secret exponents". Transactions on Information Theory. 36 (3). IEEE: 553–558. doi:10.1109/18.54902. Retrieved 2024-03-09.
- Python Implementation of Wiener's Attack.
- R. Stinson, Douglas (2002). Cryptography Theory and Practice (2e ed.). A CRC Press Company. pp. 200–204. ISBN 1-58488-206-9.