Can the NSA Crack GnuPG

[Robert J. Hansen]

And what the heck, I can't sleep, so I'll give longer answers:

> Well I hope it was a joke! I went to an EFF meeting in San Francisco
> and this big guy came up to me and said he had a program that would
> would break PGP. Then Elvis left the building fast so I could not
> follow him fast enough although I really tried. IMHO an agent of the
> Illuminati or its branch arm, the NSA.

Why would they tell you?  And if you're the sort of person they'd tell,
why would you tell us?

> Cast doubts into the strength of 4096 or larger keys.

No, it really doesn't.

> I don't know how many prime numbers are possible between 2 bits (II
> binary = decimal 3) and 4096 bits = decimal a google maybe???)

There are about n/ln n primes less than n.

2**4096 = e**2839.

  e**2839       e**2839
----------- =  ---------
ln(e**2839)      2839

ln 2839 is approximately 8.

e**2839
------- = e**(2839 - 8) = e**2831.
 e**8

e**2831 / log(2) = 2**4084 = 10**1229.

There are about 10**1229 primes less than 4096 bits.

If you repeat this exercise again for how many primes there are less
than 4095 bits, then subtract one from the other, you'll get a solid
approximation for how many 4096-bit primes there are.  I'll leave that
as your homework and just tell you the answer: it still comes out to
pretty much the same number.

10**1229 is unimaginably huge.  By comparison, there are about 10**90
neutrinos in the universe.

> Now here's a question? If you had a chart showing every prime number 
> multiplied by every other prime number

Where do you plan on storing this chart?

You literally need to store it in a bigger universe than our current
one.  Our universe doesn't have enough matter or energy to make this chart.

> The man who disappeared said he authored a database program using
> arrays for non encryption uses but said it could break PGP.

People say lots of things.  And some people are cruel enough to
deliberately mislead people they feel will believe their nonsense.  I'm
not saying you're one of these cruel people; I'm saying he probably was.

> If it just pulled two numbers out of a hat, PGP would have to
> determine if the numbers were prime or not. Reverse factoring to test
> some very large numbers might take a very long time?

Miller-Rabin is a really nice primality checking algorithm.  AKS is
an even better one.  Factoring composite numbers is really hard;
figuring out if a number is composite is really easy.