2
$\begingroup$

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!

$\endgroup$
  • 4
    $\begingroup$ "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. $\endgroup$ – fkraiem May 15 '15 at 1:06
  • 2
    $\begingroup$ @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)$. $\;\;\;\;$ $\endgroup$ – user991 May 15 '15 at 5:49
5
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ 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 $\endgroup$ – poncho May 15 '15 at 3:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.