Essay on PGP as it is used today

[Robert J. Hansen]

> I went to an EFF (Electronic Frontier Foundation) meeting  and a big
> and tall guy came to me and told me that he had a way of Breaking PGP
> and told me he had been working on a database program that made this
> possible and spouted off terms I had never heard before.

Yeah, these conspiracy theorists always show up.

> I went back inside, and I couldn't find him. I had questions.

You're in the right place.

Mathematicians have come up with different ways to estimate how many
primes there were under a certain value -- what we call the prime
counting function, or "π(x)" in mathematicalese.  There are lots of ways
to do it, but they all give answers very close to each other: these are
estimates, not precise numbers.

The first estimate for π(x) was "x divided by the natural logarithm of x".

Let x be 100.  The natural log of 100 is about 4.6.  100 divided by 4.6
is about 22.  Thus, we expect there to be about 22 primes under 100.
There are in fact 25 -- so while this method isn't perfect it's
definitely enough to get us in the neighborhood.

If we do that same equation for a 2048-bit key, it turns out there are
10 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 different prime numbers that could go into it.

Google's total data storage is about 10 exabytes.  In 10 exabytes you
could store about 40 000 000 000 000 000 prime numbers.

There's just no way anyone on earth has a list of prime numbers that
they're trying one after another.  Not only isn't there enough hard
drive space, but the hard drives required would literally be bigger than
the entire Milky Way galaxy!