RSA question

[Steven Bellovin]

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-cryptography at 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 majordomo at metzdowd.com