[145813] in cryptography@c2.net mail archive
Re: RSA question
daemon@ATHENA.MIT.EDU (Francois Grieu)
Sun Sep 5 18:11:04 2010
Date: Sun, 05 Sep 2010 17:13:17 +0200
From: Francois Grieu <fgrieu@gmail.com>
To: cryptography@metzdowd.com, cryptography@randombit.net,
Victor.Duchovni@morganstanley.com
In-Reply-To: <20100904130737.GR7575@np305c2n2.ms.com>
[reposted with a correction, the log(2) factor]
On 04/09/2010 15:07, Victor.Duchovni@morganstanley.com apparently wrote:
> 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.
>
No. According to sources such as
<http://eprint.iacr.org/2010/006.pdf>
the effort to factor a number n bits is approximately proportional to
exp( (n*(log(2)*64/9+o(1)))^(1/3) * log(n*log(2))^(2/3) )
Any of the log(2), 64/9 and o(1) term change the effort estimate
way more than by a constant factor.
> So compared to 1k RSA bits, 16k RSA bits has a GNFS cost
> that is (16*1.96)^(1/3) ~ 3.15 times higher.
This is wrong well beyond the omission of the log(2)*64/9+o(1) term.
By application of the above formula with n=16384 and n=1024, and
expressing the ratio as a power of 2, I (now) get that the cost of
factoring 16 kbits RSA numbers would be approximately 2^190 times that
of factoring a 1 kbits RSA number if we neglect the o(1) term [and still
2^99 times, rather than 3.15 times, when omitting the (necessary)
log(2)*64/9+o(1) term].
> If 1k RSA bits is comparable to 80 symmetric bits, then
> 16k RSA bits is comparable to 80*3.15 or 252 bits.
One can't multiply key bit size by ratio of effort; we must instead
*add* the *logarithm* in base 2 of the ratio of effort.
We get that 16k bits RSA would be comparable to 80+219 = 270 bits
symmetric key if we neglect the o(1) term [80+114 = 179 bits when
omitting the log(2)*64/9+o(1) term].
Francois Grieu
[Wondering if the financial and engineering crisis may have to do with
how *we* do math]
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
