12
$\begingroup$
  1. What is the probability that two separate RSA public moduli are the same? For example, consider a 2048-bit modulus. The number seems to be huge, but the choice for prime factors p and q is much more restrictive: They both should be 1024-bit in size, not too close to $\sqrt{p*q}$ and the most significant bit should remain set. Even if $2^{1023}$ seems like a lot of numbers, not every integer in this set suits the RSA scheme.

  2. Since public exponent $e$ should be set to $0x010001$, if I find a collision for the RSA modulus, have I also found a collision for the RSA private exponent?

  3. Is it possible to treat the public RSA components (e.g. represented as $H(modulus, exponent)$) as a unique value for identification purposes?

$\endgroup$
1

2 Answers 2

13
$\begingroup$

If the RSA keys were generated randomly, then it is inconceivable that two different devices would happen to pick the same key.

Taking 2048 bit RSA keys as an example, there are approximately $2^{1014}$ 1024 bit primes; if we consider them pairwise (and realise that about half the pairs yield a 2047 bit number), that means there are about $2^{2026}$ RSA modulii possible.

This is an incredibly huge number. Even if we take into account the fact that the probability for generating each modulii isn't precisely the same (depending on the actual algorithm used), it'd be far more likely that you'd win the lottery 100 times in a row than two devices happen to pick the same RSA key.

On the other hand, examples of devices having the same RSA key have been seen. In this case, the problem wasn't that someone won the lottery 100 times; instead, they got the random part wrong.

An essential part of the above argument is that we pick them randomly; that is, we start with a 'random' value, and we use that value to select two primes. If two different devices start with the same 'random' value, and use the same algorithm to select the primes, they'll end up with the same RSA key.

So, to answer your question: whether you can assume that two different devices always have different keys, well, that depends on whether whoever did generate the keys had proper amounts of randomness (entropy) when doing so. If they did, you can certainly assume it; if they're broken, any such assumption is suspect.

$\endgroup$
2
  • 1
    $\begingroup$ Call me picky, but I get "only" about $2^{2024.5}$ possible modulii, considering the usual practice of generating the primes in range $[2^{1023.5}\dots2^{1024}]$ so that the product can't be one bit short, and that multiplication is commutative :-) $\endgroup$
    – fgrieu
    Commented Jun 25, 2013 at 17:21
  • 3
    $\begingroup$ @fgrieu: Ok, "you're picky". Well, yes, you did a more thorough analysis than I did (mostly in analyzing the number of 1024-bit primes; I was sloppy there); in any case, the number of possible modulii is far, far, far beyond what Naka needs to be concerned about; entropy is what he needs to worry about $\endgroup$
    – poncho
    Commented Jun 25, 2013 at 18:03
8
$\begingroup$

On point 1: the question worded, reduced to common practice, is equivalent to: assume that we generate $k=2$ RSA public keys with public modulii $N$ of $n=2048$ bits, with prime factors $p$, $q$ random in range $[2^{(n-1)/2}\dots2^{n/2}]$, and public exponent $e=2^{16}+1$; what are the odds that any two of the $k$ public keys $(N,e)$ are the same?

Applying the Prime Number Theorem, considering that primes $p$ such that $\gcd(p-1,e)\ne 1$ are to be ruled out, and that $e$ has been chosen prime, there are about $$v=(1-1/e)\cdot\Big({{2^{n/2}}\over{\ln({2^{n/2}})}}-{{2^{(n-1)/2}}\over{\ln({2^{(n-1)/2}})}}\Big)=(1-1/e)\cdot\Big({{2^{n/2+1}}\over{n}}-{{2^{(n+1)/2}}\over{(n-1)}}\Big)/\ln2$$ primes to choose among. There are approximately $v^2/2$ modulii to choose among (that holds even considering the stated constraint that the two primes are not so close to the square root of their product that Fermat factorization is a threat). The odds asked are thus about $k\cdot(k-1)/v^2$. That is, with $k=2$ and $n=2048$, less than $2^{-2024}$. Which is, beyond negligible.


It turns out that the question does not ask for something representative of the most acute risk of collision in key generation that would truly matter in a practical application, for at least two reasons:

  • It is enough that two RSA public keys share a common prime factor in their public modulii to be both breakable (their public modulii can be factored by computing their Greatest Common Divisor). That has odds about $k\cdot(k-1)/v$, or less than $2^{-1011}$. Which remains beyond negligible.
  • $k=2$ is unrealistic. Some serious applications of public key (e.g. passports) require public keys by the hundreds of millions. Fast forward a bit in the spread of Public Key crypto, and let us assume we assign an RSA key to each particle in the universe, which last time I checked are less than $k=2^{280}$. Now our odds are only less than $2^{-452}$. Which remains beyond negligible.

To illustrate that beyond negligible: odds of winning at a lottery where one must choose the right $6$ balls among $50$ are slightly better than $2^{-24}$. Odds of $2^{-452}$ is less than a million less than winning this lottery on each of $18$ attempts.


But wait: it does happen that two devices get public modulii sharing a common factor, and get broken. This is because the really difficult problem is building a dependable TRNG.


On point 2: Yes, should a collision occur on the public key $(N,e)$, there is a functional collision on the private key. All private keys pairs $(N,d)$ corresponding to the same public key $(N,e)$ yield exactly equivalent private key functions $x\mapsto x^d\bmod N$. However, there can be multiple distinct private key pairs $(N,d)$, for $d\equiv d'\pmod{\operatorname{lcm}(p-1,q-1)}$ implies that private key pairs $(N,d)$ and $(N,d')$ yield exactly equivalent private key functions. Even when $d$ is restricted to $n$ bits, there are at least $2$, sometime more equivalent $d$.


On point 3: Yes, $(N,e)$, or the hash of a suitable representation thereof as a bitstring, can be treated as a unique identifier (fixing $e$, or restricting its bit size to say $128$ bits at most, is enough to eliminate the concern of equivalent public exponents). It is even possible to embed (a suitable representation as a bitstring of) the name and unique ID of the key holder at a specified position in the public modulus $N$. That's easy up to about $n/2$ bits, and possible up to about $2\cdot n/3$ bits; see Marc Joye's RSA Moduli with a Predetermined Portion: Techniques and Applications. As an aside, it helps convincing peoples that do not trust math that everyone has a distinct key.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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