Classical cryptography and the foundations of modern cryptography

Cryptography is the study of techniques for secure communication in the presence of adversaries. For most of its history it meant encryption: turning a readable plaintext into an unreadable ciphertext so that only someone holding a key can recover the plaintext. Today it also covers integrity, authentication, digital signatures, key agreement and much more, and it underpins nearly every other control in this course. This lesson looks at classical ciphers, not because anyone should use them, but because the ways they were broken teach the ideas that shape modern design: key space, statistical structure, the need for randomness, perfect secrecy and Kerckhoffs' principle. Lessons 3 to 6 then build the modern toolbox.

A word on scope. CMPUT-272 introduced modular arithmetic and a toy RSA example, and CISSP-112 surveys cryptography for security managers, including algorithm choices and key management policy. Here we focus on how the mechanisms work and why particular designs fail, and we write small programs that break classical ciphers so that the weaknesses are concrete rather than asserted.

The vocabulary of cryptography

An encryption scheme has three algorithms: key generation, which produces a key; encryption \( E_k(m) = c \), which maps a plaintext \( m \) to a ciphertext \( c \) under key \( k \); and decryption \( D_k(c) = m \), which inverts it. In symmetric cryptography the same key encrypts and decrypts, so both parties must share it in advance. In asymmetric or public-key cryptography, Lesson 5, a public key encrypts or verifies and a separate private key decrypts or signs. Cryptanalysis is the study of breaking schemes. Attacks are classified by what the attacker has: ciphertext only, known plaintext (some plaintext–ciphertext pairs), chosen plaintext (the attacker can obtain encryptions of messages of their choice) and chosen ciphertext (the attacker can also obtain decryptions of chosen ciphertexts, except the target). Modern schemes are expected to resist the strongest of these, because real systems routinely give attackers such abilities: a web server encrypts whatever a client sends, and an error message can leak whether a ciphertext decrypted correctly.

Shift and substitution ciphers

The Caesar cipher replaces each letter with the one three places later in the alphabet. Generalized to any shift, it has only 26 keys, so an attacker simply tries them all. This is brute force, or exhaustive key search, and it reminds us of the first requirement of any cipher: the key space must be too large to search.

import string
A = string.ascii_lowercase
def shift(text, k):
    return ''.join(A[(A.index(c) + k) % 26] if c in A else c for c in text)

secret = shift("meet at the library at noon", 3)
print("ciphertext:", secret)
# Brute force: only 26 keys, so try them all and let a human (or a dictionary) spot English
for k in range(26):
    guess = shift(secret, -k)
    if all(w in {"meet", "at", "the", "library", "noon"} for w in guess.split()):
        print(f"key {k:2d} gives: {guess}")

ciphertext: phhw dw wkh oleudub dw qrrq
key  3 gives: meet at the library at noon

A simple substitution cipher maps each letter to an arbitrary other letter, giving \( 26! \approx 4 \times 10^{26} \) keys, about 88 bits. Brute force is hopeless, yet these ciphers are solved by hand in newspaper puzzle columns. The reason is that substitution preserves the statistics of the language. In English, e is the most common letter (about 12.7 percent of letters), followed by t, a and o; th and he are the most common pairs; and words like the, and and of recur constantly. The Arab scholar al-Kindi described frequency analysis in the ninth century. Count the ciphertext letters, match the most frequent ones to e, t and a, and use common words and pairs to fill in the rest. A large key space is necessary but not sufficient: the cipher must also hide the structure of the plaintext.

Polyalphabetic ciphers and how Vigenère fell

The Vigenère cipher, described by Giovan Battista Bellaso in 1553 and later misattributed to Blaise de Vigenère, uses a keyword to choose a different shift for each position: with key lemon, the first letter is shifted by l (11), the second by e (4), and so on, repeating every five letters. A given plaintext letter encrypts to several different ciphertext letters, which flattens the frequency counts, and the cipher was called le chiffre indéchiffrable for three centuries. Charles Babbage and, independently, Friedrich Kasiski broke it in the nineteenth century. The weakness is the repeating key. If the key length is \( L \), then letters \( L \) positions apart were shifted by the same amount, so splitting the ciphertext into \( L \) columns gives \( L \) separate Caesar ciphers, each solvable by frequency analysis.

To find \( L \), we use William Friedman's index of coincidence: the probability that two letters drawn at random from a text are equal, \( IC = \sum_i n_i(n_i - 1) / (N(N-1)) \). For English it is about 0.066; for uniformly random letters it is \( 1/26 \approx 0.038 \). When we guess the right key length, every column is English shifted by a constant, so its index of coincidence is close to 0.066; wrong guesses mix shifts and look random. Then for each column we choose the shift whose decryption best matches English letter frequencies, measured with the chi-squared statistic \( \chi^2 = \sum (O - E)^2 / E \). The program below does exactly this on a paragraph encrypted with the key lemon, with no knowledge of the key.

import string
EN = {'a':8.2,'b':1.5,'c':2.8,'d':4.3,'e':12.7,'f':2.2,'g':2.0,'h':6.1,'i':7.0,'j':0.15,'k':0.77,'l':4.0,'m':2.4,
      'n':6.7,'o':7.5,'p':1.9,'q':0.095,'r':6.0,'s':6.3,'t':9.1,'u':2.8,'v':0.98,'w':2.4,'x':0.15,'y':2.0,'z':0.074}
A = string.ascii_lowercase
def clean(t): return ''.join(c for c in t.lower() if c in A)
def vig(text, key, sign=1):
    return ''.join(A[(A.index(c) + sign * A.index(key[i % len(key)])) % 26] for i, c in enumerate(text))
def ioc(s):
    n = len(s); return sum(s.count(c) * (s.count(c) - 1) for c in A) / (n * (n - 1))
def chi(s):
    n = len(s); return sum((s.count(c) - n * EN[c] / 100) ** 2 / (n * EN[c] / 100) for c in A)
plain = clean("""Every winter the students in the computing club run a puzzle hunt across the campus. Teams follow
clues hidden in the library, the engineering building and the student union, and each clue is protected by a
cipher that the organizers believe is unbreakable. This year the organizers chose an old method that was called
the indecipherable cipher for three hundred years, because it hides the frequency of each letter by shifting it
by a different amount depending on its position. The teams quickly learned that the method is anything but
indecipherable once you have enough text, because the shifts repeat with the length of the keyword and each
column of letters behaves like a simple shift cipher that can be solved by counting letters.""")
ct = vig(plain, "lemon")
print("ciphertext starts:", ct[:40])
for L in range(1, 9):
    cols = [ct[i::L] for i in range(L)]
    print(f"key length {L}: mean index of coincidence {sum(map(ioc, cols)) / L:.4f}")
L = max(range(1, 9), key=lambda L: sum(map(ioc, [ct[i::L] for i in range(L)])) / L - 0.002 * L)
key = ''.join(min(A, key=lambda k: chi(vig(ct[i::L], k, -1))) for i in range(L))
print("best key length:", L, " recovered key:", key)
print("plaintext starts:", vig(ct, key, -1)[:40])

ciphertext starts: pzqflhmzhrcxtsfeypsaewubgsioczayfwargxio
key length 1: mean index of coincidence 0.0433
key length 2: mean index of coincidence 0.0446
key length 3: mean index of coincidence 0.0441
key length 4: mean index of coincidence 0.0433
key length 5: mean index of coincidence 0.0676
key length 6: mean index of coincidence 0.0444
key length 7: mean index of coincidence 0.0444
key length 8: mean index of coincidence 0.0434
best key length: 5  recovered key: lemon
plaintext starts: everywinterthestudentsinthecomputingclub

The key length of 5 stands out clearly, with a mean index of coincidence near the English value, and frequency analysis on each column recovers the key. The lesson generalizes: any cipher that leaves a detectable statistical relationship between plaintext and ciphertext can eventually be broken given enough ciphertext. Mechanical cipher machines of the twentieth century, such as the German Enigma, were vastly more complex polyalphabetic ciphers, and they too fell to statistical attacks combined with operator mistakes and known plaintext (cribs), a story in which Polish mathematicians, then British codebreakers at Bletchley Park, played the leading roles.

Kerckhoffs' principle

In 1883 Auguste Kerckhoffs set out requirements for military ciphers. The most famous is that the system must not require secrecy and should be able to fall into enemy hands without inconvenience. In modern terms: assume the adversary knows every detail of your algorithm, and let security depend only on the secrecy of the key. Claude Shannon put it as the enemy knows the system. There are three reasons. Algorithms leak, through reverse engineering, defectors, stolen documents and published patents. Keys are small and easy to change, whereas a compromised algorithm must be replaced everywhere. And public algorithms receive scrutiny from cryptanalysts worldwide, which is the only reliable way to gain confidence in them. The history of proprietary ciphers broken shortly after their designs were revealed, from the DVD Content Scramble System to early mobile phone and car-key ciphers, is long. The modern standards in this course, AES, SHA-2, SHA-3, RSA and the elliptic-curve and post-quantum schemes, were all chosen in open processes.

Perfect secrecy and the one-time pad

In 1949 Shannon gave a mathematical definition of perfect secrecy: a cipher is perfectly secret if seeing the ciphertext gives the attacker no information at all about the plaintext, that is, \( \Pr[M = m \mid C = c] = \Pr[M = m] \) for every message and ciphertext. He proved that the one-time pad achieves it: XOR the message with a truly random key of the same length, \( c = m \oplus k \), and never reuse the key. Because every possible plaintext of that length corresponds to exactly one key, every plaintext is equally consistent with the ciphertext. He also proved the price: perfect secrecy requires a key at least as long as the message, with as much entropy as the messages themselves.

import secrets
def xor(a, b): return bytes(x ^ y for x, y in zip(a, b))

m1 = b"TRANSFER 100 TO ALEX"
key = secrets.token_bytes(len(m1))            # truly random, as long as the message, used ONCE
c1 = xor(m1, key)
print("decrypts correctly:", xor(c1, key) == m1)

# Perfect secrecy: for ANY other message of the same length there is a key that maps c1 to it
m_fake = b"TRANSFER 900 TO EVE "
k_fake = xor(c1, m_fake)
print("a different key turns c1 into:", xor(c1, k_fake))

# Reusing the pad ("two-time pad") destroys the guarantee
m2 = b"MEET AT GATE 5 TODAY"
c2 = xor(m2, key)
leak = xor(c1, c2)                             # the key cancels out: c1 XOR c2 = m1 XOR m2
print("c1 XOR c2 equals m1 XOR m2:", leak == xor(m1, m2))
# An attacker who guesses part of one message ("TRANSFER") learns the same part of the other
print("crib 'TRANSFER' reveals:", xor(leak[:8], b"TRANSFER"))

decrypts correctly: True
a different key turns c1 into: b'TRANSFER 900 TO EVE '
c1 XOR c2 equals m1 XOR m2: True
crib 'TRANSFER' reveals: b'MEET AT '

The two-time pad failure is not hypothetical. In the 1940s Soviet cipher clerks under wartime pressure reused pages of one-time pad material, and the United States Venona project exploited the reuse to read thousands of messages. The same mistake recurs in modern form whenever a stream cipher or counter-mode encryption reuses a key and nonce pair, which Lesson 3 demonstrates. The one-time pad's key-distribution burden makes it impractical for almost everything, so modern cryptography settles for computational security: schemes that no attacker with realistic computing power can break with more than negligible probability.

Computational security and key length

A modern cipher with a \( k \)-bit key should offer about \( k \) bits of security, meaning the best known attack costs about \( 2^k \) operations, no better than brute force. We measure security in bits because each extra bit doubles the work. The Data Encryption Standard (DES), adopted in 1977 with a 56-bit key, was broken by brute force in 1998 when the Electronic Frontier Foundation built a dedicated machine that searched the key space in days. Today, 128 bits is the baseline for symmetric keys and 256 bits is used where long-term or post-quantum margins are wanted, because Grover's quantum search algorithm could in principle reduce brute-force cost to about \( 2^{k/2} \).

import math
# Time to search a key space at one trillion (10^12) guesses per second
rate = 1e12
year = 365.25 * 24 * 3600
for name, size in [("Caesar shift", 26),
                   ("Simple substitution (26!)", math.factorial(26)),
                   ("8-character password, 95 printable chars", 95 ** 8),
                   ("56-bit DES key", 2 ** 56),
                   ("128-bit AES key", 2 ** 128)]:
    secs = size / 2 / rate                       # on average the key is found halfway through
    bits = math.log2(size)
    if secs < 1:
        t = f"{secs:.1e} s"
    elif secs < year:
        t = f"{secs / 3600:,.1f} hours"
    else:
        t = f"{secs / year:.2e} years"
    print(f"{name:<42} {bits:6.1f} bits  average search {t}")

Caesar shift                                  4.7 bits  average search 1.3e-11 s
Simple substitution (26!)                    88.4 bits  average search 6.39e+06 years
8-character password, 95 printable chars     52.6 bits  average search 0.9 hours
56-bit DES key                               56.0 bits  average search 10.0 hours
128-bit AES key                             128.0 bits  average search 5.39e+18 years

A trillion guesses per second is a rough figure for a well-resourced attacker against a fast cipher; dedicated hardware can go faster, but the point stands: 128-bit keys are beyond brute force by a margin of many orders of magnitude, while human passwords are not, which is why Lesson 4 stores passwords with deliberately slow hash functions. Security bits also depend on the algorithm: the best attacks on 2048-bit RSA cost about \( 2^{112} \) operations, so RSA needs much longer keys than AES for comparable strength, a theme of Lesson 5.

Randomness

Every key, nonce and salt in this course must be unpredictable to an attacker. Computers are deterministic, so they gather entropy from unpredictable physical events, such as interrupt timing and dedicated hardware noise sources, and feed it to a cryptographically secure pseudorandom number generator (CSPRNG) in the operating system. In Python, the secrets module and os.urandom draw from it; the random module does not, because it uses the Mersenne Twister, whose entire internal state can be reconstructed from 624 consecutive 32-bit outputs, after which every future value is predictable. Weak randomness has broken real systems: a 2008 Debian change reduced OpenSSL's key generation to about 32,768 possible keys per architecture, and studies of internet devices have found many RSA keys sharing prime factors because they were generated at boot before enough entropy was available.