Q: Has a change taken place in factoring RSA keys?

[Bill Stewart]

>> In particular a claim was made that recent technology has come to
>> light that allows factoring of 1024 bit RSA keys at $1B (US)/day. The
>> basic gist was that
>
> Adi Shamir's TWINKLE, I guess.

I think that's the source as well - when the most recent of the
TWINKLE and TWIRL papers came out, Lucky Green was talking about
whether it was still safe to use 1024-bit keys,
and $1B for 1 key/day is similar to Shamir & Tromer's estimate of
            ( http://www.wisdom.weizmann.ac.il/~tromer/papers/cbtwirl.pdf )
$20M upfront plus $10M for a 1 key/year capacity.
     (The alternative is that it's people believing the usual FUD sources,
     whether they're the pro-government serious FUD sources or the
     fun-yanking-people's-chains clueless FUDsters.)

>> There was some discussion about hacking GPG to generate 8k keys.

But if 1024-bit keys are too weak, RSA is still near-exponential,
and 2048-bit keys are roughly 2**100 times harder to crack than 1024-bit,
vs. 4-8 times as slow to use.  4096 is a lot harder than that;
even if you allow for Moore's law and medium mathematical breakthroughs,
you're still not going to fit a 4096-bit cracker on the planet.

Basically, by the time you're interesting enough for them to spend
$10M and a year to crack your machine, you'd better be using 2048-bit keys
for tactical applications and maybe 4096-bit for long-term military secrets,
and since they're targeting YOU, it's a lot cheaper for them to
black-bag your PC or plant cameras in your ceiling or bribe your janitor.

> That won't help unless you find a way to get random number as good as
> the keysize.

Large random numbers aren't that hard if you're using them for
long-term signature keys, as opposed to DH or symmetric session keys;
it just takes a bit longer to generate the bits.
Also, once you're up above the 1024-bit range, incremental quality is
less important, because attacks on the keyspace are hard to combine
with factoring attacks on the keys, especially if you're whitening them.

But as you say, taking GPG from 4kbit to 8kbit keys doesn't matter,
because it's no longer close to the weakest link by then.