# Given a large enough sampling of public keys could one begin to identify a private key?

For example, an ISP or government capable of tracking millions of keys being exchanged. Would that provide a sample large enough to be able to identify the private key on either end?

• You seem to think perhaps that there are multiple public keys for every private key? That isn't the case, there's only one public key for every private key. – GdD Dec 5 '12 at 9:07

No.

Examining public keys gives you no insight, no matter how many you see, that would allow you to derive the private from the public key.

• Plus you don't get multiple public keys for one private key. – Polynomial Dec 5 '12 at 9:08
• That is incorrect, if you can find a cert that uses RSA for it's PKI and they share either `P` or `Q` you can trivially do the math and find the missing component by factoring the numbers together. However this is only a problem if you did not have enough entropy while generating `P` and `Q`. See this Blog post for more info – Scott Chamberlain Dec 5 '12 at 23:02
• @ScottChamberlain That's kind of true. The modulus of the public key is `P*Q`, and it's quicker to find the GCD of two large numbers than to factor them, and with a large enough sample (and possibly a flaw in your key generation algorithm), you'll get a few moduli that share a prime. This allows you to derive the associated private keys for the keys that share a single prime, but not any other given key. So collecting a large set of public keys won't help you factor any chosen private key, you'd have to get lucky and land on a match. – tylerl Dec 6 '12 at 2:24

Yes and no.

Earlier this year a research paper was published that discovered a flaw with RSA crypto keys where if (and this is a MAJOR simplification) you found two certificates that shared a prime number you could use some math to find out the missing prime number from both certificates.

As you can tell this caused quite a stir in the various News Media. However it is not as bad as it seems. This only happens if you have a low entropy random number generator and the only commonplace location you will find them are certificates in embedded devices (like your router or firewall).

Freedom To Tinker posted a very good followup article explaining why this is not as bad as everyone first thought.

In the simplest terms, if you want to protect your self make sure you have a good random number generator with a high entropy source and allowing for entropy to build up in between generating your `P` and `Q` for your RSA key.

Each private key has one and only one public key. Anyone, regardless of resources could get access to many public keys as they are designed to be shared and in-fact, the whole system depends on the easy availability of public keys for a given private key.

To explain it another way, the purpose of a public key is simply to allow someone to know that the person they are communicating with holds the private key that corresponds to it. It can also be used to send information to the holder of the private key such that only they can decrypt the message.

The two keys are mathematically related and any change to one would require the other to change, so it isn't even possible to have a system with multiple public keys for the same private key, nor would there be any security benefit in it since public keys are not secret.