[145810] in cryptography@c2.net mail archive
Re: RSA question
daemon@ATHENA.MIT.EDU (Steven Bellovin)
Sat Sep 4 18:02:50 2010
From: Steven Bellovin <smb@cs.columbia.edu>
In-Reply-To: <20100904130737.GR7575@np305c2n2.ms.com>
Date: Sat, 4 Sep 2010 16:32:07 -0400
Cc: cryptography@metzdowd.com
To: Victor Duchovni <Victor.Duchovni@morganstanley.com>
On Sep 4, 2010, at 9:07 37AM, Victor Duchovni wrote:
> On Fri, Sep 03, 2010 at 07:16:00PM +0300, Sampo Syreeni wrote:
>=20
>> On 2010-09-02, travis+ml-cryptography@subspacefield.org wrote:
>>=20
>>> I hear that NIST Key Mgmt guideline (SP 800-57) suggests that the =
RSA key=20
>>> size equivalent to a 256 bit symmetric key is roughly 15360 bits. I=20=
>>> haven't actually checked this reference, so I don't know how they =
got such=20
>>> a big number; caveat emptor.
>>=20
>> I would imagine it'd be the result of fitting some reasonable =
exponential=20
>> to both keylengths and extrapolating, which then of course blows =
up...for=20
>> once *literally* exponentially. ;)
>=20
> 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
>=20
> exp(n^(1/3)*log(n)^(2/3))
>=20
> where "n" is the number of key bits.
>=20
> 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.
>=20
> 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".
>=20
> \lim_{n \to \infty} \frac{\mathrm{RSA}(n)}{n^3} =3D 0
>=20
> 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@metzdowd.com
