Common Modulus Attack not reproducible I want to calculate a simple example of the RSA common modulus attack. However, the result is not correct and I do not find my mistake. 

p=$29,
q=37,
n=p*q = 1073,
\phi(n) = 1008,
e1 = 5,
e2 = 11$

Let $m = 999$. 

$c_1 = m^{e_1} \pmod n = 296$, 
$c_2 = m^{e_2} \pmod n = 555$

The extended Euclidean algorithm gives me $y_1$ and $y_2$: $y_1 \cdot e_1 + y_2 \cdot e_2 = 1$ 

$y_1 = -2, y_2 = 1$ (edited)

$m = c_1^{y_1} * c_2^{y_2} = 296^{-2} \cdot 555^1 \pmod {1073}$

How do I calculate $296^{-2}$? I tried to get the inverse of $296 \pmod {1073}$ and then square it, but $296$ has no inverse. What am I doing wrong?
In real word RSA modules are so large that probability for finding $c_1$ which is not coprime with $n$ is approximately zero.


  Also if you founded such number then $p=gcd(c_1,n)\neq1$ so $p$ is a factor of $n$ and in this case attack is not necessary because $n$ is factored.


$gcd(296,1073)=37\neq 1$ so $p=37,q=\frac{1073}{37}=29$ and $\phi(n)=1008$

Now you can easily compute private key $d_2$:

$e_2\cdot d_2=1 \pmod{ \phi(n)}$ so $d_2=275$.


  $$m={c_2}^{d2}\pmod n={555}^{275}\pmod{1073}=999$$