RSA Algorithm Explained — How RSA Encryption and Signing Work

Key Takeaways

RSA security relies on the difficulty of factoring large numbers — the product of two primes is easy to compute but nearly impossible to reverse

RSA 2048-bit is the current minimum for certificates. RSA 4096 provides more margin but doubles the computational cost.

RSA is 10-100x slower than ECC for equivalent security — ECC P-256 matches RSA 3072 with 32-byte keys vs 384-byte keys

RSA key transport (encrypting the session key with RSA) has no forward secrecy — TLS 1.3 removed it entirely in favor of ECDHE

RSA (Rivest-Shamir-Adleman, 1977) is an asymmetric cryptographic algorithm based on the mathematical difficulty of factoring the product of two large prime numbers. Given two primes p and q, computing n = p × q is trivial. But given only n, finding p and q is computationally infeasible for sufficiently large values. This one-way property enables both encryption (encrypt with public key, decrypt with private key) and digital signatures (sign with private key, verify with public key).

Why it matters

Ubiquitous in TLS — the majority of TLS certificates in production today use RSA keys (2048 or 4096 bit). Every browser, server, and TLS library supports RSA.
Dual-use — RSA can both encrypt data and create digital signatures. ECC algorithms typically do one or the other (ECDSA for signatures, ECDH for key exchange).
Well-understood security — 47 years of cryptanalysis. The best known attack (General Number Field Sieve) is well-characterized, making key size recommendations reliable.
Being superseded — ECC provides equivalent security with much smaller keys and faster operations. TLS 1.3 removed RSA key transport. Post-quantum algorithms will eventually replace RSA entirely (RSA is vulnerable to Shor’s algorithm on quantum computers).
Key size growth — as computing power increases, RSA key sizes must grow. 1024-bit was broken in 2010. 2048-bit is the current minimum. 3072-bit is recommended for protection beyond 2030.

How it works

Key generation:
- Choose two large random primes: p, q (each ~1024 bits for RSA-2048)
- Compute n = p × q (the modulus — this is public)
- Compute φ(n) = (p-1)(q-1) (Euler’s totient — kept secret)
- Choose public exponent e (typically 65537)
- Compute private exponent d such that e × d ≡ 1 (mod φ(n))
- Public key: (n, e). Private key: (n, d).
Encryption: ciphertext = message^e mod n
Decryption: message = ciphertext^d mod n
Signing: signature = hash(message)^d mod n
Verification: hash(message) == signature^e mod n

In real systems

Generating RSA keys for TLS:

# Generate 2048-bit RSA private key
openssl genrsa -out server.key 2048

# Generate 4096-bit RSA key (more security margin, slower operations)
openssl genrsa -out server.key 4096

# Extract public key
openssl rsa -in server.key -pubout -out server.pub

# View key details
openssl rsa -in server.key -text -noout
# Shows: modulus (n), publicExponent (e=65537), privateExponent (d), primes (p, q)

RSA in TLS certificates:

# Check a certificate's key type and size
openssl x509 -in cert.pem -noout -text | grep "Public-Key"
# Output: RSA Public-Key: (2048 bit)

# CA/Browser Forum Baseline Requirements:
# Minimum: RSA 2048-bit
# Recommended: RSA 3072-bit or ECDSA P-256

RSA signature in certificate chain:

End-entity cert: signed with sha256WithRSAEncryption by Intermediate CA
Intermediate cert: signed with sha256WithRSAEncryption by Root CA
Root cert: self-signed with sha256WithRSAEncryption

Performance comparison (operations per second, typical server):

RSA-2048 sign:    ~1,000 ops/sec
RSA-2048 verify: ~30,000 ops/sec
RSA-4096 sign:      ~200 ops/sec
ECDSA P-256 sign: ~20,000 ops/sec
ECDSA P-256 verify: ~8,000 ops/sec

Where it breaks

RSA 1024-bit is broken — factored in 2010 using distributed computing. Any certificate or key still using RSA-1024 provides no meaningful security. Legacy systems (old embedded devices, IoT, mainframes) may still have 1024-bit keys. These must be identified and replaced — they’re equivalent to no encryption against a motivated attacker.

RSA key transport and forward secrecy — in TLS 1.2, one cipher suite mode encrypts the session key directly with the server’s RSA public key. If the server’s private key is later compromised (or subpoenaed), every recorded past session can be decrypted. TLS 1.3 eliminated this entirely — only ephemeral ECDHE key exchange is allowed, providing forward secrecy. If you’re still using RSA key exchange cipher suites (TLS_RSA_WITH_*), disable them.

Padding oracle attacks — RSA encryption requires padding (PKCS#1 v1.5 or OAEP). Bleichenbacher’s attack (1998) and its variants exploit servers that reveal whether decryption padding is valid. This allows an attacker to decrypt RSA-encrypted data by sending millions of modified ciphertexts and observing error responses. OAEP padding is resistant, but PKCS#1 v1.5 is still used in many implementations for backward compatibility.

Operational insight

RSA’s days are numbered on two fronts. Short-term: ECC (P-256, Ed25519) provides equivalent security with 10x smaller keys and 10-20x faster signing — making it strictly better for TLS performance. Long-term: quantum computers running Shor’s algorithm will factor RSA keys of any size in polynomial time. A 2048-bit RSA key that would take classical computers billions of years to factor could be broken in hours by a sufficiently large quantum computer. Organizations should be migrating to ECC now (for performance) and planning for post-quantum algorithms (ML-KEM, ML-DSA) for long-term security. New deployments should default to ECDSA P-256 unless RSA is specifically required for compatibility.

Key Takeaways

Why it matters

How it works

In real systems

Where it breaks

Operational insight

Related topics

Ready to Secure Your Enterprise?

Stay ahead on cryptography & PKI