RSA with composite numbers

Question

It has been said that RSA uses a modulus product of two prime numbers for security reasons. But does RSA even work correctly if we allow composite integers instead?

I think that the answer is "NO".

Define “work correctly” as:

• allows encryption and decryption to be carried out as in normal RSA, yielding the original message (message padding and unpadding can remain unspecified, or absent as in texbook RSA);
• a security level can be given in terms of the key generation process (which may have alternate requirements to testing that $p$ and $q$ are prime).

Answer 1

If we remove from RSA the requirement that the factors $p$ and $q$ of the public modulus $n=p\cdot q$ are prime, and instead allow composites, then depending on the definition of RSA used, the resulting cryptosystem works in the sense of allowing decryption either:

1. almost not (only for few messages or exceptional choices of $p$ and $q$); that's if we blindly apply one of the common definitions of the relation between the public and private exponents $e$ and $d$, including $d=e^{-1}\bmod((p-1)\cdot(q-1))$ and $e\cdot d\equiv1\pmod{\operatorname{lcm}(p-1,q-1)}$;
2. for some messages (often all or most); that's for relations like $d=e^{-1}\bmod\varphi(p\cdot q)$ and $e\cdot d\equiv1\pmod{\lambda(p\cdot q)}$, and if we compute Euler's totient function $\varphi$ (also noted $\phi$) or Carmichael's function $\lambda$ with knowledge of the factorization of $p$ and $q$;
3. for all messages; that's when in addition of using the above relations, $p$ and $q$ are coprime and squarefree, or otherwise said when all the factors of $n$ are distinct primes.

For an illustration of case 2., consider $p=187=11\cdot17$, $q=253=11\cdot23$, $n=p\cdot q=47311$, $\lambda(n)=\operatorname{lcm}(11-1,17-1,23-1)=880$, $e=3$, $d=e^{-1}\bmod880=587$. For any $x$ with $0\le x<47311$, $(x^e\bmod n)^d\bmod n=x$ holds when $x\bmod11\ne0$ or $x=0$, but all other $4300$ values of $x$ are exceptions; e.g. $42^{3\cdot587}\bmod47311=42$, $43^{3\cdot587}\bmod47311=43$, $44^{3\cdot587}\bmod47311=12947$.

Notice that choosing $p$ or $q$ as a huge random composite is unpractical: in order to compute a working $(e,d)$ pair we practically must know the factorization of $n$, and factoring a big-enough composite $p$ is seldom easy, and sometime entirely impractical. Also, this method of choosing $p$ and $q$ would lead to $n=p\cdot q$ that could be relatively amenable to factorization, making the cryptosystem unsafe.

By the definition of RSA per PKCS#1 after PKCS #1 v2.0 Amendment 1 of July 2000, RSA only requires that all the factors of $n$ are distinct odd primes $p_j$, and that $e\cdot d\equiv1\pmod{\lambda(n)}$, where $\lambda(n)$ simply reduces to the Least Common Multiple of the $(p_j-1)$. When there are more than two $p_j$, the cryptosystem is known as Multiprime RSA. It allows for faster computation of the private function, and is safe with proper choice of the $p_j$.

Answer 2

There are indeed multi-prime instances of RSA (ftp://ftp.rsa.com/pub/pkcs/pkcs-1/pkcs-1v2-0a1d1.doc‎). Regarding their security, I would suggest you to have a look at (http://cacr.uwaterloo.ca/techreports/2006/cacr2006-16.pdf‎) and have a look at this previous thread.

Answer 3

In fact in one of the RSA Labs CryptoBytes magazines, multiprime RSA versions and their applications for certain scenarios were discussed. Unfortunately i don't have a link to this article [possibly by Boneh] but a google search under multiprime RSA unearths quite a few links and technical papers.

Answer 4

The product can be of more than 2 prime numbers, but that makes it easier to break. Whatever method that is being used to try to break your encryption (for example elliptic curves) will have another number that factors into your modulus and that makes a correct hit more likely. After that, the modulus gets reduced to a simpler problem. This security problem is why we use 2 big prime numbers instead of just 2 big random numbers.