Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

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
    
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 at 11:35
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.