25.10.15

The RSA Problem

Back in university I stumbled upon a problem that sparked my curiosity, which lead to the Mathematics section of this blog. The problem was a part of my last assignment for one of my favourite Computing Science classes. Here's the problem:

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?'