Mathematics
The Mathematics of Factorization and the RSA Cryptosystem
Quick fact
RSA encryption works because it's easy to multiply two large prime numbers, but factoring the resulting product is computationally infeasible for sufficiently large primes—the security of the system rests on this asymmetry.
Why this is interesting
You rely on a simple math trick every time you send a secure message online—but what makes that trick so hard to break? The same multiplication you learned in grade school is the key to modern cryptography.
Read the full explanation
Understanding The Mathematics of Factorization and the RSA Cryptosystem
Imagine you have two padlocks: one public and one private. In RSA, the public lock is the product of two large prime numbers. Anyone can lock a message with this public key, but only the person who knows the original primes can unlock it. This works because multiplying two primes is straightforward, but given the product, finding those primes is extremely difficult. The encryption process uses modular arithmetic—a kind of clock arithmetic—where numbers wrap around after reaching a certain value. The private key is derived from the prime factors, allowing the intended recipient to reverse the process efficiently.
A deeper explanation
RSA's security hinges on the factorization problem. The modulus N = p × q, where p and q are large primes, is made public, but p and q are kept secret. The encryption exponent e is chosen to be coprime to φ(N) = (p-1)(q-1), and the decryption exponent d is computed as the modular inverse of e modulo φ(N), meaning e·d ≡ 1 (mod φ(N)). By Euler's theorem, for any message m coprime to N, m^(e·d) ≡ m (mod N), so encryption followed by decryption returns the original message. Without knowing p and q, an attacker cannot compute φ(N) or d, so they must factor N to break the system. The difficulty of factoring large integers is the foundation of RSA's security, making it a practical trapdoor function.