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 majord...@metzdowd.com