Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Show that if the encryption exponent $3$ is used for the RSA cryptosystem by three different people with different moduli, a plaintext message $P$ encrypted using each of their keys can be recovered from these resulting three ciphertext messages.

Proof. We have $$x_1\equiv P^3\pmod{n_1},$$ $$x_2\equiv P^3\pmod{n_2},$$ $$x_3\equiv P^3\pmod{n_3},$$ and using the Chinese Remainder Theorem, we can get $$P^3\equiv x_1(n_2n_3)(n_2n_3)^{-1}+x_2(n_1n_3)(n_1n_3)^{-1}+x_3(n_1n_2)(n_1n_2)^{-1}\pmod{n_1n_2n_3}.$$ Therefore, $P$ can be found by testing all cubes that satisfy this congruence. $\square$

Does this proof seem rigorous enough, or should I step it up one more notch and compute for $P$? Or is perhaps the exercise asking for something else? What do you guys think? Thanks in advance!

share|improve this question
    
How do you find all cubes which satisfy this congruence? And why do you think that solving $P^3=junk (\mod n_1n_2n_3)$ is easier than solving $P^3 = x_1 (\mod n_1)$, which usually takes too long? The problem probably asks you to recover $P$ without solving the cubic.... –  N. S. Mar 25 '12 at 21:18

2 Answers 2

up vote 1 down vote accepted

The basic idea is that by the configuration of RSA you know that $0 < P^3 < N_1 N_2 N_3$. But also by the Chinese remainder theorem you are guaranteed a unique solution $p$ to the congruences, with $p$ lying between $1$ and $N_1 N_2 N_3 - 1$.

Thus these numbers coincide (i.e. $P^3 = p$) and we get equality, not just congruence. This enables you to then take the cube root and regain the plaintext $P$.

The point of this question is to show you that sometimes in RSA we can avoid guesswork/brute force and if you fall into certain traps then the system is totally insecure.

share|improve this answer
    
I should add that you assumed the moduli to be coprime in using CRT. It is clear how you might use Euclids algorithm to treat the other case. –  fretty Mar 25 '12 at 23:27

Let $n_1$ be the smallest modulus and $n_3$ the largest. Then $P < n_1$ and thus $$P^3 < n_1 n_2 n_3$$. This enables you to solve the system

$$P^3=z_i n_i+x_i,\quad i=1,2,3$$

uniquely for $z_i$ over integers [just take the three pairwise differences and use knowledge that $z_i$ lie in $[1,\ldots,n_j n_k]$ and this should work I think. Then obtain $P^3$ and take integer cube root.

Edit: Use binary search with complexity at most $$c \log(n_2 n_3) \leq 2c \log(n_3) =O(\log n_3).$$ The cube root complexity should also be comparable.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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