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

-

## 1 Answer

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. – Karel Bílek Oct 27 '12 at 19:24

1
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. – Paŭlo Ebermann♦ Oct 27 '12 at 21:58

1
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 '12 at 9:13

2
@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 '12 at 9:35
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 32, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9684945344924927, "perplexity_flag": "middle"}