RSA cryptosystem - discrete secret primes

48 Views Asked by At

Why do we bother to take $n$ as a product of two secret primes in RSA cryptosystem? If $e$ is public, $d$ is private and prime factorization of $n$ is not secret, what would happen?

2

There are 2 best solutions below

0
On BEST ANSWER

I'm referring to https://simple.wikipedia.org/wiki/RSA_algorithm

If anybody knows the factorization of $n$, they can effectively calculate $\phi(n)$ (Euler totient function) and then with the knowledge of the public key $e$ do step 5 from the linked website themselves effectively. So they have the private key $d$ and can now do everything the 'rightful' owner of the private key can do.

0
On

In RSA, if $e$ and $d$ are both known, we can factor $n$.

Also, if the factorisation of $n$ is known we can compute $d$ from $e$ and vice versa.

So in both cases RSA is totally broken. It is not necessary for $n$ to be the product of two primes, but we need $n$ to be hard to factor. If the prime factorisation were computable easily, $d$ could easily be found from the public exponent $e$. Making $n$ the product of two large and unrelated primes is practically speaking the easiest way of ensuring $n$ to be hard to factor (if $p$ and $q$ are also so-called strong primes as well).