RSA encryption decryption

Question

I'm trying decrypt an RSA encryption system $\psi:\mathbb{Z_n}\rightarrow\mathbb{Z_n}$ where $n = 18721, e_1 = 43, e_2 = 7717, m^{e_1} = 12677, m^{e_2} = 14702$.

I know that the encryption works the following way: you choose an $e$, s.t. $0 < e < \phi(n)$ where $\phi$ is the Euler totient function. Then you compute $d = \gcd(e, \phi(n))$. Then we have $e^{-1} = d \mod \phi(n)$.

To encrypt the message $m$ I compute: $c = m^e \mod n$

And the decryption is done: $m = c^d \mod n$

So my question now is. Why do I need TWO encrypted messages to find $m$ (that's actually the task in my exercise)? Can I not just find $d_1$ and $d_2$ (since I know $e_1$, $e_2$ and $n$) to decrypt $m^{e_1}$ and $m^{e_2}$?

Thanks for your answers.

Answer 1

You can use the two values supplied to recover $m$ without factoring $n$, in a parallel process to an extended euclidean analysis, getting modular inverses to $18721$.

All $\bmod 18721$:

$\begin{align} m^{7717} &\equiv 14702 \\ m^{43} &\equiv 12677 \\ \implies (m^{43})^{179} \equiv m^{7697} & \equiv 907\\ m^{-7697} &\equiv 12971\\ m^{7717-7697} = m^{20} &\equiv 14702 \cdot 12971 \equiv 2555\\ \implies (m^{20})^{2} \equiv m^{40} & \equiv 13117\\ m^{-40} &\equiv 14916\\ m^{43-40} = m^{3} &\equiv 12677 \cdot 14916 \equiv 8032\\ \implies (m^{3})^{6} \equiv m^{18} & \equiv 14461\\ m^{-18} &\equiv 7651\\ m^{20-18} = m^{2} &\equiv 2555 \cdot 7651\equiv 3581\\ m^{-2} &\equiv 15532\\ m^{3-2} = \color{#FF33FF}m &\equiv 8032\cdot 15532\equiv \color{#FF33FF}{\fbox{15001 }}\\ \\\end{align}$

---

Edit: Of course there is a cleaner way to the same end... Run a normal extended Euclidean process to find Bézout's identity for $7717$ and $43$:

$\begin{array}{c|c} n & s & t & q \\ \hline 7717 & 1 & 0 & \\ 43 & 0 & 1 & 179 \\ 20 & 1 & -179 & 2 \\ 3 & -2 & 359 & 6 \\ 2 & 13 & -2333 & 1 \\ 1 & -15 & 2692 & 2 \\ \end{array}$

Then $\fbox{$1=(-15)\cdot 7717 + 2692\cdot 43$ }$, and$\bmod 18721$:

$\begin{align} (m^{7717})^{15} &\equiv 14702^{15} \equiv 3947 \\ (m^{7717})^{-15} &\equiv 3947^{-1} \equiv 5668 \\ (m^{43})^{2692} &\equiv 12677^{2692} \equiv 13145 \\ (m^{7717})^{-15}\cdot (m^{43})^{2692} \equiv m^{(-15)\cdot 7717 + 2692\cdot 43}\equiv \color{#FF33FF}m & \equiv 5668\cdot 13145 \equiv \color{#FF33FF}{\fbox{15001 }}\\ \end{align}$

Answer 2

You are right with the double $15001,$ I had a typo in my first version (instead $12667$ of $12677$). Now the computation is as follows. You have $n=18721=97\times 193,\;\phi(n)=96\times 192 =18432$. Then $$d_1 \equiv 43^{-1} \equiv 9859 \pmod {18432} $$ $$d_2 \equiv 7717^{-1} \equiv 13741 \pmod {18432} $$ $$12677^{d_1} \equiv 15001 \pmod n$$ $$14702^{d_2} \equiv 15001 \pmod n$$

Answer 3

Step 1: find $k,m \in \mathbb{Z}$ such that $7717k+ 43m = 1$, which can be done as $\gcd(e_1,e_2) = \gcd(43, 7717) =1$. (Bezout identity) Follow the extended Euclidean algorithm.

Then $$m = m^1 = m^{ 7717k+ 43m } = (m^{e_2})^k (m^{e_1})^m \pmod {n}$$

where $m^{e_1} \pmod{n}$ and $m^{e_2} \pmod{n}$ have been given, and you know $k,m$ from step 1.