Tell me more ×
IT Security Stack Exchange is a question and answer site for IT security professionals. It's 100% free, no registration required.
up vote 2 down vote favorite

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?

share|improve this question
2  
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

3 Answers

up vote 4 down vote

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.

share|improve this answer
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
up vote 2 down vote

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.

share|improve this answer
+one1eleventyone I love me an edge case. – Jeff Ferland♦ Dec 6 '12 at 2:31
up vote 0 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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