2
$\begingroup$

Just want to make sure that my understanding is correct whether there is only one public key for any private key, and vice versa.

I know that there are many algorithms, and this may not be a property of all of them (or is it?..), hence the tagging of RSA only.

$\endgroup$
3
  • $\begingroup$ That's exactly what I was looking for! Thank you! $\endgroup$
    – toraritte
    Commented Jul 18, 2021 at 18:32
  • $\begingroup$ @Andy Dienes Please present a full answer that follows the SE system of Q&A. Thank you! $\endgroup$
    – Patriot
    Commented Jul 19, 2021 at 1:34
  • $\begingroup$ There can be many private keys for the same public key, e.g., with certain LWE encryption schemes. $\endgroup$ Commented Jul 20, 2021 at 1:35

1 Answer 1

4
$\begingroup$

Just want to make sure that my understanding is correct whether there is only one public key for any private key, and vice versa.

That is not correct; formally, for any valid private RSA key, there are an infinite number of public keys that will work with it, and for any valid public RSA key, there are an infinite number of private keys that will work with it.

The reason is quite simple; for any exponent $f$ [1], we have the identity $m^f = m^{f + k \ell} \pmod n$, for $\ell = \text{lcm}(p-1,q-1)$, and any integer $k$ and any integer $m$.

That means that for any private key that corresponds to a public key with public exponent $e$, the alternative public exponent $e + k \ell$ would act just the same, and since there are an infinite number of $k$ values, we have an infinite number of public keys that all correspond.

In parallel, for any public key that corresponds to a private key with private exponent $d$, the alternative private exponent $d + k \ell$ would act just the same, and since there are an infinite number of $k$ values, we have an infinite number of private keys that all correspond.

If you limit the range of allowable exponents to $[0, \ell-1]$, then this multiplicity of keys doesn't happen - however if you allow the range $[0, \phi(n) - 1]$ (which I have seen stated in some tutorials on RSA), there will always be at least two equivalent keys (assuming that $n$ is a product of at least two odd primes).

[1]: I used the variable $f$ because this observation applies to both public and private keys.

$\endgroup$
1
  • $\begingroup$ Thank you! I will have to mull over this - and I now have multiple other questions as this kinda shatters my cozy little worldview... $\endgroup$
    – toraritte
    Commented Jul 19, 2021 at 10:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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