Mathematics
The Mathematics of Public Key Cryptography and Digital Signatures
Quick fact
Bitcoin and many secure websites rely on a single mathematical concept: a function that is easy to compute in one direction but nearly impossible to reverse without a secret 'trapdoor.' For example, multiplying two large prime numbers is quick, but factoring their product is extremely hard—a 232-digit number has never been publicly factored.
Why this is interesting
You've used it every time you bought something online, but have you ever wondered how a website can prove its identity to your browser without sharing a secret password? The answer is pure math—the same math that lets you lock a box with a padlock anyone can close, but only you can open.
Read the full explanation
Understanding The Mathematics of Public Key Cryptography and Digital Signatures
Think of public key cryptography as a locked box with two keys: one to lock (the public key) and one to unlock (the private key). The public key can be shared with the world, but the private key is kept secret. This works because the math behind it creates a one-way function: something easy to do but hard to undo. For example, it's easy to multiply two large prime numbers (say, 17 and 23 to get 391), but given 391, it's hard to find those primes (aside from guessing). In reality, the primes are hundreds of digits long, making factoring impossible with current computers. Similarly, digital signatures use a mathematical trick: you can sign a message with your private key, and anyone can verify that signature using your public key. This proves you wrote the message (authenticity) and that it hasn't been altered (integrity). The magic is that signing and verifying are two sides of the same mathematical relationship, much like a lock and key.
A deeper explanation
The mathematical foundation of public key cryptography lies in modular arithmetic and the concept of a trapdoor function. A trapdoor function is a one-way function that becomes easy to invert if you have a piece of secret information (the trapdoor). For RSA, the most famous system, the operation is modular exponentiation: given a message m, compute c = m^e mod n, where e and n are the public key. n is the product of two large primes p and q. The public key (e, n) allows anyone to encrypt, but only someone who knows the private exponent d—computed from p and q—can decrypt because the inverse operation requires knowing φ(n) = (p-1)(q-1). The security relies on the factoring assumption: given n, it is computationally infeasible to find p and q. Digital signatures work similarly: a hash of the message is raised to the private exponent d, producing a signature s = h^d mod n. Verification checks if s^e mod n equals the hash. This works because modular arithmetic ensures (h^d)^e mod n = h^(de) mod n = h mod n, thanks to Euler's theorem, as long as de ≡ 1 mod φ(n). The security of RSA and Diffie-Hellman (which uses discrete logarithms) depends on the hardness of these problems. Post-quantum alternatives like lattice-based cryptography are designed to resist quantum attacks that threaten these classical problems.