# How do we guarantee plaintext is coprime in RSA?

The specifications for RSA state: $P^{\phi(N)} \equiv 1 ~mod~N$ if and only if $P$ and $N$ are coprime. Here $P$ is the plaintext and $N$ is the product of two suitable primes $x_1, x_2$. My question is how do we guarantee that $P$, the plaintext will be coprime to $N$? Thank you in advance!

• "Pϕ(N)≡1 mod N if and only if P and N are coprime." This is correct but irrelevant for RSA. What matters is that if $k \equiv 1 \pmod{(p-1)(q-1)}$, then $M^k \equiv M \pmod N$. This is true for all $M$ in the special case where $N = pq$ where $p$ and $q$ are distinct primes. – fkraiem May 15 '15 at 1:06
• @fkraiem : $\:$ In fact, it's sufficient for $k$'s congruence to be modulo $\operatorname{L}\hspace{-0.03 in}\operatorname{cm}(\hspace{.04 in}p\hspace{-0.04 in}-\hspace{-0.05 in}1,\hspace{-0.02 in}q\hspace{-0.04 in}-\hspace{-0.05 in}1)$. $\;\;\;\;$ – user991 May 15 '15 at 5:49

If you can efficiently find a $P$ that is not coprime to $N$, then you can easily factor $N$ (use GCD). If you know the factorization of $N$ (say $N=pq$), you can easily find a $P$ that is not coprime to $N$ ($kp$ for some constant $k$).
This established the fact that finding $P$ not coprime to $N$ and factoring are equivalent problems.
Now, how many numbers are there less than $N$ that are not coprime to $N$? Well, we know that there are $\varphi(N)=(p-1)(q-1)$ numbers less than $N$ that are coprime to $N$. So, there are $N-\varphi(N)=pq-(p-1)(q-1)=pq-pq+p+q-1=p+q-1$ such numbers. This is actually a fairly large number (for 2048 bit $N$, $p$ (and $q$) would each be 1024 bits). But, it is minuscule in comparison to $\varphi(N)$, which is the number of numbers that are coprime. So, a random number is, with overwhelming probability, not coprime to $N$. At the moment, the best method for finding such a $P$ is to first factor $N$.
So, to answer your question, you don't have to worry about $P$ not being coprime to $N$. If you ever find one that isn't, bad things will happen. Your odds of a $P$ not being coprime are smaller than winning the lottery and getting struck by lightning twice, all in the same day.
• And, as fkaiem points out, even if N and P aren't coprime, it turns out RSA works out as well, as $x^{ed} \equiv x \pmod{N}$ for all $x$, including those not relatively prime to N – poncho May 15 '15 at 3:38