Mathematics Behind Cryptography

The Mathematics Behind Cryptography: How Numbers Keep Secrets

A deep dive into the number theory, algebra, and computational hardness that make modern information security possible.

Cryptography is often described as an art, but at its core it is pure mathematics. Every time you send a message on WhatsApp, log into your bank, or see a padlock icon in your browser, a set of mathematical operations — rooted in number theory, algebra, and computational complexity — is working silently to keep that information private and authentic. This post walks through the major mathematical techniques that underpin modern cryptography, from simple modular arithmetic to the elliptic curves protecting Bitcoin wallets.

---

1. Modular Arithmetic: The Foundation

Almost all of cryptography is built on modular arithmetic — arithmetic that "wraps around" after reaching a certain value, much like a clock resets after 12. We write:

a ≡ b (mod n)

which means a and b leave the same remainder when divided by n. This structure is powerful because it creates a finite set of numbers {0, 1, 2, ..., n−1} that behaves consistently under addition, subtraction, and multiplication — a mathematical structure called a ring. When n is prime, this set even forms a field, meaning every nonzero element has a multiplicative inverse. This property is essential for encryption schemes that need to be reversible only when you know the secret key.

Why it matters: Modular exponentiation — computing a^b mod n — is fast to compute (via the "square-and-multiply" algorithm) but extremely hard to reverse without extra information. This asymmetry between "easy forward, hard backward" is the seed of nearly every public-key system.

2. Prime Numbers and Factorization — The Basis of RSA

The RSA algorithm, one of the most widely deployed public-key cryptosystems, rests on a simple but profound fact: multiplying two large prime numbers is computationally trivial, but factoring their product back into the original primes is extraordinarily difficult if the numbers are large enough (typically 2048 bits or more).

How RSA uses this:

• Choose two large primes p and q, and compute n = p × q.
• Compute Euler's totient function φ(n) = (p−1)(q−1), which counts integers less than n that are coprime to it.
• Pick a public exponent e such that gcd(e, φ(n)) = 1.
• Compute the private exponent d, the modular inverse of e mod φ(n), using the Extended Euclidean Algorithm.
• Encryption: C = M^e mod n. Decryption: M = C^d mod n.

The security guarantee comes directly from Euler's theorem, which states that for any integer a coprime to n: a^φ(n) ≡ 1 (mod n). This identity is exactly what makes encryption and decryption mathematically inverse operations, while an attacker who only knows n (not p and q) cannot compute φ(n) without factoring — a problem believed to require exponential time on classical computers.

3. The Discrete Logarithm Problem — Diffie–Hellman Key Exchange

A different class of hardness underlies the Diffie–Hellman key exchange: the discrete logarithm problem (DLP). Given a prime p, a generator g of a multiplicative group, and a value g^x mod p, it is computationally infeasible to recover x for large enough p — even though computing g^x mod p itself is fast.

This lets two parties, Alice and Bob, agree on a shared secret over an insecure channel without ever transmitting it directly:

• Both agree publicly on a prime p and generator g.
• Alice picks a secret a, sends A = g^a mod p.
• Bob picks a secret b, sends B = g^b mod p.
• Alice computes B^a mod p; Bob computes A^b mod p — both arrive at the same value g^ab mod p.

An eavesdropper sees only g, p, A, and B — recovering a or b requires solving the discrete log problem, which is believed to be intractable for well-chosen groups.

4. Elliptic Curve Cryptography (ECC)

Elliptic curve cryptography achieves the same security level as RSA but with dramatically smaller keys, by replacing modular multiplication with point addition on an elliptic curve defined as:

y² = x³ + ax + b (mod p)

Points on this curve form an abelian group under a geometrically defined addition rule (draw a line through two points; where it intersects the curve a third time, reflect over the x-axis). Repeatedly "adding" a point P to itself k times gives kP — fast to compute. But recovering k from P and kP, known as the Elliptic Curve Discrete Logarithm Problem (ECDLP), is even harder relative to key size than integer factorization or classical DLP. This is why a 256-bit ECC key offers security comparable to a 3072-bit RSA key — making ECC the backbone of modern protocols like TLS 1.3, Signal, and Bitcoin's ECDSA signatures.

5. Symmetric-Key Mathematics: Finite Fields and Substitution

While public-key cryptography relies on number-theoretic hardness, symmetric ciphers like AES (Advanced Encryption Standard) use a different branch of algebra: operations over the finite field GF(2⁸), where each byte is treated as a polynomial with binary coefficients. Key mathematical components include:

• Galois Field arithmetic: Byte substitution (the S-box) is built from multiplicative inverses in GF(2⁸), providing strong non-linearity that resists algebraic attacks.
• Linear algebra (MixColumns): Each column of the AES state is multiplied by a fixed matrix over GF(2⁸), diffusing changes across the entire block.
• XOR and permutation: Simple Boolean algebra (XOR) combines round keys with data, while permutation layers ensure that small input changes cascade unpredictably — a property called the avalanche effect.

Symmetric ciphers don't rely on "hard problems" in the number-theoretic sense; their security comes from the sheer size of the key space (2¹²⁸ or 2²⁵⁶ possibilities) combined with carefully engineered algebraic structure that resists linear and differential cryptanalysis.

6. Hash Functions: One-Way Mathematical Compression

Cryptographic hash functions like SHA-256 map arbitrary-length input to a fixed-length output using iterated compression functions built from modular addition, bitwise rotation, and Boolean logic. Their security rests on three mathematical properties:

• Preimage resistance: given a hash h, it should be infeasible to find any input m such that hash(m) = h.
• Second preimage resistance: given m, it should be infeasible to find a different m′ with the same hash.
• Collision resistance: it should be infeasible to find any two distinct inputs with the same hash — a problem tied to the birthday paradox, which shows that collisions can be found in roughly √(2ⁿ) attempts for an n-bit hash rather than 2ⁿ, motivating hash output sizes of 256 bits or more.

7. Digital Signatures: Combining Hashing and Public-Key Math

Digital signatures verify authenticity and integrity by combining several of the techniques above. In RSA signatures, a sender hashes a message, then encrypts the hash with their private key; anyone can verify it using the public key. In ECDSA (used in Bitcoin and TLS), the signature is generated using elliptic curve point multiplication combined with modular arithmetic over the curve's order, producing a pair (r, s) that can be verified without ever exposing the private scalar key.

8. The Quantum Horizon: Why the Math Is Changing

Shor's algorithm, if run on a sufficiently powerful quantum computer, could solve integer factorization and discrete logarithm problems in polynomial time — breaking RSA, Diffie–Hellman, and ECC as we know them. This has driven the development of post-quantum cryptography, built on different mathematical hardness assumptions believed to resist quantum attacks:

• Lattice-based cryptography: relies on the hardness of problems like Shortest Vector Problem (SVP) and Learning With Errors (LWE) in high-dimensional lattices.
• Code-based cryptography: based on the hardness of decoding random linear error-correcting codes.
• Hash-based signatures: security depends only on the properties of cryptographic hash functions, which are more quantum-resistant than number-theoretic problems.

NIST has already standardized several of these — CRYSTALS-Kyber for encryption and CRYSTALS-Dilithium for signatures — marking the beginning of a broad transition in applied cryptography.

---

Conclusion

Every layer of digital security — from a simple HTTPS connection to a cryptocurrency transaction — is ultimately an expression of mathematical asymmetry: operations that are easy in one direction and hard to reverse without a secret. Modular arithmetic, prime factorization, discrete logarithms, elliptic curves, finite fields, and hash functions each contribute a different flavor of "one-way" hardness. As quantum computing advances, the mathematics protecting our information is evolving once again, moving toward lattice and code-based problems designed to withstand the next generation of computational power.

Understanding these mathematical foundations doesn't just satisfy curiosity — it's essential for anyone building, auditing, or trusting the systems that protect our digital lives.