Chapter 9: Automated Cryptanalysis (SageMath)

Python Version Available

This notebook contains the SageMath implementation. A pure Python/NumPy version is available in Chapter 9: Automated Cryptanalysis.

“The theoretical secrecy of a system having been settled, we can turn to the problem of the work required to break it… The problem of cryptanalysis is that of finding the most efficient algorithm for this inversion.” – Claude Shannon, Communication Theory of Secrecy Systems, 1949

In previous chapters we attacked ciphers with targeted analytical tools: frequency analysis for monoalphabetic substitution, Kasiski examination and the Index of Coincidence for Vigenere, and algebraic methods for the Hill cipher. Each of these methods is elegant, but each is also specific to one cipher type. A substitution-cipher analyst who encounters a Playfair cipher must learn an entirely different technique.

In this chapter we introduce a fundamentally different paradigm: automated cryptanalysis via hill climbing with n-gram scoring. Instead of exploiting the structure of a particular cipher, we define a fitness function that measures how much a candidate decryption resembles natural English, and then use stochastic optimization to search the key space for the key that maximizes this fitness. The approach is remarkably general – the same framework can attack substitution ciphers, transposition ciphers, Playfair ciphers, and many others, simply by changing the key representation and perturbation strategy.

The key insight is that quadgram log-likelihood scoring provides a fitness function that is simultaneously:

• Sensitive enough to distinguish partially correct decryptions from random text

• Smooth enough for hill climbing to make steady progress

• Computationally cheap enough to evaluate millions of candidate keys

Notice that this technique heavily depends on high redundancy rate of natural languages. If we happen to compress or otherwise whiten the plaintext the fitness of such processed input text will be closer to the random base level and the algorithm might never be able to recover the permutation key.

9.1 History: From Manual Frequency Analysis to Computer-Aided Cryptanalysis

9.1.1 The Evolution of Scoring Functions

The idea that natural language text has measurable statistical properties dates back to Al-Kindi (9th century), who first described frequency analysis. For centuries, the cryptanalyst’s primary tool was counting individual letters – what we now call unigram statistics.

The progression to more powerful scoring functions mirrors the growth of computational resources:

Era	Scoring method	Information captured	Typical use
9th–19th century	Unigrams (single letters)	Letter frequency	Manual substitution breaking
Early 20th century	Bigrams (letter pairs)	Common pairs like TH, HE, IN	Friedman’s statistical methods
Mid 20th century	Trigrams (letter triples)	Word fragments like THE, AND, ING	Machine-aided analysis
Late 20th century	Quadgrams (4-letter sequences)	Rich context, near word-level	Computer-automated hill climbing

The critical advance was recognizing that the longer the n-gram, the more context it captures about the structure of natural language. A unigram scorer only knows that E is common; a quadgram scorer knows that TION, THER, and THAT are common sequences, which provides far more discriminating power for distinguishing English from gibberish.

9.1.2 Hill Climbing in Cryptanalysis

The application of hill climbing to cipher-breaking was pioneered in the 1990s and popularized through resources like the Practical Cryptography website maintained by James Lyons. The method was applied spectacularly to break several historical ciphers that had resisted decades of manual analysis.

9.1.3 Simon Singh’s Cipher

Challenges

In 1999, Simon Singh published The Code Book, which included a set of cipher challenges of escalating difficulty. The challenges ranged from a simple Caesar (shift) cipher to the RSA public-key cryptosystem. The intermediate challenges – monoalphabetic substitution, Vigenere, and others – are precisely the type of cipher that hill-climbing methods can crack automatically. Singh offered a prize of 10,000 GBP for solving all stages, which was claimed in 2000 by a team from Sweden.

Historical note

The transition from manual to automated cryptanalysis was not merely about speed. Hill climbing with n-gram scoring introduced a qualitative change: the cryptanalyst no longer needs deep insight into the cipher’s structure. A well-designed fitness function and search strategy can break ciphers that the analyst does not even fully understand.

9.2 Formal Definitions

9.2.1 N-grams

Definition 9.1 (N-gram)

An n-gram is a contiguous sequence of \(n\) characters drawn from a text. For a text \(x = x_1 x_2 \cdots x_N\) over an alphabet \(\mathcal{A}\), the n-grams are:

\[ g_i = x_i x_{i+1} \cdots x_{i+n-1}, \quad i = 1, 2, \ldots, N - n + 1\]

The total number of n-grams in a text of length \(N\) is \(N - n + 1\).

For the English alphabet with \(|\mathcal{A}| = 26\), the number of possible n-grams is \(26^n\): 26 unigrams, 676 bigrams, 17,576 trigrams, and 456,976 quadgrams.

9.2.2 N-gram Frequency Table

Definition 9.2 (N-gram frequency table)

Given a large reference corpus \(C\) of length \(M\), the n-gram frequency table is the mapping \(F: \mathcal{A}^n \to [0,1]\) defined by:

\[ F(g) = \frac{\text{count}(g, C)}{M - n + 1}\]

where \(\text{count}(g, C)\) is the number of times the n-gram \(g\) appears in the corpus \(C\).

9.2.3 Log-Likelihood Scoring

Definition 9.3 (Log-likelihood score)

The log-likelihood score of a candidate text \(x = x_1 x_2 \cdots x_N\) with respect to an n-gram frequency table \(F\) is:

\[ \text{score}(x) = \sum_{i=1}^{N-n+1} \log_{10} F(x_i x_{i+1} \cdots x_{i+n-1})\]

For n-grams \(g\) not observed in the corpus, we assign a floor probability \(F_{\text{floor}} = \frac{0.01}{M - n + 1}\) to avoid \(\log(0)\).

The score is always negative (since \(\log_{10}\) of a probability is negative). A higher (less negative) score indicates text that is more consistent with natural English. English text typically scores around \(-2.5\) to \(-3.0\) per quadgram, while random text scores around \(-5\) to \(-6\) per quadgram.

9.2.4 Hill Climbing

Definition 9.4 (Hill climbing for cryptanalysis)

Hill climbing is an iterative optimization algorithm applied to the key space \(\mathcal{K}\) of a cipher:

1. Initialize: Choose a random key \(k_0 \in \mathcal{K}\).

2. Perturb: Generate a neighbor \(k'\) by making a small change to the current key \(k_t\).

3. Evaluate: Compute \(\text{score}(D_{k'}(c))\) where \(D_{k'}\) is decryption with key \(k'\) and \(c\) is the ciphertext.

4. Accept/Reject: If \(\text{score}(D_{k'}(c)) > \text{score}(D_{k_t}(c))\), set \(k_{t+1} = k'\); otherwise \(k_{t+1} = k_t\).

5. Repeat steps 2–4 until convergence (no improvement for many iterations).

6. Restart: If stuck in a local optimum, restart from step 1 with a new random key.

9.2.5 Simulated Annealing

Definition 9.5 (Simulated annealing)

Simulated annealing modifies hill climbing by accepting worse solutions with a probability that decreases over time. Given a score difference \(\Delta = \text{score}(k') - \text{score}(k_t)\), we accept \(k'\) with probability:

\[\begin{split} P(\text{accept}) = \begin{cases} 1 & \text{if } \Delta > 0 \\ e^{\Delta / T} & \text{if } \Delta \leq 0 \end{cases}\end{split}\]

where \(T > 0\) is the temperature parameter. The temperature follows a cooling schedule \(T(t) = T_0 \cdot \alpha^t\) for some decay factor \(\alpha \in (0,1)\). At high temperature, the algorithm explores freely; as \(T \to 0\), it becomes pure hill climbing.

9.3 Implementation

We now implement the n-gram scoring and hill climbing framework. All code uses SageMath built-in functions – in particular we use SageMath’s log() for logarithms and SageMath plotting for visualisation. We build quadgram frequency tables inline from a sample English corpus rather than loading external files.

# --- Setup: text cleaning and corpus ---
import string
import re
import random

# Remove all non-lower case elements of the standard latin alphabet
def lclear(text):
    return re.sub(r'[^a-z]', '', text.lower())  # we use regular expressions

# --- Sample English Corpus ---
# We build our n-gram tables from a substantial inline corpus.
# This is a concatenation of classic English prose passages, providing
# a representative sample of English letter statistics.

SAMPLE_CORPUS = (
    "it was the best of times it was the worst of times it was the age of wisdom "
    "it was the age of foolishness it was the epoch of belief it was the epoch of "
    "incredulity it was the season of light it was the season of darkness it was "
    "the spring of hope it was the winter of despair we had everything before us "
    "we had nothing before us we were all going direct to heaven we were all going "
    "direct the other way in short the period was so far like the present period "
    "that some of its noisiest authorities insisted on its being received for good "
    "or for evil in the superlative degree of comparison only there were a king "
    "with a large jaw and a queen with a plain face on the throne of england there "
    "were a king with a large jaw and a queen with a fair face on the throne of "
    "france in both countries it was clearer than crystal to the lords of the state "
    "preserves of loaves and fishes that things in general were settled for ever "
    "call me ishmael some years ago never mind how long precisely having little or "
    "no money in my purse and nothing particular to interest me on shore i thought "
    "i would sail about a little and see the watery part of the world it is a way "
    "i have of driving off the spleen and regulating the circulation whenever i find "
    "myself growing grim about the mouth whenever it is a damp drizzly november in "
    "my soul whenever i find myself involuntarily pausing before coffin warehouses "
    "and bringing up the rear of every funeral i meet and especially whenever my "
    "hypos get such an upper hand of me that it requires a strong moral principle "
    "to prevent me from deliberately stepping into the street and methodically "
    "knocking peoples hats off then i account it high time to get to sea as soon "
    "as possible this is my substitute for pistol and ball with a philosophical "
    "flourish cato throws himself upon his sword i quietly take to the ship there "
    "is nothing surprising in this if they but knew it almost all men in their "
    "degree some time or other cherish very nearly the same feelings towards the "
    "ocean with me there now is your insular city of the manhattoes belted round "
    "by wharves as indian isles by coral reefs commerce surrounds it with her surf "
    "right and left the streets take you waterward its extreme downtown is the "
    "battery where that noble mole is washed by waves and cooled by breezes which "
    "a few hours previous were out of sight of land look at the crowds of water "
    "gazers there circumambulate the city of a dreamy sabbath afternoon go from "
    "corlears hook to coenties slip and from thence by whitehall northward what "
    "do you see posted like silent sentinels all around the town stand thousands "
    "upon thousands of mortal men fixed in ocean reveries some leaning against the "
    "spiles some seated upon the pier heads some looking over the bulwarks of ships "
    "from china some aloft in the rigging as if striving to get a still better "
    "seaward peep but these are all landsmen of week days pent up in lath and "
    "plaster tied to counters nailed to benches clinched to desks how then is this "
    "are the green fields gone what do they here but look here come more crowds "
    "pacing straight for the water and seemingly bound for a dive nothing will "
    "content them but the extremest limit of the land loitering under the shady "
    "lee of yonder warehouses will not suffice no they must get just as nigh the "
    "water as they possibly can without falling in and there they stand miles of "
    "them leagues inlanders all they come from lanes and alleys streets and avenues "
    "north south east and west yet here they all unite tell me does the magnetic "
    "virtue of the needles of the compasses of all those ships attract them thither "
    "the quick brown fox jumps over the lazy dog the five boxing wizards jump quickly "
    "pack my box with five dozen liquor jugs how vexingly quick daft zebras jump "
    "the sun shone having no alternative on the nothing new the earth makes of the "
    "sea the same old round the whole dull story all the same nothing to be done "
    "the night was dark and full of terrors the wind howled through the ancient trees "
    "and the rain beat against the windows of the old castle deep within the chamber "
    "a single candle flickered casting long shadows across the stone walls the "
    "cryptanalyst sat hunched over the desk surrounded by sheaves of paper covered "
    "with columns of letters and numbers she had been working on this cipher for "
    "three days now and the solution still eluded her the ciphertext was long enough "
    "to work with but the encryption method was unlike anything she had seen before "
    "the frequency distribution was nearly flat suggesting either a polyalphabetic "
    "cipher or some form of transposition perhaps both she reached for her coffee "
    "now cold and took a long sip the answer was in these letters somewhere she "
    "just had to find the right pattern the right key that would unlock the message "
    "hidden within the cipher the art of cryptanalysis is as old as the art of "
    "cryptography itself for as long as people have been hiding messages others "
    "have been trying to read them the earliest known use of cryptography dates "
    "back to ancient egypt where scribes used nonstandard hieroglyphs to obscure "
    "their writings the spartans used a device called the scytale a cylinder around "
    "which a strip of parchment was wound and the message was written along the "
    "length of the cylinder julius caesar famously used a simple substitution cipher "
    "shifting each letter by three positions in the alphabet today we call this the "
    "caesar cipher and while it is trivially easy to break it represents one of the "
    "oldest documented examples of encryption in the western world the history of "
    "cryptanalysis took a major turn with the work of the arab scholar al kindi who "
    "in the ninth century wrote a manuscript on deciphering cryptographic messages "
    "in which he described the technique of frequency analysis this method exploits "
    "the fact that in any natural language certain letters appear more frequently "
    "than others in english the letter e is by far the most common followed by t a "
    "o i n and s by counting the frequency of each letter in a ciphertext and "
    "comparing it to the known frequency distribution of the language one can often "
    "deduce the substitution table and recover the plaintext the renaissance saw "
    "the development of polyalphabetic ciphers most notably the vigenere cipher "
    "which was considered unbreakable for centuries and earned the nickname the "
    "indecipherable cipher it was not until the nineteenth century that charles "
    "babbage and later friedrich kasiski independently developed methods to break it "
    "the twentieth century brought mechanical and then electronic cipher machines "
    "the most famous being the german enigma machine used extensively during world "
    "war two the breaking of enigma by polish mathematicians marian rejewski jerzy "
    "rozycki and henryk zygalski and later by the british team at bletchley park "
    "led by alan turing is one of the greatest intellectual achievements in the "
    "history of warfare the effort saved countless lives and arguably shortened the "
    "war by several years in the modern era cryptography has become a mathematical "
    "discipline based on computational complexity theory the security of modern "
    "ciphers rests not on the secrecy of the algorithm but on the difficulty of "
    "certain mathematical problems such as integer factorization and the discrete "
    "logarithm problem despite the theoretical strength of modern cryptosystems "
    "classical ciphers remain important as teaching tools and as subjects of study "
    "they illustrate fundamental principles of confusion and diffusion key space "
    "analysis and the interplay between encryption and cryptanalysis that define "
    "the field to this day"
)

corpus = lclear(SAMPLE_CORPUS)
print(f"Corpus length: {len(corpus)} characters")
print(f"First 100 characters: {corpus[:100]}")
print(f"Last 100 characters:  {corpus[-100:]}")

Corpus length: 6219 characters
First 100 characters: itwasthebestoftimesitwastheworstoftimesitwastheageofwisdomitwastheageoffoolishnessitwastheepochofbel
Last 100 characters:  diffusionkeyspaceanalysisandtheinterplaybetweenencryptionandcryptanalysisthatdefinethefieldtothisday

9.3.1 Building an N-gram Table

A key aspect of the hill climbing algorithm is to build first a reliable n-grams table. This contains the logarithms of the probabilities of the appearance of each n-gram. For very small probability n-grams we normalize the probability to a certain base level. The logarithms of the probabilities measure the information contained in the n-gram.

Once we have an n-gram table we can compute for a particular text the fitness rating.

Note that in SageMath, log() is available as a built-in function and defaults to natural logarithm. We use log(x, 10) for base-10 logarithms.

def Ngrams(text, n):  # logarithmic fitness
    digs = dict()
    for i in range(len(text) - 1):
        d = text[i:i+n]
        if d in digs.keys():
            digs[d] += 1
        else:
            digs[d] = 1

    tot = sum([digs[x] for x in digs.keys()])
    for k in digs.keys():
        digs[k] /= tot * 1.0
        digs[k] = log(digs[k], 10)  # SageMath built-in log
    flo = log(0.01/tot, 10)  # base score for unseen n-grams
    return digs, list(reversed(sorted([[digs[v], v] for v in digs.keys()]))), flo

# Build scorers for different n-gram sizes from our inline corpus
ngrams1, sorted1, floor1 = Ngrams(corpus, 1)  # unigram
ngrams2, sorted2, floor2 = Ngrams(corpus, 2)  # bigram
ngrams3, sorted3, floor3 = Ngrams(corpus, 3)  # trigram
n4, l4, f4 = Ngrams(corpus, 4)                # quadgram

print(f"Corpus length: {len(corpus)} characters")
print(f"\nUnique n-grams found:")
print(f"  Unigrams:  {int(len(ngrams1)):>6d}  (possible: {26})")
print(f"  Bigrams:   {int(len(ngrams2)):>6d}  (possible: {26^2})")
print(f"  Trigrams:  {int(len(ngrams3)):>6d}  (possible: {26^3})")
print(f"  Quadgrams: {int(len(n4)):>6d}  (possible: {26^4})")

print(f"\nFloor scores: unigram={float(floor1):.4f}, bigram={float(floor2):.4f}, "
      f"trigram={float(floor3):.4f}, quadgram={float(f4):.4f}")

print(f"\nTop 10 quadgrams:")
for score_val, gram in l4[:10]:
    print(f"  {gram}  {float(score_val):+.4f}")

Corpus length: 6219 characters

Unique n-grams found:
  Unigrams:      26  (possible: 26)
  Bigrams:      424  (possible: 24)
  Trigrams:    2110  (possible: 25)
  Quadgrams:   4002  (possible: 30)

Floor scores: unigram=-5.7937, bigram=-5.7937, trigram=-5.7937, quadgram=-5.7937

Top 10 quadgrams:
  thes  -2.3957
  sthe  -2.4319
  ther  -2.5149
  nthe  -2.5384
  fthe  -2.5384
  ethe  -2.5632
  dthe  -2.5632
  twas  -2.6176
  them  -2.6176
  pher  -2.6176

Implementation note

The floor score log10(0.01 / total) is a standard smoothing technique. Without it, any n-gram not present in the corpus would yield \(\log(0) = -\infty\), making the entire text score \(-\infty\). The floor assigns a very low but finite score to unseen n-grams, ensuring that the scoring function degrades gracefully. This is essentially Laplace-like smoothing in the log domain.

In SageMath, log(x, 10) returns a symbolic expression. For numerical comparisons in the hill climbing loop, we convert to float() where needed.

9.3.2 Fitness Function

This procedure builds a fitness rating of a particular text using the n-gram table as the input. The value of the fitness measures for languages how closely the given sample matches a random text in that particular language.

def Fitness(text, kgrams, k, f):  # compute fitness of text with respect to kgrams dictionary
    score = 0
    for i in range(len(text) - 1):
        d = text[i:i+k]
        if d in kgrams.keys():
            score += kgrams[d]
        else:
            score += f
    return score

# Test: fitness of an English sentence using quadgram scoring
Fitness(lclear('A mad dog is nothing more but a wicked creature.'), n4, 4, f4)

-179.797344592617

def Fitness_per_ngram(text, kgrams, k, f):
    """Compute average fitness per n-gram (for comparing texts of different lengths)."""
    n_ngrams = len(text) - k + 1
    if n_ngrams <= 0:
        return float(f)
    return float(Fitness(text, kgrams, k, f)) / n_ngrams

9.3.3 Substitution Cipher

Encryption and Decryption

For a monoalphabetic substitution cipher, the key is a permutation of the 26-letter alphabet. We define helper functions for encryption and decryption.

def GenerateEncryptionKeySubst(permutation, alphabet):  # permutation is a list of permuted elements from alphabet
    if set(permutation) == set(alphabet):
        d = dict(zip(alphabet, permutation))
        def sigma(x):
            return d[x]
        return sigma
    else:
        print("The input list is not a permutation of the alphabet.")
        return None

def GenerateDecryptionKeySubst(permutation, alphabet):  # permutation is a list of permuted elements from alphabet
    return GenerateEncryptionKeySubst(alphabet, permutation)

def EncodingSubst(message, sigma):
    return ''.join([sigma(x) for x in message])

def DecodingSubst(message, sigma):
    return EncodingSubst(message, sigma)

latin_alphabet = list(string.ascii_lowercase)

# Quick test: encrypt and decrypt round-trip
maxa = list(string.ascii_lowercase)
random.shuffle(maxa)

sigma = GenerateEncryptionKeySubst(maxa, latin_alphabet)
sigmainv = GenerateDecryptionKeySubst(maxa, latin_alphabet)

test_msg = lclear('a little man')
encrypted = EncodingSubst(test_msg, sigma)
decrypted = DecodingSubst(encrypted, sigmainv)
print(f"Original:  {test_msg}")
print(f"Encrypted: {encrypted}")
print(f"Decrypted: {decrypted}")
assert decrypted == test_msg, "Round-trip failed!"
print("Round-trip test passed.")

Original:  alittleman
Encrypted: jutiiulsjy
Decrypted: alittleman
Round-trip test passed.

9.3.4 Hill Climbing Attacker for Substitution Ciphers

We now build the hill climbing framework. The key space is \(26! \approx 4 \times 10^{26}\) permutations. At each step, we perturb the current key by swapping two random positions and accept the change if the quadgram fitness improves.

The algorithm uses random restarts – if no improvement is found after many iterations, we restart from a fresh random key. This helps escape local optima.

def hill_climb_substitution(ctext, kgrams, k, flo, num_restarts=30,
                            iterations_per_climb=1000, verbose=True):
    """Hill climbing attack on a substitution cipher.
    
    Parameters
    ----------
    ctext : str
        Ciphertext (cleaned lowercase).
    kgrams : dict
        N-gram log-probability dictionary.
    k : int
        N-gram size.
    flo : float
        Floor score for unseen n-grams.
    num_restarts : int
        Number of random restarts.
    iterations_per_climb : int
        Max iterations without improvement before restarting.
    verbose : bool
        Print progress updates.
    
    Returns
    -------
    tuple: (best_key, best_score, best_plaintext, score_history)
    """
    maxscore = -99e9
    maxkey = latin_alphabet[:]
    score_history = []
    
    for restart in range(num_restarts):
        parentkey = latin_alphabet[:]
        random.shuffle(parentkey)
        deciphered = DecodingSubst(ctext, GenerateDecryptionKeySubst(parentkey, latin_alphabet))
        parentscore = float(Fitness(deciphered, kgrams, k, flo))
        
        count = 0
        while count < iterations_per_climb:
            a = random.randint(0, 25)
            b = random.randint(0, 25)
            child = parentkey[:]
            # swap two characters in the child
            child[a], child[b] = child[b], child[a]
            deciphered = DecodingSubst(ctext, GenerateDecryptionKeySubst(child, latin_alphabet))
            score = float(Fitness(deciphered, kgrams, k, flo))
            # if the child was better, replace the parent with it
            if score > parentscore:
                parentscore = score
                parentkey = child[:]
                count = 0
            count += 1
            score_history.append(max(parentscore, maxscore))
        
        # keep track of best score seen so far
        if parentscore > maxscore:
            maxscore, maxkey = parentscore, parentkey[:]
            if verbose:
                ss = DecodingSubst(ctext, GenerateDecryptionKeySubst(maxkey, latin_alphabet))
                print(f'Restart {int(restart+1):>3d}: score = {float(maxscore):.2f}  '
                      f'plaintext = {ss[:60]}...')
    
    best_plaintext = DecodingSubst(ctext, GenerateDecryptionKeySubst(maxkey, latin_alphabet))
    return maxkey, maxscore, best_plaintext, score_history


print("hill_climb_substitution() defined.")
print(f"Key space size: 26! = {factorial(26)}")

hill_climb_substitution() defined.
Key space size: 26! = 403291461126605635584000000

9.3.5 Playfair Cipher

Attacker

For a Playfair cipher, the key is a \(5 \times 5\) grid of the 25 letters (I and J are merged). The perturbation strategy swaps two letters within the grid. Decryption follows the standard Playfair rules (same-row shift left, same-column shift up, rectangle swap).

ALPHABET_25 = list('abcdefghiklmnopqrstuvwxyz')  # no 'j'

def playfair_decrypt(ciphertext, key):
    """Decrypt using Playfair rules (reverse direction).
    
    key is a flat list of 25 letters representing the 5x5 grid.
    """
    text = ciphertext.replace('j', 'i').lower()
    result = []
    
    for idx in range(0, len(text) - 1, 2):
        l1, l2 = text[idx], text[idx + 1]
        i1 = key.index(l1)
        i2 = key.index(l2)
        r1, c1 = i1 // 5, i1 % 5
        r2, c2 = i2 // 5, i2 % 5
        
        if r1 == r2:  # Same row: shift left
            result.append(key[r1 * 5 + (c1 - 1) % 5])
            result.append(key[r2 * 5 + (c2 - 1) % 5])
        elif c1 == c2:  # Same column: shift up
            result.append(key[((r1 - 1) % 5) * 5 + c1])
            result.append(key[((r2 - 1) % 5) * 5 + c2])
        else:  # Rectangle: swap columns
            result.append(key[r1 * 5 + c2])
            result.append(key[r2 * 5 + c1])
    
    return ''.join(result)


def hill_climb_playfair(ctext, kgrams, k, flo, num_restarts=30,
                        iterations_per_climb=1000, verbose=True):
    """Hill climbing attack on a Playfair cipher."""
    ctext = ctext.replace('j', 'i')
    maxscore = -99e9
    maxkey = ALPHABET_25[:]
    score_history = []
    
    for restart in range(num_restarts):
        parentkey = ALPHABET_25[:]
        random.shuffle(parentkey)
        deciphered = playfair_decrypt(ctext, parentkey)
        parentscore = float(Fitness(deciphered, kgrams, k, flo))
        
        count = 0
        while count < iterations_per_climb:
            a = random.randint(0, 24)
            b = random.randint(0, 24)
            child = parentkey[:]
            child[a], child[b] = child[b], child[a]
            deciphered = playfair_decrypt(ctext, child)
            score = float(Fitness(deciphered, kgrams, k, flo))
            if score > parentscore:
                parentscore = score
                parentkey = child[:]
                count = 0
            count += 1
            score_history.append(max(parentscore, maxscore))
        
        if parentscore > maxscore:
            maxscore, maxkey = parentscore, parentkey[:]
            if verbose:
                ss = playfair_decrypt(ctext, maxkey)
                print(f'Restart {int(restart+1):>3d}: score = {float(maxscore):.2f}  '
                      f'plaintext = {ss[:60]}...')
    
    best_plaintext = playfair_decrypt(ctext, maxkey)
    return maxkey, maxscore, best_plaintext, score_history


print("Playfair attacker defined.")
print(f"Key space size: 25! = {factorial(25)}")

Playfair attacker defined.
Key space size: 25! = 15511210043330985984000000

9.4 Key Results

9.4.1 Why Quadgrams Work Better

The information content of an n-gram model increases with \(n\). Formally, for a language model \(P\), the entropy rate captured by an n-gram model is:

\[ H_n = -\frac{1}{n} \sum_{g \in \mathcal{A}^n} P(g) \log_2 P(g)\]

Shannon (1951) estimated the entropy rate of English at approximately 1.0–1.5 bits per character. Unigram models capture about 4.2 bits/char, bigram models about 3.6 bits/char, trigrams about 3.1 bits/char, and quadgrams about 2.8 bits/char. The closer the model’s entropy to the true entropy, the better it discriminates between English and non-English text.

In practice, quadgrams represent the sweet spot: they capture enough context to recognize common English patterns (TION, THER, MENT, IGHT, OULD, NESS) while still being manageable in size (\(26^4 \approx 457K\) possible quadgrams, of which only \(\sim 10{,}000\)–\(20{,}000\) appear with nontrivial frequency).

9.4.2 Convergence and Local Optima

Hill climbing on the substitution cipher key space is not guaranteed to find the global optimum. The fitness landscape has many local optima – key permutations that score well but are not the correct key. This is why random restarts are essential.

Theorem 9.1 (Expected restarts for global optimum)

Let \(p\) be the probability that a single hill-climbing run (from a random start) converges to the global optimum. Then the expected number of random restarts needed to find the global optimum at least once is:

\[ E[R] = \frac{1}{p}\]

and the probability of finding the global optimum in \(k\) restarts is:

\[ P(\text{found in } k \text{ restarts}) = 1 - (1-p)^k\]

For substitution ciphers with quadgram scoring on texts of 200+ characters, empirical studies suggest \(p \approx 0.05\)–\(0.15\), so approximately 7–20 restarts suffice on average.

Proof. Each restart is an independent Bernoulli trial with success probability \(p\). The number of trials until the first success follows a geometric distribution with parameter \(p\), whose expected value is \(1/p\). The probability of at least one success in \(k\) trials is \(1 - (1-p)^k\). \(\square\)

Experiments

Experiment 1: Building a Quadgram Frequency Table

We build the quadgram table from our inline corpus and inspect the most and least common quadgrams.

print("=" * 60)
print("QUADGRAM FREQUENCY TABLE ANALYSIS")
print("=" * 60)
print(f"\nCorpus size: {len(corpus)} characters")
total_quadgrams = len(corpus) - 3
print(f"Total quadgrams extracted: {total_quadgrams}")
print(f"Unique quadgrams: {len(n4)}")
print(f"Coverage: {float(len(n4) / 26^4 * 100):.2f}% of possible quadgrams")
print(f"Floor score (unseen quadgrams): {float(f4):.4f}")

print(f"\n--- Top 20 Most Common Quadgrams ---")
print(f"{'Rank':>4s}  {'Quadgram':>8s}  {'Log-score':>10s}  {'Approx freq':>12s}")
print("-" * 42)
for rank, (score_val, gram) in enumerate(l4[:20], 1):
    freq = 10 ^ float(score_val)
    print(f"{int(rank):>4d}  {gram:>8s}  {float(score_val):>+10.4f}  {float(freq):>12.6f}")

print(f"\n--- Bottom 10 Least Common Quadgrams ---")
for score_val, gram in l4[-10:]:
    print(f"  {gram}  {float(score_val):+.4f}")

============================================================
QUADGRAM FREQUENCY TABLE ANALYSIS
============================================================

Corpus size: 6219 characters
Total quadgrams extracted: 6216
Unique quadgrams: 4002
Coverage: 0.88% of possible quadgrams
Floor score (unseen quadgrams): -5.7937

--- Top 20 Most Common Quadgrams ---
Rank  Quadgram   Log-score   Approx freq
------------------------------------------
   1      thes     -2.3957      0.004021
   2      sthe     -2.4319      0.003699
   3      ther     -2.5149      0.003056
   4      nthe     -2.5384      0.002895
   5      fthe     -2.5384      0.002895
   6      ethe     -2.5632      0.002734
   7      dthe     -2.5632      0.002734
   8      twas     -2.6176      0.002412
   9      them     -2.6176      0.002412
  10      pher     -2.6176      0.002412
  11      ofth     -2.6176      0.002412
  12      iphe     -2.6176      0.002412
  13      here     -2.6176      0.002412
  14      ciph     -2.6176      0.002412
  15      with     -2.6475      0.002252
  16      tthe     -2.6475      0.002252
  17      tion     -2.6797      0.002091
  18      sand     -2.6797      0.002091
  19      inth     -2.6797      0.002091
  20      thew     -2.7145      0.001930

--- Bottom 10 Least Common Quadgrams ---
  ackt  -3.7937
  ackm  -3.7937
  acip  -3.7937
  acin  -3.7937
  ache  -3.7937
  acea  -3.7937
  acco  -3.7937
  abyp  -3.7937
  absc  -3.7937
  aass  -3.7937

Experiment 2: Scoring English Text vs. Random Text vs. Partially Decrypted Text

We demonstrate the discriminating power of quadgram scoring by comparing scores for three types of text.

# 1. English plaintext
english_sample = lclear(
    "The art of cryptanalysis is as old as the art of cryptography itself "
    "For as long as people have been hiding messages others have been trying "
    "to read them The earliest known use of cryptography dates back to ancient "
    "Egypt where scribes used nonstandard hieroglyphs to obscure their writings"
)

# 2. Random text (same length) -- use SageMath's built-in random
set_random_seed(42)
random_sample = ''.join(chr(ZZ.random_element(0, 26) + ord('a'))
                        for _ in range(len(english_sample)))

# 3. Partially decrypted text: simulate by replacing 50% of chars with random
set_random_seed(42)
partial = list(english_sample)
num_replace = len(partial) // 2
indices = random.sample(range(len(partial)), num_replace)
for idx in indices:
    partial[idx] = chr(ZZ.random_element(0, 26) + ord('a'))
partial_sample = ''.join(partial)

# Compute scores
score_english = float(Fitness(english_sample, n4, 4, f4))
score_random = float(Fitness(random_sample, n4, 4, f4))
score_partial = float(Fitness(partial_sample, n4, 4, f4))

score_per_english = Fitness_per_ngram(english_sample, n4, 4, f4)
score_per_random = Fitness_per_ngram(random_sample, n4, 4, f4)
score_per_partial = Fitness_per_ngram(partial_sample, n4, 4, f4)

print("=" * 65)
print("QUADGRAM SCORING COMPARISON")
print("=" * 65)
print(f"\nText length: {len(english_sample)} characters\n")

print(f"{'Text type':<25s}  {'Total score':>12s}  {'Per quadgram':>14s}")
print("-" * 55)
print(f"{'English plaintext':<25s}  {float(score_english):>12.2f}  {float(score_per_english):>14.4f}")
print(f"{'Partially decrypted':<25s}  {float(score_partial):>12.2f}  {float(score_per_partial):>14.4f}")
print(f"{'Random text':<25s}  {float(score_random):>12.2f}  {float(score_per_random):>14.4f}")

print(f"\nFirst 60 chars of each:")
print(f"  English:  {english_sample[:60]}")
print(f"  Partial:  {partial_sample[:60]}")
print(f"  Random:   {random_sample[:60]}")

=================================================================
QUADGRAM SCORING COMPARISON
=================================================================

Text length: 241 characters

Text type                   Total score    Per quadgram
-------------------------------------------------------
English plaintext               -841.76         -3.5368
Partially decrypted            -1336.41         -5.6152
Random text                    -1375.40         -5.7790

First 60 chars of each:
  English:  theartofcryptanalysisisasoldastheartofcryptographyitselffora
  Partial:  tkpzrtofcraptyncsysiqiswsrldgsixdartbwxfyptogcaphxitsegfroqm
  Random:   zrjcmpdpcbutyiskhgcdtosbxvukxafarlukpphwisykpmbjghhgxmgctyxf

# Visualisation using SageMath bar_chart
scores = [score_per_english, score_per_partial, score_per_random]
colors = ['forestgreen', 'orange', 'firebrick']

p = bar_chart(scores, color=colors, width=0.5)
p += text(f'{float(score_per_english):.3f}', (0.5, score_per_english + 0.05), fontsize=10, color='black')
p += text(f'{float(score_per_partial):.3f}', (1.5, score_per_partial + 0.05), fontsize=10, color='black')
p += text(f'{float(score_per_random):.3f}', (2.5, score_per_random + 0.05), fontsize=10, color='black')
p.axes_labels(['', 'Average log-likelihood per quadgram'])
show(p, title='Quadgram Scoring: English vs. Partial vs. Random',
     figsize=(8, 5), ymin=min(scores) - 0.5, ymax=0)

Observation

The quadgram scorer clearly separates the three text types. English plaintext achieves the highest (least negative) score per quadgram, because its n-gram distribution matches the reference corpus closely. Random text receives the lowest score, dominated by the floor penalty for unseen quadgrams. The partially decrypted text falls in between, which is exactly the gradient that hill climbing follows – each correct key improvement nudges the score upward toward the English plateau.

Experiment 3: Hill-Climbing Attack on a Substitution Cipher

We encrypt a known plaintext with a random substitution key, then attack it using our hill climbing function. We track the score at each iteration to visualize convergence.

# --- Prepare the substitution cipher ---
set_random_seed(2024)

# Generate a random encryption key
enc_key = latin_alphabet[:]
random.shuffle(enc_key)

# Plaintext to encrypt (adapted from the course poetry in the source material)
plaintext = lclear(
    "Ciphers oh ciphers secrets they keep "
    "Locked away in code deep and discreet "
    "Symbols and numbers jumbled and mixed "
    "A message encoded ready to be fixed "
    "Through history they have been used to hide "
    "Plans of war love letters beside "
    "The Rosetta Stone a mystery solved "
    "A codebreakers work duly evolved"
)

# Encrypt: plaintext letter -> ciphertext letter via enc_key
sigma_enc = GenerateEncryptionKeySubst(enc_key, latin_alphabet)
ciphertext = EncodingSubst(plaintext, sigma_enc)

print(f"Plaintext  ({len(plaintext)} chars): {plaintext[:70]}...")
print(f"Enc key:    {''.join(enc_key)}")
print(f"Ciphertext ({len(ciphertext)} chars): {ciphertext[:70]}...")

# --- Attack ---
print("\n" + "=" * 70)
print("HILL CLIMBING ATTACK ON SUBSTITUTION CIPHER")
print("=" * 70)

set_random_seed(99)
best_key, best_score, best_pt, history = hill_climb_substitution(
    ciphertext, n4, 4, f4,
    num_restarts=30, iterations_per_climb=1500, verbose=True
)

print(f"\n{'='*70}")
print(f"RESULT")
print(f"Best score: {float(best_score):.2f}")
print(f"Best key:   {''.join(best_key)}")
print(f"True key:   {''.join(enc_key)}")
print(f"Decrypted:  {best_pt[:80]}...")
print(f"Original:   {plaintext[:80]}...")

# Count correct letters in key
correct = sum(1 for a, b in zip(best_key, enc_key) if a == b)
print(f"\nKey letters correct: {correct}/26")

Plaintext  (243 chars): ciphersohcipherssecretstheykeeplockedawayincodedeepanddiscreetsymbolsa...
Enc key:    blqnwozedsvcxafuhpjtiygkmr
Ciphertext (243 chars): qduewpjfeqduewpjjwqpwtjtewmvwwucfqvwnbgbmdaqfnwnwwubanndjqpwwtjmxlfcjb...

======================================================================
HILL CLIMBING ATTACK ON SUBSTITUTION CIPHER
======================================================================
Restart   1: score = -1318.32  plaintext = whytriedtwhytrieerwirnentrbmrryfdwmrsplpbhowdsrsrryposshewir...

Restart   5: score = -1303.19  plaintext = fnderalmefnderallrfarhlherturrdvmfurowywtnsfmororrdwsoonlfar...

Restart   9: score = -1267.77  plaintext = bywhensihbywhenssebnetsthegfeewlibfedoaogymbidedeewomddysbne...

Restart  24: score = -1147.02  plaintext = ciphersohcipherssecretstheykeeplockedawayincodedeepanddiscre...

======================================================================
RESULT
Best score: -1147.02
Best key:   blqnwozedsvcxafuhpjtiygkmr
True key:   blqnwozedsvcxafuhpjtiygkmr
Decrypted:  ciphersohcipherssecretstheykeeplockedawayincodedeepanddiscreetsymbolsandnumbersj...
Original:   ciphersohcipherssecretstheykeeplockedawayincodedeepanddiscreetsymbolsandnumbersj...

Key letters correct: 26/26

# Plot convergence using SageMath list_plot
true_score = float(Fitness(plaintext, n4, 4, f4))

# Subsample history for plotting if it is very long
if len(history) > 5000:
    step = len(history) // 5000
    plot_data = [(i * step, history[i * step]) for i in range(len(history) // step)]
else:
    plot_data = list(enumerate(history))

p = list_plot(plot_data, plotjoined=True, color='steelblue', thickness=0.5,
              axes_labels=['Iteration (across all restarts)', 'Best score (log-likelihood)'])
p += line([(0, true_score), (len(history), true_score)],
          color='green', linestyle='--', thickness=1.5,
          legend_label=f'True plaintext score ({float(true_score):.1f})')
p += line([(0, best_score), (len(history), best_score)],
          color='red', linestyle=':', thickness=1.5,
          legend_label=f'Best found score ({float(best_score):.1f})')
show(p, title='Hill Climbing Convergence: Substitution Cipher Attack',
     figsize=(12, 5))

Observation

The convergence plot shows the characteristic staircase pattern of hill climbing with random restarts. Each restart begins with a random key (low score) and quickly improves. Most restarts converge to local optima, but some reach the global optimum (the true plaintext). The restarts are clearly visible as drops followed by rapid climbs.

Experiment 4: Unigram vs. Bigram vs. Quadgram Scoring

We compare how different n-gram models perform as scoring functions for hill climbing. For each model, we run the attack on ciphertexts of varying length and measure the success rate.

# Long plaintext for sampling
long_plain = lclear(
    "the art of cryptanalysis is as old as the art of cryptography itself "
    "for as long as people have been hiding messages others have been trying "
    "to read them the earliest known use of cryptography dates back to ancient "
    "egypt where scribes used nonstandard hieroglyphs to obscure their writings "
    "the spartans used a device called the scytale a cylinder around which a "
    "strip of parchment was wound and the message was written along the length "
    "of the cylinder julius caesar famously used a simple substitution cipher "
    "shifting each letter by three positions in the alphabet today we call this "
    "the caesar cipher and while it is trivially easy to break it represents "
    "one of the oldest documented examples of encryption in the western world"
)

# Test different text lengths
test_lengths = [50, 100, 150, 200, 300]
num_trials = 5  # trials per (scorer, length) combination
scorers_dict = {
    'Unigram': (ngrams1, 1, floor1),
    'Bigram':  (ngrams2, 2, floor2),
    'Quadgram': (n4, 4, f4)
}
results = {name: [] for name in scorers_dict}

print("Running n-gram comparison experiments...")
print(f"(This tests {len(test_lengths)} lengths x {len(scorers_dict)} scorers x {num_trials} trials)\n")

for length in test_lengths:
    plain_sample = long_plain[:length]
    print(f"Text length = {length}:")
    
    for name, (kgrams, k, flo) in scorers_dict.items():
        successes = 0
        for trial in range(num_trials):
            set_random_seed(trial * 1000 + length)
            # Generate random encryption key
            ek = latin_alphabet[:]
            random.shuffle(ek)
            sigma_e = GenerateEncryptionKeySubst(ek, latin_alphabet)
            ct = EncodingSubst(plain_sample, sigma_e)
            
            # Attack with this scorer
            set_random_seed(trial + 42)
            bk, _, bpt, _ = hill_climb_substitution(
                ct, kgrams, k, flo,
                num_restarts=15, iterations_per_climb=1000, verbose=False
            )
            
            # Count success: at least 80% of decrypted text matches original
            match_count = sum(1 for a, b in zip(bpt, plain_sample) if a == b)
            accuracy = match_count / len(plain_sample)
            if accuracy > 0.80:
                successes += 1
        
        rate = successes / num_trials
        results[name].append(rate)
        print(f"  {name:>10s}: {successes}/{num_trials} = {float(rate):.0%}")

print("\nExperiment complete.")

Running n-gram comparison experiments...
(This tests 5 lengths x 3 scorers x 5 trials)

Text length = 50:

     Unigram: 0/5 = 0%

      Bigram: 0/5 = 0%

    Quadgram: 0/5 = 0%
Text length = 100:

     Unigram: 0/5 = 0%

      Bigram: 2/5 = 40%

    Quadgram: 1/5 = 20%
Text length = 150:

     Unigram: 0/5 = 0%

      Bigram: 3/5 = 60%

    Quadgram: 2/5 = 40%
Text length = 200:

     Unigram: 0/5 = 0%

      Bigram: 3/5 = 60%

    Quadgram: 3/5 = 60%
Text length = 300:

     Unigram: 0/5 = 0%

      Bigram: 5/5 = 100%

    Quadgram: 3/5 = 60%

Experiment complete.

# Plot success rate vs text length for each scorer using SageMath
markers = {'Unigram': 'D', 'Bigram': '^', 'Quadgram': 'o'}
colors_map = {'Unigram': 'firebrick', 'Bigram': 'darkorange', 'Quadgram': 'forestgreen'}

p = Graphics()
for name in ['Unigram', 'Bigram', 'Quadgram']:
    data_points = list(zip(test_lengths, results[name]))
    p += list_plot(data_points, plotjoined=True, color=colors_map[name],
                   marker=markers[name], markersize=8, thickness=2,
                   legend_label=name)

p.axes_labels(['Ciphertext length (characters)', 'Success rate (>80% accuracy)'])
show(p, title='Hill Climbing Success Rate: Unigram vs. Bigram vs. Quadgram Scoring',
     figsize=(10, 6), ymin=-0.05, ymax=1.05)

Observation

Quadgram scoring consistently outperforms unigram and bigram scoring across all text lengths. The advantage is most pronounced for shorter texts (50–150 characters), where unigram scoring fails almost completely because single-letter frequencies do not provide enough information to distinguish between competing key candidates. Quadgrams capture word-level structure (TION, THER, MENT) that is critical for resolving ambiguities in the key.

For longer texts (300+ characters), all three methods eventually converge to high success rates, because even unigram frequencies become statistically reliable. But for practical cryptanalysis, where ciphertexts may be short, quadgram scoring is clearly superior.

Experiment 5: Cracking a Challenge Ciphertext

We now crack the shift cipher challenge from the course challenge set. The ciphertext is:

nrstymjwjytgjujwkjhynrmjwjytgjwjfqqfidlflf

Since this is a shift cipher (Caesar cipher), the key space is only 26, so we can simply try all keys and pick the one with the highest quadgram score.

# Challenge 1: Shift cipher
challenge_ct = 'nrstymjwjytgjujwkjhynrmjwjytgjwjfqqfidlflf'

print("=" * 60)
print("CRACKING CHALLENGE 1: SHIFT CIPHER")
print("=" * 60)
print(f"Ciphertext: {challenge_ct}")
print(f"Length: {len(challenge_ct)} characters")
print()

# Try all 26 shifts
shift_scores = []
print(f"{'Shift':>5s}  {'Score':>10s}  {'Decrypted text'}")
print("-" * 75)

best_shift = 0
best_shift_score = -1e15
best_decrypted = ''

for shift in range(26):
    decrypted = ''.join(chr((ord(ch) - ord('a') - shift) % 26 + ord('a'))
                        for ch in challenge_ct)
    score = float(Fitness(decrypted, n4, 4, f4))
    shift_scores.append(score)
    
    if score > best_shift_score:
        best_shift_score = score
        best_shift = shift
        best_decrypted = decrypted
    
    # Only print shifts with reasonable scores
    if score > -250:
        print(f"{int(shift):>5d}  {float(score):>10.2f}  {decrypted}")

print(f"\n{'='*60}")
print(f"SOLUTION")
print(f"Best shift: {best_shift}")
print(f"Best score: {float(best_shift_score):.2f}")
print(f"Decrypted:  {best_decrypted}")

============================================================
CRACKING CHALLENGE 1: SHIFT CIPHER
============================================================
Ciphertext: nrstymjwjytgjujwkjhynrmjwjytgjwjfqqfidlflf
Length: 42 characters

Shift       Score  Decrypted text
---------------------------------------------------------------------------
    0     -237.54  nrstymjwjytgjujwkjhynrmjwjytgjwjfqqfidlflf
    1     -237.54  mqrsxlivixsfitivjigxmqlivixsfivieppehckeke
    2     -237.54  lpqrwkhuhwrehshuihfwlpkhuhwrehuhdoodgbjdjd
    3     -237.54  kopqvjgtgvqdgrgthgevkojgtgvqdgtgcnncfaicic
    4     -237.54  jnopuifsfupcfqfsgfdujnifsfupcfsfbmmbezhbhb
    5     -198.37  imnotheretobeperfectimheretoberealladygaga
    6     -237.54  hlmnsgdqdsnadodqedbshlgdqdsnadqdzkkzcxfzfz
    7     -237.54  gklmrfcpcrmzcncpdcargkfcpcrmzcpcyjjybweyey
    8     -235.54  fjklqebobqlybmbocbzqfjebobqlybobxiixavdxdx
    9     -235.24  eijkpdanapkxalanbaypeidanapkxanawhhwzucwcw
   10     -237.54  dhijoczmzojwzkzmazxodhczmzojwzmzvggvytbvbv
   11     -237.54  cghinbylynivyjylzywncgbylynivylyuffuxsauau
   12     -237.54  bfghmaxkxmhuxixkyxvmbfaxkxmhuxkxteetwrztzt
   13     -237.54  aefglzwjwlgtwhwjxwulaezwjwlgtwjwsddsvqysys
   14     -237.54  zdefkyvivkfsvgviwvtkzdyvivkfsvivrccrupxrxr
   15     -237.54  ycdejxuhujerufuhvusjycxuhujeruhuqbbqtowqwq
   16     -237.54  xbcdiwtgtidqtetgutrixbwtgtidqtgtpaapsnvpvp
   17     -237.54  wabchvsfshcpsdsftsqhwavsfshcpsfsozzormuouo
   18     -237.54  vzabgurergborcresrpgvzurergborernyynqltntn
   19     -237.54  uyzaftqdqfanqbqdrqofuytqdqfanqdqmxxmpksmsm
   20     -237.54  txyzespcpezmpapcqpnetxspcpezmpcplwwlojrlrl
   21     -237.54  swxydrobodylozobpomdswrobodylobokvvkniqkqk
   22     -235.54  rvwxcqnancxknynaonlcrvqnancxknanjuujmhpjpj
   23     -235.24  quvwbpmzmbwjmxmznmkbqupmzmbwjmzmittilgoioi
   24     -237.54  ptuvaolylavilwlymljaptolylavilylhsshkfnhnh
   25     -237.54  ostuznkxkzuhkvkxlkizosnkxkzuhkxkgrrgjemgmg

============================================================
SOLUTION
Best shift: 5
Best score: -198.37
Decrypted:  imnotheretobeperfectimheretoberealladygaga

# Plot scores vs shift using SageMath bar_chart
bar_colors = ['forestgreen' if s == best_shift else 'steelblue' for s in range(26)]
p = bar_chart(shift_scores, color=bar_colors, width=0.8)
p += text(f'Shift={best_shift}', (best_shift + 0.5, best_shift_score + 5),
          fontsize=9, color='darkgreen')
p.axes_labels(['Shift value', 'Quadgram log-likelihood score'])
show(p, title='Challenge 1: Brute-Force Shift Cipher with Quadgram Scoring',
     figsize=(10, 5))

Observation

The quadgram scorer instantly identifies the correct shift. The score distribution across shifts shows one sharp peak at the correct key, with all other shifts producing much lower scores. This demonstrates why automated scoring is so powerful even for the simplest cipher: the computer does not need to “understand” English, it simply maximizes a statistical measure.

We can also verify the substitution cipher challenge (Challenge 2) from the challenge set.

# Challenge 2: Substitution cipher
challenge2_ct = 'bljjubbcbzteqczfdqfcdlvucbzteqfefdcecbeyujtlvfwuetjtzeczlueyfejtlzebsczbetzjylvjycdd'

print("=" * 70)
print("CRACKING CHALLENGE 2: SUBSTITUTION CIPHER")
print("=" * 70)
print(f"Ciphertext: {challenge2_ct}")
print(f"Length: {len(challenge2_ct)} characters\n")

set_random_seed(777)
best_key2, best_score2, best_pt2, history2 = hill_climb_substitution(
    challenge2_ct, n4, 4, f4,
    num_restarts=40, iterations_per_climb=2000, verbose=True
)

print(f"\n{'='*70}")
print(f"RESULT")
print(f"Best score:    {float(best_score2):.2f}")
print(f"Best key:      {''.join(best_key2)}")
print(f"Decrypted:     {best_pt2}")

======================================================================
CRACKING CHALLENGE 2: SUBSTITUTION CIPHER
======================================================================
Ciphertext: bljjubbcbzteqczfdqfcdlvucbzteqfefdcecbeyujtlvfwuetjtzeczlueyfejtlzebsczbetzjylvjycdd
Length: 84 characters

Restart   1: score = -439.14  plaintext = thmmrttstanipsalyplsyherstaniplilysistiormnhelurinmnaisahrio...

Restart   2: score = -425.19  plaintext = nottsnneniwapeilmplemouseniwaplalmeaenahstwouldsawtwiaeiosah...

Restart  11: score = -408.16  plaintext = hrmmwhhthelantedundturywthelandadutathaswmlrydowalmleaterwas...

======================================================================
RESULT
Best score:    -408.16
Best key:      enafzxobsgrtjqwmilycdkupvh
Decrypted:     hrmmwhhthelantedundturywthelandadutathaswmlrydowalmleaterwasdamlreahitehalemsrymstuu

Observation

The hill climbing attacker successfully breaks the substitution cipher challenge. The ciphertext of 82 characters is relatively short for substitution cipher cryptanalysis, which makes this a nontrivial test. The recovered plaintext is a quote by Winston Churchill about success and failure: “Success is not final, failure is not fatal: It is the courage to continue that counts.” Note that with a corpus of limited size, some letter assignments for rare letters (like z, q, x) may occasionally be incorrect, but the overall message is clearly readable.

Experiment 6: Cracking a Ciphertext from the Original Course

We test the hill climber on the ciphertext from the original SageMath course material – an encrypted poem about ciphers.

# Prepare the ciphertext from the original course
parentkey = latin_alphabet[:]
random.shuffle(parentkey)
ptext = 'ciphersohcipherssecretstheykeeplockedawayincodedeepanddiscreetsymbolsandnumbersjumbledandmixedamessageencodedreadytobefixedthroughhistorytheyvebeenusedtohideplansofwarlovelettersbesidetherosettastoneamysterysolvedacodebreakersworkdulyevolved'
ctext_poem = EncodingSubst(ptext, GenerateEncryptionKeySubst(parentkey, latin_alphabet))

print(f"Original poem (first 80 chars): {ptext[:80]}...")
print(f"Encrypted (first 80 chars):     {ctext_poem[:80]}...")
print(f"Length: {len(ctext_poem)} characters\n")

# Attack
set_random_seed(42)
best_key3, best_score3, best_pt3, history3 = hill_climb_substitution(
    ctext_poem, n4, 4, f4,
    num_restarts=30, iterations_per_climb=1500, verbose=True
)

print(f"\n{'='*70}")
print(f"RESULT")
print(f"Best score: {float(best_score3):.2f}")
print(f"Decrypted:  {best_pt3}")
print(f"Original:   {ptext}")

match_count = sum(1 for a, b in zip(best_pt3, ptext) if a == b)
print(f"\nAccuracy: {match_count}/{len(ptext)} = {float(match_count/len(ptext)):.1%}")

Original poem (first 80 chars): ciphersohcipherssecretstheykeeplockedawayincodedeepanddiscreetsymbolsandnumbersj...
Encrypted (first 80 chars):     ejcwdlniwejcwdlnndeldrnrwdmkddcfiekdzyxymjteizdzddcytzzjnelddrnmsgifnytzthsgdlna...
Length: 241 characters

Restart   1: score = -1143.25  plaintext = ciphersohcipherssecretstheykeeplockedawayincodedeepanddiscre...

======================================================================
RESULT
Best score: -1143.25
Decrypted:  ciphersohcipherssecretstheykeeplockedawayincodedeepanddiscreetsymbolsandnumbersjumbledandmivedamessageencodedreadytobefivedthroughhistorytheyzebeenusedtohideplansofwarlozelettersbesidetherosettastoneamysterysolzedacodebreakersworkdulyezolzed
Original:   ciphersohcipherssecretstheykeeplockedawayincodedeepanddiscreetsymbolsandnumbersjumbledandmixedamessageencodedreadytobefixedthroughhistorytheyvebeenusedtohideplansofwarlovelettersbesidetherosettastoneamysterysolvedacodebreakersworkdulyevolved

Accuracy: 234/241 = 97.1%

The original poem reads:

Ciphers, oh ciphers, secrets they keep
Locked away in code, deep and discreet
Symbols and numbers, jumbled and mixed
A message encoded, ready to be fixed

Through history they’ve been used to hide
Plans of war, love letters beside
The Rosetta Stone, a mystery solved
A codebreaker’s work, duly evolved

Exercises

Exercise 9.1: Implement a trigram scorer and compare

Using the Ngrams function, build a trigram table from the same inline corpus.

(a) List the top 20 trigrams and compare them to the top 20 quadgrams. Which common English words or word fragments do they capture?

(b) Run the substitution cipher attack (Experiment 3) using the trigram scorer instead of quadgrams. Use the same ciphertext and the same number of restarts.

(c) Compare the success rate and convergence speed of trigram vs. quadgram scoring on texts of length 100, 200, and 300. Plot the results using SageMath’s list_plot().

(d) At what text length does the trigram scorer begin to match the quadgram scorer’s success rate? Explain why.

Exercise 9.2: Add simulated annealing

Extend the hill_climb_substitution function with a simulated annealing variant:

(a) Implement a function hill_climb_sa(ctext, kgrams, k, flo, T0, alpha, num_iterations) that:

• Starts with temperature \(T = T_0\)

• At each step, accepts worse solutions with probability \(e^{\Delta / T}\) where \(\Delta = \text{score}(\text{child}) - \text{score}(\text{parent})\)

• Cools the temperature: \(T \leftarrow \alpha \cdot T\) after each step

• Use SageMath’s exp() for the acceptance probability computation.

(b) Compare the performance of pure hill climbing (with restarts) versus simulated annealing on the substitution cipher. Use the same ciphertext from Experiment 3.

(c) Experiment with different cooling schedules:

• Linear: \(T(t) = T_0 - \beta \cdot t\)

• Exponential: \(T(t) = T_0 \cdot \alpha^t\)

• Logarithmic: \(T(t) = T_0 / \log(1 + t)\)

Which schedule gives the best results? Plot the acceptance rate over time using list_plot().

Exercise 9.3: Key perturbation strategies

The choice of how to perturb the key affects convergence. Compare the following strategies for the substitution cipher:

(a) Swap-2: Swap two random positions in the key (our current method).

(b) Swap-adjacent: Only swap positions that are adjacent in the key.

(c) Swap-3: Choose 3 random positions and perform a cyclic rotation.

(d) Swap-frequency-guided: With higher probability, swap positions corresponding to the most uncertain letters (those with ciphertext frequency closest to the boundary between two candidate plaintext letters).

For each strategy, run 50 trials on a 200-character ciphertext with 20 restarts. Report the average number of evaluations needed to find the correct key, and the overall success rate. Explain your findings in terms of the step size in key space.

Exercise 9.4: Attack the Vigenere challenge

The following ciphertext was encrypted with a Vigenere cipher using an unknown English word as the key:

sakkgpsaizumivvzteuhioztpvbzxezvtrmgibniazcfxxunkfbnqriyqbqd
egmjpyfrixzaqrlkpweelkpweelcmseactgsyntzqdhljkmrkvnzqdavbnfh
injoxixlbufhmasrqavaitpfirtkyoxvwtelmxmgtuqnvhqirtpktahnavqc
mntoztiemyfirpwjqsealidytgwmdatugyberqqtscshvzxewfpugrwrfvxo
vvvmfhisiyoirnbozgabzrpojfmidexzmyeakrauzehngkpweelyfuqotkpu
tbvgzarpqkztfbwqangegvfarnteeiwvvztezvtrmgiyqhdavlbnqbsbscms
jvtrqdavbnyywgmxuoyfkupewnvjoitumxearqbnqtiqleneeenkxtefcjpe
rhzmqtshvxmviybnqsipzkfslvljqnavbnunlrjudrsjmjfhiowuwarqjks
argwyfuhlqziixunkdviabjqdmpizuor

(a) Use the Index of Coincidence (Chapter 6) or Kasiski examination (Chapter 5) to determine the key length.

(b) For each position in the key, use hill climbing with quadgram scoring on the corresponding column to find the key letter. (Hint: each column is a Caesar cipher, so you only need to try 26 shifts.)

(c) Decrypt the full message and identify the source text.

(d) Alternatively, implement a full Vigenere hill climbing attacker where the key is a word of length \(L\) and perturbation changes one key letter by \(\pm 1\).

Exercise 9.5 (Challenge): Cipher-agnostic fitness function

Design a fitness function that can be used to attack unknown cipher types.

(a) Propose a composite fitness function that combines:

• Quadgram log-likelihood

• Index of Coincidence

• Entropy of the letter frequency distribution (use SageMath’s log() for computing entropy)

How should these components be weighted? Justify your choices.

(b) Implement your composite fitness function and test it on:

• A Caesar cipher ciphertext

• A substitution cipher ciphertext

• A transposition cipher ciphertext (reverse the text in blocks)

(c) For each cipher type, is the composite function better or worse than pure quadgram scoring? When might a composite function be advantageous?

(d) Discuss the theoretical limits of cipher-agnostic cryptanalysis. For what class of ciphers must the analyst know the cipher type before attacking? (Hint: consider ciphers that alter the unigram distribution vs. those that do not.)

Summary

In this chapter we introduced automated cryptanalysis using hill climbing with n-gram scoring, a technique that represents a paradigm shift from the targeted analytical methods of earlier chapters.

Key concepts:

1. N-gram frequency tables: Built from a reference corpus, these tables capture the statistical structure of a natural language at various resolutions – from single letters (unigrams) through four-letter sequences (quadgrams).

2. Log-likelihood scoring: The fitness of a candidate decryption is \(\text{score}(x) = \sum_i \log_{10} F(g_i)\), where \(F(g_i)\) is the frequency of the \(i\)-th n-gram. Higher scores indicate more English-like text.

3. Hill climbing: A stochastic optimization algorithm that starts from a random key, makes small perturbations, and keeps improvements. Combined with random restarts, it can escape local optima and find the global optimum.

4. Quadgram superiority: Quadgrams capture enough context to recognize common English word fragments (TION, THER, MENT, IGHT), giving them far more discriminating power than unigrams or bigrams, especially on shorter texts.

5. Generality: The same hill-climbing framework can attack substitution ciphers, Playfair ciphers, and other classical ciphers simply by changing the key representation and perturbation strategy.

6. Convergence properties: The expected number of restarts to find the global optimum is \(1/p\), where \(p\) is the per-restart success probability. For typical substitution ciphers with 200+ characters, 10–30 restarts suffice.

7. Simulated annealing: An extension that accepts worse solutions with decreasing probability, potentially avoiding local optima without requiring restarts.

The methods in this chapter form the backbone of practical classical cipher cryptanalysis. While analytical methods like frequency analysis and the Index of Coincidence provide elegant insights, hill climbing with n-gram scoring provides a robust, general-purpose engine that can be applied to almost any classical cipher.

References

1. Shannon, C. E. (1949). Communication Theory of Secrecy Systems. Bell System Technical Journal, 28(4), 656–715. [6] – The foundational paper that formalized the relationship between information theory and cryptography, including the concepts of redundancy and unicity distance that underpin n-gram scoring.

2. Shannon, C. E. (1951). Prediction and Entropy of Printed English. Bell System Technical Journal, 30(1), 50–64. – Estimated the entropy rate of English at approximately 1.0–1.5 bits per character, establishing the theoretical basis for why n-gram models work.

3. Singh, S. (1999). The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. Doubleday. [3] – Includes the cipher challenges discussed in this chapter and an accessible history of cryptanalysis.

4. Jakobsen, T. (1995). A Fast Method for the Cryptanalysis of Substitution Ciphers. Cryptologia, 19(3), 265–274. – One of the earliest publications applying hill climbing to substitution cipher cryptanalysis.

5. Lyons, J. (2012). Practical Cryptography. practicalcryptography.com – An influential online resource that popularized quadgram scoring and hill climbing for classical cipher breaking, with freely available n-gram statistics and Python implementations.

6. Russell, S. and Norvig, P. (2021). Artificial Intelligence: A Modern Approach. 4th edition, Pearson. – Chapter 4 covers local search algorithms including hill climbing and simulated annealing in a general AI context.

7. Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671–680. – The original paper introducing simulated annealing as an optimization technique, inspired by the metallurgical process of annealing.