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 primesp and q. Then he calculates the RSA modulusN = 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 , where , is Euler’s phi function (note: this is the order of the multiplicative group). The encryption exponent e and 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 (d, N). The encryption of the message M is given by and the decryption of cipher text is given by (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.
In the RSA Cryptosystem, Bob might tend to use a small value of d, rather than a large random number to improve the RSAdecryption 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 by , where for some large of . When is large enough, i.e. , then Wiener’s attack can not be applied regardless of how small is.
1. First compute and .
2. Use the Chinese Remainder Theorem to compute the unique value of which satisfies and . The result of satisfies as needed. The point is that Wiener’s attack does not apply here because the value of can be large. 
Define to be substituted in the equation above which gives:
Defining and , and substituting into the above gives:
Divided by :
, where .
So, is slightly smaller than , and the former is composed entirely of public information. However, a method of checking a guess is still required. Assuming that (a reasonable assumption unless is large) the last equation above may be written as:
Suppose that the public keys are
The attack shall determine .
By using Wiener's Theorem and continued fractions to approximate , first we try to find the continued fractions expansion of . Note that this algorithm finds fractions in their lowest terms. We know that