Score:2

Is the relationship between private and public keys an example of bijection between two sets?

ng flag

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.

ng flag
That's exactly what I was looking for! Thank you!
Patriot avatar
cn flag
@Andy Dienes Please present a full answer that follows the SE system of Q&A. Thank you!
Chris Peikert avatar
in flag
There can be many private keys for the same public key, e.g., with certain LWE encryption schemes.
Score:4
my flag

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.

ng flag
Thank you! I will have to mull over this - and I now have multiple other questions as this kinda shatters my cozy little worldview...
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.