2048 bits, damn the electrons! [rt at openssl.org: [openssl.org #2354] [PATCH] Increase Default RSA Key Size to 2048-bits]

Samuel Neves sneves at dei.uc.pt
Fri Oct 1 14:27:52 EDT 2010


 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 at metzdowd.com



More information about the cryptography mailing list