Re: Comparing Cryptographic Key Sizes II

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