Return to Answer

I'm getting the following information from here (slide 26).

$c_1 \equiv m^{e_1} \mod n$

$c_2 \equiv m^{e_2} \mod n$

if $\gcd(e_1,e_2)=1$ then $\exists a,b\in\mathbb{Z} : e_1\cdot a + e_2\cdot b = 1$ ($a$ and $b$ can be found by extended euclidean algorithm)

And,

$m\equiv c_1^a\cdot c_2^b \mod n$

Note: In practice, either $a$ or $b$ will be negative. WLOG, let $b$ be negative. This leads to problems in the above equation. To get around this, use the following computation.

Let $i\equiv c_2^{-1} \mod n$ (i.e., the modular inverse of $c_2$)

$m\equiv c_1^a\cdot i^{-b} \mod n$

$c_1 \equiv m^{e_1} \bmod n$

$c_2 \equiv m^{e_2} \bmod n$

if $\gcd(e_1,e_2)=1$ then $\exists a,b\in\mathbb{Z} : e_1\cdot a + e_2\cdot b = 1$ ($a$ and $b$ can be found by extended euclidean algorithm)

And,

$m\equiv c_1^a\cdot c_2^b \bmod n$

Note: In practice, either $a$ or $b$ will be negative. WLOG, let $b$ be negative. This leads to problems in the above equation. To get around this, use the following computation.

Let $i\equiv c_2^{-1} \bmod n$ (i.e., the modular inverse of $c_2$)

$m\equiv c_1^a\cdot i^{-b} \bmod n$

Update to show details of $m\equiv c_1^a\cdot c_2^b\bmod n$. All math below done modulo $n$.

$$ c_1^a\cdot c_2^b\\ (m^{e_1})^a\cdot (m^{e_2})^b\\ m^{e_1a}\cdot m^{e_2b}\\ m^{e_1a+e_2b}\\ m^1\\ m $$

I'm getting the following information from here (slide 26).

$c_1 \equiv m^{e_1} \mod n$

$c_2 \equiv m^{e_2} \mod n$

if $\gcd(e_1,e_2)=1$ then $\exists a,b\in\mathbb{Z} : e_1\cdot a + e_2\cdot b = 1$ ($a$ and $b$ can be found by extended euclidean algorithm)

And,

$m\equiv c_1^a\cdot c_2^b \mod n$

I'm getting the following information from here (slide 26).

$c_1 \equiv m^{e_1} \mod n$

$c_2 \equiv m^{e_2} \mod n$

if $\gcd(e_1,e_2)=1$ then $\exists a,b\in\mathbb{Z} : e_1\cdot a + e_2\cdot b = 1$ ($a$ and $b$ can be found by extended euclidean algorithm)

And,

$m\equiv c_1^a\cdot c_2^b \mod n$

Note: In practice, either $a$ or $b$ will be negative. WLOG, let $b$ be negative. This leads to problems in the above equation. To get around this, use the following computation.

Let $i\equiv c_2^{-1} \mod n$ (i.e., the modular inverse of $c_2$)

$m\equiv c_1^a\cdot i^{-b} \mod n$

I'm getting the following information from here (slide 26).

$c_1 \equiv m^{e_1} \mod n$

$c_2 \equiv m^{e_2} \mod n$

if $\gcd(c_1,c_2)=1$ then $\exists a,b\in\mathbb{Z} : e_1\cdot a + e_2\cdot b = 1$ ($a$ and $b$ can be found by extended euclidean algorithm)

And,

$m\equiv c_1^a\cdot c_2^b \mod n$

I'm getting the following information from here (slide 26).

$c_1 \equiv m^{e_1} \mod n$

$c_2 \equiv m^{e_2} \mod n$

if $\gcd(e_1,e_2)=1$ then $\exists a,b\in\mathbb{Z} : e_1\cdot a + e_2\cdot b = 1$ ($a$ and $b$ can be found by extended euclidean algorithm)

And,

$m\equiv c_1^a\cdot c_2^b \mod n$