**Bob wants to send Alice a secret message using the RSA encryption algorithm. Bob's message m is 88 and he encrypts it using Alice's public key, which is (n, e) = (4699, 1171), to obtain a ciphertext c. If the ciphertext is c = 3908, then what is Bob's message m?**

**The plaintext can be obtained by obtaining Alice's private key, which is easy to obtain because it is possible to factor 4699 in polynomial time to find phi(n). Let's assume though that only Alice knows the two primes p and q that 4699 is made of and 4699 can't be factored in polynomial time.**

Alice 's private key d₁ can be computed using phi(n)

Alice computes phi(n) = phi(p)*phi(q) = (127-1)*(37-1) = 4536

Alice's private key d₁ is ed₁ ≡ 1 mod 4536 which is 1171d₁ ≡ 1 mod 4536

because 1171d₁ + 4536y₁ = 1 for some d₁, y₁ in Z

=> d₁ = 1747 because 1171*1747+4536*(-451) = 1 in Z

Since c = 3908 then m ≡ 3908¹⁷⁴⁷ mod 4699 ≡ 88 mod 4699

This was the answer that the TA was expecting to see, which is why he was blown away when he saw this instead:

*Eve computes a private key d₂ by overcounting exactly 3 times*

*d₂ = 235 because 1171*235+3276*(-84) = 1 in Z*

*Since c = 3908 then m ≡ 3908²³⁵ mod 4699 ≡ 88 mod 4699*

The second key d₂ is a number that's 7 times less than the TA's key! As far as the TA was concerned there is only one decryption key, namely d₁ = 1747, and he naturally had a marking meltdown on my assignment.

But there are even more keys that decrypt the cipher text. For example, 504, 546, 702, 756 also decrypt the message in this example and so a pattern emerges. It can be verified that all combinations of 2ʳ x 3ˢ x 7ᵗ , 2ʳ x 3ˢ x 13ᵘ, 2ʳ x 3ˢ x 7ᵗ x 13ᵘ where 0 < r, s, t < 5 and u = 1 among others produce private keys, which can be used to decrypt the ciphertext c in this example even though these keys are not the same as the one generated with phi(n).

Generally speaking, when n is the product of 2 distinct odd primes, then there will always be at least 1 extra private key, other than the private key generated using phi(n)

**So how can one find d₂, or rather, how can one find the other keys that decrypt c?'**