1
$\begingroup$

I am given 5 different encryption modulus, $N$, each ranging from 78 to 88 numbers long. Then for the encryption exponent, each has the same which is 5. Then I am given 5 different encrypted messages, $E$, which also ranges from 76 to 88 numbers long. I am trying to decrypt the message without having to discover the private key.

One way is to use the Chinese Remainder Theorem where we follow the procedure as follows: $x=E_i \mod R_i$ for $i=1,2,3,4,5$. So for $x$, I took all the combination for i and tried to decrypt it by taking the 5-th root of the solution I get for all the $x^\prime$s. However, this is not really working for me as for every solution I get for $x$, it is not possible to take the 5-th root without having decimal fraction.

Anyone who is familiar with the procedure I am taking about, could you tell me what I am doing wrong and possibly help me through this? Thanks in advance. The method I am using by the way is known as the common encryption exponent.

|improve this question
$\endgroup$
  • 2
    $\begingroup$ 1) Do the different encrypted messages correspond to the same plaintext? There is an attack if the same message is encryted to e different public keys, but not if those messages are different. 2) Do you use textbook RSA (no secure padding) or real RSA? The attack doesn't work if proper padding is used, since then you will never get identical padded plaintext messages. $\endgroup$ – CodesInChaos Oct 3 '13 at 19:28
  • $\begingroup$ Hint: if $x$ is the message that you want to know, what do you know about $y=x^5$? And if you knew $y$, how would you get $x$? $\endgroup$ – fgrieu Oct 3 '13 at 20:01
  • $\begingroup$ Is this homework by the way? Forgive me for asking but I had a similar assignment a few months back. If so, please edit your post to add the 'homework' tag. Cheers $\endgroup$ – rath Oct 3 '13 at 23:19
  • 1
    $\begingroup$ @rath The homework tag is rather discouraged. All the cool Stack Exchange sites have gotten rid of it. It is definitely not required. $\endgroup$ – Gilles 'SO- stop being evil' Oct 4 '13 at 11:13
  • $\begingroup$ Final hint: Generically, the CRT allows you to find $y\bmod (N1\cdot N2\cdot N3\cdot N4\cdot N5)$ knowing $y\bmod N1$, $y\bmod N2$, $y\bmod N3$, $y\bmod N4$, $y\bmod N5$ $\endgroup$ – fgrieu Oct 4 '13 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.