RSA Duplication Flaws: Prime, Exponent, and Modulus

Implementation flaws in RSA encryption make it less secure in practice than in theory.

RSA encryption depends on five 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. 2¹⁶ + 1, because this makes implementation faster. One study found that this exponent was used 99.5 percent 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.

Related Posts

• Factoring RSA numbers
• Economics, power laws, and password cracking

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