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$
    – user
    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$ 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
  • $\begingroup$ What exactly is λ? i.e. what is λ(n)? Is it the carmichel function? How does it matter here - can you elaborate? $\endgroup$
    – user93353
    Mar 25 '21 at 4:08
  • $\begingroup$ @user93353: I meant the lambda function, however if $p$ is prime, then $\lambda(p) = \phi(p) = p-1$, so in this case, it doesn't matter... $\endgroup$
    – poncho
    Mar 25 '21 at 11:57
  • $\begingroup$ Yes, got it. Since phi(p) = p-1, you would no longer need to factor the modulus. $\endgroup$
    – user93353
    Mar 25 '21 at 12:00

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.