Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
up vote 9 down vote accepted

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

share|improve this answer
    
@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
1  
@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
1  
@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
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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