Mathematical Well-Maintained Cryptographic

The Mathematics Behind Cryptography: From Theory to Coded Algorithms

A practical walk-through of the number theory that powers modern encryption, with the algorithms coded out step by step.

---

1. Why Cryptography Is Really Just Applied Mathematics

Every lock in the digital world — from the padlock icon in your browser to the encryption on your phone — is built out of number theory, abstract algebra, and probability. Cryptography does not hide information by being clever with words; it hides information by exploiting mathematical problems that are easy to compute in one direction and extremely hard to reverse without a secret key. This asymmetry is called a trapdoor function, and almost every algorithm on this list is built around one.

Before looking at any algorithm, it helps to fix the handful of mathematical ideas that reappear constantly:

• Modular arithmetic — arithmetic that "wraps around" after reaching a fixed number (the modulus), the same way a clock wraps around after 12.
• Prime numbers and factorization — multiplying two large primes is fast; factoring the result back into those primes is (currently) computationally infeasible for large enough numbers.
• Discrete logarithms — given g^x mod p, finding x is hard even though computing the power itself is easy.
• Group and field theory — the structures (like elliptic curves) that let us define addition and multiplication in ways that keep these hard problems intact but make the numbers involved smaller.
• Entropy and randomness — the statistical unpredictability that keeps keys from being guessable.

2. Modular Arithmetic: The Engine Room

Almost nothing in cryptography works without the modulo operation. Formally, for integers a and n, we say a mod n is the remainder when a is divided by n. Two numbers a and b are congruent mod n if they leave the same remainder:

a ≡ b (mod n)   ⇔   n divides (a − b)

This single idea gives cryptography a finite, closed universe of numbers to work in (0 through n−1), which is exactly what's needed to build predictable, reversible operations on a computer with fixed-size integers.

Coded: Fast Modular Exponentiation

Nearly every public-key algorithm needs to compute something like a^b mod n where b can be hundreds of digits long. Doing this by repeated multiplication would take forever, so we use exponentiation by squaring, which reduces the number of multiplications from b down to roughly log₂(b).

def mod_pow(base, exponent, modulus):
    result = 1
    base = base % modulus
    while exponent > 0:
        if exponent % 2 == 1:            # if current bit is 1
            result = (result * base) % modulus
        exponent = exponent // 2         # shift right one bit
        base = (base * base) % modulus   # square the base
    return result

# Example: 7^560 mod 561
print(mod_pow(7, 560, 561))  # -> 1

3. Primes, GCD, and the Extended Euclidean Algorithm

Public-key cryptography leans heavily on prime numbers because their multiplicative structure is well understood but their factorization is not efficiently reversible at scale. Two supporting tools are essential:

Greatest Common Divisor (GCD), computed with Euclid's algorithm, tells us whether two numbers share no common factors (i.e., are coprime) — a requirement for choosing valid keys.

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

The Extended Euclidean Algorithm goes one step further: it finds the modular inverse of a number — the value that, when multiplied by the original number, gives 1 mod n. This inverse is exactly what RSA needs to turn a public key into a private key.

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = extended_gcd(b, a % b)
    x, y = y1, x1 - (a // b) * y1
    return g, x, y

def mod_inverse(e, phi):
    g, x, _ = extended_gcd(e, phi)
    if g != 1:
        raise Exception("No modular inverse exists")
    return x % phi

4. RSA: Public-Key Cryptography from First Principles

RSA (Rivest–Shamir–Adleman) is the clearest illustration of a trapdoor function built from number theory. Its security rests on this fact: multiplying two large primes p and q is trivial, but factoring their product n = p × q back into p and q is computationally infeasible when the primes are large (2048+ bits in practice).

The Math

1. Choose two large primes, p and q. Compute n = p × q.
2. Compute Euler's totient: φ(n) = (p − 1)(q − 1). This counts the integers less than n that are coprime to it.
3. Choose a public exponent e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1. Commonly e = 65537.
4. Compute the private exponent d as the modular inverse of e mod φ(n), i.e. d ≡ e⁻¹ (mod φ(n)).
5. Public key: (n, e). Private key: (n, d).
6. Encrypt: c = m^e mod n. Decrypt: m = c^d mod n.

The decryption works because of Euler's theorem, which guarantees that m^(e·d) ≡ m (mod n) whenever e·d ≡ 1 (mod φ(n)) — the exact relationship step 4 constructs.

Coded: A Minimal RSA Implementation

import random
from sympy import isprime, nextprime

def generate_prime(bits):
    n = random.getrandbits(bits)
    return nextprime(n)

def generate_keypair(bits=512):
    p = generate_prime(bits)
    q = generate_prime(bits)
    n = p * q
    phi = (p - 1) * (q - 1)

    e = 65537
    if gcd(e, phi) != 1:
        raise Exception("e is not coprime with phi, pick new primes")

    d = mod_inverse(e, phi)
    return (n, e), (n, d)   # public, private

def encrypt(public_key, message_int):
    n, e = public_key
    return mod_pow(message_int, e, n)

def decrypt(private_key, cipher_int):
    n, d = private_key
    return mod_pow(cipher_int, d, n)

# Demo
public, private = generate_keypair(512)
message = 42
cipher = encrypt(public, message)
plain = decrypt(private, cipher)
print(cipher, plain)  # plain -> 42

Note: This is a teaching implementation. Production RSA needs proper padding schemes (like OAEP), constant-time arithmetic to prevent timing attacks, and cryptographically secure prime generation — never roll your own crypto for real systems; use audited libraries.

5. Diffie–Hellman: Sharing a Secret Over an Open Channel

Diffie–Hellman solves a different problem than RSA: two parties who have never met agree on a shared secret over a public channel, without ever transmitting the secret itself. It relies on the discrete logarithm problem: given a prime p, a generator g, and g^x mod p, recovering x is computationally hard.

# Publicly agreed values
p = 23   # small prime, for demonstration only
g = 5    # generator

# Alice picks a private value
a = random.randint(1, p - 2)
A = mod_pow(g, a, p)     # Alice's public value

# Bob picks a private value
b = random.randint(1, p - 2)
B = mod_pow(g, b, p)     # Bob's public value

# Both compute the same shared secret independently
alice_secret = mod_pow(B, a, p)
bob_secret   = mod_pow(A, b, p)

assert alice_secret == bob_secret

An eavesdropper sees p, g, A, and B but cannot efficiently recover a or b — and therefore cannot compute the shared secret g^(ab) mod p.

6. Elliptic Curve Cryptography: Smaller Keys, Same Security

Elliptic Curve Cryptography (ECC) replaces the multiplicative group used in RSA/Diffie–Hellman with the group of points on an elliptic curve, defined over a finite field by an equation such as:

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

Points on this curve can be "added" together using geometric rules (drawing a line through two points, finding the third intersection, reflecting it), and this addition operation forms a mathematical group. The hard problem here is the Elliptic Curve Discrete Logarithm Problem: given a point P and Q = kP (P added to itself k times), finding k is infeasible. Because this problem is harder to attack per bit than integer factorization, ECC achieves the same security as RSA with far smaller keys (a 256-bit ECC key is roughly comparable to a 3072-bit RSA key), which is why it's now the default in TLS, SSH, and cryptocurrency wallets.

7. Symmetric Encryption: AES and the Algebra of Bytes

Where RSA and ECC use number-theoretic hard problems, symmetric ciphers like AES (Advanced Encryption Standard) use a different branch of algebra: operations over the finite field GF(2⁸), which treats each byte as a polynomial with binary coefficients. AES repeatedly applies four mathematical transformations across multiple rounds (10, 12, or 14 depending on key size):

• SubBytes — a non-linear substitution using an S-box derived from the multiplicative inverse in GF(2⁸), which resists linear and differential cryptanalysis.
• ShiftRows — a permutation that shifts bytes across rows of the state matrix.
• MixColumns — a linear transformation implemented as polynomial multiplication modulo a fixed irreducible polynomial, spreading influence across bytes (diffusion).
• AddRoundKey — a simple XOR with a subkey derived from the main key via a key-schedule algorithm.

Coded: The Core GF(2⁸) Multiplication

def gmul(a, b):
    """Multiply two bytes in GF(2^8) using AES's irreducible polynomial."""
    p = 0
    for _ in range(8):
        if b & 1:
            p ^= a
        high_bit_set = a & 0x80
        a = (a << 1) & 0xFF
        if high_bit_set:
            a ^= 0x1B   # AES irreducible polynomial: x^8 + x^4 + x^3 + x + 1
        b >>= 1
    return p

This finite-field multiplication is the mathematical core of AES's MixColumns step — swapping ordinary integer arithmetic for field arithmetic is exactly what gives the cipher its diffusion properties while remaining fast in hardware and software.

8. Hash Functions: One-Way Compression

Cryptographic hash functions (SHA-256, SHA-3) compress arbitrary-length input into a fixed-length digest such that the process is effectively irreversible, small changes cause drastically different outputs (the avalanche effect), and finding two inputs with the same output (a collision) is computationally infeasible. Mathematically, SHA-256 builds this from repeated rounds of modular addition, bitwise rotation, and XOR over 32-bit words:

def rotr(x, n, bits=32):
    return ((x >> n) | (x << (bits - n))) & 0xFFFFFFFF

def sigma0(x):
    return rotr(x, 7) ^ rotr(x, 18) ^ (x >> 3)

def sigma1(x):
    return rotr(x, 17) ^ rotr(x, 19) ^ (x >> 10)

# These mixing functions are applied across 64 rounds in SHA-256,
# combined with modular addition (mod 2^32) to build the message schedule.

In practice, always use a vetted library (Python's hashlib, for example) rather than a hand-rolled implementation — the value of coding it yourself is understanding the math, not deploying it.

import hashlib
digest = hashlib.sha256(b"hello world").hexdigest()
print(digest)

9. Putting It Together: A Small End-to-End Flow

A realistic secure message exchange typically layers several of these ideas rather than using just one:

1. Key exchange — Diffie–Hellman or ECC establishes a shared symmetric key.
2. Bulk encryption — AES encrypts the actual message using that shared key, since symmetric ciphers are far faster than public-key ones for large data.
3. Integrity — a hash-based MAC (HMAC-SHA256) ensures the ciphertext hasn't been tampered with.
4. Authentication — RSA or ECDSA digital signatures confirm the sender's identity using the same mathematical trapdoor ideas as RSA encryption, but in reverse: signing with the private key, verifying with the public key.

This layered approach — often called a hybrid cryptosystem — is exactly how TLS (the protocol behind HTTPS) works.

10. Further Reading

• Introduction to Modern Cryptography — Katz & Lindell (rigorous, textbook-level treatment of the number theory)
• Handbook of Applied Cryptography — Menezes, van Oorschot, Vanstone (freely available reference)
• NIST's FIPS 197 (AES) and FIPS 180-4 (SHA) specifications for exact algorithmic detail

All code samples above are simplified for clarity and educational use. Do not use hand-written implementations of RSA, AES, or SHA in production — always rely on audited, well-maintained cryptographic libraries.