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!
$\begingroup$
$\endgroup$
2
-
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$– fkraiemCommented May 15, 2015 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$– user991Commented May 15, 2015 at 5:49
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
-
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$– ponchoCommented May 15, 2015 at 3:38
$\begingroup$
$\endgroup$
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}$
