[145951] in cryptography@c2.net mail archive
Re: 2048 bits, damn the electrons! [rt@openssl.org: [openssl.org
daemon@ATHENA.MIT.EDU (Samuel Neves)
Fri Oct 1 18:35:09 2010
Date: Fri, 01 Oct 2010 19:27:52 +0100
From: Samuel Neves <sneves@dei.uc.pt>
To: cryptography@metzdowd.com
In-Reply-To: <20101001014122.GQ11550@np305c2n2.ms.com>
X-FCTUC-DEI-SIC-MailScanner-From: sneves@dei.uc.pt
On 01-10-2010 02:41, Victor Duchovni wrote:
> Should we be confident that 4-prime RSA is stronger at 2048 bits than
> 2-prime is at 1024? At the very least, it is not stronger against ECM
> (yes ECM is not effective at this factor size) and while GNFS is not
> known to benefit from small factors, is this enough evidence that
> 4-prime 2048-bit keys are effective?
>
It is slightly stronger than RSA-1024 against ECM, since ECM is then
performed modulo a 2048 bit value instead of a 1024 bit one. This slows
down arithmetic by a factor between 3 and 4 (Karatsuba vs Schoolbook
multiplication). Further, there are now 3 factors to find by ECM instead
of just 1.
Going by asymptotic complexities, factoring 4-prime RSA-2048 by NFS
should cost around 2^116 operations. Using ECM to find a 512-bit prime
costs around 2^93 elliptic curve group additions (add arithmetic cost
here). Factoring RSA-1024 by NFS costs around 2^80 operations.
Thus, I believe that 4-prime RSA-2048 is slightly easier than 2-prime
RSA-2048, but still significantly harder than RSA-1024.
Best regards,
Samuel Neves
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
