Proof of Unique Solution for Modular Exponentiation In Cryptography

Question

The question is about the encryption equation in asymmetric encryption.

For $c\equiv m^e\bmod n$, prove that for every unique $m$ there is a unique $c$.

Here $n=pq$ where $p$ and $q$ are primes larger than $m$ and the exponent $e$, is $\geq3$ and coprime with $p-1$ and $q-1$.

Thanks!

Answer 1

If ${\rm GCD}(e,(p-1)(q-1))={\rm GCD}(e,\phi(pq))={\rm GCD}(e,\phi(n))=1$ then you can find (by the so called Bezout identity) integers $r,s$ such that $$ re+s\phi(n)=1. $$ Thus you have $$ m\equiv m^{re+s\phi(n)}\equiv c^r\bmod n $$ and so you recover $m$ from $c$ proving its unicity.

In the above one uses the well known fact that $m^{\phi(n)}\equiv1\bmod n$ since the condition on $m$ implies that ${\rm GCD}(m,n)=1$ ($\phi$ is Euler's function, of course)

Answer 2

Hint $\ $ Raise $\ c\equiv m^{\large e}\pmod{pq}$ to power $\, k \equiv \dfrac{1}e\pmod{\phi(pq)}\ $ [it exists by $\,\gcd(e,\phi) = 1]$ which yields $\ c^k\equiv m,\ $ i.e. we can simply take the $e$'th root of both sides.

Answer 3

Showing that $m$ can be extracted from $c$ is fine, but I was looking for a more direct proof. Here's how I started:

To prove that $c$ is unique to $m$ assume that the opposite is true, i.e. that two different $m$ can equal the same c:

$$m_1^e \equiv m_2^e \mod n$$

where $m_1$ and $m_2$ are distinct.

By definition that means:

$(m_1^e - m_2^e) = kn$ where k is an integer not equal to zero.

This means that if there are two distinct $m$ producing same $c$, then $(m_1^e - m_2^e)$ is divisible by $n$.

Here $n = pq$, $p, q$ are primes, $e$ is 3 or greater and co-prime with $(p-1)$ and $(q-1)$, and $m$ is not divisible by $n$.

Can we show that the last statement above cannot be true for any $m_1$ and $m_2$? This would prove that $c$ is unique for any $m$ in the equation in the original posting.