RSA Performance Anatomy: Why is 'Verification' Blazing Fast and 'Signing' Extremely Slow?

Source: Dev.to

Who decides the numbers?

The key‑pair creator (the owner of the key pair) decides the numbers.

Below is a detailed sequence that answers three common questions:

Roles

Technical Supplement

1. How is (d) (private key) calculated?

(d) is not a random number. It is the unique integer that satisfies

[ e \cdot d \equiv 1 \pmod{(p-1)(q-1)} ]

i.e. the modular multiplicative inverse of (e) modulo ((p-1)(q-1)).
Only the server, which knows the prime factors (p) and (q), can solve this equation using the Extended Euclidean Algorithm.

2. How is the public key ((e,n)) distributed?

Through a Digital Certificate (X.509). Inside the certificate you will find a structure similar to:

Certificate:
    Data:
        Subject Public Key Info:
            Public Key Algorithm: rsaEncryption
                RSA Public-Key: (2048 bit)
                Modulus: 00:C3:A7:1F:...:4D:

The binary exponentiation (square‑and‑multiply) algorithm used for RSA looks like this:

// If the current least‑significant bit is 1, multiply
if exponent % 2 == 1 {
    result = (result * base) % modulus
}

// Square the base for the next bit
base = (base * base) % modulus

// Shift right to process the next bit
exponent /= 2

return result

Recap of the RSA workflow

The heavy computation stays on the server (signing), while verification on the client is cheap. This asymmetry is why RSA‑based signatures can become a bottleneck on high‑traffic servers, prompting a shift toward ECDSA, whose verification is similarly cheap but whose signing is also far less CPU‑intensive.

RSA Verification vs. Signature Creation

Verification

[ \text{Verification} \equiv s^{e}\pmod n ]

• Public exponent (e) can be chosen arbitrarily (subject to security requirements).
• The value 65537 is conventionally used because it minimizes the cost of the binary exponentiation method.

Binary representation of 65537

[ 65537_{10}=10000000000000001_{2} ]

• Bit length: 17 bits
• Hamming weight (number of 1’s): 2 (the leading and trailing bits)

Binary exponentiation (Square‑and‑Multiply)

Only ≈ 17 modular multiplications are required, which is why RSA verification (and encryption with a public key) is blazing fast.

Why 65537 is “miraculous”

Signature Creation (Private‑Key Decryption)

[ \text{Signature} \equiv m^{d}\pmod n ]

• The private exponent (d) is not chosen arbitrarily.
• It must satisfy

[ e,d \equiv 1 \pmod{\phi(n)} ]

where (\phi(n)) is Euler’s totient function.

• For a 2048‑bit modulus, (d) is roughly the same size (≈ 2048 bits) and appears random.

Example (illustrative)

[ d \approx 1101011\ldots00110_{2} ]

• Bit length: ≈ 2048 bits (RSA‑2048)
• Hamming weight: ≈ 1024 (about half the bits)

Binary exponentiation for signing

Thus, signing is hundreds of times slower than verification.

“What if we made (d) small?”

Choosing a small‑weight (d) (e.g., making it as easy to compute as (e=65537)) would open the door to attacks such as Wiener’s attack or Boneh–Durfee attack, which can recover (d) from ((e,n)).
The security of RSA relies on (d) being a large, seemingly random integer; otherwise the private key can be derived without factoring (n).

Asymmetric Performance in TLS (SSL)

Because the server must perform the costly private‑key operation, many modern systems prefer ECDSA (Elliptic Curve Digital Signature Algorithm), which offers a much lighter server load (signature creation is fast, verification is slightly slower than RSA but still acceptable).

Summary: Who Holds What & What They Compute

Prover (e.g., Server) – “I am the principal”

Verifier (e.g., Client) – “Is the signature authentic?”

The asymmetric cost of RSA (fast verification, slow signing) is a fundamental design characteristic that influences protocol choices and motivates the adoption of elliptic‑curve alternatives.