Score:4

In RSA, why are there multiple possible private keys, and even the public key itself that can be used to decrypt the message?

uy flag

This is with reference to Eddie Woo's video on RSA. He uses the prime numbers '2' and '7' to make the product, n=14. He chooses the public key to be '5', the only possibility. However, many numbers meet the criteria to be the private key, where (5 * private key mod 14) = 1. To name a few, the numbers include 5,11,17. Eddie Woo chooses 11 to be his decryption key.

However, I realised that applying the decryption formula using any of the other options, 5 or 17 also works to decrypt the ciphertext. Doesn't this mean that multiple private keys exist that can decrypt the ciphertext, making it less secure? In fact, in this example, the public key itself can even be used to decrypt the cipher text. I feel like I'm misunderstanding something here,and would like some clarifications. Thanks for reading this!

Here's the link: https://www.youtube.com/watch?v=oOcTVTpUsPQ

Morrolan avatar
ng flag
The public key $e$ being equal to (a) private key $d$ is a side-effect of that video using an unrealistically small value for $N$. For real-world sizes of $N$, it is vanishingly unlikely that $d = e$, see [this question](https://crypto.stackexchange.com/questions/39645/rsa-public-key-can-decrypt-the-ciphertext-it-encrypted) as a potential duplicate.
Morrolan avatar
ng flag
As for there being, for a fixed choice of $e$, multiple values for $d$, see [this question](https://crypto.stackexchange.com/questions/39486/is-it-possible-to-have-multiple-rsa-private-keys?rq=1) or [this question](https://crypto.stackexchange.com/questions/48828/multiple-private-keys-with-rsa). In a nutshell, for a fixed $e$, if $d$ is a valid private key, then $d + \lambda(N)$ is also a valid private key, due to the choice of the algebraic structure RSA operates over. Intuitively this has no impact on security, as there are 'vanishingly few' possible values of $d$ in real-world usage.
Score:4
my flag

Doesn't this mean that multiple private keys exist that can decrypt the ciphertext,

Well, yes. The relationship that a public and private key must have is $$e \cdot d \equiv 1 \pmod{ \text{lcm}(p-1,q-1) }$$

Because of this relationship, then if we take a valid private key $d$ and add $\text{lcm}(p-1,q-1)$ to it (or a multiple of that), we'll come up with another valid private key.

In the example you have, $\text{lcm}(p-1,q-1) = \text{lcm}(1,6) = 6$, so adding 6 to the private key gives you another valid key. And, if you look at your examples, you'll see that all your private keys differ by 6.

making it less secure?

Well, no. For one, for realistic sized RSA modulus (rather than the toy example you have), $\text{lcm}(p-1, q-1)$ is huge (about the same size as the modulus); we don't have to worry about someone stumbling on a private key by randomly guessing them.

In fact, in this example, the public key itself can even be used to decrypt the cipher text.

Yes, that's another artifact of the tiny modulus. For real RSA modulus, this doesn't happen.. In fact, if we select a small public exponent $e$ [1], which is common practice, this cannot happen, as $d$ must be at least $\text{lcm}(p-1, q-1) / e \ge (p-1)/e$, which is for the primes we actually use, is quite large.


[1]: I'm assuming that you aren't silly enough to use $e=1$...

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.