RSA question

[Victor Duchovni]

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.

-- 
	Viktor.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com