Capstone: the mathematics of a secure network

This final lesson puts the course to work on a single realistic project. A company with six offices wants to connect them with private fiber links, keep the network running when a link fails, route traffic efficiently, and protect the data that travels over it. Each of these requirements turns out to be a question from an earlier lesson. Designing the cheapest connection is a minimum spanning tree problem (Lesson 9). Asking what single failures can do is a question about bridges and cycles (Lesson 8). Routing is shortest paths (Lesson 10). Choosing password rules, key lengths and hash sizes is counting, including the pigeonhole principle and the birthday problem (Lessons 2 to 4). And the encryption itself, RSA, is the number theory of Lesson 11. Working through the project shows how the pieces of discrete mathematics fit together in practice.

Step 1: the cheapest network

The offices are A to F, and the costs, in tens of thousands of dollars, of the links that the telecom provider can install are those of the graph in Lesson 9: AB 4, AC 1, BC 3, BD 5, CD 2, CE 8, DE 6, DF 7, EF 9. A minimum spanning tree connects all six offices at the least total cost. Kruskal's algorithm takes AC, CD and BC, skips AB and BD because their ends are already connected, then takes DE and DF, for a total of 19. By the cut property this is optimal, and because all the costs are different it is the unique optimum: no cheaper set of links connects every office.

But a tree has a weakness that Lesson 8 identified: every edge of a tree is a bridge. If the DF link is cut by a backhoe, office F is isolated; if CD fails, the network splits into \(\{A, B, C\}\) and \(\{D, E, F\}\). A tree is the cheapest connected network precisely because it has no redundancy.

Step 2: surviving a single failure

The company decides that no single link failure may disconnect the network. By the bridge theorem, that means every link must lie on a cycle; such a graph is called 2-edge-connected. What is the cheapest way to achieve this? Finding the cheapest 2-edge-connected spanning subgraph is in general a hard problem, related to the traveling salesman problem, but for six offices we can solve it by brute force: check every subset of the nine links, keep those that are connected with no bridge, and take the cheapest. A useful lower bound guides the search. A 2-edge-connected graph has minimum degree at least 2, so it has at least \(n = 6\) edges, and since it contains a spanning tree it costs at least the MST cost plus the cheapest link outside the tree.

Menger's theorem of 1927 explains what 2-edge-connectivity buys. A graph remains connected after the removal of any \(k - 1\) edges exactly when every pair of vertices is joined by \(k\) paths that share no edge. So in a 2-edge-connected network every pair of offices has two edge-disjoint routes, and traffic can be rerouted when one fails. This is the theorem behind ring topologies in metropolitan fiber networks, which are designed so that a cut anywhere on the ring is survived by sending traffic the other way around.

Step 3: routing

On the chosen network, each router must know a shortest route to every other office, where the length of a link is now its latency rather than its cost. Routers running a link-state protocol each hold a copy of the network map and run Dijkstra's algorithm from themselves, producing a shortest-path tree. When a link fails, the change is flooded to every router, and each simply runs Dijkstra again on the new map. Because a 2-edge-connected network still has a path between every pair after one failure, the new run always succeeds.

Step 4: counting and the strength of secrets

Security begins with counting. A password of length 8 drawn from the 94 printable keyboard characters allows \(94^8 \approx 6.1 \times 10^{15}\) possibilities, by the product rule. An attacker who has stolen a file of password hashes and can test \(10^{11}\) guesses per second with specialized hardware tries them all in about 17 hours. Length helps far more than character variety: twelve characters give \(94^{12} \approx 4.8 \times 10^{23}\) possibilities, about 150 thousand years at the same rate, and a passphrase of five words chosen at random from a list of 7776 words, the Diceware method, gives \(7776^5 \approx 2.8 \times 10^{19}\). Counting makes clear why such advice works, and also why users' actual choices, which cluster on common words and patterns, are far weaker than the total count suggests. Defenders therefore store passwords with deliberately slow hash functions and add a random value, the salt, to each one so that every guess must be made separately for each account.

Keys for encryption are counted the same way. A 128-bit symmetric key has \(2^{128} \approx 3.4 \times 10^{38}\) possible values. Even at \(10^{18}\) guesses per second, a search would take about \(10^{13}\) years, roughly 800 times the age of the universe. Exhaustive search is not the threat; flaws in design and implementation are.

Hash functions show the pigeonhole principle and the birthday problem at work. A cryptographic hash function such as SHA-256 maps any input, of any length, to 256 bits. There are infinitely many inputs and only \(2^{256}\) outputs, so by the pigeonhole principle collisions, two inputs with the same hash, must exist. Security requires only that they be infeasible to find. The birthday calculation from Lesson 2 says how hard that is: among \(k\) random values from \(N\) possibilities, a collision becomes likely once \(k\) is around \(\sqrt{N}\), since the probability of no collision is roughly \(e^{-k^2/(2N)}\). For a 256-bit hash this is about \(2^{128}\) attempts, which is out of reach. For the older 128-bit hash MD5 it is about \(2^{64}\), and attacks that exploit the structure of MD5 do much better still; practical MD5 collisions were demonstrated in 2004, which is why it is no longer used for security.

Step 5: public-key encryption with RSA

The offices must exchange secret messages over links the company does not fully control. Symmetric encryption is fast, but both ends must already share a key. Public-key cryptography solves the key distribution problem. In 1976 Whitfield Diffie and Martin Hellman published the idea, together with a method for two parties to agree on a secret key over a public channel using modular exponentiation. In 1977 Ron Rivest, Adi Shamir and Leonard Adleman at MIT found the first practical public-key encryption system, RSA. It later emerged that Clifford Cocks at the British intelligence agency GCHQ had found an equivalent scheme in 1973; his work was declassified in 1997.

RSA key generation:

• Choose two large distinct primes \(p\) and \(q\), and let \(n = pq\). Primality tests make finding them quick.

• Compute \(\varphi(n) = (p - 1)(q - 1)\).

• Choose a public exponent \(e\) with \(\gcd(e, \varphi(n)) = 1\); 65537 is the usual choice.

• Compute the private exponent \(d = e^{-1} \bmod \varphi(n)\) with the extended Euclidean algorithm.

• Publish the public key \((n, e)\). Keep \(d\), \(p\) and \(q\) secret.

To encrypt a message, encoded as a number \(M\) with \(0 \le M < n\), compute \(C = M^e \bmod n\) by fast exponentiation. To decrypt, compute \(C^d \bmod n\).

Theorem. For every \(M\) with \(0 \le M < n\), \((M^e)^d \equiv M \pmod n\).

Proof. Since \(ed \equiv 1 \pmod{\varphi(n)}\), write \(ed = 1 + k(p-1)(q-1)\). Consider the congruence modulo \(p\). If \(p \nmid M\), Fermat's little theorem gives \(M^{p-1} \equiv 1 \pmod p\), so \(M^{ed} = M \cdot (M^{p-1})^{k(q-1)} \equiv M \pmod p\). If \(p \mid M\), both sides are \(0 \bmod p\). Either way \(M^{ed} \equiv M \pmod p\), and by the same argument \(M^{ed} \equiv M \pmod q\). So the distinct primes \(p\) and \(q\) both divide \(M^{ed} - M\), and since they share no factor, by unique factorization \(pq = n\) divides it too. Hence \(M^{ed} \equiv M \pmod n\), and as \(0 \le M < n\), decryption returns exactly \(M\).

Why is RSA secure? Anyone who can factor \(n\) can compute \(\varphi(n)\) and then \(d\), so RSA is no stronger than factoring. No efficient classical factoring algorithm is known, and with \(n\) of 2048 bits, about 617 decimal digits, the best known methods are far out of reach; the largest RSA challenge number factored publicly, RSA-250 with 829 bits, took about 2700 core-years of computation in 2020. Peter Shor showed in 1994 that a large quantum computer could factor efficiently, which is why new post-quantum standards based on different mathematics, such as lattices, were published by the US National Institute of Standards and Technology in 2024.

The toy example also shows why practice requires care beyond the mathematics. Encrypting a small message directly with small \(e\) can be undone by taking an ordinary root; the same message always encrypts to the same ciphertext, which lets an eavesdropper recognize repeats. Real systems therefore add randomized padding before encryption, use RSA mainly to protect a fresh symmetric key or to sign data, and rely on carefully reviewed libraries rather than code written from a textbook. Digital signatures run RSA in reverse: the owner computes \(S = H^d \bmod n\) from the hash \(H\) of a document, and anyone can check that \(S^e \bmod n = H\) using the public key. Signatures are how a browser knows a web site's certificate is genuine.

from itertools import combinations
from collections import deque
import math, random

names = "ABCDEF"
E = [(4,"A","B"),(1,"A","C"),(3,"B","C"),(5,"B","D"),(2,"C","D"),
     (8,"C","E"),(6,"D","E"),(7,"D","F"),(9,"E","F")]

def connected(edges):
    adj = {v: [] for v in names}
    for _, u, v in edges:
        adj[u].append(v); adj[v].append(u)
    seen, q = {"A"}, deque("A")
    while q:
        for w in adj[q.popleft()]:
            if w not in seen:
                seen.add(w); q.append(w)
    return len(seen) == len(names)

def bridgeless(edges):
    return connected(edges) and all(connected([f for f in edges if f != e]) for e in edges)

best_tree = min((s for s in combinations(E, 5) if connected(s)), key=lambda s: sum(w for w, _, _ in s))
print("MST cost", sum(w for w, _, _ in best_tree), [u + v for _, u, v in best_tree])
designs = sorted((sum(w for w, _, _ in s), sorted(u + v for _, u, v in s))
                 for k in range(6, len(E) + 1) for s in combinations(E, k) if bridgeless(s))
low = designs[0][0]
print("cheapest network with no bridge costs", low, "and", sum(c == low for c, _ in designs), "designs tie:")
for c, links in designs:
    if c == low:
        print("  ", links)

print("8 chars from 94: %.1e choices, %.0f hours at 1e11 per second" % (94**8, 94**8 / 1e11 / 3600))
print("5 Diceware words: %.1e choices" % 7776**5)
def no_collision(k, N):
    p = 1.0
    for i in range(k):
        p *= (N - i) / N
    return p
print("23 people, 365 days: P(shared birthday) = %.3f" % (1 - no_collision(23, 365)))
print("32-bit hash, 77,000 values: P(collision) = %.3f" % (1 - math.exp(-77000**2 / 2 / 2**32)))

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

p, q, e = 61, 53, 17
n, phi = p * q, (p - 1) * (q - 1)
g, x, _ = ext_gcd(e, phi)
d = x % phi
print("n =", n, " phi =", phi, " d =", d, " check e*d mod phi =", e * d % phi)
M = 65
C = pow(M, e, n)
print("encrypt 65 ->", C, " decrypt ->", pow(C, d, n))
print("every message decrypts correctly:", all(pow(pow(m, e, n), d, n) == m for m in range(n)))
H = 1234
S = pow(H, d, n)
print("signature of 1234:", S, " verifies:", pow(S, e, n) == H)

def factor(n):
    f = 2
    while f * f <= n:
        if n % f == 0:
            return f, n // f
        f += 1
print("factoring the toy modulus breaks it:", factor(3233))

MST cost 19 ['AC', 'BC', 'CD', 'DE', 'DF']
cheapest network with no bridge costs 34 and 3 designs tie:
   ['AB', 'AC', 'BC', 'CD', 'CE', 'DF', 'EF']
   ['AB', 'AC', 'BD', 'CD', 'DE', 'DF', 'EF']
   ['AB', 'AC', 'BD', 'CE', 'DF', 'EF']
8 chars from 94: 6.1e+15 choices, 17 hours at 1e11 per second
5 Diceware words: 2.8e+19 choices
23 people, 365 days: P(shared birthday) = 0.507
32-bit hash, 77,000 values: P(collision) = 0.499
n = 3233  phi = 3120  d = 2753  check e*d mod phi = 1
encrypt 65 -> 2790  decrypt -> 65
every message decrypts correctly: True
signature of 1234: 1512  verifies: True
factoring the toy modulus breaks it: (53, 61)

The brute-force search confirms the costs in the figure: 19 for the tree and 34 for the cheapest network that survives any single link failure, well above the lower bound of 23. The reason is office F: it has only two possible links, DF and EF, and a bridgeless network must use both, including the most expensive link of all. Three different designs tie at 34. The ring in the figure is the best of them for another reason: the other two pass through a single office, C or D, whose loss would split the network, while a ring has no cut vertex at all. Choosing among optimal solutions by a second criterion is typical of real design work. Here redundancy costs almost four fifths more than the bare tree. The 32-bit hash line is the birthday problem at scale: with only about 77 thousand random values, a collision in a 32-bit space of over four billion is already more likely than not. This is why identifiers that must be unique, and hashes that must resist collisions, need far more bits than a naive count suggests.

Looking back

The project used every part of the course. Counting set the sizes of passwords, keys and hashes. The pigeonhole principle said collisions must exist, and the birthday problem said when they become likely. Recurrences and induction were behind the analysis of Euclid's algorithm and fast exponentiation. Graph theory supplied the vocabulary of networks, the bridge theorem and Menger's theorem for reliability, minimum spanning trees for cost, and shortest paths for routing. Number theory supplied modular arithmetic, inverses and Fermat's theorem, which together make RSA work. Each of these topics continues in later courses: MATH-460 for advanced counting and graph theory, MATH-351 for number theory, CMPUT-204 for algorithms and their running times, and CMPUT-272 and MATH-228 for the logic and proof techniques used throughout.