Cracking Challenges (SageMath)

Cracking Challenges (SageMath)#

Standalone Challenges Notebook

This notebook contains practice challenges covering classical ciphers from Parts I–III of the course. Each challenge provides a ciphertext generated by a specific cipher. Your task is to crack it using the techniques you have learned.

Prerequisites and Cross-References#

These challenges draw on techniques from the following chapters:

Challenge	Cipher	Relevant Chapter
1	Caesar (shift) cipher	Ch 1 – Introduction
2	Monoalphabetic substitution	Ch 4 – Monoalphabetic Cryptanalysis
3a/3b	Vigenère cipher	Ch 5 – Vigenère & Kasiski, Ch 6 – Index of Coincidence
4	Playfair cipher	Ch 8 – Playfair Cipher

Setup: Utility Functions and Plaintext Data#

The cell below defines the lclear() helper function (used throughout the challenges to strip non-alphabetic characters) and declares the plaintext messages and keys that will be used to generate the challenge ciphertexts.

import re
import string
def lclear(text):
    return re.sub(r'[^a-z]', '', text.lower()) # we use regular expressions

#Caesar

plain1='''I'm not here to be perfect, I'm here to be real. - Lady Gaga'''
key1=5


#Substitution cipher
plain2='''"Success is not final, failure is not fatal: It is the courage to continue that counts." - Winston Churchill'''
key2='fxjguqwycpidnztkhvbelmsoar'

#Vigenere
#John Donne
plain3='''No man is an island,

Entire of itself,

Every man is a piece of the continent,

A part of the main.

If a clod be washed away by the sea,

Europe is the less.

As well as if a promontory were.

As well as if a manor of thy friend’s

Or of thine own were:

Any man’s death diminishes me,

Because I am involved in mankind,

And therefore never send to know for whom the bell tolls;

It tolls for thee.'''
key='island'

#Playfair cipher
plain4=''''''
key4=''

Challenge 1: Caesar Cipher#

Difficulty: Easy

The ciphertext below was produced by a Caesar (shift) cipher with shift key \(k = 5\).

Your task: Decrypt the ciphertext. Try all 26 possible shifts, or use frequency analysis to identify the correct offset.

print(''.join([chr((ord(x)-ord('a')+5)%26+ord('a')) for x in lclear(plain1).lower()]))

nrstymjwjytgjujwkjhynrmjwjytgjwjfqqfidlflf

Hint — Challenge 1

A Caesar cipher shifts every letter by the same fixed amount. To decrypt, shift each letter back by the key value. In SageMath you can write:

''.join([chr((ord(x) - ord('a') - key1) % 26 + ord('a')) for x in ciphertext])

Alternatively, try all 26 shifts and see which one produces readable English.

Challenge 2: Monoalphabetic Substitution Cipher#

Difficulty: Medium

The ciphertext below was produced by a monoalphabetic substitution cipher — a general permutation of the 26-letter alphabet (not just a shift). The encryption key is a permutation \(\sigma \in S_{26}\), constructed using SageMath’s Permutations group.

Your task: Recover the plaintext using frequency analysis, digram analysis, or the hill-climbing approach from Chapter 4.

#challenge 2

import string
import re
latin_alphabet = list(string.ascii_lowercase)

Sigmas=Permutations(range(26))
sig=Sigmas([5, 23, 9, 6, 20, 16, 22, 24, 2, 15, 8, 3, 13, 25, 19, 10, 7, 21, 1, 4, 11, 12, 18, 14, 0, 17])
#Sigmas.random_element()
subs=[latin_alphabet[i] for i in sig]

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)

sigma  = GenerateEncryptionKeySubst(subs,latin_alphabet)
sigmad = GenerateDecryptionKeySubst(subs,latin_alphabet)

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

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

m=lclear(plain2)
c=EncodingSubst(m,sigma)

key2=''.join([sigma(x) for x in latin_alphabet])
print(c)

bljjubbcbzteqczfdqfcdlvucbzteqfefdcecbeyujtlvfwuetjtzeczlueyfejtlzebsczbetzjylvjycdd

Hint — Challenge 2

Frequency analysis: Count the letter frequencies in the ciphertext and compare them to standard English letter frequencies (e, t, a, o, i, n, s, h, r, …).
Digram analysis: Look at the most common two-letter pairs (th, he, in, er, an, …).
Automated approach: Use the hill-climbing substitution-cipher cracker from Chapter 4 with n-gram fitness scoring.

Remember: the decryption key is the inverse permutation of the encryption key.

Challenge 3a: Vigenère Cipher (English Text)#

Difficulty: Medium

The ciphertext below was produced by a Vigenère cipher. The plaintext is an English-language story about a teddy bear named Edward, encrypted with the key "enigma" (length 6).

Your task: Determine the key length using the Kasiski examination or the index of coincidence, then recover the key and decrypt the message.

#challenge 3

#Vigener cipher


import string
import re

def vigenere_encrypt(plaintext, key):
    # Create a dictionary to map each letter to its position in the alphabet
    alphabet = string.ascii_lowercase
    letter_to_index = dict(zip(alphabet, range(len(alphabet))))
    
    # Create a list to store the ciphertext
    ciphertext = []
    
    # Convert the key to lowercase
    key = key.lower()
    
    # Loop over the plaintext and encrypt each letter
    for i, letter in enumerate(plaintext):
        # Skip non-letter characters
        if letter.lower() not in alphabet:
            ciphertext.append(letter)
            continue
        
        # Determine the index of the key letter to use
        key_letter = key[i % len(key)]
        key_index = letter_to_index[key_letter]
        
        # Determine the index of the plaintext letter
        plaintext_index = letter_to_index[letter.lower()]
        
        # Encrypt the letter and append it to the ciphertext
        ciphertext_letter = alphabet[(plaintext_index + key_index) % len(alphabet)]
        ciphertext.append(ciphertext_letter)
    
    # Convert the ciphertext list to a string and return it
    return ''.join(ciphertext)


def vigenere_decrypt(ciphertext, key):
    # Create a dictionary to map each letter to its position in the alphabet
    alphabet = string.ascii_lowercase
    letter_to_index = dict(zip(alphabet, range(len(alphabet))))
    
    # Create a list to store the plaintext
    plaintext = []
    
    # Convert the key to lowercase
    key = key.lower()
    
    # Loop over the ciphertext and decrypt each letter
    for i, letter in enumerate(ciphertext):
        # Skip non-letter characters
        if letter.lower() not in alphabet:
            plaintext.append(letter)
            continue
        
        # Determine the index of the key letter to use
        key_letter = key[i % len(key)]
        key_index = letter_to_index[key_letter]
        
        # Determine the index of the ciphertext letter
        ciphertext_index = letter_to_index[letter.lower()]
        
        # Decrypt the letter and append it to the plaintext
        plaintext_letter = alphabet[(ciphertext_index - key_index) % len(alphabet)]
        plaintext.append(plaintext_letter)
    
    # Convert the plaintext list to a string and return it
    return ''.join(plaintext)

plaintext = lclear('''Once upon a time in the quaint little village of Cozysprings, there lived a teddy bear named Edward. Edward was an unusual teddy bear, gifted with the ability to think, learn, and feel emotions like a human being. He had a special interest in codes and cryptography, spending countless hours exploring the fascinating world of secret messages.

One day, Edward stumbled upon an ancient book on cryptanalysis in the village library. The book was filled with mysterious codes and ciphers, and the teddy bear felt a sudden urge to unravel the secrets hidden within. He borrowed the book and began to study it with fervent dedication.''')
key = "enigma"
ciphertext = vigenere_encrypt(plaintext, key)
print(ciphertext)

sakkgpsaizumivvzteuhioztpvbzxezvtrmgibniazcfxxunkfbnqriyqbqdegmjpyfrixzaqrlkpweelkpweelcmseactgsyntzqdhljkmrkvnzqdavbnfhinjoxixlbufhmasrqavaitpfirtkyoxvwtelmxmgtuqnvhqirtpktahnavqcmntoztiemyfirpwjqsealidytgwmdatugyberqqtscshvzxewfpugrwrfvxovvvmfhisiyoirnbozgabzrpojfmidexzmyeakrauzehngkpweelyfuqotkputbvgzarpqkztfbwqangegvfarnteeiwvvztezvtrmgiyqhdavlbnqbsbscmsjvtrqdavbnyywgmxuoyfkupewnvjoitumxearqbnqtiqleneeenkxtefcjperhzmqtshvxmviybnqsipzkfslvljqnavbnunlrjudrsjmjfhiowuwarqjksargwyfuhlqziixunkdviabjqdmpizuor

Hint — Challenge 3a

Key length: Use the Kasiski examination — find repeated trigrams in the ciphertext and compute the GCD of the distances between them. Or compute the index of coincidence for different candidate key lengths.
Key recovery: Once you know the key length \(k\), split the ciphertext into \(k\) streams (every \(k\)-th letter). Each stream is a simple Caesar cipher — use frequency analysis on each stream independently.
The key has 6 letters.

Challenge 3b: Vigenère Cipher (Polish Text)#

Difficulty: Hard

This challenge uses the same Vigenère cipher and key as Challenge 3a, but the plaintext is in Polish. The text describes the historic 1939 meeting at Pyry where Polish cryptanalysts shared their Enigma-breaking methods with British and French intelligence.

Your task: Decrypt the ciphertext. Note that standard English frequency tables will not work here — you will need Polish letter frequencies, or you can try the key from Challenge 3a.

plaintextrej=lclear('''Spotkanie w lesie Pyrskim trwalo wszystkiego kilka godzin. Wystarczylo ono jednak calkowicie, by komandor Knox, kryptolog z prawdziwego zdarzenia, nie tylko wszystko w lot zrozumial, lecz i doskonale zapamietal i nie robiac sobie zadnych notatek, natychmiast po powrocie do Londynu, kazal zbudowac takie same czy nawet ulepszone "superbomby" i zorganizowal prace dla fabrykacji w sposób zmechanizowany naszych płacht. (...) Na pomysl placht Anglicy sami by nie wpadli. Komandor Knox po powrocie do Londynu przeslal kazdemu z naszej trojki chustke jedwabna pieknie malowana jako pamiatke po spotkaniu w Pyrach. ''')

plaintextrej

'spotkaniewlesiepyrskimtrwalowszystkiegokilkagodzinwystarczyloonojednakcalkowiciebykomandorknoxkryptologzprawdziwegozdarzenianietylkowszystkowlotzrozumialleczidoskonalezapamietalinierobiacsobiezadnychnotateknatychmiastpopowrociedolondynukazalzbudowactakiesameczynawetulepszonesuperbombyizorganizowalpracedlafabrykacjiwsposbzmechanizowanynaszychpachtnapomyslplachtanglicysamibyniewpadlikomandorknoxpopowrociedolondynuprzeslalkazdemuznaszejtrojkichustkejedwabnapiekniemalowanajakopamiatkepospotkaniuwpyrach'

key = "enigma"
ciphertextrej = vigenere_encrypt(plaintextrej, key)
print(ciphertextrej)

wcwzwarvmcxewvmvkrwxqsfrantuisdlazwiitwqulonoupzmaeeeteekfklsbvuvehaiqoapxwcucmrjewoqnvjaroawdwrccbuxokmxxmwhmqcqgsmlgdziaqgziiggrwoafheetoberatdewfgmmntrqcdvlueksairqzecisuexntoziiewhuagfwhuednltkclawzmtixvgfyguuomsxcwvawvbkoqdsywtpyrhsglapmjapoankzmkmragyegmgtmwigcrqpwmwtqsycmxnoqogolovtituzsjirbrepmjxajnjxkkeproistbahlmippgzidbegzyrnafkclciittrnxuyywyxrmclgitslmpgymmmogtueacijxiobugzdsestaxtbxuirspqkpopbvjknyczfqspntqmzhrualnefhkvtvbrquclhazwenrlcmbrnxoqkrvmsmlsjitmjexwvmmmnbqqpsfxufkeaqaipceiit

len(ciphertextrej)

Hint — Challenge 3b

This ciphertext uses the same key ("enigma") as Challenge 3a. If you have already recovered the key there, simply apply it here.

If you are attacking this independently:

The Kasiski examination and index of coincidence are language-independent methods for finding the key length.
For per-stream frequency analysis, use Polish letter frequencies. The most common letters in Polish are: a, i, e, o, n, z, r, s, w, t.
The ciphertext is relatively short (~400 characters), which makes pure frequency analysis harder — consider using mutual index of coincidence or chi-squared fitting.

Challenge 4: Playfair Cipher#

Difficulty: Hard

The ciphertext below was produced by a Playfair cipher with the key "marshmallow". The Playfair cipher is a digraphic substitution cipher that encrypts pairs of letters using a 5×5 key matrix (with I and J sharing a cell).

Your task: Decrypt the ciphertext. You may either:

Use the provided key directly with the Playfair decryption function, or
Attempt a ciphertext-only attack using n-gram fitness and hill climbing (simulated annealing).

The cell below uses %%cython for performance. It also loads the file Ulysses_4300-0.txt to build 4-gram statistics for the fitness function.

Note on the Ulysses corpus

The fitness function below reads Ulysses_4300-0.txt from the current working directory. Make sure this file is available, or update the path accordingly.

import copy
import random
import math
import string
import re
#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
def Ngrams(text,n): #logarithmic fitness
    digs=dict()
    for i in range(len(text)-n):
        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]=math.log(digs[k],10)
    flo=math.log(0.01/tot,10) #base score
    return digs, list(reversed(sorted([[digs[v],v] for v in digs.keys()]))),flo
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
counter=0
longtxt=''
try:
    with open('Ulysses_4300-0.txt', encoding='utf8') as f:
        for line in f:
            longtxt+=lclear(line.strip())
            counter+=1
except FileNotFoundError:
    # Fallback: use a built-in English text corpus for 4-gram statistics
    import urllib.request, os
    url = 'https://www.gutenberg.org/cache/epub/4300/pg4300.txt'
    fname = 'Ulysses_4300-0.txt'
    try:
        urllib.request.urlretrieve(url, fname)
        with open(fname, encoding='utf8') as f:
            for line in f:
                longtxt+=lclear(line.strip())
                counter+=1
    except Exception:
        # Last resort: use a long sample of English text
        sample = "the quick brown fox jumps over the lazy dog " * 2000
        sample += "stately plump buck mulligan came from the stairhead bearing a bowl of lather " * 500
        longtxt = lclear(sample)
        counter = 1
n4,l4,f=Ngrams(longtxt.replace('j','i'),4) #in playfair j and i are the same
def fit(text):
    return Fitness(lclear(text),n4,4,f)
def indexOf(letter,matrix):
    for i in range (5):
        try:
            index = matrix[i].index(letter)
            return (i,index)
        except:
            continue
def create_matrix(key):
    key=key.upper()
    matrix = [[0 for i in range (5)] for j in range(5)]
    letters_added = []
    row = 0
    col = 0
    # add the key to the matrix
    for letter in key:
        if letter not in letters_added:
            matrix[row][col] = letter
            letters_added.append(letter)
        else:
            continue
        if (col==4):
            col = 0
            row += 1
        else:
            col += 1
    #Add the rest of the alphabet to the matrix
    # A=65 ... Z=90
    for letter in range(65,91):
        if letter==74: # I/J are in the same position
                continue
        if chr(letter) not in letters_added: # Do not add repeated letters
            letters_added.append(chr(letter))
            
    #print (len(letters_added), letters_added)
    index = 0
    for i in range(5):
        for j in range(5):
            matrix[i][j] = letters_added[index]
            index+=1
    return matrix
def separate_same_letters(message):
    index = 0
    while (index<len(message)):
        l1 = message[index]
        if index == len(message)-1:
            message = message + 'X'
            index += 2
            continue
        l2 = message[index+1]
        if l1==l2:
            message = message[:index+1] + "X" + message[index+1:]
        index +=2   
    return message
def playfair(key, message, encrypt=True):
    inc = 1
    if encrypt==False:
        inc = -1
    matrix = create_matrix(key)
    message = message.upper()
    message = message.replace(' ','')    
    message = separate_same_letters(message)
    cipher_text=''
    for (l1, l2) in zip(message[0::2], message[1::2]):
        row1,col1 = indexOf(l1,matrix)
        row2,col2 = indexOf(l2,matrix)
        if row1==row2: #Rule 2, the letters are in the same row
            cipher_text += matrix[row1][(col1+inc)%5] + matrix[row2][(col2+inc)%5]
        elif col1==col2:# Rule 3, the letters are in the same column
            cipher_text += matrix[(row1+inc)%5][col1] + matrix[(row2+inc)%5][col2]
        else: #Rule 4, the letters are in a different row and column
            cipher_text += matrix[row1][col2] + matrix[row2][col1]
    return cipher_text

Generate the Playfair Ciphertext#

The cell below encrypts a passage about Edward the teddy bear using the Playfair cipher with key "marshmallow". Note that the letter j is replaced with i before encryption, as is standard for the Playfair cipher.

key4='marshmallow'
text4=lclear('''Edward spent long hours poring over the ancient texts, trying to decipher the meaning behind the cryptic symbols. He felt an immense sense of achievement whenever he managed to break a code, but his progress was slow, and he grew increasingly frustrated.

As Edward wrestled with the codes, he began to notice a change within himself. The gentle, loving teddy bear he once was started to vanish, replaced by a creature obsessed with cryptanalysis. He no longer enjoyed playing with the children in Cozysprings, and his once-soft fur became matted and unkempt. Even his once-sparkling eyes seemed to lose their luster.

Despite his struggles, Edward was determined to unlock the final code in the book, which was said to contain an ancient secret. The code was unlike any he had encountered before, a seemingly unsolvable puzzle that consumed his every waking thought.

One evening, as Edward sat at his desk, scribbling feverishly on a piece of paper, a young girl named Lily knocked on his door. Lily was a sweet, curious girl who had befriended Edward in happier times. She had noticed his absence from the village and had grown concerned for her friend.''')
plain4=text4.replace('j','i')
cc=playfair(key4, plain4)
print(cc.lower())

feormfrqnvkcevislvshnwhfqeeafazcnotodfpknizphqsxetiqleioftaihpaiadovetqgiaetikaiwhxqztbhuscwbmaigfckovdhadqaganvagwehoctnadanvpcaivnansmdaovsefencwsnonmlweflyzcghxwbeafryrbrhmbwbovimfiafcftoafrhetdbxgmxhqsrniemagflrsflafhqodfltzczailwefhmgofiovncveztoihomrqefotzcttadhagwdzcfinvkcdoeaetiqfeguogrsaievoiorryhqrsniikeaovghmsfnomoiglvswhnokzafwcagryagfltzcisxqkovmosbghaiveowqefanvecvgfkomzgqecfzczcioctdkaftetocvsbxwetqbovimghevoiabipdxswioradahnniemkevkndrkniantaghevoirqrsudetifvgryagdafencowagzcfdmwymnimfgatfnictryhqmxfydbgafeormformginfahdvniklvkowlnkaigdvoollefdpkaicwlncrtircrhhrdenclwpkhevovotodfpkagwhinzcioleforhvkcdndovzsiamenvlwvkniafglfgwanoagdaetdbzvqawoaocofnvuucinmrzievmyadimghnafaxbmnetiqacydczevfvnanvetesagflrsgmhnhnctmggaqmwhgccoetignafaghmcvbvotfionepxrnfasvlvqeidmwvoadkddcuqveltfeevctmgwvwacdbuorhrrbfvinlzhflvbqfhobacmrglfghfnvefefflrsedtarntffaztadryhmiameveztoiimghsoagtofgawhkaizewuomifovimmefswbtoevoiapfeewsmfapwdfke

Hint — Challenge 4

Known-key decryption: Call playfair(key4, ciphertext, encrypt=False) to decrypt.

Ciphertext-only attack: The Playfair cipher is much harder to break without the key. A practical approach uses simulated annealing:

Start with a random 5x5 key matrix.
Decrypt the ciphertext with the current key.
Score the decrypted text using the fit() function (4-gram log-likelihood).
Make a small random change to the key (swap two letters in the matrix).
If the new score is better, keep the change. If worse, keep it with probability \(e^{(\text{new} - \text{old}) / T}\) where \(T\) is a temperature parameter.
Gradually reduce \(T\) and repeat.

See Chapter 9 — Automated Cryptanalysis for a full implementation.

Your Solutions#

Use the cells below to work on your solutions to the challenges above.