Re: Comparing Cryptographic Key Sizes II
I can assure you that in moving from a 1024 bit key to a 4096 bit key, the attackers job is well in excess of 50x harder. Greatly in excess of a trillion trillion times harder.
First part true, second part false. See Schneier, p.160. Extrapolating using GNFS factoring indicates ratio of 1E21. If SNFS factoring becomes possible it is much worse, ratio less than one million.
Anonymous writes:
Adam Back
writes: I can assure you that in moving from a 1024 bit key to a 4096 bit key, the attackers job is well in excess of 50x harder. Greatly in excess of a trillion trillion times harder.
First part true, second part false. See Schneier, p.160. Extrapolating using GNFS factoring indicates ratio of 1E21. If SNFS factoring becomes possible it is much worse, ratio less than one million.
Schneier (the quote you give) gives this table (some values omitted):
# of bits MIPS-years required to factor
512 bits 3*10^4
1024 bits 3*10^11
1536 bits 3*10^16
2048 bits 3*10^20
How are you extrapolating that to 4096 bits? Hardness to break
increases as a superpolynomial function of the key size. The memory
requirements increase with key sizes, also, which I don't think these
figures are taking into account.
If someone would like to post the big O notation for GNFS space and
time complexity, plus current estimates of the constants, perhaps we
could improve upon that.
I reckon my estimate is conservative, if hardness relates to cost,
rather than mathematical number of operations ignoring memory
considerations.
Adam
--
Have *you* exported RSA today? --> http://www.dcs.ex.ac.uk/~aba/rsa/
print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0
participants (2)
-
Adam Back
-
nobody@REPLAY.COM