A design uses RSA-3072 and a colleague proposes a 256-bit elliptic curve instead. State the security level of each, explain the exponent difference in the best known attacks that produces that ratio…

Question

A design uses RSA-3072 and a colleague proposes a 256-bit elliptic curve instead. State the security level of each, explain the exponent difference in the best known attacks that produces that ratio, and give the operational consequences for a system signing 200,000 messages per second.

Accepted Answer

Both give roughly 128 bits of security, and the twelvefold size difference comes from factoring having a subexponential algorithm while the elliptic curve discrete logarithm problem has only generic square root attacks. The general number field sieve factors an integer n in time exponential in the cube root of log n, so the key must grow much faster than the security level: 2048 bits gives about 112 bits of security, 3072 gives 128, and 15360 is needed for 256. On a well chosen elliptic curve no subexponential algorithm is known, so the best attack is Pollard's rho at 2^(k/2) work for a k-bit group, meaning a 256-bit curve gives 128 bits and the key size is simply twice the security level. Operationally the curve wins on every axis that matters at 200,000 signatures per second: a signature is 64 bytes against 384, a public key is 32 bytes against 384, and signing is a single scalar multiplication of a few tens of microseconds rather than a modular exponentiation with a 3072-bit exponent. RSA keeps one advantage, which is that verification with a small public exponent is very cheap, so a workload dominated by verification rather than signing can still prefer it. Bandwidth matters too, since 320 extra bytes per message at that rate is 64 MB/s of pure overhead.