The attack uses continued fraction representation to expose the private key d when d is small.
The decryption exponent d satisfies ed ≡ 1 (mod λ(N)), 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 (Z/NZ)×, which is not necessarily a cyclic group).
The factorization of N and the private key d are kept secret, so that only Bob can decrypt the message.
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] 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.
Since ed ≡ 1 (mod λ(N)), there exists an integer K such that Defining k = K/gcd(K, G) and g = G/gcd(K, G), and substituting into the above gives: Divided by dpq: So, e/pq is slightly smaller than k/dg, and the former is composed entirely of public information.
Given ⟨N, e⟩ with ed ≡ 1 (mod λ(N)), the attacker can efficiently recover d.[2][failed verification] Suppose that the public keys are ⟨N, e⟩ = ⟨90581, 17993⟩.
Therefore we have found the factorization Notice that, for the modulus N = 90581, Wiener's theorem will work if The proof is based on approximations using continued fractions.