RSA question

[Joseph Ashwood]

--------------------------------------------------
From: "Sampo Syreeni" <decoy at iki.fi>
Subject: Re: RSA question

> 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. ;)

Actually it's a fairly straight forward calculation. Given the known 
computational requirements for a 512-bit factoring gives a scale multiplier 
for the asymptote for complexity of factoring, so it is a simple matter of 
using that scalar S in 2^256 = S*O(factoring n), then length of n is very 
close to 15360.

The cost-based analysis is really only valid at a single point in time, as 
technology progresses is does not do so smoothly. So while the lengths given 
by RSA were accurate at the time of their computation, they are no longer 
accurate and need to be reanalyzed.

The different approachs are very much like the difference between a sniper 
and a massive bomb to kill someone. Both will eliminate the target, but the 
bomb (NIST numbers) will have significant collateral damage, the sniper 
(cost based analysis) though you have to make sure you've got the right 
target.

For most purposes the best solution is something between a massive bomb and 
a sniper, just as for most cryptographic purposes your actual security 
equivalence will be somewhere between the old cost analysis numbers and the 
NIST numbers.
                    Joe 

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