The Mathematics Behind Cryptography (Conceptually)

Why Cryptography Seems Impossible

How can Alice send Bob a secret message when they have no shared secret and an eavesdropper Eve listens to all their communication?

Classically, this seems impossible. How can you publicly announce a key that only you and your recipient can use?

This is the paradox of public key cryptography: using public information to enable private communication.

How Traditional Encryption Works

Symmetric encryption (Caesar cipher, AES):

Alice and Bob share secret key K
Alice encrypts: ciphertext = message XOR K
Bob decrypts: message = ciphertext XOR K
Eve (without K) cannot decrypt

The problem: Alice and Bob must securely share K before they can communicate. This requires meeting in person or using a secure channel—expensive and impractical.

How Public Key Cryptography Works (The Magical Part)

RSA Algorithm:

Bob chooses two large prime numbers (p and q), each ~200 digits
Bob computes n = p × q (a 400-digit number)
Bob computes special exponents e (public) and d (private) using number theory
Bob publishes his public key: (n, e)
Bob keeps secret: d (and the factors p and q)

To encrypt a message m:

Alice computes: c = m^e mod n
Alice sends ciphertext c to Bob

To decrypt:

Bob computes: m = c^d mod n = (m^e)^d mod n = m
Bob recovers original message m

The Mathematical Trick: Why This Works

Fermat's Little Theorem and Euler's Theorem:

If n = p × q (product of two primes), then:

(m^e)^d ≡ m (mod n) ... if e×d ≡ 1 (mod φ(n))

Where φ(n) = (p-1)(q-1) is Euler's totient function—the count of numbers less than n that are coprime with n.

The security relies on factorization hardness:

Easy: Multiply two 200-digit primes → 400-digit number (seconds on computer)
Hard: Factor 400-digit number into two 200-digit primes (millions of years even with supercomputers)

The public exponent e allows encryption without revealing the secret d, because recovering d requires factoring n.

Elliptic Curve Cryptography: Alternative Approach

Instead of integer factorization, ECC uses discrete logarithm problem on curves:

An elliptic curve is a geometric curve defined by equation: y² = x³ + ax + b

Points on this curve can be "added" geometrically:

Take two points P and Q on the curve
Draw a line through them
Where the line intersects the curve again is P+Q

Repeating this operation (P+P+P+...+P, k times) gives k×P, which is easy to compute.

But finding k given k×P (the discrete logarithm problem) is hard.

Why ECC matters: ECC achieves same security as RSA with much smaller keys (256-bit ECC ≈ 2048-bit RSA), enabling efficient cryptography for mobile devices and embedded systems.

Why It's Secure (In Principle)

One-way functions:

Exponentiation is easy: Computing m^e mod n is polynomial-time (seconds)
Factorization is hard: Breaking n = p×q is exponential-time (millennia)
Asymmetry is crucial: Encryption should be easy, decryption should be easy with secret key, but decryption should be hard without secret key

This asymmetry is the mathematical foundation of public key cryptography.

What They Are Good At

RSA/ECC Applications:

TLS/HTTPS: Securing web communication (90% of internet uses this)
Digital signatures: Proving you signed a message without revealing signature process
Bitcoin/blockchain: Wallet security and transaction verification
VPN: Establishing secure tunnels
Email encryption: End-to-end secure communication

Common Myths

Myth 1: "Public key cryptography is weaker than symmetric encryption"

Reality: Both have different strengths. Symmetric is faster but requires secure key sharing. Public key is slower but solves the key distribution problem. Combined (hybrid cryptography), they're the foundation of modern security.

Myth 2: "Quantum computers will break all cryptography"

Reality: Quantum computers threaten RSA and ECC (which use factorization and discrete log problems), but quantum-resistant algorithms exist (lattice-based, hash-based, etc.).

Myth 3: "Mathematical elegance guarantees security"

Reality: Several historically-used cryptographic systems were mathematically elegant but broken later through clever attacks. Security requires ongoing evaluation.

Why Trending Now?

Post-quantum cryptography is urgent as quantum computers near practical capability. NIST is standardizing new algorithms immune to quantum attacks.

Lattice-based cryptography appears to be the leading post-quantum candidate, relying on hardness of shortest vector problem in high-dimensional lattices—a different mathematical foundation than integer factorization.

Conclusion

Cryptography exploits mathematical asymmetries: operations that are easy in one direction but hard in reverse, without knowing a secret. RSA's security rests on integer factorization difficulty. ECC's security rests on discrete logarithm difficulty. Both enable the modern internet's security, creating public key infrastructure that allows secure communication without prior secret sharing—a remarkable achievement of applied mathematics.