On Sep 4, 2010, at 9:07 37AM, Victor Duchovni wrote: > On Fri, Sep 03, 2010 at 07:16:00PM +0300, Sampo Syreeni wrote: > >> On 2010-09-02, travis+ml-cryptogra...@subspacefield.org wrote: >> >>> I hear that NIST Key Mgmt guideline (SP 800-57) suggests that the RSA key >>> size equivalent to a 256 bit symmetric key is roughly 15360 bits. I >>> haven't actually checked this reference, so I don't know how they got such >>> a big number; caveat emptor. >> >> I would imagine it'd be the result of fitting some reasonable exponential >> to both keylengths and extrapolating, which then of course blows up...for >> once *literally* exponentially. ;) > > Instead of imagining, one could look-up the brute-force cost of RSA > vs. (ideal) symmetric algorithms, and discover that while brute forcing > an ideal symmetric algorithm doubles in cost for every additional key > bit, GNFS factoring cost is approximately proportional to > > exp(n^(1/3)*log(n)^(2/3)) > > where "n" is the number of key bits. > > So compared to 1k RSA bits, 16k RSA bits has a GNFS cost that is > (16*1.96)^(1/3) ~ 3.15 times higher. If 1k RSA bits is comparable to 80 > symmetric bits, then 16k RSA bits is comparable to 80*3.15 or 252 bits. > > The mystery of the NIST numbers goes away, and one learns that the > "blowing-up" of RSA key sizes relative to symmetric key sizes is less > than cubic, and so definitely not "exponential". > > \lim_{n \to \infty} \frac{\mathrm{RSA}(n)}{n^3} = 0 > > where RSA(n) is the number of RSA bits to match an n-bit symmetric key.
Also see RFC 3766, which comes up with comparable numbers and several types of analysis. --Steve Bellovin, http://www.cs.columbia.edu/~smb --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com