1
$\begingroup$

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.)

$\endgroup$
6
  • $\begingroup$ Given that $n$ divides each of $nR,nS,nT$, we get $n=1$. Maybe we assume $R,S,T$ are coprime? $\endgroup$ Mar 19, 2014 at 6:51
  • $\begingroup$ How did we get n divides nR,nS,nT? $\endgroup$
    – user136088
    Mar 19, 2014 at 6:59
  • $\begingroup$ Does $nR$ not mean $n\cdot R$? $\endgroup$ Mar 19, 2014 at 7:03
  • $\begingroup$ @user136088 if $R$ is an integer, then $\frac{nR}{n}=R$ which as we just said was an integer. Likewise for the rest. $\endgroup$
    – Guy
    Mar 19, 2014 at 7:04
  • $\begingroup$ Im not sure but if nR means n*R does that make it easier? $\endgroup$
    – user136088
    Mar 19, 2014 at 7:13

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.