The problem is to reliably and efficiently find message $m$ (with $0\le m<n$) given RSA modulus $n$, distinct RSA public exponents $e_1$ and $e_2$ coprime to each others and to the unknown $\phi(n)$, and ciphertexts $c_1=m^{e_1}\bmod n$ and $c_2=m^{e_2}\bmod n$. WLoG, and per the corrected question, $y_1$ is negative when it is applied the extended euclidean algorithm to $e_1$ and $e_2$ in order to find $y_1$ and $y_2$ with $y_1\cdot e_1+y_2\cdot e_2=1$.
For random choice of message $m$, odds that $\gcd(m,n)=0$ are low, precisely $1-\phi(n)/n$, that is $1/p+1/q-1/n$ if $n=p\cdot q$ with $p$ and $q$ distinct primes. If $n$ is square-free (as assumed in most definitions of RSA), $\gcd(m,n)=\gcd(m^e_1,n)$, thus odds that $\gcd(c_1,n)=0$ also are $1-\phi(n)/n$. Hence, odds that $c_1$ has no inverse for random choice of $m$ are low (less than $2^{-510}$ of 1024-bit RSA with two 512-bit primes factors). Hence, for overwhelmingly most $m$, $c_1^{y_1}\cdot c_2^{y_2}\bmod n$ is well-defined, and is the desired $m$. But that does not quite always work.
We can make an efficient algorithm that always work, including for the definition of RSA in PKCS#1v2 where $n$ can have multiple prime factors, even though we might be unable to efficiently find any prime factor in $n$. The method goes:
- Check if $c_1=0$, in which case $m=0$.
- Compute $r=\gcd(c_1,n)$. That's a divisor of $n$, often $1$ (however it is possible that $r>1$, in which case $r$ divides $n$; and also that $r$ or/and $n/r$ are composite, thus factoring $n$ might remain uneasy).
- Compute $s=n/r$; with the assumption that $n$ is square-free, $\gcd(r,s)=1$ holds.
- Compute $i_1=((((c_1\bmod s)\cdot r)\bmod s)^{-1}\bmod s)\cdot r$, the so-called meadow inverse of $c_1$ modulo $n$, such that $i_1\cdot c_1\bmod r=0$ and $i_1\cdot c_1\bmod s=1$, with $r$ and $s$ defined as above.
- Compute $i_1^{-y_1}\cdot c_2^{y_2}\bmod n$, which is the desired $m$ (as pointed by Ricky Demer in a comment to the question).
Proof sketch: we prove $i_1^{-y_1}\cdot c_2^{y_2}-m\equiv0\pmod r$ and $i_1^{-y_1}\cdot c_2^{y_2}-m\equiv0\pmod s$.
Example: $e_1=5$, $e_2=11$, $n=837876170870196973028071$, $c_1=621961884462245272210948$, $c_2=653042419105836777869045$. We compute
- $r=932340427217$; that's a factor of $n$ (this example is crafted to make it composite)
- $s=898680510263$; that's a factor of $n$ (also composite in this example)
- $i_1=653042419105836777869045$
- $m=331563319321409011786785$.
Note: we do not need to factor $n$ (or $r$ or $s$), as required to compute a valid private exponent $d$, as would be required by the method outlined in that other answer; and we always find $m$ with polynomial effort w.r.t. the bit size of parameters, contrary to the method in that other answer.
