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$.
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.