Question

Alice and her three friends are all users of the RSA cryptosystem. Her friends have public keys $\left(N_i,e_i=3\right)\mathbf{,}\mathbf{i}\mathbf{=}\mathbf{1}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{3}$ where as always,${\mathbf{N}}_{\mathbf{i}}\mathbf{=}{\mathbf{p}}_{\mathbf{i}}{\mathbf{q}}_{\mathbf{i}}$ for randomly chosen n-bit primes ${\mathbf{p}}_{\mathbf{i}}{\mathbf{q}}_{\mathbf{i}}$. Showthat if Alice sends the same n-bit message M (encrypted using RSA) to each of her friends, then anyone who intercepts all three encrypted messages will be able to efficiently recover M.
(Hint: It helps to have solved problem 1.37 first.)

Short answer

The plain text can be efficiently recovered when encrypted all messages M.

Step-by-step solution

Given data

Alice is sending the same message to all of her friends through RSA (Rivest-Shamir-Adleman)cryptosystem.

Public keys of her three friends are$\left({\mathrm{N}}_{\mathrm{i}},{\mathrm{e}}_{\mathrm{i}}\right)$ where $\mathrm{i}=1,2,3$.

The message is "MSG" and the size of message is "n-bit".

Explanation

The cyphertext of "${\mathrm{M}}_{\mathrm{i}}$" for "${\mathrm{e}}_{\mathrm{i}}=3$" (where,$\mathrm{i}=1,2,3$) can be written as follows:

${\mathrm{M}}_1={\mathrm{MSG}}^3\left(\mathrm{mod}{\mathrm{N}}_1\right)$

$$\begin{gathered} {\mathrm{M}}_2={\mathrm{MSG}}^3\left(\mathrm{mod}{\mathrm{N}}_2\right) \\ {\mathrm{M}}_3={\mathrm{MSG}}^3\left(\mathrm{mod}{\mathrm{N}}_3\right) \end{gathered}$$

Rearrange the above terms to find the "MSG" value. In the above terms, the "$\left(\mathrm{mod}\mathrm{N}\right)$" values are common for both left and right side of the equation. So, it can be placed at either left or right side of the equation.

Thus, the above terms can be rearranged as follows:

$$\begin{gathered} {\mathrm{M}}_1\mathrm{mod}{\mathrm{N}}_1={\mathrm{MSG}}^3 \\ {\mathrm{M}}_2\mathrm{mod}{\mathrm{N}}_2={\mathrm{MSG}}^3 \\ {\mathrm{M}}_3\mathrm{mod}{\mathrm{N}}_3={\mathrm{MSG}}^3 \end{gathered}$$

And the above can be written as follows:
$$\begin{gathered} {\mathrm{MSG}}^3={\mathrm{M}}_1\left(\mathrm{mod}{\mathrm{N}}_1\right) \\ {\mathrm{MSG}}^3={\mathrm{M}}_2\left(\mathrm{mod}{\mathrm{N}}_2\right) \\ {\mathrm{MSG}}^3={\mathrm{M}}_3\left(\mathrm{mod}{\mathrm{N}}_3\right) \end{gathered}$$

Here, if anyone intercepts all the three encrypted messages${\mathrm{M}}_1,{\mathrm{M}}_2,{\mathrm{M}}_3$ with the public
keys${\mathrm{N}}_1,{\mathrm{N}}_2,{\mathrm{N}}_3,\mathrm{e}$ then they can determine the original message "MSG" by using the

Chinese Remainder Theorem.

Therefore, the plain text can be efficiently recovered when someone intercepts all encrypted messages "M".