README.md

Franklin Reiter's Attack on related messages

Prerequisites:

1. RSA Encryption/Decryption
2. Coppersmith's Theorem

This attack works in a scenario where two messages differ only by a fixed known difference and are encrypted using public key e and same modulus N. The attacker can then recover the two messages in the above scenario using Franklin Reiter's Attack.

Theorem

Suppose there are two messages M₁ and M₂ where M₁ != M₂, both less than N and related to each other as for some linear polynomial where b!=0. These two messages are to be sent by encrypting using the public key (N, e), thus giving ciphertexts C₁ and C₂ respectively. Then, given (N, e, C₁, C₂, f), the attacker can recover messages M₁ and M₂.

Proof

We can write C₁ and C₂ as:

We can also write,


We can then write the polynomials g₁(x) and g₂(x) as:


So clearly M₂ is a root of both the polynomials above and hence they have a common factor x-M₂ (Since, g₁(M₂) = 0 and g₂(M₂) = 0) Therefore, we can simply calculate GCD of g₁ and g₂ and if the resultant polynomial is linear, then we get out M₂ and hence M₁!

Exploit in a nutshell:
1. Calculate g1 and g2 as given above
2. Calculate GCD(g1, g2) and check if the resultant polynomial is linear or not
3. If the resultant polynomial is linear, then return GCD

Check the implementation of the above attack here

References

1. Wikipedia- Franklin Reiter's related message attack