16
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 3
    $\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, 2016 at 11:35

1 Answer 1

Reset to default
23
$\begingroup$

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}$$

Improve this answer
$\endgroup$
7
  • $\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, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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