# how to use common modulus attack?

I am struck with the following problem:

Let Alice, Bob, Chris and Eve communicate over a public network. They encrypt all messages they send using RSA system. Bob and Chris have the RSA modulus $$n_B$$ and $$n_C$$ respectively with $$n_B$$ = $$n_C$$ But different public encryption exponents: $$e_B \neq e_C$$. Suppose $$\gcd(e_B, e_C)=1$$, and that Alice sends the same secret message to Bob and Chris.

Show how Eve can decipher the message.

• The question assumes that Alice, Bob and Chris are using raw/textbook RSA, rather than RSA with random padding or hybrid encryption, as they should; therefore, Eve can verify a guess of a message sent by Alice to Bob, e.g. tell if it is head or tail; this fails modern security definition. Independently: Chris can factor his modulus, and since that the same as Bob's, Chris can find Bob's private key (or an equivalent), and decipher messages intended to Bob only, another disaster. – fgrieu Apr 14 '16 at 11:35

## 1 Answer

Think about this: what does it mean that $\gcd(e_B, e_C)=1$. Formally that means there exist some $s_1, s_2$ such that $e_Bs_1 + e_Cs_2=1$.

Say you have two ciphertexts (the following math is all done modulo the shared modulus), $C_B=M^{e_B}$ and $C_C=M^{e_C}$. You can do the following:

\begin{align} C_B^{s_1}*C_C^{s_2}&=(M^{e_B})^{s_1}*(M^{e_C})^{s_2}\\ &=M^{e_Bs_1}*M^{e_Cs_2}\\ &=M^{e_Bs_1+e_Cs_2}\\ &=M^1\\ &=M \end{align}

• @mikeazo thanks..this helps to solve my problem..and this is not homework kind of question..i found this problem in an examination paper & i was just curious about it. – Shankha Jana May 21 '14 at 12:36
• @ShankhaJana Since you found it on an examination paper, you should specify that in the question and give credit to the source. – mikeazo May 29 '14 at 12:33
• @mikeazo how did you move to the 2nd step where M^e^s1 became M^e*s1 – Scarl May 30 '14 at 13:31
• @Sara, that is just algebra. Maybe I should have put parenthesis to make it more clear what was going on . I'll update. – mikeazo May 30 '14 at 13:47
• @Sara The ciphertext is raised to the $s_1$ and $s_2$ respectively, which multiplies in the exponent. – mikeazo May 30 '14 at 14:54