RSA Ciphertext Message.

Question

Hey I'm really stuck and I have to finish soon.

Part A

Ray, Sam and Todd are lazy, and they have set up their RSA public keys as $(3,nR),(3,nS),(3,nT)$ respectively. We may assume that any two of $nR,nS,nT$ are coprime. Zach encrypted a message $M$ using each of the three keys, producing the ciphertexts $CR,CS,CT$ for Ray, Sam and Todd respectively. Note that we must have: $0 ≤ M ≤ \mathrm{min} \{nR,nS,nT\}$

Prove that if one obtains the values of $CR,CS,CT$,then the message $M$ can be determined.

Part B

Suppose $nR = 7729,nS = 8023,nT = 8383$, and you have found out that $CR = 2553,CS = 5337,CT = 4156$. Use what you have learned from part (a) to solve for $M$. (Do not factor the public keys, show the set up of the calculations and the results.)

Answer 1

As the comments show, your notation is slightly suboptimal; I will use a more standard one.

Part A: Because the $N_k$ are pair-wise coprime it follows from the Chinese Remainder Theorem that $$C_R \equiv M^3 \pmod {N_R}$$ $$C_S \equiv M^3 \pmod {N_S}$$ $$C_T \equiv M^3 \pmod {N_T}$$ has a solution $C$ with $C \equiv M^3 \pmod {N_R N_S N_T}$. Since $M<N_k\;$ we have $M^3 < N_R N_S N_T\;$ and can we compute $M = C^{\frac{1}{3}}\;$ without modular arithmetic.

Part B: With the given values solve the CRT system

x=2553 mod 7729
x=5337 mod 8023
x=4156 mod 8383

and get $x=C=2460375\;$ and $M=C^{\frac{1}{3}} = 135.\;$ It is easy to check that

135^3 mod 7729 = 2553
135^3 mod 8023 = 5337
135^3 mod 8383 = 4156

Note that this is a simple case of Hastad's Broadcast Attack on plain RSA.