3.12.17

Proving The Existence Of A Second Private Key That Decrypts a Message Encrypted With The RSA Encryption Algorithm

While taking a course in cryptography 6 years ago I stumbled upon a problem that kept me awake at night for many nights.

In school we learn that the RSA encryption algorithm consists of one public key and one private key. I've asked several professors if there could be a second private key that decrypts all messages in the same way as the intended private key and I've always received a negative answer.

And yet I stumbled upon two private keys in one particular example. I delved into the Mathematics behind the RSA algorithm and I found out that in fact there are at least two keys in every single example. I not only managed to prove the existence of a second private key but I was also able to find two different formulas for obtaining the second key.

One of the formulas requires knowledge of phi(n)/2 where phi(n) is Euler's Totient Function.

If d1 is the intended private key and (n, e) is the public key then the second key d2 can be found using the following formula:

d2*e = phi(n)/2

Here's the full paper: https://marinaibrishimova.net/docs/otherkeys.pdf

Currently, I'm looking into ways of obtaining phi(n)/2 without having to factor n.