Slashdot Mirror
TWIRL: Are 1024-bit RSA Keys Unsafe?
This came across the
Interesting-People list
today: a
preliminary draft of a paper,
co-authored by Adi Shamir, that proposes new hardware for factoring large numbers. It is claimed that a machine could be built which would be "3-4 orders of magnitude more cost effective than the best previously published designs," and that "the NFS sieving step for 1024-bit RSA keys can be completed in less than a year by a $10M device." For background, here's a
primer
on key length in symmetric and asymmetric crypto.
In the extra reference Bruce Schneier says:
If 512-bit keys are insecure today, they were just as insecure last month. Anyone implementing RSA should have moved to 1024-bit keys years ago, and should be thinking about 2048-bit keys today...
IANAC(ryptographer), but I have done a little Number Theory at Cambridge (the real one, Turing, GCHQ, etc). The reason for these doublings is that the FFT (Fast Fourier Transform) requires a power of 2 (actually, the 2^N complex roots of 1).
On the other hand, a doubling in key length squares the size of the problem (at least until P=NP), so it seems odd to say that we need to move to 2048. After all, a single extra bit of key (theoretically) would compensate for Moore's Law. As the article points out, add 14 bits anyway.
Having said all that in explanation, my question is: How much difference does it make to use (e.g.) a 1280-bit key? Is it cheaper to implement this as a 2048 FFT, or could it be beneficial to do (perhaps) 9 256x256 and 1 1Kx1K multiplications and then add up? I am talking about the speed of 'legal' crypting as opposed to cracking here, obviously.