# Decrypting a Message Encrypted in RSA Using Two Coprime Encryption Keys

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?

-
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é 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é May 6 '12 at 2:53
@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

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$?
I ended up with $P\equiv C_1^s\cdot C_2^t$. –  Josué 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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 2, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.957257866859436, "perplexity": 417.3702410836592}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2015-35/segments/1440645293619.80/warc/CC-MAIN-20150827031453-00117-ip-10-171-96-226.ec2.internal.warc.gz"}