Why does RSA need p and q to be prime numbers?

Despite having read What makes RSA secure by using prime numbers?, I seek a clarification because I am still struggling to really grasp the underlying concepts of RSA.

Specifically, why can't we choose a non-prime p and q?

I do understand the key concept: multiplying two integers, even two very large integers, is relatively simple. However, factoring a large integer is extremely difficult, even for a computer using known factoring algorithms.

If this is correct, then the original question posed by the OP in this thread continues to befuddle me. This section from Henrick's answer in this post contains the relevant information:

It also means that if you were to select p,q just as odd integers, you would make it harder for yourself to find ϕ(n), while at the same time decreasing the relative size of the second largest prime factor, and thereby making it easier for everyone else to factor n. In fact, it would be as hard for you to factor n as it would be for everyone else, so you would completely loose the trapdoor component of your scheme (if not making it completely infeasible to find a pair e,d).

But I do not understand why we make it harder for ourselves to find ϕ(n). I BELIEVE that it has to do with the fact that for any prime, n, all integers up to n-1 are relatively prime. If the integer is not prime, then we actually need to find which integers up to n are actually relatively prime.

I understand how we are decreasing the relative size of the 2nd largest prime. For example: 10403 has prime factors of [101,103] while 11000 has prime factors of [2, 2, 2, 5, 5, 5, 11].

So, if I understand things correctly, choosing a non-prime p and a non-prime q would theoretically work, but the issue is that we would be creating a more insecure encryption scheme since:

• the product of non-prime p and non-prime q are more easily factored (2nd largest prime is smaller than if p and q were prime);
• finding ϕ(n) becomes more difficult for the key generator step, which decreases efficiency with the aforementioned decrease in security

Sorry if this is completely obvious, but I am a newbie in higher math and programming. I really want to understand this as deeply as I can.

• It's harder to find $\varphi(a*b)$ where $a$ and $b$ are randomly selected odd integers because you have to know the prime factorization of each one as $\varphi(n) =n \prod_{p\mid n} \left(1-\frac{1}{p}\right)$. If $a$ and $b$ are typical RSA size numbers factoring them is non-trivial. – puzzlepalace May 19 '16 at 18:52
• By the way, it's not clear if your question is about the correctness of RSA or the security of RSA (i.e. does RSA need to have a modulus with two prime factors to be correct vs does RSA need to have a modulus with two prime factors to be secure). – puzzlepalace May 19 '16 at 23:24
• The answers below are all good, but if you still struggle to get them, maybe enlightenment will come from looking at another angle: why use only /two/ primes ? the algorithm can be perfectly adapted to use three primes p, q and r. You just get a comparatively bigger modulus for equivalent security. – b0fh May 20 '16 at 13:09

However, factoring a large integer is extremely difficult, even for a computer using known factoring algorithms.

Not categorically. Factoring a large integer is trivial if it is only composed of small factors.

A fairly naive algorithm for factoring N is the following:

while N > 1:
for p in increasing_primes:
while p divides N:
N = N / p


With this algorithm, $340$ $282$ $366$ $920$ $938$ $463$ $463$ $374$ $607$ $431$ $768$ $211$ $456$ can be factored in exactly $128$ iterations of the innermost while. (The number, of course, is $2^{128}$)

The more prime factors a composite number has, the smaller those factors have to be. For example, $919 \cdot 677 = 622$ $163$. With the naive algorithm, this takes $157 + 1 = 158$ iterations to factor. A number of roughly the same size comprised of three factors, $73 \cdot 89 \cdot 97 = 630$ $209$, only takes $25 + 2 = 27$ iterations to factor.

Similarly, a 1000-digit number composed of two roughly equally-sized factors will take about $10^{497}$ iterations to factor. A 1000-digit number composed of 100 roughly equally-sized factors will take about $434$ $294$ $481 + 99 \approx 10^{9}$ iterations. And a 1000-digit number composed of 1000 roughly equally-sized factors will take about $4 + 999 \approx 10^{3}$ iterations.

So, to make factoring as difficult as possible, you want the prime factors to be as large as possible, which means you want N to have the fewest factors possible. With $p$ and $q$ prime, $N$ has two factors. With $p$ and $q$ composite, $N$ has at least four factors, possibly more.

Note that this is far from a complete answer on why (we think) RSA is secure, but I hope it gives a more intuitive / example-based idea of why $p$ and $q$ should be primes.

Note also that $p$ and $q$ should be similar in magnitude. If one is much larger than the other, factorization becomes easier. For example, if $p = 43$, the naive algorithm would only take $14$ iterations.

(After reading the comments (thanks Taemyr and Daz C), I corrected some mistakes in the answer. The main point is unaffected.)

• if p divides N should be while p divides N. – Taemyr May 20 '16 at 22:27
• How are the # of iterations determined? – Daz C May 21 '16 at 16:08
• @Taemyr You're right, thanks! I corrected the algorithm. – marcelm May 21 '16 at 18:52
• Nitpicking, but your code won't factor $2^{128}$ in 128 iterations as you loop over all the primes inside the while loop hence you'll check every prime in your list regardless of if $N$ was already completely factored. – puzzlepalace May 22 '16 at 8:24
• Nitpicking too on for p in increasing_primes. It requires to know the list of consecutive primes: this is not possible for big numbers. – Biv May 22 '16 at 9:24

The main reasons we usually choose $$p$$ an $$q$$ prime numbers are:

1. For a given size of $$N=p\,q$$, that makes $$N$$ harder to factor, hence RSA safer. Although efficient factoring algorithms do not find factors by trial division, it remains much easier to find very small prime factors than large ones. If we chose $$p$$ and/or $$q$$ at random without consideration for their factorization, they will tend to often have factors that it will be possible to pull out from $$N$$.
2. If $$p$$ and $$q$$ were not prime, we would need to find their factorization to compute the RSA private function; or/and compute the RSA private exponent $$d$$ from the public exponent $$e$$ (or vice versa), since we need to know the factorization of $$N$$ to compute $$\varphi(N)$$ or $$\lambda(N)$$; and that would be quite hard (typically easier than factoring $$N$$, but still too hard for many practical purposes). It is much easier to generate a prime than it typically is to factorize an integer of equivalent size, much more of twice the size.

There are variants of RSA (Multiprime RSA) where $$N$$ is the product of more than two primes; that can be viewed as $$p$$ or/and $$q$$ not prime. This has some interest, despite fact 1.

RSA moduli are generally of the form $N = pq$ for two primes $p$ and $q$. It is also important that $p$ and $q$ have (roughly) the same size. The main reason is that the security of RSA is related to the factoring problem. The most difficult numbers to factor are numbers that are the product of two primes of similar size.

Note. There are basically two classes of methods for attacking the factoring problem:

1. Methods like the number field sieve (NFS) whose complexity depends on the size of $N$. To protect against these methods an RSA modulus $N$ should have at least, say, 2048 bits.
2. Methods like the elliptic curve method (ECM) whose complexity depends on the smallest prime factor of $N$. To protect against these methods an RSA modulus $N$ should have all its prime factors of size at least, say, 256 bits.
• This is pretty much spot on. You could use non-primes, but then the difficulty to crack would be based upon the difficulty of factoring $p=p_1p_2$ and/or $q=q_1q_2$ which is by definition an easier problem than factoring $N=pq$. – Stephen Touset May 19 '16 at 22:16
• But as far as I know many modern fast prime-generation algorithms will not guarantee that the output is a prime number, but only produce primes with a very high confidence ( 99.999% ) so there is a small chance of the generated p and q actually not being primes But I don't think this leads to a practical attack, since you don't know if your N has more than 2 factors (most of the time it will only have 2) – Falco May 20 '16 at 11:15
• @StephenTouset: You can't use any odd non-primes, though -- it is important that $N$ is square-free, or the encryption and decryption primitives wouldn't be each other's inverses. – hmakholm left over Monica May 20 '16 at 13:23
• @Falco: The evidence of probabilistic primality tests stacks up exponentially, so "99.999%" vastly understates the confidence we get. It is simple and common to do enough rounds of the test that the risk of accepting a composite number due to the probabilistic nature of the test is only, say, $2^{-100}$ -- which is much smaller than EITHER OF the risk of the computer being destroyed by a random meteorite impact while executing the test OR the risk that a bit of your new prime will be corrupted by undetected DRAM faults ("cosmic rays") before you get around to using it for anything. – hmakholm left over Monica May 22 '16 at 12:07

$\varphi(n)$ is a multiplicative function: it is computed by the formula

$$\varphi(n) = n \prod_{p \mid n} \frac{p-1}{p}$$

or something equivalent. This is basically the only method of computation known that remains feasible when $n$ is not small.

Thus, if $N$ is the modulus you want to use for RSA, you need to know its prime factorization so that you can compute $\varphi(N)$. And you don't want anyone else to know it's prime factorization, otherwise they could compute $\varphi(N)$.

Also, all RSA cares about is that it has some $N$ and $\varphi(N)$. The only reason we talk about $p$ and $q$ is because choosing $N=pq$ because it is the best way to satisfy the previous paragraph.

• And possibly CRT? – Maarten Bodewes May 20 '16 at 0:24

I had the same question and so I landed here. RSA has two key properties

1. The mapping $$m \to m^e (mod\ N)$$ is a bijection
2. The inverse mapping $$(m^e)^d \equiv m\ (mod\ N)$$ is easy to compute (given $$p$$ and $$q$$ of course)

From what I read, the proof of working (of these two properties of RSA) assumes that $$p$$ and $$q$$ primes. So I worked on a few examples that violate this property and I found that it has, in my opinion, a more serious problem.

While all the answers focus on the practical aspect that it is harder for the encrypting party to compute the $$totient$$ of a large composite number that it chose, I think, allowing $$p$$ and $$q$$ to be composite has a fundamental problem that the encryption will lose its bijective property (decryption becomes ambiguous).

For example, if we let $$p = 8$$ and $$q = 9$$, then $$N = 72$$. $$\phi(72) = 24$$. A possible $$e$$ is $$5$$. With this public key $$(N, e) = (72, 5)$$, there is no bijection. Consider a message $$m = 4$$, upon encryption, it becomes $$16$$ while a message $$m = 22$$ also becomes $$16$$. ($$m = 58,\ 40$$ also become $$16$$ upon encryption).

I don't have a proof of this and I'm also to new to this theory. I would appreciate any suggestions and improvements.

As here many people have answer correctly

I will point to the fact that in one of the answers if p and q are chose to non prime then still RSA will do work though it will be less secure but it will not loose its bijection let see the example:

let 𝑝=8 and 𝑞=9, then 𝑁=72. 𝜙(72)=24. A possible 𝑒 is 5. So, public key (𝑁,𝑒)=(72,5), Consider a message 𝑚=4,

[(This is example taken from @rranjik ) upon encryption, it becomes 16 while a message 𝑚=22 also becomes 16. (𝑚=58, 40 also become 16 upon encryption). ] in this case we can choose m which are co prime to N(72 IN THIS CASE) or better say its co-prime to its prime factors as in this case m=4 is not co-prime to 72 so that's why algorithm is not working ) as this is because we have chosen simple composite numbers whose factors are likely to be in our message m.Thus that why bijections don't appears to be there. due to wrong choice of m ) so we can say algorithm will not works for some m but this does not meant it loses its bijection , the algorithm brokes due to our such choice of p and q or say m which doesn't satisfy it condition ).

New contributor
Ar_Unncertainity is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

There are multiple reasons, RSA uses a Modulo multiplication group with modulus $$PQ$$. Due to the nature of groups, this group does not contain all natural numbers between 1 and $$PQ$$, rather it only contains the numbers that are coprime with $$PQ$$. Coinsidentaly, the number of elements happens to be $$(P-1)(Q-1)$$.

But that is when $$P$$ and $$Q$$ are prime. If you assume, P is not prime, but rather is semiprime so that $$P=AB$$ and $$A$$ and $$B$$ are prime, the number of elements in group $$PQ$$ is no longer $$(P-1)(Q-1)$$ but rather $$(A-1)(B-1)(Q-1)$$. So if you where to use $$(P-1)(Q-1)$$ during the extended euclidean algorithm you would not find the correct decryption key (the key can be found using $$(A-1)(B-1)(Q-1)$$).

Thats the first reason, the second reason is that by using 3 prime numbers rather than 2, there are 3 additional keys that partly work for decryption. by applying the EEA to the same encryption key and $$(A-1)(B-1)$$, $$(A-1)(Q-1)$$, and $$(B-1)(Q-1)$$ you get keys that can decrypt messages encrypted using E with modulo $$ABQ$$. Decryption is not guaranteed, but it is possible. Additionaly these 3 keys can also decrypt some messages that cant be decrypted using modulo $$ABQ$$ by using modulo $$AB$$, $$BQ$$, or $$AQ$$ depending on which of the 3 extra keys is used.

Lastly all 3 prime numbers need to be as long as a traditional RSA prime (if not, $$A$$ and $$B$$ would be easier to find than $$Q$$, and finding $$Q$$ is trivial if you know $$A$$ and $$B$$), as both keys contains $$PQ$$, the key length is $$len(P)len(Q)+len(E)$$ (roughly $$len(Q)^2)$$. If 3 primes are used, they key length is now $$len(A)len(B)len(Q)+len(E)$$ (roughly $$len(Q)^3$$).

These 3 reasons make it rather impractical to use 3 prime numbers, you have to specially implement non prime handling, to result in an overall weaker algorithm, with a longer key. All of these issues only compound if more primes are used.

• Actually, multiprime RSA (that is, RSA modulii with > 2 prime factors) is actually practical (if rarely used). There isn't any confusion about the "keys", as $\text{lcm}(A-1, B-1, Q-1)$ is well defined. In addition, each prime doesn't have to be as long as the prime used within normal RSA (because the NFS algorithm doesn't get an advantage by the smaller prime factors, and while ECM would, it would still take longer than NFS for the length of prime factors we're talking about) – poncho Aug 5 '20 at 12:51