RSA: What happens to restrictions of plaintext n, dependent on p and q?

Question

Ok - i will try to ask my question as clear as possible. Im getting a little deeper into the RSA-cryptosystem. At one point i'm a little confused. We have a plaintext $x$ and ciphertext $y$, with

$x \in\Bbb Z_n = \{0,...,n-1\} $.

Additonally we choose $p$ and $q$ as primes. My source says $x$ must be less than $n$, which really makes sense to me. It proves that the RSA scheme works by using Euler's Theorem for:

$$ \\ $$

First case: $gcd(x,n)=1$

$d_{k_{pr}}(y) \equiv ( x^{\Phi(n)} )^t \cdot x \equiv 1\cdot\ x \equiv x\ mod\ n $

$$ \\ $$

Second case: $gcd(x,n) = gcd(x,p\cdot q) \ne 1$

• So we can assume $x$ to be: $\qquad x = r \cdot p\ $ or $\ x = s \cdot q \qquad$ ($r\lt q$ and $s \lt p$)
• Without loss of generality: $\qquad \ \ x=r\cdot p$
• Implict we have: $\qquad \qquad \quad \ \ \ gcd(x,q)=1$

Euler's Theorem holds in the following form:

$\qquad 1 \equiv 1^t \equiv (x^{\Phi(q)})^t\ mod\ q. $

Substitution:

$\qquad (x^{\Phi(n)} )^t \equiv (x^{(p-q)(q-1)})^t \equiv ((x^{\Phi(q)})^t)^{p-1} \equiv 1^{(p-1)} = 1\ mod\ q. $

Using the definition of the modulo operator, we can show that:

$ \\ \qquad (x^{\Phi(n)})^t \quad = 1 + u \cdot q \\ \qquad x \cdot (x^{\Phi(n)})^t = x + x \cdot u \cdot q \\ \qquad x \cdot (x^{\Phi(n)})^t = x + (r\cdot p) \cdot u \cdot q \\ \qquad x \cdot (x^{\Phi(n)})^t = x + r \cdot u \cdot n \\ \qquad x \cdot (x^{\Phi(n)})^t \equiv x\ mod\ n . $ $$ \\ $$ This proof seems plausible to me. Now my questions:

1. If $x \in \Bbb Z_n = \{0, ..., n-1 \}$ for $n=p \cdot q$, what happens to $n$ when $p$ and $q$ are not prime. Does this restrict the choice of an input $x$. For example, has $x$ to be less than $min(q,p)$? In this lecture Prof. Dr. Spannagel tolds the students that $x$ should be choosen always less than $min(q,p)$, to ensure that $gcd(x,n)=1$.

2. In addition, what happens if $p = q$ for $p$ and $q$ are prime. Does this affect our proof in case two?

The questions are not about argueing about the security of RSA and well choosen parameters $p$ and $q$. It's more about the restrictions on $n$ we will cause by choosing these factors.

Thanks in advance.

Answer 1

RSA has quite a few aspects, which are utilized implicitly, and these questions aim at those:

• Concerning your first point about what happens if $x$ is not coprime to $n$, it does not compromise the correctness of the encryption and decryption, but if you find such an $x$, you also found a nontrivial factor of $n$. However, if $p$ and $q$ are prime, the probability to find such an $x$ is negligible (in the mathematical sense).
• Concerning your first question, about what happens if $p$ and $q$ are not prime, is that you effectively weaken the scheme. For every known factor $f$ of $n$ you can reduce the RSA-problem into solving it in $f$ and $n/f$ and afterwards use the chinese remainder theorem to put them back together. An other minor aspect is, that finding $e$ might be more difficult (it has to be coprime to $\phi(n)$, otherwise decryption does not work any more, because it's not a bijection).
• For your second question: If $p=q$, then $\phi(n)=\phi(p^2)=p(p-1)$ is not secret any more. Everyone can just compute $d$ by solving $ed=1$ mod $\phi(n)$. Effectively there is no trapdoor left anymore, which is required for a public key scheme to work.

Answer 2

If you read more carefully you will see that RSA's security depends on the hardness of integer factorization. If p=q then an adversary has to compute a square root which is trivial. If p or q are not primes then integer factorization becomes easier. In either case you are jeopardizing the security of your algorithm.