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.

  • $\begingroup$ 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. $\endgroup$ – 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}$$

  • $\begingroup$ @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. $\endgroup$ – Shankha Jana May 21 '14 at 12:36
  • 1
    $\begingroup$ @ShankhaJana Since you found it on an examination paper, you should specify that in the question and give credit to the source. $\endgroup$ – mikeazo May 29 '14 at 12:33
  • $\begingroup$ @mikeazo how did you move to the 2nd step where M^e^s1 became M^e*s1 $\endgroup$ – Scarl May 30 '14 at 13:31
  • 1
    $\begingroup$ @Sara, that is just algebra. Maybe I should have put parenthesis to make it more clear what was going on . I'll update. $\endgroup$ – mikeazo May 30 '14 at 13:47
  • 1
    $\begingroup$ @Sara The ciphertext is raised to the $s_1$ and $s_2$ respectively, which multiplies in the exponent. $\endgroup$ – mikeazo May 30 '14 at 14:54

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.