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?

  • $\begingroup$ 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. $\endgroup$ – Henning Makholm Dec 18 '13 at 20:55
  • $\begingroup$ 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? $\endgroup$ – unterbrause Dec 18 '13 at 21:49

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.


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.