# Find the RSA factorization

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?

• What do you mean "how can I factor $n$"? You already factored $n=55$ when you computed $\varphi(55)=40$, and the value of $n$ doesn't change, so there's no need to factor it again. – Henning Makholm Dec 18 '13 at 20:55
• Okay it's written this way: How can Eve find the factorization of n knowing c and k only? I think it's just refering to when one knows c and k (???and maybe that the computer made the mistake listed above???) only. So from the theoretical Point of view... derive how to factor now.... of course 55=11*5 and that's easy. But the Point is from this c and k on... Do you understand the task? – unterbrause Dec 18 '13 at 21:49

• 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!