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

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.

• See this answer I gave to a related question. And a more concise proof using the Chinese Remainder Theorem, there, with trivial generalization to $N$ with any number of distinct prime factors. – fgrieu Feb 13 '14 at 12:19
• @fgrieu I just overflew your posts quickly and also saw that you updated your other post from Oct'2011. I will try to sum up the different answers and check if they fully clearify my doubts and troubles... Thank you very much. (A conclusion of both posts would match my answer perfectly - i will check that) – kn000x Feb 13 '14 at 15:45
• @fgrieu I would also be interested in a comprehensive answer from you – Murmel Feb 16 '14 at 16:23
• @user1885518: Please: (A) Clarify the question. "What happens to restrictions of plaintext n" does not make sense to me (same for "what happens to $n$"). Should that be "What happens to restrictions on plaintext $x$"; or "what happens to restrictions on $m$ such that any $x\in\{0\dots m-1\}$ can be a plaintext?". (B) Make the question self-contained (I can't understand German, used in video reference). (C) Quote some authoritative source using $\Phi$ (\Phi) for Euler's totient, not $\varphi$ (\varphi) as Knuth, your video, and others, or $\phi$ (\phi) as the original RSA article. – fgrieu Feb 16 '14 at 16:58

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.
• I think that you want to revise your third point. With $p=q$ prime, RSA no longer works for messages that are non-zero multiples of $p$. Also, the relation between $e$ and $d$ to make these work for the other messages becomes $e\cdot d\equiv 1\pmod{(p−1)}$. And in the second point, you need $p$ and $q$ coprime and squarefree in order to avoid restrictions on message. Finally, considerations on security arising from how $p$ and $q$ are chosen are explicitly out of the question's scope, see the butlast paragraph in the question. – fgrieu Feb 13 '14 at 14:29

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.

• This is not an answer; and the (valid) point raised is excluded from the question, by the butlast paragraph (in its original version). – fgrieu Feb 13 '14 at 9:14
• @fgrieu Could you elaborate more on why this is not an answer or what is the valid point? I believe that the case of p=q is not the case, so we are talking about p or q not being primes. Sure there are multi-prime instances of RSA link, however, if someone is using the multi-prime version for the same length with normal RSA, then he is jeopardizing the security of the scheme. Some attacks can be found for instance here link. – absinthe_minded Feb 13 '14 at 12:19
• You note the lack of security of RSA when $p=q$. This is a valid point (in the sense of observation). But it is excluded by the question stating: "The questions are not about argueing about the security of RSA and well choosen parameters $p$ and $q$". The question really asks if RSA works in the sense of allowing decryption (or signature verification) for any message and choice of $p,q$. – fgrieu Feb 13 '14 at 12:22
• So the question according to your interpretation is: Will RSA work encrypt, decrypt, sign if I chose the wrong paremeters? and the answer is: Yes it will work". IMHO since the last paragraph clearly states "It's more about the restrictions on n we will cause by choosing these factors", the restriction is fairly obvious: make n difficult to factor. If you have n1=pq* k bits long and $n2=p'*q'*r$ again k bits long then $n2$ is more easy to break, for equibalanced primes. So do not chose $n2$. The restrictions are made to make RSA safe, otherwise it can work with arbitrary numbers. – absinthe_minded Feb 13 '14 at 12:39
• That's my interpretation of the question. The answer is: NO, it will NOT work for quite all messages; specifically, not for those few messages such that the (padded) message is a non-zero multiple of $r>1$ such that $r^2$ divides $N$. – fgrieu Feb 13 '14 at 13:57