# RSA: What would happen if you chose n to be a prime? [duplicate]

If Alice were to choose n to be a prime, instead of the product of two primes, what exactly would go wrong in the RSA cryptosystem? How would Bob decrypt her message?

• This seems to be the opposite case from RSA with modulus product of many primes, which you might also be interested in. – user Mar 28 '18 at 17:30
• idownvotedbecau.se/noattempt – fkraiem Mar 29 '18 at 2:30
• @fkraiem: IMO, that'd be a good reason to downvote if the OP had asked us to do their homework or debug their code or to solve some narrowly scoped problem that others are unlikely to encounter. This question, however, is one that a lot of people first learning about RSA have likely wondered about; IMO, it deserves an answer on this site, and we shouldn't fault the OP for being the first to ask it here. Of course, you're free to downvote any post for (almost) any reason, including just "I don't like it." But since you did choose to give a reason, let me choose to respectfully disagree with it. – Ilmari Karonen Mar 29 '18 at 12:11

That'd be easy, all we would need to assume that Bob has the public key. If $n$ is a prime, he is able to compute $d = e^{-1} \bmod{\lambda(n)}$, because $\lambda(n) = n - 1$. He can then raise the ciphertext to the $d$th power modulo $n$, and that's the padded plaintext.
• @Basj: well, if (say) $p$ happens to be composite, and you use the standard RSA algorithm $d = e^{-1} \pmod{ \text{lcm}(p-1, q-1)}$ or $d = e^{-1}\pmod{ (p-1)(q-1) }$, then most likely RSA doesn't work (decrypt doesn't decrypt properly). The exception is if $p$ happens to be a Carmichael number; in that case, it does work (but if the attacker guesses that, he can factor $n$ easier than expected) – poncho Mar 29 '18 at 2:09
That is impossible; it cannot happen. $n$ is not just chosen, instead we choose two primes $p$ and $q$ and set $n=p\cdot q$. As you can see, by definition $n$ is composite.