Common modulus attack question RSA.

cryptography

If we are in the context of understanding how Common Modulus Attack for RSA:

$C_1=M^{e_1} \pmod{n} $

$C_2=M^{e_2} \pmod n $

We know that if $\gcd(e_1,e_2)=1$ the attack works fine.

¿What would happen if $\gcd(e_1,e_2)>1$?

Best Answer

You would need to be able to extract $k$th roots where $k=\gcd(e_1,e_2)$ (and to do so efficiently). The common modulus attack allows one to recover $m^k \bmod n$ where $m$ is the desired plaintext. However, extracting $k$th roots is probably hard. (Extracting $e$th roots would lead to an immediate breaking of RSA through a single known ciphertext message: knowledge of $c$ and that $c=m^e$ would give us $m$ immediately by taking the $e$th root.)

Related Question