What to do when the same message is encrypted twice with the same modulus but a different public key?
Imagine we have Alice and Bob. Alice sends the SAME message to Bob more than once using the same public key. The internet being the internet, a problem may happen; a bit is flipped, and the public key changed while the modulus stayed the same.
Let be the following:
m the message in plaintext
e1 the public key of the first ciphertext
c1 the first ciphertext
e2 the public key of the second ciphertext
c2 the second ciphertext
n the modulus that is common to both ciphertexts
All of these but m are essentially given to us.
Because we are going to need to calculate inverses for this attack, we must first make sure that these inverses exist in the first place:
We know that RSA goes as follows:
Now to truly recover the plaintext, we are actually doing:
From the conditions above we also know that and are co-prime. Thus using Bezout's Theorem we can get:
Using this, we can derive the original message :
NB: all the calculations are done mod
In general, Bezout's Theorem gives a pair of positive and negative numbers. We just need to adapt this equation a little to make it work for us. In this case, let's assume is the negative number: