Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The last question of our number theory final review is as follows:

The same plaintext $P$ is encrypted in RSA using two coprime encryption keys $e_1$, $e_2$. Show how this message can be decrypted quickly if both ciphertexts $C_1$, $C_2$ are intercepted.

Hint: Bézout's identity.

I know the RSA cryptosystem has it that

$$\begin{align} C_1&\equiv P^{e_1}\pmod{n_1}\text{ and}\\ C_2&\equiv P^{e_2}\pmod{n_2}, \end{align}$$

where $n_1=p_1q_1$, $n_2=p_2q_2$, $(e_1,\varphi(n_1))=1$, and $(e_2,\varphi(n_2))=1$, for some large primes $p_1$, $q_1$, $p_2$, and $q_2$.

Since one does not have access to the secret keys $d_1$ and $d_2$, I assume Bézout's identity must play a big role here. However, the only place I can think of using it is with the encryption keys

$$\begin{align} 1&=e_1s_1+n_1t_1,\\ 1&=e_2s_2+n_2t_2,\text{ and}\\ 1&=e_1s_3+e_2t_3, \end{align}$$

for some integers $s_1$, $t_1$, $s_2$, $t_2$, $s_3$, and $t_3$.

Nevertheless, this is not very useful. What am I missing?

share|improve this question
    
Use the third one, relating $e_1$ and $e_2$. –  Ted May 6 '12 at 2:10
    
I suppose then that one can find the plaintext $P$ by multiplying $C_1$ by $(e_2t_3)/s_3$? Is it that simple? –  Josué Molina May 6 '12 at 2:33
    
Are you sure that two different moduli $n_1$ and $n_2$ are used? Perhaps you just have a single $n=pq$ used in both encryptions, so that $C_1 \equiv P^{e_1} \pmod{n}$ and $C_2 \equiv P^{e_2} \pmod{n}$. –  Jonas Kibelbek May 6 '12 at 2:47
    
@JonasKibelbek, the question doesn't specify that, but you could be right, and forgive my ignorance, but what difference would different moduli make? –  Josué Molina May 6 '12 at 2:53
1  
@JosuéMolina: The solution actually does not require taking roots modulo $n$. When you write $C_2^{t/s}$, it looks like you are asking for an $s$-th root modulo $n$. This is a problem, because if $(s,\varphi(n))\neq 1$, then not every residue class has a unique $s$-th root. Every residue class does have a unique $e_2$-th root, but finding it is very difficult in general-- this is the strength of RSA encryption. –  Jonas Kibelbek May 6 '12 at 3:27
show 1 more comment

1 Answer

up vote 2 down vote accepted

I suspect that the messages $C_1$ and $C_2$ were encrypted with the same modulus $n=pq$, even though different exponents $e_1$ and $e_2$ were used. Then we have $$C_1 \equiv P^{e_1} \pmod{n}$$ $$C_2 \equiv P^{e_2} \pmod{n}.$$ Further, we can find integers $s$ and $t$ such that $se_1+te_2 =1$.

Can you figure out how to obtain $P^{se_1+te_2} \pmod{n}$? Can you see why this idea works if the same modulus $n$ is used for both encryptions, but does not work if we have two different moduli $n_1$ and $n_2$?

share|improve this answer
1  
I ended up with $P\equiv C_1^s\cdot C_2^t$. –  Josué Molina May 6 '12 at 3:24
    
Yes, exactly. One of the integers $s$ and $t$ will be negative. So to calculate $P$, you will need to find an inverse of $C_1$ or of $C_2$ modulo $n$, do modular exponentiation, and multiply two numbers modulo $n$. All of these steps are very fast, so you have found an easy way to calculate $P$. –  Jonas Kibelbek May 6 '12 at 3:31
add comment

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.