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?

  • $\begingroup$ This seems to be the opposite case from RSA with modulus product of many primes, which you might also be interested in. $\endgroup$ – a CVn Mar 28 '18 at 17:30
  • 1
    $\begingroup$ idownvotedbecau.se/noattempt $\endgroup$ – fkraiem Mar 29 '18 at 2:30
  • $\begingroup$ @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. $\endgroup$ – Ilmari Karonen Mar 29 '18 at 12:11

How would Bob decrypt her message?

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.

Since anyone with the public key can do this, RSA based on a prime modulus is insecure.

  • $\begingroup$ Another interesting case is "Let n = p q. What happens if p or q is not a prime as it should be? What goes wrong in RSA if we have this?" (Example: if the Miller-Rabin probabilistic primality test fails!) $\endgroup$ – Basj Mar 28 '18 at 22:32
  • $\begingroup$ @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) $\endgroup$ – 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.

  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Mar 28 '18 at 23:39

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