# 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

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}
• @Sara The ciphertext is raised to the $s_1$ and $s_2$ respectively, which multiplies in the exponent. May 30 '14 at 14:54