How RSA Encryption Works: Public Key Cryptography Explained

The Problem RSA Solves

Symmetric encryption (like AES) uses the same key to encrypt and decrypt. This is fast, but how do two parties who have never met agree on a shared secret key? If they send the key over an untrusted network, an eavesdropper captures it.

Public-key cryptography solves this with a key pair: a public key that anyone can know and a private key that only you know. Data encrypted with the public key can only be decrypted with the private key — and vice versa.

The Mathematics of RSA

RSA (Rivest–Shamir–Adleman, 1977) is based on the difficulty of factoring large integers.

Key Generation

1. Choose two large prime numbers p and q
2. Compute n = p × q (the modulus)
3. Compute Euler's totient: φ(n) = (p−1)(q−1)
4. Choose e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1 (usually e = 65537)
5. Compute d as the modular multiplicative inverse of e mod φ(n): d × e ≡ 1 (mod φ(n))

Public key: (n, e)
Private key: (n, d) (keep p, q, d secret — destroy p and q)

Encryption and Decryption

To encrypt a message m:

C = m^e mod n

To decrypt ciphertext C:

m = C^d mod n

This works because of Euler's theorem: m^(e·d) ≡ m (mod n).

RSA Key Sizes

Larger keys are more secure but slower:

Key size	Security level	Recommended for
1024-bit	Broken	Do not use
2048-bit	~112-bit security	Current minimum for most uses
3072-bit	~128-bit security	Recommended for long-term data
4096-bit	~140-bit security	High-security applications

NIST recommends transitioning away from 2048-bit by 2030 for long-lived keys.

RSA in Practice: HTTPS

When your browser connects to an HTTPS site, it uses RSA (or increasingly, elliptic-curve key exchange) during the TLS handshake:

1. The server sends its public key (embedded in its SSL/TLS certificate)
2. The browser generates a random session key and encrypts it with the server's public key
3. Only the server (with its private key) can decrypt the session key
4. All subsequent traffic is encrypted with that fast symmetric session key (AES)

RSA is used only to securely exchange the AES key — not for bulk data encryption, because RSA is much slower than AES.

Digital Signatures: The Reverse Operation

RSA can also create digital signatures. The signer uses their private key to sign, and anyone with the public key can verify:

1. Compute a hash of the message: H = SHA256(message)
2. Sign: signature = H^d mod n
3. Verify: H' = signature^e mod n — if H' == SHA256(message), the signature is valid

This proves two things:

• The message was signed by the holder of the private key (authentication)
• The message has not been modified since it was signed (integrity)

Digital signatures are used in code signing, email (S/MIME), and package managers (npm, apt, etc.).

PEM Format

RSA keys are typically serialised in PEM (Privacy-Enhanced Mail) format — a Base64-encoded DER structure wrapped in header/footer lines:

-----BEGIN RSA PRIVATE KEY-----
MIIEowIBAAKCAQEA2a2rwplBQLF29amygykEMmYz0+Kcj3bKBp29Ca7fB88+
...
-----END RSA PRIVATE KEY-----

PKCS#8 format uses the headers BEGIN PRIVATE KEY and BEGIN PUBLIC KEY and is preferred for new keys as it is algorithm-agnostic.

RSA vs Elliptic Curve Cryptography

Elliptic Curve Cryptography (ECC) achieves equivalent security to RSA with much smaller keys. A 256-bit ECC key provides roughly the same security as a 3072-bit RSA key. ECC is faster, uses less bandwidth, and is now the default in most modern TLS connections (ECDHE key exchange).

However, RSA remains widely deployed for legacy compatibility and is still the standard for code signing certificates and some enterprise PKI systems.