# Why do we need in RSA the modulus to be product of 2 primes?

I think I roughly understand how the RSA alorithm is working.

However, I don't understand why we need the $N$, which we use as a modulus, to be $pq$ for some large primes $p, q$.

I vaguely know it has something to do with factorization, but I am kind of lost. So, hypothetical questions.

• What would happen if the $N$ was not $pq$, but just a big prime?
• What if $N$ would be some random composite (that's easy to factor)?

The other parts of RSA would stay the same.

RSA would still "work" with such $N$, but isn't secure for $N$ that are easily factored. If you know the factorization of $N$ (which is trivial for prime $N$s) you can calculate the private key from the public key. This totally breaks the desired security properties of RSA.

The essential equation for RSA is that $m^{\phi(N)+1}= m \mod N$ for all $m$. This works for all $N$, but only for some $N$ it's hard to calculate $\phi(N)$. When using RSA we require $\phi(N)$ being hard to calculate, since once you know $\phi(N)$ you can get $d$ from $e$ by solving $e \cdot d = 1 \mod \phi(N)$ using the extended Euclidean algorithm (just like what you do when legitimately creating the key-pair).

If $N$ has more than two factors, but at least two of those are large and hard to guess, it's still secure. But almost nobody uses this RSA variation.

• Oh.... so because the attacker would know $\phi(N)$, he would be able to deduce $d$ from $e$ because $de=1$ in mod $\phi(N)$. I think I am starting to get it. Oct 27, 2012 at 19:24
• Also, we need at least the key creator to be able to calculate $\phi(N)$, so a random non-factorable number doesn't fit, too. Oct 27, 2012 at 21:58
• As explained, more than two factors for $N$ work. Combined with the CRT it is actually useful if you have fast hardware to perform $n$-bit modular exponentiation (e.g. $n=512$) and want more security than $2n$-bit RSA allows. This was noticed by several academics (including Pr. Jean-Jacques Quisquater, who has shown me the technique in the context of projected Smart Card signature system in the late 199x), patented in the US, and used to some degree.
– fgrieu
Oct 28, 2012 at 9:13
• @fgrieu: nice link. It might be worth noting that the encryption scheme also "works" with $N=p$ a big prime, but then becomes symmetric (and was actually invented by Polhig and Hellman) as opposed to RSA which is an asymmetric one.
– bob
Oct 28, 2012 at 9:35