RSA Encryption: The Math Inside Every Certificate

The One-Way Problem

RSA security comes from a single mathematical asymmetry:

Here is the simplest possible illustration:

17 × 19 = 323

Given only 323, could you find 17 and 19? Yes — in seconds. Now consider two prime numbers each 300 digits long. Their product is a 600-digit number. Finding the original primes from that product would take longer than the current age of the universe, even using the world's fastest supercomputers.

This is called the integer factorization problem, and it is the entire security foundation of RSA.

Key Generation

Generating an RSA key pair follows five steps. These steps happen when you run openssl genrsa, when your HSM creates a key pair, or when a CA initializes its root key.

Step 1 — Choose two large primes: p and q

In production, these are generated by a cryptographically secure random number generator (CSPRNG). They are typically 1024–2048 bits each, producing a combined modulus of 2048–4096 bits. The randomness of this step is critical — predictable primes have led to real-world key compromise in embedded devices.

Step 2 — Compute the modulus: n = p × q

n is the public modulus. It appears in both your public key and private key. For a 2048-bit RSA key, n is a 2048-bit number.

Step 3 — Compute Euler's totient: φ(n) = (p−1)(q−1)

φ(n) counts how many integers less than n are coprime to n. This value is used to derive the private exponent and is kept secret. Once n is published, φ(n) can only be computed by someone who knows p and q — which is why factoring n would break RSA.

Step 4 — Choose the public exponent: e

e must be coprime to φ(n). In practice, e = 65537 is used almost universally. It is prime, coprime to any valid φ(n), and its binary representation (10000000000000001) allows efficient modular exponentiation.

Step 5 — Compute the private exponent: d

d is the modular multiplicative inverse of e with respect to φ(n):

e × d ≡ 1 (mod φ(n))

This is computed using the Extended Euclidean Algorithm. The result d is your private key exponent.

Encryption and Decryption

With a key pair generated, the encrypt/decrypt operations are compact:

Encryption (anyone with the public key can perform this)

c = m^e mod n

Where m is the message (represented as an integer), e is the public exponent, and n is the modulus. The result c is the ciphertext.

Decryption (only the private key holder can perform this)

m = c^d mod n

Where c is the ciphertext, d is the private exponent, and n is the modulus. The result is the original message m.

The mod operation (modulo) returns the remainder after integer division. It is what makes this computation one-directional without d.

Why does this work?

Euler's theorem guarantees that for any m and the key pair (e, d, n):

m^(e×d) ≡ m (mod n)

Because e × d ≡ 1 (mod φ(n)) by construction, encrypting and then decrypting always returns the original value. The mathematical proof relies on the Chinese Remainder Theorem and is covered in any number theory textbook.

RSA in Your PKI Stack

X.509 Certificates

The public key (e, n) is stored in the Subject Public Key Info (SPKI) extension of your X.509 certificate. When you inspect a certificate:

openssl x509 -in cert.pem -text -noout | grep -A 10 "Public Key"

You will see the public exponent (e, almost always 65537) and the public modulus (n). The private key (d, n) is never in the certificate — it lives in a separate file (key.pem) or inside your HSM.

TLS Handshake (TLS 1.2)

In a TLS 1.2 handshake using RSA key exchange:

1. The server sends its X.509 certificate (containing the public key)
2. The client verifies the certificate chain using the CA's public key
3. The client generates a random pre-master secret
4. The client encrypts the pre-master secret using the server's public key: c = m^e mod n
5. The server decrypts it using the private key: m = c^d mod n
6. Both sides independently derive the session keys from the pre-master secret
7. The encrypted session begins

Digital Signatures

RSA is also used for signing, which works in reverse:

signature = hash(data)^d mod n    ← private key signs
verified  = signature^e mod n     ← public key verifies

The CA uses its private key to sign your certificate. Clients verify that signature using the CA's public key (embedded in the trusted root or intermediate cert). This is how the certificate chain is validated.

Key Ceremonies

The most sensitive RSA operation is not encryption or decryption — it is prime generation. Generating p and q for a CA root key is a high-security event because:

• The security of every certificate the CA ever issues depends on p and q remaining secret
• The operation cannot be repeated without issuing a new root and re-establishing trust
• Regulators require it to be witnessed, audited, and documented

A formal Key Ceremony controls this process: offline hardware, multiple trusted witnesses, roles assigned in advance, and an auditable record of every action. This is a requirement for WebTrust and ETSI certification.

What Can Go Wrong

Weak or predictable prime generation

If the CSPRNG used to generate p and q is seeded poorly, primes can be predicted or repeated across devices. In 2012, researchers factored a significant percentage of public RSA keys collected from the internet by exploiting shared prime factors — keys that had been generated on devices with insufficient entropy at boot time. Use a properly seeded CSPRNG. Use an HSM if generating CA keys.

Private key exposure

Missing or incorrect padding

Textbook RSA (as shown in this guide) is not directly used in production. Raw RSA without padding is vulnerable to several attacks. In practice:

• PKCS#1 v1.5 padding is used for backwards compatibility (but has known vulnerabilities — ROBOT attack)
• OAEP (Optimal Asymmetric Encryption Padding) is the current standard for encryption
• PSS (Probabilistic Signature Scheme) is the standard for signing

If you are implementing RSA in code, use a well-maintained cryptographic library and let it handle padding. Do not implement raw RSA.

Key size below 2048 bits

1024-bit RSA keys are considered broken by modern standards. NIST deprecated them in 2013. Most CAs no longer issue certificates with 1024-bit public keys. Use 2048-bit as a minimum; 4096-bit for long-lived CA keys.

The quantum horizon

Shor's algorithm, running on a fault-tolerant quantum computer, would solve the integer factorization problem efficiently — breaking RSA entirely. This is not an immediate threat; fault-tolerant quantum computers at the required scale do not yet exist. However, NIST published its first post-quantum cryptography (PQC) standards in 2024. If you are designing a PKI with a 10–20 year lifespan, PQC migration planning is worth including in your roadmap.

Key Takeaways

Related Guides