I consider RSA one of the most important algorithms in the history of computing, because it was the first practical public-key cryptosystem, meaning I can encrypt something with a publicly known key while only the holder of a separate private key can decrypt it. This solved a problem that had plagued cryptography for centuries: how do two parties who have never met exchange a secret key securely? RSA made secure communication over open channels like the internet possible, and it remains widely used today for encryption, digital signatures, and key exchange.
History and Background
I trace RSA to 1977, when Ron Rivest, Adi Shamir, and Leonard Adleman, three researchers at MIT, published the algorithm, and its name comes directly from their initials. What I find fascinating is that a similar idea had actually been discovered a few years earlier, in 1973, by Clifford Cocks, a mathematician working for the British intelligence agency GCHQ, but his work was classified and not revealed publicly until 1997. Rivest, Shamir, and Adleman built on ideas from Whitfield Diffie and Martin Hellman, who had introduced the concept of public-key cryptography in 1976 but had not yet found a full working implementation. RSA filled that gap and became the first widely deployed public-key algorithm, eventually forming the backbone of protocols like SSL/TLS, PGP, and SSH.
Problem Statement
The problem RSA solves is enabling two parties to communicate securely without first exchanging a shared secret key over a secure channel. Before public-key cryptography, if I wanted to send someone an encrypted message, we both needed to already share a secret key, which itself required a secure way to exchange that key in the first place, a chicken-and-egg problem. RSA solves this by using two mathematically linked keys: a public key that I can share with anyone, used to encrypt messages or verify signatures, and a private key that I keep secret, used to decrypt messages or create signatures. The security relies on the fact that multiplying two large prime numbers together is computationally easy, but factoring their product back into the original primes is computationally very hard.
Core Concepts
Terms I rely on throughout this explanation:
- Public key: a pair of numbers $(n, e)$ that anyone can use to encrypt a message intended for me or to verify my digital signature.
- Private key: a pair of numbers $(n, d)$ that only I know, used to decrypt messages encrypted with my public key or to sign messages.
- Modulus $n$: the product of two large prime numbers $p$ and $q$, which forms the basis of both keys.
- Euler’s totient function $\phi(n)$: counts the positive integers up to $n$ that are coprime to $n$; for $n = pq$, this equals $(p-1)(q-1)$.
- Coprime: two numbers that share no common factors other than 1.
- Modular exponentiation: raising a number to a power and taking the remainder after dividing by a modulus, the core operation used in both encryption and decryption.
How It Works
I break RSA into three phases: key generation, encryption, and decryption.
- Key generation: I choose two large distinct prime numbers, $p$ and $q$, and compute $n = p \times q$. I compute $\phi(n) = (p-1)(q-1)$. I choose a public exponent $e$ such that $1 < e < \phi(n)$ and $e$ is coprime with $\phi(n)$ (commonly 65537 is used). I compute the private exponent $d$ as the modular multiplicative inverse of $e$ modulo $\phi(n)$, meaning $d \times e \equiv 1 \pmod{\phi(n)}$. My public key becomes $(n, e)$, and my private key becomes $(n, d)$.
- Encryption: given a message $M$ (represented as an integer less than $n$), the sender computes ciphertext $C = M^e \bmod n$ using my public key.
- Decryption: I compute $M = C^d \bmod n$ using my private key to recover the original message.
Working Principle
The security of RSA rests on an asymmetry: computing $n = p \times q$ from two primes is fast, but recovering $p$ and $q$ from $n$ alone (factoring) is believed to be computationally infeasible for sufficiently large primes using classical computers. Because $d$ is derived specifically to be the inverse of $e$ modulo $\phi(n)$, and because $\phi(n)$ can only be efficiently computed if I know $p$ and $q$, an attacker who only sees the public key $(n, e)$ cannot easily derive $d$ without factoring $n$. The actual encryption and decryption operations rely on modular exponentiation, which I can compute efficiently even for very large numbers using the technique of repeated squaring, even though the numbers involved are hundreds of digits long.
Mathematical Foundation
Given two primes $p$ and $q$:
$$n = p \times q$$
$$\phi(n) = (p – 1)(q – 1)$$
I choose $e$ such that:
$$\gcd(e, \phi(n)) = 1$$
I compute $d$ such that:
$$d \times e \equiv 1 \pmod{\phi(n)}$$
Encryption:
$$C = M^e \bmod n$$
Decryption:
$$M = C^d \bmod n$$
The correctness of this scheme follows from Euler’s theorem, which states that for any integer $M$ coprime with $n$:
$$M^{\phi(n)} \equiv 1 \pmod n$$
Since $d \times e \equiv 1 \pmod{\phi(n)}$, I can write $d \times e = 1 + k\phi(n)$ for some integer $k$, so:
$$C^d = (M^e)^d = M^{ed} = M^{1 + k\phi(n)} = M \times (M^{\phi(n)})^k \equiv M \times 1^k \equiv M \pmod n$$
This confirms that decrypting an encrypted message always recovers the original message.
Diagrams
flowchart TD
A[Choose primes p and q] --> B["Compute n = p times q"]
B --> C["Compute phi(n) = (p-1)(q-1)"]
C --> D["Choose e coprime with phi(n)"]
D --> E["Compute d as inverse of e mod phi(n)"]
E --> F["Public key: (n, e)"]
E --> G["Private key: (n, d)"]Pseudocode
function RSA_KEYGEN(bit_length):
p = generate_large_prime(bit_length / 2)
q = generate_large_prime(bit_length / 2)
n = p * q
phi = (p - 1) * (q - 1)
e = 65537 // common choice, must be coprime with phi
d = modular_inverse(e, phi)
return public_key(n, e), private_key(n, d)
function RSA_ENCRYPT(message, n, e):
return modular_exponentiation(message, e, n)
function RSA_DECRYPT(ciphertext, n, d):
return modular_exponentiation(ciphertext, d, n)
function MODULAR_EXPONENTIATION(base, exponent, modulus):
result = 1
base = base mod modulus
while exponent > 0:
if exponent is odd:
result = (result * base) mod modulus
exponent = exponent >> 1
base = (base * base) mod modulus
return result
Step-by-Step Example
I like to use small numbers to make the arithmetic traceable by hand, even though real RSA uses numbers hundreds of digits long.
- I choose $p = 61$ and $q = 53$.
- I compute $n = 61 \times 53 = 3233$.
- I compute $\phi(n) = (61-1)(53-1) = 60 \times 52 = 3120$.
- I choose $e = 17$, since $\gcd(17, 3120) = 1$.
- I compute $d$ such that $17d \equiv 1 \pmod{3120}$, which gives $d = 2753$.
- My public key is $(3233, 17)$ and my private key is $(3233, 2753)$.
- Suppose I want to encrypt the message $M = 65$. I compute $C = 65^{17} \bmod 3233 = 2790$.
- To decrypt, I compute $M = 2790^{2753} \bmod 3233 = 65$, recovering the original message exactly.
Time Complexity
Key generation requires finding large prime numbers, and primality testing algorithms like Miller-Rabin run in roughly $O(k \log^3 n)$ time for a $k$-round test on an $n$-bit candidate, and I typically need to test several candidates before finding a prime, since primes become less dense as numbers grow, though still frequent enough in practice. Encryption and decryption both rely on modular exponentiation, which using repeated squaring runs in $O(\log e)$ or $O(\log d)$ multiplications, each multiplication on $b$-bit numbers costing roughly $O(b^2)$ with schoolbook multiplication or faster with optimized algorithms, giving an overall cost of about $O(b^2 \log e)$ per operation. Because $e$ is often small (like 65537), encryption is fast, while decryption, which uses the much larger $d$, is comparatively slower unless I apply the Chinese Remainder Theorem optimization.
Space Complexity
RSA’s space requirements are dominated by storing the key material itself: the modulus $n$, and the exponents $e$ and $d$, each of which is as large as the key size (commonly 2048 or 4096 bits today). This gives $O(b)$ space for a $b$-bit key, independent of the size of the message being encrypted, aside from the space needed to hold the message itself, which is also $O(b)$ per block since messages larger than $n$ must be broken into chunks or, more commonly in practice, RSA is used only to encrypt a smaller symmetric key rather than large data directly.
Correctness Analysis
I demonstrated the correctness of RSA mathematically above using Euler’s theorem: because $ed \equiv 1 \pmod{\phi(n)}$, raising a message to the power $e$ and then to the power $d$ modulo $n$ returns the original message. This holds for any message $M$ that is coprime with $n$, and can be extended to all messages using the Chinese Remainder Theorem even when $M$ shares a factor with $n$ (an edge case that essentially never occurs in practice given $n$’s primes are enormous and kept secret). The correctness therefore rests on solid number-theoretic foundations rather than heuristics, which is part of why RSA has remained trusted for decades.
Advantages
- I can share my public key openly without compromising security, solving the key distribution problem inherent in symmetric cryptography.
- RSA supports both encryption and digital signatures using the same underlying mathematics.
- Its security is based on a well-studied mathematical problem (integer factorization) that has resisted decades of attack attempts on well-chosen key sizes.
- It integrates naturally into hybrid cryptosystems, where RSA encrypts a symmetric key that then encrypts the bulk of the data.
Disadvantages
- RSA is significantly slower than symmetric ciphers like AES, so I would never use it directly to encrypt large amounts of data.
- Choosing weak or improperly generated primes, or reusing moduli across keys, can catastrophically break security, as has happened in real-world incidents.
- Quantum computers running Shor’s algorithm could, in principle, factor large numbers efficiently, which would break RSA entirely, motivating the ongoing shift toward post-quantum cryptography.
- Without proper padding schemes like OAEP, RSA is vulnerable to various mathematical attacks, so naive “textbook RSA” is not safe to use directly.
Applications
I see RSA used across the internet’s security infrastructure: in TLS/SSL for securing HTTPS websites, in SSH for secure remote login, in PGP and S/MIME for encrypting and signing emails, in digital certificates issued by certificate authorities, and in software code-signing to verify that a program has not been tampered with. It also underlies many secure messaging and file-sharing systems as part of a hybrid encryption scheme.
Implementation in C
#include <stdio.h>
#include <stdint.h>
/* Small-number RSA demonstration for educational purposes only.
Real RSA requires big-integer arithmetic libraries, since keys
are hundreds of digits long; this uses 64-bit values to keep the
demonstration self-contained. */
uint64_t modular_exponentiation(uint64_t base, uint64_t exponent, uint64_t modulus) {
uint64_t result = 1;
base = base % modulus;
while (exponent > 0) {
if (exponent & 1) {
result = (result * base) % modulus;
}
exponent >>= 1;
base = (base * base) % modulus;
}
return result;
}
int main() {
/* Using the small example from the walkthrough above */
uint64_t n = 3233;
uint64_t e = 17;
uint64_t d = 2753;
uint64_t message = 65;
uint64_t ciphertext = modular_exponentiation(message, e, n);
printf("Encrypted: %llu\n", (unsigned long long)ciphertext);
uint64_t decrypted = modular_exponentiation(ciphertext, d, n);
printf("Decrypted: %llu\n", (unsigned long long)decrypted);
return 0;
}
Sample Input and Output
Using the small example key from the walkthrough, with $n = 3233$, $e = 17$, and $d = 2753$, encrypting the message $65$ produces the ciphertext $2790$, and decrypting $2790$ with the private exponent recovers the original message $65$ exactly, confirming the round trip works correctly even though these are toy-sized numbers used purely for illustration.
Optimization Techniques
I rely on several well-known optimizations when using RSA in practice:
- Using the Chinese Remainder Theorem (CRT) during decryption, which lets me perform two smaller modular exponentiations (modulo $p$ and modulo $q$) instead of one large one modulo $n$, roughly a fourfold speedup.
- Choosing a small public exponent like $e = 65537$ (which has few bits set to 1 in binary), speeding up encryption and signature verification significantly.
- Using padding schemes such as OAEP for encryption and PSS for signatures, which are essential for security but also structured to avoid unnecessary computational overhead.
- Employing optimized big-integer libraries that use techniques like Karatsuba or Montgomery multiplication to speed up the underlying modular arithmetic.
Common Mistakes
I frequently see mistakes such as using “textbook RSA” without proper padding, which is vulnerable to a range of attacks including chosen-ciphertext attacks; generating primes that are too small or too close together, weakening the factorization difficulty; reusing the same prime across multiple keys, which allows an attacker who obtains two public moduli sharing a prime to factor both instantly using the GCD; and using an $e$ value shared across many recipients in a way that allows the Håstad broadcast attack when the same message is sent to several people. I also see confusion between RSA encryption (used for confidentiality) and RSA signatures (used for authenticity), which use the operations in opposite roles.
Further Reading
- Rivest, R., Shamir, A., and Adleman, L. “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems.” Communications of the ACM, 1978. https://people.csail.mit.edu/rivest/Rsapaper.pdf
- RSA Laboratories, PKCS #1: RSA Cryptography Standard. https://datatracker.ietf.org/doc/html/rfc8017
- NIST Special Publication 800-56B, Recommendation for Pair-Wise Key-Establishment Using Integer Factorization Cryptography. https://csrc.nist.gov/publications/detail/sp/800-56b/rev-2/final
- “Handbook of Applied Cryptography” by Menezes, van Oorschot, and Vanstone. https://cacr.uwaterloo.ca/hac/
