[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Comparing Cryptographic Key Sizes II
Anonymous writes:
> Adam Back <[email protected]> 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<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`