Mathematics
Public Key Cryptography and the Mathematics Behind RSA Encryption
Quick fact
RSA encryption uses a pair of keys—a public key for encrypting and a private key for decrypting—yet the security of the entire system rests on the fact that while multiplying two large prime numbers is easy, figuring out which two primes created a given product is computationally infeasible.
Why this is interesting
You've probably seen a padlock icon in your browser, but did you know that the security behind that tiny symbol relies on a centuries-old mathematical puzzle? How can we share a secret key without anyone else intercepting it?
Read the full explanation
Understanding Public Key Cryptography and the Mathematics Behind RSA Encryption
Imagine you want to send a secret message to a friend, but you can't meet in person to share a key. Traditional cryptography requires that both parties know the same secret key—but how do you get that key to your friend securely? Public key cryptography solves this by using two different keys: one that everyone can see (public key) and one that only the recipient knows (private key). The most famous public key system is RSA. It's like a locked mailbox with a slot: anyone can drop a letter through the slot (encrypt with public key), but only the person with the key to the mailbox can open it (decrypt with private key). The magic is that the public key is derived from the private key in a way that is mathematically easy to generate but incredibly hard to reverse. Specifically, RSA picks two large prime numbers, p and q, and multiplies them to get n. The public key is (e, n) and the private key is (d, n). The security relies on the difficulty of factorizing n back into p and q. While multiplying two primes is trivial, factoring their product is extremely slow for large primes. This asymmetry—easy one way, hard the other—is the foundation of RSA.
A deeper explanation
The heart of RSA is modular exponentiation. To encrypt a message M (treated as a number), you compute C = M^e mod n. To decrypt, you compute M = C^d mod n. These are simple operations, but why do they work? The trick is in the choice of e and d. We choose e and d such that e d ≡ 1 (mod φ(n)), where φ(n) is Euler's totient function: φ(n) = (p-1)(q-1). This relationship ensures that for any M relatively prime to n (which is almost all numbers, as n is huge), M^(ed) ≡ M (mod n) by Fermat's little theorem and the Chinese Remainder Theorem. The public key exponent e is typically a small number like 65537, and the private exponent d is computed using the Extended Euclidean Algorithm from e and φ(n). An attacker who knows n but not p and q cannot compute φ(n) easily, so they cannot derive d. The security of RSA thus reduces to the hardness of integer factorization—a problem that has resisted efficient algorithms for centuries, though quantum computing may change this in the future.