3
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ 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 as a potential duplicate. $\endgroup$
    – Morrolan
    Dec 13, 2022 at 13:12
  • $\begingroup$ As for there being, for a fixed choice of $e$, multiple values for $d$, see this question or this question. 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. $\endgroup$
    – Morrolan
    Dec 13, 2022 at 13:16

1 Answer 1

Reset to default
2
$\begingroup$

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)/q$, 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$...

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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