Common Modulus Attack

In this blog we are going to take a look at one of the popular attacks on RSA, Common Modulus Attack.

As the name suggests, this attack works when a common modulus but different encryption exponents such that their gcd is 1 are used. Let us consider a scenario for better understanding.

Person A wants to send a common message m to Person B1 and B2. She decides to use a common modulus n so that time and memory are not wasted on generating another large modulus. However, she uses different encryption exponents e1 and e2 such that gcd(e1,e2) = 1 and sends the encrypted messages c1 and c2.

So, how is the middle man going to use the scenario to decipher m??

As we know the gcd of e1 and e2 i.e 1, from extended euclidean theorem we know that there exists some constants a and b such that e1*a + e2*b = gcd(e1,e2) = 1. How are we going to use it?

Firstly, let us compute the ciphertexts c1 and c2

c1 = m^e1 mod n

c2 = m^e2 mod n

Now, calculate c1^a and c2^b where a, b are the constants from euclidean extended theorem and then calculate the product of c1^a and c2^b.

 c1^a * c2^b = (m^e1)^a * (m^e2)^b mod n

c1^a * c2^b = m^{e1*a + e2*b} mod n

From euclidean extended theorem we know that e1*a + e2*b = 1

 c1^a * c2^b = m¹ mod n
Therefore, c1^a * c2^b = m

Hence, calculating c1^a*c2^b gives our required message m. This attack allows the eavesdropper to find message m even without knowing the decryption key.

This is how Common Modulus Attack works. It’s end of the blog but not an end to RSA. 🙂

Advertisement