Prerequisites:
- RSA encryption/decryption
- Continued Fractions --> Read only basic intro to get an idea of what are continued fractions and also about Infinite Continued Fractions to get a basic idea of convergents
Wiener's Attack is based on the vulnerability that when d < N0.25, then one of the convergents of Continued Fraction of e/N is k/d where k satisfies this equation: 
. This equation is derived from: 
. We will see what exactly does the above statement mean and also see its proof in this write-up. To understand the statement above, it is essential to understand what are continued fractions and the concept of convergents in infinite fractions. Considering the reader has read it using the link provided in the Prerequisites section, we will discuss why convergents are important by understanding how the attack works.
Let N = pq with q < p < 2q. Let 
. Then given (e, n), the attacker can efficiently recover d.
- Store the convergents of continued fraction of e/n in a list
- Iterate over each element in the list
- For each iteration assign the denominator of the convergent as
d - Decrypt the ciphertext using the value of decryption key exponent found
- If the ciphertext decrypts to some meaningful value then break the loop and print the message
The public key pair (e, n) has value (17993, 90581). We should determine d with the help of the above attack.
- Find the continued fraction expansion of
e/N
- Thus, the convergents are:
- We can iterate over the convergents and check if the denominators of any of them is
dor not. To check it for each iteration, we must do the following: Take an arbitrary message M, encrypt it using (e, n) to give c. Now check if cd mod n equals M or not. If not, move on to next iteration but if they match then the corresponding denominator of the convergent is ourd. For our example, d is 5 which is in fact the denominator of the first convergent.
You can find an implementation of this attack written in sage/python here