This is an article in a series on Cryptography for the Everyday Developer. Follow along to learn the basics of modern cryptography and encryption.
Before the late 1970s, secure communication largely meant symmetric encryption. This included the complexity that comes with maintaining and sharing secrets every time two parties wished to communicate. RSA changed that by showing that encryption and decryption could use different keys, making secure communication practical for applications across the Internet.
In this post we’ll explore the basic mechanics of RSA, building on our understanding of the number theory required for public key cryptography.
Symmetric encryption is conceptually straightforward. You and I agree on a secret key and anything encrypted with that key can be decrypted with the same key. It’s exactly like locking and unlocking a safe — if both of us have copies of the same physical key, we both can open it. The trouble with symmetric encryption is figuring out how to exchange the key in the first place. How do Alice and Bob share a secret key without someone else seeing it? And how do they do that when they have never communicated before, or when they’re operating across a distributed and insecure network like the Internet? Safely distributing the key becomes the hardest part of the problem.
Asymmetric cryptography offers a different way to think about secrecy. Instead of sharing a single key, each person generates a pair of keys: one public and one private. The public key is designed to be shared widely. Anyone can use it to encrypt a message. But only the corresponding private key can decrypt the result. With this scheme, the key that needs protection — the private key — never leaves its owner’s control. Alice can encrypt messages destined to Bob using Bob’s public key, confident that only Bob, with his private key, can read them.
How RSA Works
RSA is built on number theory. Specifically, the properties of modular arithmetic and prime factorization. Although the underlying mathematics are deep, the high-level protocol is remarkably simple.
Let’s walk through the protocol, beginning with key generation.
How RSA Constructs a Key Pair
The process begins by choosing two large prime numbers, traditionally called \( p \) and \(q \). Modern implementations choose primes hundreds of bits long, usually around 512 bits each. The modulos, \( n \) is calculated as \( n = p \times q \), which is around 2048 bits. \( n \) is the public key that can be widely shared.
Given \( n \), we compute Euler’s totient function \(\phi(n)\). This is simply the product \(\phi(n) = (p - 1)(q - 1)\).
With the totient, \(\phi(n)\), we choose a value that can be shared publically. We select a number \(e\) that shares no common factors with \(\phi(n)\). Once \(e\) is chosen, we can compute \(d\), the private exponent, such that \( d \times e \equiv 1 \mod \phi(n) \).
The public key is the pair \( (n, e) \). The private key is the pair \( (n, d) \). What falls out of this process are two keys that are mathematically linked, but computationally difficult to determine without access to all computations along the way.
In summary, you can compute the key used for encryption with RSA by following these steps:
- Choose Two Large Primes
- Pick random prime numbers \(p\) and \(q\). Modern systems choose primes on the order of 512+ bits each.
- Compute the Modulus
- \( n = p \times q \)
- Compute Euler’s Totient
- \( \phi(n) = (p - 1)(q - 1) \)
- Choose a Public Exponent, \(e\), such that
- \(1 < e < \phi(n) \)
- \( \gcd(e, \phi(n)) = 1 \)
- Compute the Private Exponent, \( d \), such that
- \(d \times e \equiv 1 \mod \phi(n)\)
After these steps, we have:
- Public key = \( (n, e) \)
- Private key = \( (n, d) \)
If you aren’t sure about some of the properties of these formulas, or how to perform these calculations, you can learn about them in the previous post Number Theory for Public Key Cryptography.
Encryption and Decryption as Simple Exponentiation
With the keys in hand, RSA encryption and decryption are surprisingly simple. Encryption takes a message \(x\) and raises it to the power \(e \mod n\). In mathematical terms, the ciphertext is \(y = x^e \mod n\). Decryption mirrors this but uses the private exponent, so retrieving the original plaintext is as simple as \(x = y^d \mod n\).
This is the best part: despite the messy key generation, encryption and decryption are mechanically simple, we take modular exponentiation in both directions.
Given a message \(x \in {0, \ldots, n-1}\), and computing ciphertext \(y\):
Encryption becomes
$$ y = x^e \mod n $$
and decryption becomes
$$ x = y^d \mod n $$
Example
We can use a toy example with small numbers to make the process feel concrete. Assume that Alice wants to communicate with Bob. Bob first has to generate his public-private keypair, then share his public key. Afterwards, Alice can encrypt a message with Bob’s public key, and only Bob’s private key can decrypt the message.
Bob Generates Keys
- Choose two primes numbers:
- p = 3, q = 11
- Compute \(n = p \times q\)
- n = 33
- Compute \(\phi(n) = (p-1)(1-1)\)
- \(\phi(n) = (3-1)(11-1) \)
- \(\phi(n) = 20 \)
- Compute the public exponent \( e \) such that \(\gcd(e, \phi(n)) = 1\).
- \(e = 3\) since \(gcd(3, 20) = 1\)
- Compute the private exponent \( d \) such that \(d \times e \equiv
1 \mod \phi(n)\).
- \(d = 7 \) since \(3 \times 7 = 21 \equiv 1 \mod 20\)
Alice Encrypts a Message
For the sake of example, assume Alice sends the message \(x\) which is simply the number \(4\). The ciphertext \(y\) can be computed as:
$$ \begin{aligned} y & = x^e \mod n \cr y & = 4^3 \mod 33 \cr y & = 64 \mod 33 \cr y & = 31 \end{aligned} $$
Alice sends the message \(31\) to Bob.
Bob Decrypts the Message
With the ciphertext \(y = 31 \) in hand, Bob can compute the plaintext \(x\) as:
$$ \begin{aligned} x & = y^d \mod n \cr x & = 31^7 \mod 33 \cr x & = 27512614111 \mod 33 \cr x & = 4 \end{aligned} $$
And voilà, we get \(4\)!
Why RSA Is Hard to Break
The relevant insight to why RSA is hard to break is that all paths to recovering the private key flow through recovering ϕ(n). To compute ϕ(n), you need to know p and q. To find p and q, you need to factor n. And factoring large integers — on the order of 2048 bits — remains a computationally intractable task with classical computers.
That difficulty is the wall protecting RSA.
RSA is one of those ideas that feels almost magical the first time you encounter it. From two large primes and a bit of modular arithmetic, you get a system that allows strangers to exchange secrets over an open network without ever having met. But behind the magic is a clear structure: key generation rooted in number theory, encryption and decryption expressed as exponentiation, and performance made possible by efficient algorithms.