From: Adam Back <aba@dcs.ex.ac.uk>
Date: Fri, 27 Jun 1997 07:03:05 +0800
To: cypherpunks@cyberpass.net
Subject: Re: Comparing Cryptographic Key Sizes II
In-Reply-To: <199706250645.IAA16548@basement.replay.com>
Message-ID: <199706261714.SAA00698@server.test.net>
MIME-Version: 1.0
Content-Type: text/plain




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`