[82516] in Cypherpunks
Re: Comparing Cryptographic Key Sizes II
daemon@ATHENA.MIT.EDU (Adam Back)
Thu Jun 26 19:31:59 1997
Date: Thu, 26 Jun 1997 18:14:24 +0100
From: Adam Back <aba@dcs.ex.ac.uk>
To: cypherpunks@cyberpass.net
In-Reply-To: <199706250645.IAA16548@basement.replay.com> (nobody@REPLAY.COM)
Reply-To: Adam Back <aba@dcs.ex.ac.uk>
Anonymous writes:
> Adam Back <aba@dcs.ex.ac.uk> 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`
