The Math Behind Cryptography

Easy one way, hard the other way

The page Cryptography Basics explains what asymmetric encryption, key pairs, hashes and signatures are for. This page shows the mathematics underneath. It all depends on a handful of operations that are quick to compute but, as far as anyone knows, infeasible to undo without a secret:

• Multiplying versus factoring. 61 × 53 = 3233 is one multiplication. Going back from 3233 to 61 and 53 means searching for a divisor. For small numbers that is quick; for a number of 617 decimal digits (2048 bits), no known method on a classical computer finishes in any useful time.
• Modular exponentiation versus the discrete logarithm. Computing 5⁶ mod 23 = 8 is easy. Being told "5 to the power what gives 8, modulo 23?" is hard when the modulus is huge, because the results of modular powers jump around without a visible pattern.

The building blocks come from earlier pages: modular arithmetic (working with remainders) and primes and the greatest common divisor. "Hard" here is a belief backed by decades of public research, not a mathematical proof — which is why key sizes are reviewed regularly.

Modular exponentiation

Modular exponentiation is computing b^e \bmod n: the remainder of a base b raised to an exponent e after division by a modulus n. In real cryptography all three numbers have hundreds of digits, so the power itself, b^e, would have more digits than there are atoms in the universe. Two tricks make it fast anyway.

Trick 1: reduce as you go. Remainders can be taken after every multiplication without changing the final answer: (x \cdot y) \bmod n = ((x \bmod n) \cdot (y \bmod n)) \bmod n. The numbers never grow beyond n^2.

Trick 2: square and multiply. Instead of multiplying by b again and again, square repeatedly: b, b^2, b^4, b^8, \dots Each squaring doubles the exponent, and any exponent is a sum of powers of two — its binary digits.

Worked example: square and multiply

Compute 5^6 \bmod 23.

1. Write the exponent in binary: 6 = 110₂ = 4 + 2.
2. Square repeatedly, reducing mod 23 each time: 5^1 = 5; 5^2 = 25 \bmod 23 = 2; 5^4 = 2^2 = 4.
3. Multiply the powers that the binary digits select (4 and 2): 5^6 = 5^4 \cdot 5^2 = 4 \cdot 2 = 8.

A second one, 5^{15} \bmod 23: 15 = 1111₂ = 8 + 4 + 2 + 1. Square once more: 5^8 = 4^2 = 16. Then 16 \cdot 4 \cdot 2 \cdot 5 = 640, and 640 mod 23 = 640 − 27 × 23 = 640 − 621 = 19.

The number of steps grows with the number of bits in the exponent, not with the exponent itself. Python's built-in three-argument pow(b, e, n) uses this method; the function below spells it out and counts the work:

def power_mod(base, exponent, modulus):
    result, steps = 1, 0
    for bit in bin(exponent)[2:]:            # binary digits, left to right
        result = result * result % modulus   # square
        steps += 1
        if bit == "1":
            result = result * base % modulus # multiply
            steps += 1
    return result, steps

print(power_mod(5, 6, 23), pow(5, 6, 23))
print(power_mod(5, 15, 23), pow(5, 15, 23))

e = 65537                                    # the usual RSA public exponent
print(bin(e), e.bit_length(), "bits")
print(power_mod(65, e, 3233)[1], "steps instead of", e - 1, "multiplications")

big = 3 ** 1290                              # an exponent of about 2,000 bits
print(big.bit_length(), "bits:", power_mod(7, big, 2 ** 2048 - 159)[1], "steps")

(8, 5) 8
(19, 8) 19
0b10000000000000001 17 bits
19 steps instead of 65536 multiplications
2045 bits: 3079 steps

A 2,000-bit exponent costs a few thousand multiplications: milliseconds for a computer. Multiplying one by one would take more steps than any computer could ever perform. That gap between "easy" and "impossible" is the heart of public-key cryptography.

Modular inverses

In ordinary arithmetic, the inverse of 4 is ¼, because 4 × ¼ = 1. Modular arithmetic has no fractions, but it can have inverses too. A modular inverse of a modulo n is a whole number x with a \cdot x \equiv 1 \pmod{n}: multiplying by it "undoes" multiplying by a. The inverse of 3 modulo 11 is 4, because 3 × 4 = 12, and 12 mod 11 = 1.

An inverse exists exactly when a and n have no common factor other than 1, that is, \gcd(a, n) = 1. (6 has no inverse modulo 9: 6 × x is always a multiple of 3, so it can never leave a remainder of 1 after dividing by 9.) It is found with the extended Euclidean algorithm, which runs the Euclidean algorithm for the gcd and then works backwards.

Worked example: the inverse of 17 modulo 3120

1. Divide: 3120 = 183 × 17 + 9.
2. Divide the divisor by the remainder: 17 = 1 × 9 + 8.
3. Again: 9 = 1 × 8 + 1. The last nonzero remainder is 1, so the gcd is 1 and an inverse exists.
4. Work backwards from the last line: 1 = 9 − 8.
5. Replace the 8 using line 2 (8 = 17 − 9): 1 = 9 − (17 − 9) = 2 × 9 − 17.
6. Replace the 9 using line 1 (9 = 3120 − 183 × 17): 1 = 2 × 3120 − 366 × 17 − 17 = 2 × 3120 − 367 × 17.
7. Modulo 3120 the multiple of 3120 disappears: −367 × 17 ≡ 1. A negative inverse is fine, but the usual answer lies between 0 and 3119: −367 + 3120 = 2753.
8. Check: 17 × 2753 = 46,801 = 15 × 3120 + 1. Correct.

Since Python 3.8, pow with exponent −1 does this in one call:

import math

print(pow(3, -1, 11))
print(pow(17, -1, 3120), 17 * 2753 % 3120)
print(math.gcd(6, 9))
try:
    pow(6, -1, 9)
except ValueError as error:
    print("ValueError:", error)

4
2753 1
3
ValueError: base is not invertible for the given modulus

Toy RSA, step by step

RSA, named after Ron Rivest, Adi Shamir and Leonard Adleman (1977), uses one more ingredient. Euler's totient function \varphi(n) (phi of n) counts the whole numbers from 1 to n that have no common factor with n. For 15, those are 1, 2, 4, 7, 8, 11, 13 and 14, so \varphi(15) = 8. For a prime p every smaller positive number qualifies, so \varphi(p) = p - 1, and for a product of two different primes:

Check with 15 = 3 × 5: (3 − 1)(5 − 1) = 2 × 4 = 8. The formula is only easy to use if you know p and q; from n alone you would have to factor it first. That is the trapdoor.

Making a key pair and sending a message

1. Choose two primes (secret): p = 61, q = 53.
2. Multiply them: n = 61 \cdot 53 = 3233. This modulus is public.
3. Compute \varphi(n) = 60 \cdot 52 = 3120 (secret).
4. Choose a public exponent e with \gcd(e, 3120) = 1: here e = 17. Real keys almost always use e = 65537.
5. Compute the private exponent: the modular inverse of 17 modulo 3120, d = 2753 (worked out above).
6. The public key is (n, e) = (3233, 17); the private key is d = 2753. The primes and \varphi(n) are no longer needed and must stay secret.
7. To encrypt the message m = 65 (a number smaller than n), anyone computes c = m^e \bmod n = 65^{17} \bmod 3233 = 2790.
8. Only the key owner can decrypt: m = c^d \bmod n = 2790^{2753} \bmod 3233 = 65.

import math

p, q = 61, 53                    # secret primes (toy size!)
n = p * q
phi = (p - 1) * (q - 1)
e = 17
d = pow(e, -1, phi)
print(n, phi, d, e * d % phi)

m = 65
c = pow(m, e, n)                 # encrypt with the public key (n, e)
print(c, pow(c, d, n))           # decrypt with the private key d

lam = math.lcm(p - 1, q - 1)     # the standard (RFC 8017) uses lambda(n)
d2 = pow(e, -1, lam)
print(lam, d2, pow(c, d2, n))

3233 3120 2753 1
2790 65
780 413 65

Why does decryption give the message back? Because e \cdot d \equiv 1 \pmod{\varphi(n)}, raising to the power e and then to the power d amounts to raising to the power 1 + k \cdot \varphi(n) for some whole number k, and a theorem of Euler says that such a power brings you back to m modulo n. Textbooks use \varphi(n); the RSA standard (RFC 8017) uses the smaller \lambda(n) = \operatorname{lcm}(p - 1, q - 1), which gives a different but equally working private exponent (413 instead of 2753, as the last line shows).

Why it is secure — and why the toy is not

Everyone knows n and e. To find d, an attacker needs \varphi(n), and for that the factors of n. For 3233, trying divisors up to √3233 ≈ 57 takes a moment:

n, e, c = 3233, 17, 2790         # everything an eavesdropper sees

factor = next(k for k in range(2, n) if n % k == 0)
p, q = factor, n // factor
d = pow(e, -1, (p - 1) * (q - 1))
print("factors:", p, q, " private key:", d, " message:", pow(c, d, n))

factors: 53 61  private key: 2753  message: 65

Real RSA moduli have 2048 bits or more, and the best known factoring methods are hopeless at that size on classical computers. Real RSA also never encrypts a message number directly as above ("textbook RSA"): that is deterministic (the same message always gives the same ciphertext) and has other known weaknesses. Standard RSA wraps the message in randomized padding first — OAEP for encryption, PSS for signatures, both defined in RFC 8017.

Toy Diffie–Hellman

Diffie–Hellman key exchange, published by Whitfield Diffie and Martin Hellman in 1976, lets two parties agree on a shared secret over a channel that anyone can listen to, without ever sending the secret itself. The shared secret then becomes the key for fast symmetric encryption. In the original form both sides agree publicly on a large prime p and a base g:

1. Public: p = 23, g = 5.
2. Alice picks a secret a = 6 and sends A = g^a \bmod p = 5^6 \bmod 23 = 8.
3. Bob picks a secret b = 15 and sends B = g^b \bmod p = 5^{15} \bmod 23 = 19.
4. Alice computes B^a \bmod p = 19^6 \bmod 23 = 2.
5. Bob computes A^b \bmod p = 8^{15} \bmod 23 = 2.

Why do both arrive at the same number? Because of the power rule (x^a)^b = x^{ab} = (x^b)^a, which still holds after reducing modulo p:

p, g = 23, 5             # public: prime modulus and generator
a, b = 6, 15             # private: Alice's and Bob's secrets
A = pow(g, a, p)
B = pow(g, b, p)
print(A, B)
print(pow(B, a, p), pow(A, b, p))

8 19
2 2

The discrete logarithm problem

An eavesdropper sees p, g, A and B. To get the secret, they would need a from A = g^a \bmod p. That is the discrete logarithm problem: given g, p and A, find the exponent a with g^a \equiv A \pmod{p}. It is the remainder-world version of the logarithm. With ordinary numbers, logarithms are easy because powers grow smoothly; modulo a prime they jump around, and for a well-chosen prime of 2048 bits or more no efficient classical method is known. For p = 23, though, there are only 22 candidates:

p, g, A = 23, 5, 8                        # what the eavesdropper sees

for start in range(1, p, 6):              # 5^1 .. 5^22 mod 23, six per line
    print("  ".join(f"5^{a}={pow(g, a, p)}" for a in range(start, min(start + 6, p))))
print("secret exponent:", next(a for a in range(1, p) if pow(g, a, p) == A))

5^1=5  5^2=2  5^3=10  5^4=4  5^5=20  5^6=8
5^7=17  5^8=16  5^9=11  5^10=9  5^11=22  5^12=18
5^13=21  5^14=13  5^15=19  5^16=3  5^17=15  5^18=6
5^19=7  5^20=12  5^21=14  5^22=1
secret exponent: 6

The table shows how irregular the powers are, and also that 5 reaches every value from 1 to 22 (it is a generator modulo 23). Real deployments use standardized groups, such as the 2048- to 8192-bit groups ffdhe2048 to ffdhe8192 of RFC 7919 (with g = 2), or, much more often today, the elliptic-curve variant (ECDHE, for example X25519), which reaches the same strength with far shorter numbers. TLS 1.3 dropped RSA key transport: every full handshake (one not resumed with a pre-shared key) uses a fresh ephemeral key exchange, in practice elliptic-curve Diffie–Hellman such as X25519, today often combined with ML-KEM; see TLS.

Hashes and the birthday bound

A cryptographic hash function maps any input to a fixed-size output, say 256 bits. Since there are far more possible inputs than outputs, different inputs with the same hash (collisions) must exist; the design goal is that nobody can find one. How much work does a brute-force search take?

• Finding an input for one given hash (a preimage) takes about 2^{b} tries for a b-bit hash.
• Finding any two inputs with the same hash takes only about 2^{b/2} tries.

The second number is the birthday bound: for a hash with b output bits, after roughly 2^{b/2} random inputs the chance that two of them share a hash becomes large (more precisely, about 1.18 \cdot 2^{b/2} inputs give a 50% chance). It is the same effect as the birthday paradox: in a group of 23 people, two share a birthday with a chance above 50%, because what matters is the number of pairs, which grows with the square of the group size.

import math

# Birthday bound: about 2^(bits/2) hashes for a 50% collision chance
for bits in (32, 64, 128, 256):
    print(bits, f"2^{bits // 2}", f"{math.sqrt(2 * math.log(2)) * 2 ** (bits / 2):.3e}")

32 2^16 7.716e+04
64 2^32 5.057e+09
128 2^64 2.172e+19
256 2^128 4.007e+38

A 32-bit checksum collides after about 77,000 inputs — fine for catching transmission errors (see Error Detection and Correction), useless against an attacker. SHA-256 has 256 output bits, so its collision resistance is about 128 bits: still far out of reach. This halving is why hash outputs are twice as long as the security level they aim for, and why MD5 (128 bits, and broken by better attacks besides) and SHA-1 must not be used where collisions matter. Git, for example, is moving from SHA-1 to SHA-256 object names (see commit hashes).

Key sizes and security strength

Key lengths of different algorithms cannot be compared directly: a 256-bit elliptic-curve key is far stronger than a 256-bit RSA key would be, because the best attacks on each are different. To compare them, standards use the security strength: a number of bits s meaning that breaking the algorithm with the best known attack takes about 2^s operations — as much work as trying every key of an ideal s-bit symmetric cipher. NIST Special Publication 800-57 Part 1 (Revision 5, 2020) gives these equivalents:

RSA grows badly: going from 128 to 256 bits of strength multiplies the modulus by five, while an elliptic-curve key only doubles. Why even 112 bits is plenty against brute force: the example assumes an attacker who can test a trillion (10¹²) keys per second.

guesses_per_second = 10 ** 12
seconds_per_year = 365.25 * 24 * 3600

for bits in (56, 80, 112, 128):
    years = 2 ** bits / guesses_per_second / seconds_per_year
    print(f"{bits:3} bits: {years:.1e} years")

 56 bits: 2.3e-03 years
 80 bits: 3.8e+04 years
112 bits: 1.6e+14 years
128 bits: 1.1e+19 years

56 bits (the old DES cipher) falls in under a day; 128 bits takes almost a billion times the age of the universe. Real attacks on RSA and Diffie–Hellman are cleverer than brute force, which is exactly what the table already accounts for.

Current guidance (as of 2026)

• NCSC-NL (the Dutch National Cyber Security Centre), TLS guidelines version 2025-05: an RSA modulus of 3072 bits or more is "sufficient", 2048 to 3071 bits is "to be phased out", below 2048 is "insufficient". It recommends configuring the hybrid post-quantum key exchange X25519MLKEM768 now, and lists the Diffie–Hellman groups ffdhe3072 and ffdhe4096 as adequate for most applications.
• BSI (the German Federal Office for Information Security), TR-02102-1 version 2026-01: aims for at least 120 bits of security; RSA and classic Diffie–Hellman at least 3000 bits, elliptic curves at least 250 bits. Purely classical key agreement is recommended only until the end of 2031; quantum-safe key agreement should be used in hybrid form (ML-KEM-768 and ML-KEM-1024 are among the recommended mechanisms). Classical signatures remain recommended until the end of 2035.
• NIST (the United States National Institute of Standards and Technology), IR 8547, still an initial public draft (November 2024): quantum-vulnerable algorithms at 112-bit strength, such as RSA-2048, deprecated after 2030, and all quantum-vulnerable public-key algorithms (RSA, elliptic curve and classic Diffie–Hellman, ECDSA, EdDSA) disallowed after 2035.

In practice: RSA-2048 is still widespread and acceptable for now, but new keys should be RSA-3072 or larger, or elliptic curves such as P-256 or X25519/Ed25519. When Ravi Kumar renews the certificate of portal.kestrel.example.com, an ECDSA P-256 or RSA-3072 key is the sensible choice; for SSH, ssh-keygen -t ed25519 creates a modern elliptic-curve key. These recommendations change over time — check the current versions before a design decision.

Quantum computers and post-quantum cryptography

A sufficiently large quantum computer running Shor's algorithm could factor large numbers and compute discrete logarithms efficiently, breaking RSA, classic and elliptic-curve Diffie–Hellman, and elliptic-curve signatures — the toy problems on this page, at full size. Symmetric ciphers and hashes are affected far less: Grover's algorithm at best square-roots the work of a brute-force search, so AES-256 and SHA-256 are expected to stay secure. No such quantum computer exists as of 2026, but recorded traffic could be decrypted later ("harvest now, decrypt later"), which is why the migration is already under way (see post-quantum cryptography).

The replacement algorithms rest on different mathematics, mainly lattices: problems related to finding short vectors in huge grids of points in hundreds of dimensions (the vectors and matrices page covers the basic objects). On 13 August 2024 NIST published FIPS 203, ML-KEM (Module-Lattice-Based Key-Encapsulation Mechanism, in the sizes ML-KEM-512, -768 and -1024), for key establishment, together with the signature standards FIPS 204 (ML-DSA) and FIPS 205 (SLH-DSA, based on hash functions). As of 2026, major browsers and many servers combine a classical exchange with ML-KEM in a hybrid such as X25519MLKEM768, so the connection stays secure as long as either part holds.