Which divisors produce unique moduli? (for RSA encryption)

Question

Sorry if this question is confusing, I'm still confused by the whole thing.

I'm trying to understand how RSA encryption works, but I'm having trouble with the modulus part. For RSA to work, $c=m^e \bmod n$ must give an unique $c$ as long as $0<m<n$. I'm trying to find a pattern for the combinations of $e$ and $n$ that produce an unique $c$ for each $m$. I'm having trouble find any patterns.

When I tried $e=3$, $n=2,3,5,6,10,11,15,17$ all produce unique $c$'s as long as $0<m<n$. I don't see any patterns in that list.

Answer 1

There are two conditions, one on $n$ and one on $e$ in relation to $n$:

• $n$ must be square-free (= not divisible by square of any prime). If $n$ was divisible by $p^2$ for some prime $p$, then $(n/p)^e = n\left(\frac{n}{p^2}\right)(n/p)^{e-2}$ would be a obvious multiple of $n$ for $e\geq 2$, which means $(n/p)$ would clash with $0$ modulo $n$ when raised to $e$-th power. This condition is usually guaranteed in the RSA scheme by making $n$ a product of two distinct primes.
• $e$ must be coprime to $\phi(n)$: $\gcd(e,\phi(n))=1$.

Answer 2

RSA is motivated by how computationally difficult it is to factor large numbers. I was under the impression that $n$ had to be a product of two unique prime numbers (in any sort of practical application these would be very large primes). If we set this restriction for $n$, then we can produce a unique $c$ for any $e$ such that $\gcd(\phi(n),e)=1$.

An informal proof that the algorithm works for $n=pq$, where $p,q$ are prime, can be found on page 108 of Tom Judson's open source intro algebra book: abstract.pugetsound.edu

Answer 3

As was said above, RSA ensures this by taking $n = pq$ for $p,q$ two distinct (large) primes, and $e$ coprime with $\phi(n) = (p-1)(q-1)$. Then the encryption map $\mathsf{enc}: m \mapsto m^e \bmod n$ is a permutation of $\{0,\dots,n-1\}$.

To show this, since the set is finite we need only show either injectivity or surjectivity, we will show surjectivity. Let $c \in \{0,\dots,n-1\}$, we claim that $c = \mathsf{enc}(c^d \bmod n)$, where $d = e^{-1} \bmod{\phi(n)}$. This means that $c = c^{de} \bmod n$. Now, we have $de = 1+k\phi(n) = 1+k(p-1)(q-1)$, so we get $$c^{de} = c^{1+k(p-1)(q-1)} = c\times (c^{p-1})^{k(q-1)} \mod p,$$ and Fermat says that if $c$ is not a multiple of $p$, we have $c^{p-1} = 1 \bmod p$ so we obtain $c^{de} = c \bmod p$. If $c$ is a multiple of $p$ we have $c = 0 \bmod p$ and so $c^{de} = 0 = c \bmod p$ as well. Apply the same argument mod $q$, and the Chinese theorem concludes that $c^{de} = c \bmod n$.

(The proof is somewhat simpler if you assume that $m$ and $n$ are coprime as Gerry Myerson indicated.)