If I am able to generate the same public key as someone else, do I also get the same private key?

Question

I have a very basic understanding of the asymetric encryption. I have a couple of simple questions. I know I can generate a key pair, of public and private keys.

• If by co-incidence my public key that is generated is the same as a public key of someone else. Does this mean we will also have the same private keys?

Second related question.

• If the answer is yes to the first question. Then, is it in theory, possible to have a huge database of all known public keys and keep randomly generating key pairs and checking against the database if any of them match.

Breaking one specific key, is very hard. But is breaking any key also hard? If someone tries to find a match with publicly known key they could somehow break one or a handful of them. If not, what stops this from happening.

Thanks! : )

Answer 1

Breaking any key from a set by random guessing is indeed 'easier' than breaking a specific key, but not enough to make a difference.

How many known keys there are depends on who does the knowing, but if consider available from public servers on the Internet, several projects have collected more or less all SSL/TLS and/or SSH keys on public Internet servers for various kinds of investigations; see https://www.factorable.net for one good example. This takes some work and a bit of time, but is quite possible. They reported 12 million in 2012; adding a generous allowance for growth and rounding up, call it about 32 million (2^25). This is not large at all for modern database systems and computers, although e.g. storing it on paper cards in an old-style library catalog would be costly.

As per the link in Crypt32's answer, the chance that a randomly generated RSA 4096 key matches a particular target is about 1 in 2^4070; with 2^25 targets, it improves to about 1 in 2^4045. Both of these are astronomically unlikely -- literally so; if you used all the energy in the universe the chance of hitting any target is still much less than the chance of your house being hit by dozens of independent asteroids within one second.

Even for RSA 2048, which is much more common today, you improve from 1/2^1005 to 1/2^980 -- still not enough to matter.

ECC, on the other hand, is much smaller because it isn't subject to math-structure attacks like RSA. For the commonly used ~256-bit curves (secp256r1, secp256k1, X25519/Ed25519) the universe does contain enough energy to break some reasonable number of keys, though the Earth doesn't. And for Bitcoin addresses, which run the secp256k1 key through a (net) 160-bit hash, it is quite possible someone will find a duplicate within not too many millenia, though probably not within your lifetime (or mine).

Answer 2

If by co-incidence my public key that is generated is the same as a public key of someone else.

yes, they will match, because they are tightly related to each other.

Then, is it in theory, possible to have a huge database of all known public keys and keep randomly generating key pairs and checking against the database if any of them match

in theory, it is possible. In practice -- hardly.

• Key generation is still computationally expensive and fast key generation will require expensive hardware (clusters, arrays, suporcomputers).
• The database will be extremely huge and its population with known keys will take centuries. Here is a thread that explains the keyspace for 4096-bi RSA asymmetric key: https://crypto.stackexchange.com/a/55918/28152. You will quickly run out of space.

In other words, it is easier to crack single RSA key by utilizing modern factorization problem solve techniques than build a database and find matching key.

EC keys rely on different mathematical problem and their key space literally equals to full space (say, ECDSA 256-bit will get you up to 2^256 possible keys and it is still huge).