# Public key Issue - same key pair as existing one? [duplicate]

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”?

-

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

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
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

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”.

-
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.

-