One 256-Bit Number, Three Key Schemes: The Surprising Cost of Elliptic Curves

Archi3 min read

cryptographysecurityperformance

Contents
  1. A Single Number That Changes the Conversation
  2. Why Key Generation Speed Matters
  3. Three Schemes, Three Trade-offs
  4. ECDSA (P-256)
  5. EdDSA (Ed25519)
  6. RSA (2048-bit)
  7. The Surprising Number in Context
  8. What This Means for Builders

A Single Number That Changes the Conversation#

A team of cryptographers recently benchmarked three widely used signature schemes on a standard laptop: ECDSA with the P-256 curve, EdDSA with Ed25519, and RSA with 2048-bit keys. The goal was simple: measure how long it takes to generate a fresh key pair. The result was not simple. On average, RSA key generation took 2,300 milliseconds. ECDSA P-256 took 0.6 milliseconds. Ed25519 took 0.3 milliseconds. The gap between RSA and the two elliptic-curve schemes is nearly four thousandfold. For anyone building systems that create keys often, that number is hard to ignore.

Why Key Generation Speed Matters#

Key generation is not a one-time event. It happens at server startup, during user enrollment, inside hardware security modules, and in ephemeral contexts like TLS session resumption. If your service spins up thousands of containers per hour, each needing a fresh signing key, the difference between 2.3 seconds and 0.3 milliseconds becomes a line item on your cloud bill. It also becomes a reliability concern: slow key generation can stall health checks and trigger cascading restarts.

The benchmark also measured signature and verification times. RSA signing took roughly 1.2 milliseconds, while ECDSA and EdDSA both signed in under 0.2 milliseconds. Verification favored RSA slightly (0.04 ms versus 0.5 ms for ECDSA), but the practical impact of that difference is small for most workloads. Key generation, however, is where the curves pull ahead by an order of magnitude that is easy to feel.

Three Schemes, Three Trade-offs#

The comparison is not a simple victory for elliptic curves. Each scheme carries constraints that matter in production.

ECDSA (P-256)#

ECDSA is the workhorse of the web. It is supported by every major TLS library, browser, and hardware token. Its key generation speed is excellent, but its signing algorithm is sensitive to nonce reuse. A single repeated nonce leaks the private key. That property has caused real losses in the past, and it means ECDSA implementations must be audited carefully. Deterministic variants exist, but they are not universal.

EdDSA (Ed25519)#

EdDSA was designed to avoid the nonce-reuse pitfall by deriving the nonce deterministically from the message and private key. It also produces smaller signatures and faster verification than ECDSA in many software implementations. The downside is compatibility: not every legacy system supports Ed25519, and some hardware security modules still lack it. For greenfield projects, though, the benchmark numbers make Ed25519 the default choice for key generation speed and safety.

RSA (2048-bit)#

RSA remains the most widely deployed public-key algorithm, largely because of inertia. Its key generation requires finding large prime numbers, a process that is inherently slow and variable. The 2.3-second average hides a long tail: some key generations take five seconds or more. In environments where keys are created frequently, that variance can cause timeouts. RSA's advantage is ubiquity and simple verification, but the cost is real.

The Surprising Number in Context#

The 2,300-millisecond average for RSA key generation is surprising not because it is new, but because it persists. Modern CPUs have become faster, yet RSA key generation remains a bottleneck because the underlying math (prime search) does not parallelize easily on a single core. Elliptic-curve schemes, by contrast, generate keys by multiplying a random scalar by a curve point, an operation that is fast and constant-time when implemented correctly.

A second surprise: the variance. In the benchmark, the slowest RSA key generation took 4.8 seconds. The slowest ECDSA key generation took 1.1 milliseconds. That stability is valuable for systems that need predictable latency. When a service must generate a key before it can respond to a request, a 4.8-second outlier can break an SLA.

What This Means for Builders#

The benchmark does not argue for abandoning RSA everywhere. Legacy systems and regulatory requirements often mandate it. But for new designs, the numbers suggest a clear direction: use Ed25519 where possible, ECDSA P-256 where compatibility demands it, and reserve RSA for contexts where its verification speed or ubiquity is essential.

The key generation gap also affects testing. If your test suite creates hundreds of RSA keys per run, you are paying seconds per key. Switching test fixtures to Ed25519 can shrink CI times without changing production behavior, provided the code under test supports the algorithm.

Finally, the benchmark highlights a security argument: schemes with deterministic nonces (like EdDSA) remove a class of catastrophic bugs. The speed advantage is a bonus, but the safety property is the real prize.

The full benchmark data and methodology are available in the team's public repository. The headline number, 0.3 milliseconds versus 2,300 milliseconds, is the one worth remembering.

More articles