RSA, cryptography

Question

Consider the RSA system with $n=55$ and $e=17$, where $e$ is the encryption key. Now encrypting $9$ gives

$c_1 = 9^e = 4$ mod $5$

$c_2 = 9^e = 4$ mod $11$.

Using the Chinese Remainder Theorem I get $c=9^e$ = $4$ mod $55$. Now assume that there was a mistake in the computation of $9^e$ mod $5$ and you got $2$ instead of $4$. $(c_1' =9^e = 2)$

This will lead to $c' = 37$ mod $55$.

How can I find the factorisation of $n$ by knowing $c$ and $c'$?

I thought the Chinese Remainder Theorem might be helpful since we then have:

$a\cdot p \cdot c_2 + b \cdot q \cdot c_1 = 4$ mod $55$

$a\cdot p \cdot c_2 + b \cdot q \cdot c_1' = 37$ mod $55$

where $a,b$ are such that $a \cdot p + b \cdot q = 1$, and hence

$b \cdot q \cdot (c_1' - c_1) = 33$ mod $55$.

But here I don't know how to proceed. Thanks for any help.

Answer 1

In the way you have presented it, I don't think this is solvable. Unless the "mistake" in computation was done in a very specific way, I don't see how a wrong computation could help you break RSA. Is this an exercise in a textbook? If so, could you post the exact text?

Answer 2

We know $c' = c$ mod $q$, therefore $c'-c = 0$ mod $q$. This means $c'-c$ is a multiple of $q$. Hence $gcd(c'-c,n)=q$

In our example $gcd(37-4,55) = gcd(33,55) = 11$