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^{1} 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. 🙂

### Like this:

Like Loading...

## Published by 4lph4

Halo!! Ich heiβe Sowmya. Ich bin studentin an der Amrita Universitat. Ich mache Kryptographie. Ich bin teil von Team Bi0s. Dieser Blog ist für Crypto-Attacken erlernt und Herausforderungen gelöst. Danke :)
View all posts by 4lph4