# 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. May 15, 2015 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, 2015 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 May 15, 2015 at 3:38

We do not guarantee, but it has a negligible probability of not being coprime (say $$Pr <= 2^{-80}$$)

Lets assume $$x_1$$ and $$x_2$$ of size 1024 bits, and $$N=x_1x_2$$. So for one collision between $$x_1$$ or $$x_2$$ and the message $$P$$, we have a probability $$Pr \approx 2 * 2^{1024} / 2^{2048} = 2^{-1023}$$