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

Improve this question
$\endgroup$
4
  • $\begingroup$ What is done there with the $e$s kinda smells like the chinese remainder theorem. $\endgroup$
    – SEJPM
    Jun 28, 2017 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, 2017 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$
    – Zagatho
    Jun 28, 2017 at 19:08
  • 1
    $\begingroup$ @PatrickSweigl hint for this last step: $m< n$ for any valid RSA message. $\endgroup$
    – SEJPM
    Jun 28, 2017 at 19:44

1 Answer 1

Reset to default
4
$\begingroup$


note that $e_2g=e_2\cdot\frac{(f\cdot e_1-1)}{e_2}=f\cdot e_1 - 1$
so we can have
$m ^ {e_1f-e_2g}=m^{e_1f-e_1f+1}=m^1=m $

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.