Find the RSA factorization

Question

I want to solve this exercise:

Assume you have to do with an RSA System whose public parameters are (n,e)=(55,17). Now you can compute d.

-->That's easy I've got d=33.

You know a computer uses CRT to encrypt the message 9. Instead of $k_1\equiv k$ mod 5 the computer calculates wrongly $k_1 \equiv 2$mod5. Now the wrongly decrypted message is k=37? How do you factor n using k and the a correct decrypted number $c\equiv9^{17} \equiv 4 \mod 55$?

.... Alright I got $\phi(55)=40$ and using the CRT isomorphism and Fermat's Little Theorem I have

$\mathbb{Z}_{55} \simeq \mathbb{Z}_5 \times \mathbb{Z}_{11}$

$9\equiv4 \mod5$ ; $9 \equiv 9 \mod 17$ and

$17 \equiv 1 \mod 4=\phi(5)$ ; $17 \equiv 7 \mod 10 =\phi(11)$

So $9^{17} $ corresponds to $(4^{17},9^{17})=(4^{1},9^{7})=(4,4)$ That's why c=4 . So if one has $9^{17}$ corresponds (wrongly ...this is the mistake the computer makes) to $(2^{17},9^7)=(2^{1},9^7)=(2,4)$ we have to solve the equivalence equation

$k=2 \mod 5$ and $k=4 \mod 11$. I solve it by $1=11+(-2)*5$ which gives me a $k=22-40\equiv 37 \mod 55$

Now how can I factor n? I don't know how to do this? Does anyone of you know how I can factor n now?

Answer 1

If I understood the description correctly, what happens looks as follows (I took the liberty of changing some of the letters, hopefully for better clarity):

• Computer attempts to encrypt the number $m=9$ using $(n,e)$. In other words, it tries to calculate $c=9^{17}\bmod 55=4$.
• The intended mode of operation consists of calculating $m_1=(9\bmod 5)=4$ and $m_2=(9\bmod 11)=9$, raising them to $17$-th power separately and combining them using CRT into number $c$.
• Instead, a mistake happens and the calculation is performed with $m_1^* = 2$ and $m_2^*=m_2$, obtaining $c^*$ as a result.

Assuming that the attacker knows $n$, $c$ and $c^*$, our goal is to factor $n$. Let's summarize what we know about the numbers (with $p$ and $q$ being the two prime factors of $n$): $$\begin{eqnarray} c & \equiv & m_1^e\pmod p \\ c & \equiv & m_2^e\pmod q \\ c^* & \equiv & (m_1^*)^e\pmod p \\ c^* & \equiv & (m_2^*)^e \pmod q \\ \end{eqnarray}$$

Since $m_2=m_2^*$, we have $c\equiv c^*\pmod q$ and, at the same time, $m_1\not=m_1^*$, so $c\not\equiv c^*\pmod p$. Thus $(c-c^*)$ is divisible by $q$ but not $p$. But that's exactly what we're looking for! It's a number which has a non-trivial common factor with $n$; so we can compute $\gcd(n, c-c^*)$ to find it out!

Note that it didn't really matter what was the original number which was being encrypted, nor the exact nature of the error the computer made, as long as it only happened in one part of the CRT calculation but not in the other.