Crypto Math Demystified: No PhD Needed

The math you need for cryptography isn’t about finding the next prime number; it’s about properties of numbers and how to manipulate them efficiently and securely.

Let’s see some of this in action with a simplified example of the Diffie-Hellman key exchange, which is a foundational concept. Imagine Alice and Bob want to agree on a secret key without anyone eavesdropping on their initial communication. They can use a publically agreed-upon prime number p and a public base g.

Alice picks a secret integer a and computes A = g^a mod p. Bob picks a secret integer b and computes B = g^b mod p.

p = 23  # A prime number
g = 5   # A primitive root modulo p

alice_secret = 6
bob_secret = 15

alice_public = pow(g, alice_secret, p)  # 5^6 mod 23 = 8
bob_public = pow(g, bob_secret, p)    # 5^15 mod 23 = 19

print(f"Alice's public value: {alice_public}")
print(f"Bob's public value: {bob_public}")

# Alice computes shared secret: B^a mod p
alice_shared = pow(bob_public, alice_secret, p) # 19^6 mod 23 = 2

# Bob computes shared secret: A^b mod p
bob_shared = pow(alice_public, bob_secret, p)   # 8^15 mod 23 = 2

print(f"Alice's computed shared secret: {alice_shared}")
print(f"Bob's computed shared secret: {bob_shared}")

Notice how alice_shared and bob_shared are the same. An eavesdropper, Eve, sees p, g, A, and B. To find the shared secret, Eve would need to compute a from A = g^a mod p (the discrete logarithm problem) or b from B = g^b mod p. For large primes, this is computationally infeasible.

The core problem cryptography solves is making certain mathematical operations easy to do in one direction but incredibly hard to reverse. This is the essence of one-way functions. In our Diffie-Hellman example, exponentiation modulo a prime (g^x mod p) is easy. Finding the exponent (x) given g, p, and the result (g^x mod p) is the discrete logarithm problem, which is hard.

This reliance on hard problems is why number theory is central. You need to understand:

Modular Arithmetic: This is the bedrock. It’s about remainders after division. Operations like addition, subtraction, and multiplication behave predictably within a modulus. For example, (a + b) mod n = ((a mod n) + (b mod n)) mod n. Cryptography heavily uses this to keep numbers within manageable bounds and to build its "clockwork" systems. You’ll work with Z_n, the set of integers modulo n.
Prime Numbers: Their unique factorization property (the Fundamental Theorem of Arithmetic) is crucial. For example, RSA encryption relies on the difficulty of factoring large numbers into their prime components. Understanding primality testing and the distribution of primes is important.
Group Theory (specifically, cyclic groups): This provides the abstract framework for operations like modular exponentiation. A group (G, *) has a set G and an operation * that satisfies closure, associativity, has an identity element, and every element has an inverse. The set of integers modulo p under multiplication, excluding 0 (denoted Z_p^*), forms a group. Understanding its structure, like its generator (a primitive root), is key to algorithms like Diffie-Hellman and ElGamal.
Polynomials over Finite Fields: Many modern cryptographic algorithms, especially in symmetric encryption (like AES) and error correction codes used in public-key systems, use operations on polynomials whose coefficients are elements of a finite field (like GF(2^k)). This allows for efficient hardware implementations.

The "surprise" in cryptography’s math is that it’s not about finding exact solutions but about exploiting the computational difficulty of certain problems. The security of your encrypted message doesn’t come from a complex calculation that’s impossible to undo, but from a problem that’s just too hard for current computers to solve in a reasonable amount of time. The actual math is often very simple operations (like multiplication and exponentiation), but applied to enormous numbers where reversing them becomes intractable.

The next hurdle you’ll face is understanding how these number-theoretic problems are used to construct actual encryption schemes, like the ElGamal cryptosystem.