"2. Al Qaeda uses 2048bit RSA for internal communications

3. Most corps, diplomats, criminals, and normal people use 2048bit RSA either directly (SSH keys, Website Certs, VPNs) or indirectly (CA's still use 2048bit RSA certs valid until 2020)"

I don't see how this is evidence that NSA has the ability to compromise 2048 bit keys, at will. Only that they very likely desire that ability. Math doesn't respond to desire.

That's not to say I believe they don't. Just that I can't accept two of your three premises for why one should believe they do.

Given rumor of NSA crypto breakthroughs and fact massive expenditures, it's not unreasonable to believe they've compromised a primary target.

> normal people use 2048bit RSA either directly (SSH keys, Website Certs, VPNs)

Any reason for that?

[Almost] all of my SSH and TLS (be it HTTPS or OpenVPN) keys are 4096 bits long.

I wasn't woried about TLAs with supercomputers snooping on my wires, just heard that 4096 bit RSA keys are considered more secure than 2048 while not sacrificing performance much, so I just didn't have the reason to specify lower size.

When a lot of these tools were first implemented, to get enough entropy, you would have to type and move your mouse for a long time to generate a 1024-bit key. I remember really, really hating that process.

Now, you kids these days with your entropy pools and PRNGs in your CPUs because you had an empty spot on the tape-out...get off my lawn!

    Any reason for that?

OpenSSL's default keylength is 2048? ssh-keygen uses 2048 by default.

The (public) factorization record with GNFS is 768 bits, in an effort that took about 2000 CPU years. 1024 bits is about 1000x harder, so probably within reach with government resources. 2048 bits is 10^12 times harder, which surely is out of reach for the time being time unless the NSA has a better algorithm.

Lenstra et al performed the factorization you cite, again on CPUs. Lenstra said in 2007 that he expected with in 5 years to be able to do 1024bit number - again with CPUs. 2048bit is no where near 10^12 harder if you use GPUs with larger word/op/register sizes. That's especially so with FGPAs/custom hardware with custom sized words/registers/ops. With FGPAs and custom hardware you can also locate things physically in places to give a speed advantage. I really don't think you'd need a replacement for GNFS to do a 2048bit number.

This isn't directed at you, but I wish people would stop talking about how strong crypto is if they haven't written software to break it, don't understand the mathematics, and don't understand hardware design. I just facepalm and shake my head when people post publicly that you'd have to boil the oceans to factor a 1024bit number (break a 1024bit RSA openPGP key).

10^12 is how much more work you have to do (according to the complexity estimate for the GNFS), regardless of how you do that work. If your custom-built hardware is 10^12 times faster than a general-purpose CPU, you can factor a 2048-bit number on your hardware as fast as a 768-bit number on general-purpose CPUs, but it will still take 10^12 times more work than factoring a 768-bit number on the same hardware. And I've never heard of GPUs or FPGAs giving a speedup of more than perhaps 10^4 on any problem, which still leaves a factor 10^8.

I think you're confusing complexity with difficulty. It may be 10^12 times more complex. But, if you're making your own FGPAs or chips and you can just use different word sizes or massively add more gates or processing cores. Or, even more specialized custom built super computers. The capabilities of what they're able to fabricate I think mitigate most of the protection provided by using 2048bit over 1024bit. It seems you need to be talking on the scale of at least 4096bit before the problem becomes intractable due to the limits of technology and the processing improvements that can be provided by custom hardware.

To put it in simple terms, doing operations with a 32bit numbers and a 64bit numbers have a calculable complexity gap. But, that gap means very different things in terms of difficulty on a 8bit microprocessor vrs a 32bit microprocessor vrs a 64bit microprocessor.

IIRC some piece of news surrounding all this stated that the NSA considers anyone using cryptography to protect their communications to be people of interest, whose dragnetted correspondence will be stored indefinitely. I'm curious if the NSA prioritizes these people according to how strong their keys are. I imagine that the logic would be that someone using 4096bit keys is either paranoid or really really has something to hide.

It's more of a sign that the user is au fait with computers. The sort of person with a 4096-key probably looks at the advanced settings to find the option, or carefully reads the manual.

I think it is a bit of a stretch to say that 2048 bit keys can be factored with NSA resources unless the NSA also has a more efficient algorithm than GNFS. However, it is also good to protect against potential future improvements over GNFS, so 3072 or 4096 bit RSA is still probably a good idea.