6
$\begingroup$

I think I roughly understand how the RSA algorithm works.

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Karel Bílek
    Commented Oct 27, 2012 at 19:24
  • 1
    $\begingroup$ 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. $\endgroup$
    – Paŭlo Ebermann
    Commented Oct 27, 2012 at 21:58
  • 1
    $\begingroup$ 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. $\endgroup$
    – fgrieu ♦
    Commented Oct 28, 2012 at 9:13
  • 2
    $\begingroup$ @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. $\endgroup$
    – bob
    Commented Oct 28, 2012 at 9:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.