PGP Attack FAQ: What if...

This section of the PGP Attack FAQ discusses answers to frequently-asked "but what if" type of questions.

What if... my secret key was compromised?

A PGP secret key is kept conventionally encrypted with IDEA. Assuming your passphrase is secure enough the best method of attack will be a brute force key-search. If an attacker could test 1,000,000,000,000 keys per second, it would take 1x1017 years before the odds will be in the attacker's favor...

What if... PGP ran out of primes?

There are an infinite amount of prime numbers. The approximate density of primes lesser than or equal to n is n/ln(n). For a 1024-bit key, this yields:

1.8*10308/ln(1.8*10308) = 2.5*10305

There are about 2.5*10228 times more prime numbers smaller than 21024 than there are atoms in the universe...

What if... someone just listed all the prime numbers?

If you could store 1,000,000 terabytes of information in a device that weighs 1 gram, (and we figure each number fits in a space of 128 bytes or less) we would need a device that weighs 3.2*10289 grams or 7*10286 pounds. This is 1.6*10 256 times more massive than our sun. Nevermind the fact that we don't have enough matter to even concieve of building such a device, and if we could, it would collapse into a black-hole...

Even worse, to do a brute force attack with all these numbers, the attacker needs to try out every pair of prime numbers. There are 2.5E305(2.5E305-1)/2 possible pairs. This is 3.12*10610 combinations. Absurd, isn't it?

What if... PGP chose composite numbers instead of primes?

The likelyhood of the Fermat Tests of passing a composite off as a prime is 1 in 1052. If PGP could generate 1,000,000,000,000 primes per second, It would take about 1032 years until odds are better than even for that to happen.