# RSA with composite numbers

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).
-
RSA uses a composite modulus. Usually it is the product of two primes (called a semiprime), but you could use more if you want. – CodesInChaos Jan 23 '14 at 9:13
i delete my previous question because i found the question is not correct and here i am asking about that question – Aria Jan 23 '14 at 10:02
I think you need to clarify your question. Currently what you've written doesn't really make sense... – figlesquidge Jan 23 '14 at 10:15
Can RSA work with a different modulus than a product of 2 large primes? Yes, however the key generation will be different and security will affected – ratchet freak Jan 23 '14 at 11:05
– Ilmari Karonen Feb 8 '15 at 19:06

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.

-

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

-
I like the caveat that the we have to use odd primes. It suggests that using 2 would be disastrous but 3 would be perfectly fine! – Nate Eldredge Feb 13 '14 at 19:41
@Nate Eldredge: note that I only report this caveat. I agree with you that it does not make much sense: it is NOT necessary for RSA to work, for the definition of that considered in the current question; and any small prime factor is bad from the standpoint of security. – fgrieu Feb 13 '14 at 20:33

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.

-
I have located that article by Boneh in an archived copy of CryptoBytes Volume 5, No. 1 Winter/Spring 2002: Fast Variants of RSA. It does discuss Multi-factor RSA. – fgrieu Feb 14 '14 at 6:44

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.

-
Quadratic Sieve or Number Field Sieve are NOT helped by 3 or more factors. Elliptic Curve factoring and several other methods are. That's how Multiprime RSA gets parameterized: the number of primes is made such that it just bridges the gap between GNFS and Elliptic Curve. – fgrieu Feb 13 '14 at 20:47
You are right, my mistake. – Minkus CNB Feb 13 '14 at 21:03