Take the 2-minute tour ×
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.

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
    
Didn't realize RSA had this property. Even though this is a low effort question, +1 for making be learn something new. –  CodesInChaos May 20 at 18:31
1  
This is not a homework-answering or exercise-solving service. We want to help you, but we can't do that if you haven't shown us what you have tried. So, I suggest you edit the question to show us what you have tried and where you got stuck. Finally, make sure you give proper attribution to the source where you copied this from. –  D.W. May 22 at 22:47

1 Answer 1

up vote 6 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 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 at 12:33
    
@mikeazo how did you move to the 2nd step where M^e^s1 became M^e*s1 –  Sara May 30 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 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 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.