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

Question

Despite having read What makes RSA secure by using prime numbers?, I seek 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 $\phi(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 lose 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 $\phi(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 $\phi(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.

Answer 1

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
      factors.add(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.)

Answer 2

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.

Answer 3

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.

Answer 4

$\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.

Answer 5

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.

Answer 6

As many people here have answered correctly, I will point to the fact that in one of the answers if $p$ and $q$ are chose to non-primes then RSA still works though it will be less secure but it will not lose its bijection, as an example:

let $p=8$ and $q=9$, then $N=72$. $\phi(72=24)$. A possible $e$ is $5$. So, public key $(N,e)=(72,5)$, Consider a message $m=4$,

[(This is example taken from @rranjik) upon encryption, it becomes $16$ while a message $m=22$ also becomes $16$. ($m=58$, $40$ also becomes $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's why bijection doesn't appear to be there (due to wrong choice of $m$) so we can say the algorithm will not work for some $m$, but this does not mean it loses its bijection, the algorithm broke due to our such choice of $p$ and $q$ or say $m$ which doesn't satisfy the condition).

Answer 7

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$. Coincidentally, 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 a group $PQ$ is no longer $(P-1)(Q-1)$ but rather $(A-1)(B-1)(Q-1)$. So if you were 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)$).

That's 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. Additionally, these 3 keys can also decrypt some messages that cannot be decrypted using modulo $ABQ$ by using modulo $AB$, $BQ$, or $AQ$ depending on which of the 3 extra keys are 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 especially 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.