Implementation flaws in RSA encryption make it less secure in practice than in theory.
RSA encryption depends on 5 numbers:
- Large primes p and q
- The modulus n = pq
- Encryption key e
- Decryption key d
The numbers p, q, and d are kept secret, and the numbers e and n are made public. The encryption method relies on the assumption that in practice one cannot factor n into p and q.
All five numbers should be chosen anew for each certificate [1], but in practice numbers are sometimes reused.
Duplicate primes
The numbers p and q should be unique to each use of the method, but in practice there have been instances of duplicate primes, where two instances may have one of their two primes in common, which lets you factor the modulus using the Euclidean algorithm.
Duplicate encryption keys
The encryption key e does not need to be unique, or so we thought. In practice the encryption exponent e is usually 65537, i.e. 216 + 1, because this makes implementation faster. Once study found that this exponent was used 99.5% of the time. However, this allows an attack on RSA encryption if any of the bits of p or q can be recovered from computer memory. More on this here.
Duplicate moduli
The author of this post found several instances of certificates with shared moduli. One way this could happen is if a negligent certificate authority recycles p, q, and n, only generating new e and d pairs for each user. If you and someone else share a modulus n, you can use your (e, d) pair to factor n, and from knowing their public key e you can recover their private key d.
Duplicate moduli cannot happen by chance. As described here, the probability of having one shared prime due to random selection is roughly the probability of winning the Powerball jackpot 40 times in a row. The probability of having two shared primes due to random selection is inconceivably small.
More RSA posts
[1] Everyone agrees that p, q, and hence n should be unique. This also means that d will be unique. But there is disagreement over whether the exponent e should be unique, though reusing e does lead to a possible attack as described here.