Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

This question already has an answer here:

My question is a bit naive, but what if someone generates the same RSA key pair as someone else? This person would have the same private key and so would be able to decrypt messages not intended to him.

I bet that the answer will be: “It is very unlikely”, but I would like a more persuasive answer to realize that it can't happen in practice.

A related question: when someone generates a key pair, how can he/she be sure that nobody has already generated this key pair? Would the answer again be, that it is “very unlikely”?

share|improve this question

marked as duplicate by e-sushi, DrLecter, otus, archie, mikeazo Jul 30 at 11:18

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
It is very unlikely if everything is done properly (i.e., a good random number generator is used). Unfortunately, it has happened in practice. See the Debian OpenSSL RNG bug also this paper which details other issues found in practice. –  mikeazo Jul 29 at 15:08
1  
Related question or possibly even a duplicate. –  mikeazo Jul 29 at 15:09
    
Cryptography is all about attacks being "very unlikely". Consider AES128 - the attacker can guess correctly with probability $2^{-128}$ with a single guess. The probability of colliding RSA keys is much smaller than that if you use perfectly random primes. –  CodesInChaos Jul 29 at 21:20
    
@CodesInChaos : $\;\;$ On the other hand, except for 3-prime 1024-bit RSA, I don't know of any way to give a mathematical proof that the "probability of colliding RSA keys is much smaller than that if you use" primes compatible at least one $\: e \in \{3,\hspace{-0.03 in}5,\hspace{-0.04 in}17\} \:$ or with $\: e = 257 \:$ specifically that are otherwise chosen perfectly at random. $\;\;\;\;\;$ –  Ricky Demer Jul 29 at 21:52

2 Answers 2

up vote 0 down vote accepted

The answer to both questions lies in understanding entropy, and how entropy is gathered to create a key. (And, of course, how well the implementation does so without bugs.) Each operating system creates and maintains a pool of entropy from which the entropy – also known as “randomness” – is tapped in the process of generating the key. Also, to the extent that you request a larger number of key bits, the larger the primes used to compute the keys and which would need to be factored as an attack. That’s why it is best to stick to RSA with 2048 bits (versus DSA with its limit of 1024).

So, to more specifically answer your question: if you assume that no one has made a mistake in coding the algorithms, then the first item that makes it likely not to generate a duplicate key is that the OS is sampling lots of states of different parts of itself to create the random numbers (entropy) to create the key.

As far as how likely, look at uniqueness of the RSA public modulus. Does $2^{2026}$ look big?

And if you really want to understand, this set of lecture notes (PDF) explains how random numbers from the OS entropy pool are used to compute the RSA primes $p$ and $q$, which are part of the public/private keypair and which would need to be factored to attack the algorithm. Section 12.3.1 of the Purdue lectures explain “Computational Steps for Selecting the Primes $p$ and $q$ in RSA Cryptography”.

share|improve this answer
    
More relevantly, does 2**2024.5 look big? $\;$ –  Ricky Demer Jul 29 at 22:30

if someone generates the same RSA key pair as someone else,

then ... someone will have the same RSA key pair as someone else.

when someone generates a key pair, how can he/she be sure that nobody has already generated this key pair?

The exact same ways he/she can generate any unique value.

Proof: Let the unique value be the key pair, or let the secret key be the empty string and let the public key be the unique value.

See GUID and UUID.

share|improve this answer

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