1
$\begingroup$

I am learning for the exam in cryptography and I have found an assignment about the common protocol failure in RSA.

Assignment:

Suppose Bob uses an RSA cryptosystem with modulus $n$ and encryption
exponent $e_1$, and Charlie uses an RSA cryptosystem with the same modulus n and encryption exponent $e_2$ , where the greatest common divisor of $e_1$ and $e_2$ is 1. If Alice encrypts the same plaintext m to send to both Bob and Charlie, she computes $c_1=m^{e1} \mod n$ and $c_2=m^{e2} \mod n$, and sends $c_1$ to Bob and $c_2$ to Charlie. Suppose Oscar intercepts $c_1$ and $c_2$, and computes as follows:

$f=e_1^{−1} \mod e_2$

$g=(f ∗ e_1 − 1)/e_2$

$h=c_1^{f}∗(c_2^g)^{−1} \mod n$

(a) Prove that $h = m$, thus Oscar can decrypt the message Alice sent without knowing the private keys of Bob or Charlie.

(b) Illustrate the attack for $n=18721$, $e_1=43$, $e_2=7717$ , $c_1=12677$ and $c_2=14702$.

No I try to prove it:

$h=c_1^f*(c_2^g)^{-1} \mod n$

$h = m^{e_1f}*(m^{e_2g})^{-1} \mod n$

$h=m^{e_1(e_1^{-1} \mod e_2)} * m^{-e_2(((e_1^{-1} \mod e_2)*e_1-1)/e_2)}$

But now I got stuck. Maybe I don't have to expand $f$ and $g$. I also found a useful site on this problem, but there it is not clear why $m^{e_1f - e_2g} = m$.

RSA common modulus failure

I also found some interesting questions and answers here on this site, but they do not explain me the steps I need.

Maybe someone can help me here.

$\endgroup$
  • $\begingroup$ What is done there with the $e$s kinda smells like the chinese remainder theorem. $\endgroup$ – SEJPM Jun 28 '17 at 18:24
  • 2
    $\begingroup$ Have you tried a little basic algebra, like that apply $m^x*m^y\bmod n\;=\;m^{x+y}\bmod n$ to your $h=m^{e_1(e_1^{-1} \bmod e_2)} * m^{-e_2(((e_1^{-1} \bmod e_2)*e_1-1)/e_2)}\bmod n$? Also: prove that $g$ is an integer, and get rid of two $e_2$ with basic algebra. $\endgroup$ – fgrieu Jun 28 '17 at 18:34
  • $\begingroup$ thank you @fgrieu for pointing it out. But now I have another problem $h=m \mod n$ how can I get rid of $\mod n$? the result should be $h=m$. $\endgroup$ – Patrick Sweigl Jun 28 '17 at 19:08
  • 1
    $\begingroup$ @PatrickSweigl hint for this last step: $m< n$ for any valid RSA message. $\endgroup$ – SEJPM Jun 28 '17 at 19:44

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.