Chapter 2: Permutations and Substitution Ciphers#
2.1 Introduction: The Mathematics of Rearrangement#
The substitution cipher is among the oldest and most natural ideas in cryptography. Its mathematical essence is remarkably simple: replace each letter in a message with another letter according to some fixed rule. Yet behind this simplicity lies the rich algebraic structure of permutation groups, a structure that both enables and ultimately undermines these ciphers.
Historical trajectory#
Caesar’s cipher (1st century BC). Julius Caesar reportedly shifted every letter in his military dispatches by three positions in the Latin alphabet. Suetonius, in The Twelve Caesars, describes this method explicitly: “If he had anything confidential to say, he wrote it in cipher, that is, by so changing the order of the letters of the alphabet, that not a word could be made out.” This is the earliest well-documented use of a substitution cipher in the Western tradition.
The general substitution cipher. Rather than restricting to shifts, one can use any rearrangement of the alphabet as the encryption rule. This dramatically increases the number of possible keys from 26 (for the English alphabet) to \(26! \approx 4 \times 10^{26}\). For centuries, this enormous keyspace was considered sufficient for security.
Al-Kindi and the birth of cryptanalysis (9th century). The Arab polymath Abu Yusuf Ya’qub ibn Ishaq al-Kindi wrote A Manuscript on Deciphering Cryptographic Messages, the earliest known description of frequency analysis. Al-Kindi observed that in any natural language, letters appear with characteristic frequencies – and a substitution cipher merely relabels these frequencies without altering them. This insight broke the general substitution cipher and established the principle that a large keyspace alone does not guarantee security.
The algebraic viewpoint#
A substitution cipher replaces each letter \(x\) in the alphabet \(\mathcal{A}\) with another letter \(\sigma(x)\), where \(\sigma: \mathcal{A} \to \mathcal{A}\) is a bijection (one-to-one and onto mapping). The collection of all such bijections on an \(n\)-element set forms the symmetric group \(S_n\), one of the most fundamental objects in algebra.
The symmetric group \(S_n\) has order \(n!\) (factorial of \(n\)), which means:
\(|S_3| = 6\)
\(|S_{10}| = 3{,}628{,}800\)
\(|S_{26}| = 403{,}291{,}461{,}126{,}605{,}635{,}584{,}000{,}000 \approx 4 \times 10^{26}\)
Understanding the group-theoretic properties of permutations – their composition, inverses, orders, and cycle structure – is essential for both constructing and breaking substitution-based cryptosystems.
Tip
The key lesson from history: security depends not on the size of the keyspace, but on the structure the cipher preserves. The substitution cipher preserves letter frequencies, and that single invariant suffices to break it. This principle will recur throughout this course.
2.2 Formal Definitions#
Definition 2.1 (Permutation)
Let \(\mathcal{A}\) be a finite set (the alphabet) with \(|\mathcal{A}| = n\). A permutation of \(\mathcal{A}\) is a bijection \(\sigma: \mathcal{A} \to \mathcal{A}\), that is, a mapping that is both injective (one-to-one) and surjective (onto).
We often identify \(\mathcal{A}\) with \(\{0, 1, \ldots, n-1\}\) and represent \(\sigma\) as the list \([\sigma(0), \sigma(1), \ldots, \sigma(n-1)]\).
Definition 2.2 (Symmetric Group)
The symmetric group \(S_n\) is the set of all permutations of \(\{0, 1, \ldots, n-1\}\) equipped with the operation of function composition. It satisfies:
Closure: if \(\sigma, \tau \in S_n\), then \(\sigma \circ \tau \in S_n\).
Associativity: \((\sigma \circ \tau) \circ \rho = \sigma \circ (\tau \circ \rho)\).
Identity: the identity permutation \(\text{id}(x) = x\) is in \(S_n\).
Inverses: for every \(\sigma \in S_n\) there exists \(\sigma^{-1} \in S_n\) such that \(\sigma \circ \sigma^{-1} = \text{id}\).
The order of \(S_n\) is \(|S_n| = n!\).
Definition 2.3 (Shift Cipher / Caesar Cipher)
Let \(\mathcal{A} = \{0, 1, \ldots, n-1\}\). For a fixed key \(k \in \mathbb{Z}_n\), the shift cipher (or Caesar cipher) is the substitution cipher defined by the permutation
The decryption permutation is \(\sigma_k^{-1} = \sigma_{-k}\), i.e., \(\sigma_{-k}(x) = (x - k) \mod n\).
Definition 2.4 (General Substitution Cipher)
A general substitution cipher over an alphabet \(\mathcal{A}\) with \(|\mathcal{A}| = n\) uses an arbitrary permutation \(\sigma \in S_n\) as the encryption key. For a message \(m = (m_1, m_2, \ldots, m_\ell)\), the ciphertext is
Decryption uses the inverse permutation: \(m = (\sigma^{-1}(c_1), \sigma^{-1}(c_2), \ldots, \sigma^{-1}(c_\ell))\).
Definition 2.5 (Involution)
A permutation \(\sigma \in S_n\) is called an involution if \(\sigma^2 = \sigma \circ \sigma = \text{id}\), i.e., applying \(\sigma\) twice returns every element to its original position. Equivalently, \(\sigma = \sigma^{-1}\): the permutation is its own inverse.
A substitution cipher based on an involution is self-invertible: the same key is used for both encryption and decryption.
Danger
The shift cipher has a dangerously small keyspace. For the 26-letter English alphabet, there are only 26 possible shift ciphers (including the identity shift \(k=0\)). An attacker can try all 26 keys by hand in minutes. This is an example of a brute-force attack: exhaustively checking every possible key. Any cipher whose keyspace is small enough to enumerate is insecure against brute force.
Implementation#
We now implement class-based substitution and shift ciphers in pure Python with NumPy.
The design mirrors the mathematical definitions above: a SubstitutionCipher wraps
an arbitrary permutation, while ShiftCipher is the special case \(\sigma_k(x) = (x+k) \bmod n\).
import numpy as np
import matplotlib.pyplot as plt
import string
%matplotlib inline
class SubstitutionCipher:
"""General substitution cipher over a given alphabet.
Parameters
----------
permutation : list
A list where permutation[i] is the character that alphabet[i] maps to.
Must be a permutation (rearrangement) of alphabet.
alphabet : list
The ordered list of characters in the alphabet.
"""
def __init__(self, permutation, alphabet):
if sorted(permutation) != sorted(alphabet):
raise ValueError("permutation must be a rearrangement of alphabet")
self.alphabet = list(alphabet)
self.permutation = list(permutation)
self.n = len(alphabet)
# Build forward and inverse lookup dictionaries
self._forward = dict(zip(self.alphabet, self.permutation))
self._inverse = dict(zip(self.permutation, self.alphabet))
def encrypt_char(self, ch):
"""Encrypt a single character. Characters not in alphabet are unchanged."""
return self._forward.get(ch, ch)
def decrypt_char(self, ch):
"""Decrypt a single character. Characters not in alphabet are unchanged."""
return self._inverse.get(ch, ch)
def encrypt(self, plaintext):
"""Encrypt a plaintext string."""
return ''.join(self.encrypt_char(ch) for ch in plaintext)
def decrypt(self, ciphertext):
"""Decrypt a ciphertext string."""
return ''.join(self.decrypt_char(ch) for ch in ciphertext)
def is_involution(self):
"""Check if sigma^2 = id, i.e. sigma is its own inverse."""
for a, b in self._forward.items():
if self._forward[b] != a:
return False
return True
def get_permutation_array(self):
"""Return the permutation as a NumPy index array."""
char_to_idx = {ch: i for i, ch in enumerate(self.alphabet)}
return np.array([char_to_idx[self._forward[ch]] for ch in self.alphabet])
def order(self):
"""Compute the order of the permutation (smallest k such that sigma^k = id)."""
perm = self.get_permutation_array()
current = np.arange(self.n)
for k in range(1, self.n + 1):
current = perm[current]
if np.array_equal(current, np.arange(self.n)):
return k
return self.n # fallback (should not happen)
def compose(self, other):
"""Return the composition self(other(x)) as a new SubstitutionCipher."""
new_perm = [self.encrypt_char(other.encrypt_char(ch)) for ch in self.alphabet]
return SubstitutionCipher(new_perm, self.alphabet)
def inverse(self):
"""Return the inverse permutation as a new SubstitutionCipher."""
inv_perm = [self._inverse[ch] for ch in self.alphabet]
# Note: inv_perm[i] = sigma^{-1}(alphabet[i])
# We need the permutation list where index i maps alphabet[i] -> result
return SubstitutionCipher(inv_perm, self.alphabet)
def __repr__(self):
return f"SubstitutionCipher(perm={''.join(self.permutation)}, n={self.n})"
class ShiftCipher(SubstitutionCipher):
"""Caesar/shift cipher: sigma_k(x) = (x + k) mod n.
Parameters
----------
shift : int
The shift amount k.
alphabet : list
The ordered list of characters in the alphabet.
"""
def __init__(self, shift, alphabet):
self.shift = shift % len(alphabet)
n = len(alphabet)
# sigma_k(a_i) = a_{(i+k) mod n}
permutation = [alphabet[(i + shift) % n] for i in range(n)]
super().__init__(permutation, alphabet)
def __repr__(self):
return f"ShiftCipher(shift={self.shift}, n={self.n})"
# ---------------------------------------------------------------
# Demo: basic encryption and decryption
# ---------------------------------------------------------------
alphabet = list(string.ascii_lowercase)
print("=" * 60)
print("SHIFT CIPHER DEMO")
print("=" * 60)
caesar = ShiftCipher(3, alphabet)
msg = "attackatdawn"
enc = caesar.encrypt(msg)
dec = caesar.decrypt(enc)
print(f"Plaintext : {msg}")
print(f"Shift : k = {caesar.shift}")
print(f"Ciphertext: {enc}")
print(f"Decrypted : {dec}")
print(f"Correct : {dec == msg}")
print()
# ROT13 -- the classic self-invertible shift
rot13 = ShiftCipher(13, alphabet)
msg2 = "helloworld"
enc2 = rot13.encrypt(msg2)
dec2 = rot13.encrypt(enc2) # encrypt again to decrypt (involution!)
print(f"ROT13 of '{msg2}': {enc2}")
print(f"ROT13 of '{enc2}': {dec2}")
print(f"ROT13 is involution: {rot13.is_involution()}")
print(f"Order of ROT13: {rot13.order()}")
print()
print("=" * 60)
print("GENERAL SUBSTITUTION CIPHER DEMO")
print("=" * 60)
# Create a random permutation
rng = np.random.default_rng(42)
perm = list(np.array(alphabet)[rng.permutation(26)])
gen_cipher = SubstitutionCipher(perm, alphabet)
msg3 = "thisisasecretmessage"
enc3 = gen_cipher.encrypt(msg3)
dec3 = gen_cipher.decrypt(enc3)
print(f"Plaintext : {msg3}")
print(f"Permutation: {''.join(perm)}")
print(f"Ciphertext: {enc3}")
print(f"Decrypted : {dec3}")
print(f"Correct : {dec3 == msg3}")
print(f"Is involution: {gen_cipher.is_involution()}")
print(f"Order: {gen_cipher.order()}")
============================================================
SHIFT CIPHER DEMO
============================================================
Plaintext : attackatdawn
Shift : k = 3
Ciphertext: dwwdfndwgdzq
Decrypted : attackatdawn
Correct : True
ROT13 of 'helloworld': uryybjbeyq
ROT13 of 'uryybjbeyq': helloworld
ROT13 is involution: True
Order of ROT13: 2
============================================================
GENERAL SUBSTITUTION CIPHER DEMO
============================================================
Plaintext : thisisasecretmessage
Permutation: hpvurfszkjgqdawtmloycexbni
Ciphertext: yzkokohorvlrydroohsr
Decrypted : thisisasecretmessage
Correct : True
Is involution: False
Order: 26
2.3 Properties of Substitution Ciphers#
We now state and justify the key structural results about substitution ciphers.
Theorem 2.1 (Size of the keyspace)
The number of distinct substitution ciphers over an alphabet of size \(n\) is \(n!\).
Proof
A substitution cipher is determined by a permutation \(\sigma \in S_n\). The first letter of the alphabet can be mapped to any of \(n\) letters; once that choice is made, the second letter can be mapped to any of the remaining \(n-1\) letters; and so on. By the multiplication principle, the total number of permutations is
Since each permutation gives a distinct cipher (different permutations produce different ciphertexts for at least one plaintext character), the number of distinct substitution ciphers is exactly \(n!\). \(\square\)
Theorem 2.2 (Shift ciphers form a cyclic subgroup)
The set of all shift ciphers \(\{\sigma_0, \sigma_1, \ldots, \sigma_{n-1}\}\) forms a cyclic subgroup of \(S_n\) of order \(n\), isomorphic to \(\mathbb{Z}_n\).
Proof
We verify the group axioms:
Closure: \(\sigma_j \circ \sigma_k(x) = (x + k) + j = x + (j+k) \pmod{n} = \sigma_{j+k}(x)\). Since \((j+k) \bmod n \in \{0, \ldots, n-1\}\), the composition is again a shift cipher.
Identity: \(\sigma_0(x) = x\) is the identity permutation.
Inverses: \(\sigma_k^{-1} = \sigma_{n-k}\), since \(\sigma_{n-k} \circ \sigma_k(x) = x + k + (n-k) = x + n \equiv x \pmod{n}\).
Generator: \(\sigma_1\) generates the entire group, since \(\sigma_k = \sigma_1^k\) (applying \(\sigma_1\) \(k\) times).
The map \(k \mapsto \sigma_k\) is a group isomorphism from \((\mathbb{Z}_n, +)\) to the shift subgroup. \(\square\)
Theorem 2.3 (Self-invertible ciphers and involutions)
A substitution cipher is self-invertible (encryption equals decryption) if and only if its permutation \(\sigma\) is an involution, i.e., \(\sigma^2 = \text{id}\). Equivalently, \(\sigma\) is a product of disjoint transpositions (2-cycles) and possibly fixed points.
Proof
(\(\Rightarrow\)) If the cipher is self-invertible, then encrypting twice recovers the plaintext: \(\sigma(\sigma(x)) = x\) for all \(x\), so \(\sigma^2 = \text{id}\).
(\(\Leftarrow\)) If \(\sigma^2 = \text{id}\), then \(\sigma = \sigma^{-1}\), so the decryption function is the same as the encryption function.
Cycle structure: Every permutation decomposes uniquely (up to ordering) into disjoint cycles. If \(\sigma^2 = \text{id}\), then every cycle \((a_1, a_2, \ldots, a_r)\) of \(\sigma\) must satisfy \(r \leq 2\), because \(\sigma^2(a_1) = a_1\) requires the cycle length to divide 2. Hence \(\sigma\) is a product of disjoint transpositions and fixed points. \(\square\)
Corollary (Self-invertible shift ciphers)
For the shift cipher \(\sigma_k\) on an alphabet of size \(n\), the order of \(\sigma_k\) is \(n / \gcd(n, k)\). Thus \(\sigma_k\) is an involution (order 2) if and only if \(n / \gcd(n, k) = 2\), i.e., \(k = n/2\). This requires \(n\) to be even.
For the 26-letter English alphabet, the unique self-invertible shift cipher is ROT13 (\(k = 13\)).
Verifying self-invertible shift ciphers#
Let us computationally verify the corollary above: for each shift \(k \in \{0, 1, \ldots, 25\}\), we compute the order of \(\sigma_k\) and check which ones are involutions. This adapts the SageMath exploration from the source material into pure Python.
import numpy as np
import string
alphabet = list(string.ascii_lowercase)
n = len(alphabet) # 26
print(f"Alphabet size n = {n}")
print(f"{'k':>3} {'Order':>6} {'Involution?':>12} {'gcd(n,k)':>9} {'n/gcd':>6}")
print("-" * 45)
involutions = []
for k in range(n):
cipher = ShiftCipher(k, alphabet)
ord_k = cipher.order()
is_inv = cipher.is_involution()
g = np.gcd(n, k) if k > 0 else n
ratio = n // g if g > 0 else '-'
print(f"{k:>3} {ord_k:>6} {str(is_inv):>12} {g:>9} {ratio:>6}")
if is_inv and k > 0:
involutions.append(k)
print(f"\nSelf-invertible shifts (excluding identity): {involutions}")
print(f"Unique non-trivial self-invertible shift: k = {n // 2} (ROT{n // 2})")
Alphabet size n = 26
k Order Involution? gcd(n,k) n/gcd
---------------------------------------------
0 1 True 26 1
1 26 False 1 26
2 13 False 2 13
3 26 False 1 26
4 13 False 2 13
5 26 False 1 26
6 13 False 2 13
7 26 False 1 26
8 13 False 2 13
9 26 False 1 26
10 13 False 2 13
11 26 False 1 26
12 13 False 2 13
13 2 True 13 2
14 13 False 2 13
15 26 False 1 26
16 13 False 2 13
17 26 False 1 26
18 13 False 2 13
19 26 False 1 26
20 13 False 2 13
21 26 False 1 26
22 13 False 2 13
23 26 False 1 26
24 13 False 2 13
25 26 False 1 26
Self-invertible shifts (excluding identity): [13]
Unique non-trivial self-invertible shift: k = 13 (ROT13)
Visualization 1: Permutation mapping diagram#
A substitution cipher can be visualized as a set of arrows from plaintext letters (top row) to ciphertext letters (bottom row). This makes the structure of the permutation immediately visible: a shift cipher produces parallel arrows, while a random permutation produces a tangle of crossings.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as patches
import string
%matplotlib inline
def plot_permutation_mapping(cipher, title="Permutation Mapping", ax=None):
"""Draw a mapping diagram: arrows from plaintext to ciphertext letters."""
n = cipher.n
alphabet = cipher.alphabet
if ax is None:
fig, ax = plt.subplots(figsize=(14, 4))
y_top = 1.0
y_bot = 0.0
x_positions = np.linspace(0, 1, n)
# Map character to its x position
char_to_x = {ch: x_positions[i] for i, ch in enumerate(alphabet)}
# Use a colormap for the arrows
cmap = plt.cm.tab20
for i, ch in enumerate(alphabet):
target = cipher.encrypt_char(ch)
x_start = char_to_x[ch]
x_end = char_to_x[target]
color = cmap(i / n)
# Draw arrow from top row to bottom row
ax.annotate(
'', xy=(x_end, y_bot + 0.08), xytext=(x_start, y_top - 0.08),
arrowprops=dict(arrowstyle='->', color=color, lw=1.2, alpha=0.7)
)
# Draw letters
for i, ch in enumerate(alphabet):
ax.text(x_positions[i], y_top + 0.05, ch.upper(), ha='center', va='bottom',
fontsize=9, fontweight='bold', fontfamily='monospace')
ax.text(x_positions[i], y_bot - 0.05, ch.upper(), ha='center', va='top',
fontsize=9, fontweight='bold', fontfamily='monospace')
# Labels
ax.text(-0.03, y_top + 0.05, 'Plain:', ha='right', va='bottom', fontsize=10, fontstyle='italic')
ax.text(-0.03, y_bot - 0.05, 'Cipher:', ha='right', va='top', fontsize=10, fontstyle='italic')
ax.set_xlim(-0.08, 1.05)
ax.set_ylim(-0.2, 1.25)
ax.set_title(title, fontsize=13, fontweight='bold')
ax.axis('off')
# --- Generate two ciphers for comparison ---
alphabet = list(string.ascii_lowercase)
rng = np.random.default_rng(2024)
# Shift cipher (Caesar, k=3)
shift_cipher = ShiftCipher(3, alphabet)
# Random permutation cipher
random_perm = list(np.array(alphabet)[rng.permutation(26)])
random_cipher = SubstitutionCipher(random_perm, alphabet)
fig, axes = plt.subplots(2, 1, figsize=(14, 7))
plot_permutation_mapping(shift_cipher, title="Shift Cipher (k = 3)", ax=axes[0])
plot_permutation_mapping(random_cipher, title="Random Substitution Cipher", ax=axes[1])
plt.tight_layout()
plt.savefig('ch02_permutation_mapping.png', dpi=150, bbox_inches='tight')
plt.show()
Visualization 2: All 26 shift ciphers applied to a word#
Below we apply every possible shift (\(k = 0, 1, \ldots, 25\)) to a sample word and display the results in a grid. This is essentially the brute-force attack on a shift cipher: simply try all keys and look for readable plaintext.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
import string
%matplotlib inline
alphabet = list(string.ascii_lowercase)
sample_word = "cryptanalysis"
# Generate all 26 shifts
shifts_data = []
for k in range(26):
cipher = ShiftCipher(k, alphabet)
encrypted = cipher.encrypt(sample_word)
shifts_data.append((k, encrypted))
# Create a visual table using matplotlib
fig, ax = plt.subplots(figsize=(12, 10))
ax.axis('off')
ax.set_title(f'All 26 Shift Ciphers Applied to "{sample_word}"',
fontsize=14, fontweight='bold', pad=20)
# Table data
table_data = [[f"k = {int(k):2d}", encrypted.upper()] for k, encrypted in shifts_data]
col_labels = ["Shift (k)", "Ciphertext"]
table = ax.table(
cellText=table_data,
colLabels=col_labels,
loc='center',
cellLoc='center',
colWidths=[0.15, 0.45]
)
table.auto_set_font_size(False)
table.set_fontsize(10)
table.scale(1, 1.15)
# Style the header
for j in range(2):
cell = table[0, j]
cell.set_facecolor('#2c3e50')
cell.set_text_props(color='white', fontweight='bold', fontfamily='monospace')
# Style the body rows
for i in range(26):
for j in range(2):
cell = table[i + 1, j]
cell.set_text_props(fontfamily='monospace')
if i == 0: # k=0 is identity
cell.set_facecolor('#d5f5e3') # light green for identity
elif i == 13: # ROT13
cell.set_facecolor('#fadbd8') # light red for ROT13
else:
cell.set_facecolor('#f8f9fa' if i % 2 == 0 else 'white')
# Add legend annotations
ax.text(0.78, 0.95, 'Green: identity (k=0)', transform=ax.transAxes,
fontsize=9, color='#27ae60', fontweight='bold')
ax.text(0.78, 0.91, 'Red: ROT13 (k=13)', transform=ax.transAxes,
fontsize=9, color='#e74c3c', fontweight='bold')
plt.tight_layout()
plt.savefig('ch02_all_shifts.png', dpi=150, bbox_inches='tight')
plt.show()
Visualization 3: Keyspace size comparison#
How do the keyspaces of different substitution-type ciphers compare? The differences are so enormous that we must plot on a logarithmic scale.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
import math
%matplotlib inline
# Keyspace sizes for n = 26
n = 26
# Shift cipher: n = 26 keys
shift_keys = n
# Affine cipher: E(x) = (ax + b) mod 26
# a must be coprime to 26: phi(26) = 12 choices for a
# b can be anything: 26 choices for b
# Total: 12 * 26 = 312
from math import gcd
valid_a = [a for a in range(1, n) if gcd(a, n) == 1]
affine_keys = len(valid_a) * n
# General substitution: 26! keys
subst_keys = math.factorial(n)
print(f"Shift cipher keyspace: {shift_keys:>40,d}")
print(f"Affine cipher keyspace: {affine_keys:>40,d}")
print(f"General substitution keyspace: {subst_keys:>40,d}")
print(f" = {subst_keys:.3e}")
print()
print(f"Valid values of a for affine cipher (gcd(a,26)=1): {valid_a}")
print(f"Number of valid a: {len(valid_a)}")
# Bar chart on log scale
fig, ax = plt.subplots(figsize=(9, 6))
labels = ['Shift Cipher\n(Caesar)', 'Affine Cipher', 'General\nSubstitution']
values = [shift_keys, affine_keys, subst_keys]
log_values = [math.log10(v) for v in values]
colors = ['#3498db', '#e67e22', '#e74c3c']
bars = ax.bar(labels, log_values, color=colors, edgecolor='black', linewidth=0.8, width=0.5)
# Annotate each bar with the actual value
for bar, val, log_val in zip(bars, values, log_values):
if val < 1000:
label = f"{val}"
else:
label = f"{val:.2e}"
ax.text(bar.get_x() + bar.get_width() / 2, log_val + 0.5,
label, ha='center', va='bottom', fontsize=11, fontweight='bold')
ax.set_ylabel(r'$\log_{10}$(keyspace size)', fontsize=12)
ax.set_title('Keyspace Size Comparison for Substitution Ciphers (n = 26)',
fontsize=13, fontweight='bold')
ax.set_ylim(0, max(log_values) + 3)
# Add a reference line at log10(2^128)
ax.axhline(y=math.log10(2**128), color='gray', linestyle='--', alpha=0.5)
ax.text(2.3, math.log10(2**128) + 0.3, r'$2^{128}$ (modern standard)',
fontsize=9, color='gray', ha='right')
ax.grid(axis='y', alpha=0.3)
plt.tight_layout()
plt.savefig('ch02_keyspace_comparison.png', dpi=150, bbox_inches='tight')
plt.show()
Shift cipher keyspace: 26
Affine cipher keyspace: 312
General substitution keyspace: 403,291,461,126,605,635,584,000,000
= 4.033e+26
Valid values of a for affine cipher (gcd(a,26)=1): [1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25]
Number of valid a: 12
Experiment: Words that are shifts of each other#
An interesting combinatorial question, explored in the original course material: are there English words that are Caesar shifts of other English words? For example, the word “green” shifted by 13 (ROT13) becomes “terra” – but is “terra” a valid English word?
Let us search for such pairs using a standard word list. This adapts the exploration
from the shifts.ipynb notebook.
import numpy as np
import string
import re
alphabet = list(string.ascii_lowercase)
def clean_word(text):
"""Remove all non-lowercase-letter characters."""
return re.sub(r'[^a-z]', '', text.lower())
def shift_word(word, k):
"""Apply shift cipher with key k to a word."""
return ''.join(chr((ord(c) - ord('a') + k) % 26 + ord('a')) for c in word)
# Use a curated list of common English words
# (In a full course you might load from /usr/share/dict/words)
common_words = [
"add", "ant", "ape", "arc", "are", "art", "ash", "ate", "awe",
"bag", "ban", "bar", "bat", "bay", "bed", "bee", "bet", "bid", "big",
"bin", "bit", "bow", "box", "boy", "bud", "bug", "bun", "bus", "but", "buy",
"cab", "can", "cap", "car", "cat", "cop", "cow", "cry", "cub", "cup", "cut",
"dad", "dam", "day", "den", "dew", "did", "dig", "dim", "dip", "dog", "dot",
"dry", "dub", "dud", "due", "dug", "dye",
"ear", "eat", "eel", "egg", "ego", "elm", "end", "era", "eve", "ewe", "eye",
"fan", "far", "fat", "fax", "fed", "fee", "few", "fig", "fin", "fir", "fit",
"fix", "fly", "foe", "fog", "for", "fox", "fry", "fun", "fur",
"gag", "gap", "gas", "gel", "gem", "get", "gin", "god", "got", "gum", "gun", "gut", "guy",
"had", "ham", "has", "hat", "hay", "hen", "her", "hew", "hid", "him", "hip",
"his", "hit", "hob", "hog", "hop", "hot", "how", "hub", "hue", "hug", "hum", "hut",
"ice", "icy", "ill", "imp", "ink", "inn", "ion", "ire", "irk", "ivy",
"jab", "jag", "jam", "jar", "jaw", "jay", "jet", "jig", "job", "jog", "jot", "joy", "jug",
"keg", "ken", "key", "kid", "kin", "kit",
"lab", "lad", "lag", "lap", "law", "lay", "lea", "led", "leg", "let", "lid",
"lie", "lip", "lit", "log", "lot", "low", "lug",
"mad", "man", "map", "mar", "mat", "maw", "may", "men", "met", "mid",
"mix", "mob", "mod", "mop", "mow", "mud", "mug", "mum",
"nab", "nag", "nap", "net", "new", "nil", "nip", "nit", "nod", "nor", "not", "now", "nun", "nut",
"oak", "oar", "oat", "odd", "ode", "off", "oft", "oil", "old", "one", "opt",
"orb", "ore", "our", "out", "owe", "owl", "own",
"pad", "pal", "pan", "pap", "par", "pat", "paw", "pay", "pea", "peg", "pen", "pep",
"per", "pet", "pie", "pig", "pin", "pit", "ply", "pod", "pop", "pot", "pow", "pro",
"pub", "pug", "pun", "pup", "pus", "put",
"rag", "ram", "ran", "rap", "rat", "raw", "ray", "red", "ref", "rib", "rid",
"rig", "rim", "rip", "rob", "rod", "rot", "row", "rub", "rug", "rum", "run", "rut",
"sac", "sad", "sag", "sap", "sat", "saw", "say", "sea", "set", "sew", "she",
"shy", "sin", "sip", "sir", "sis", "sit", "six", "ski", "sky", "sly", "sob",
"sod", "son", "sop", "sot", "sow", "soy", "spa", "spy", "sty", "sub", "sue",
"sum", "sun", "sup",
"tab", "tad", "tag", "tan", "tap", "tar", "tax", "tea", "ten", "the", "thy",
"tie", "tin", "tip", "toe", "ton", "too", "top", "tow", "toy", "try", "tub", "tug", "two",
"urn", "use",
"van", "vat", "vet", "vie", "vim", "vow",
"wad", "wag", "war", "was", "wax", "way", "web", "wed", "wet", "who",
"why", "wig", "win", "wit", "woe", "wok", "won", "woo", "wot", "wow",
"yam", "yap", "yaw", "yea", "yes", "yet", "yew", "yip", "you", "yow",
"zap", "zed", "zen", "zip", "zoo",
# Some 4-5 letter words
"been", "beer", "bell", "bird", "bone", "book", "burn", "cold",
"door", "envy", "fall", "fish", "fury", "given", "green", "terra",
"hall", "help", "hero", "horn", "iron", "jazz", "king", "lamp",
"love", "milk", "moon", "nine", "open", "pure", "rain",
"ring", "road", "ruby", "seal", "send", "ship", "silk", "snow",
"star", "stem", "step", "swan", "tree", "wall", "wind", "wolf",
"cheer", "clerk", "green", "jolly", "unity",
"ahem", "chef", "purr", "sheer",
]
# Remove duplicates and sort
word_set = set(clean_word(w) for w in common_words if len(clean_word(w)) >= 3)
print(f"Dictionary size: {len(word_set)} words")
print()
# Find shift pairs
found_pairs = []
for k in range(1, 26):
pairs_for_k = []
for w in sorted(word_set):
shifted = shift_word(w, k)
if shifted in word_set and shifted != w:
pairs_for_k.append((w, shifted))
if pairs_for_k:
found_pairs.append((k, pairs_for_k))
for k, pairs in found_pairs:
# Deduplicate: only show each unordered pair once
shown = set()
unique_pairs = []
for w1, w2 in pairs:
key = tuple(sorted([w1, w2]))
if key not in shown:
shown.add(key)
unique_pairs.append((w1, w2))
if unique_pairs:
pair_str = ', '.join(f'{w1} -> {w2}' for w1, w2 in unique_pairs[:8])
print(f" Shift k={int(k):2d}: {pair_str}")
Dictionary size: 433 words
Shift k= 1: add -> bee, dud -> eve, end -> foe
Shift k= 2: eye -> gag, ice -> keg, rum -> two
Shift k= 3: box -> era, elm -> hop, lab -> ode, ply -> sob
Shift k= 4: bet -> fix, cap -> get, lap -> pet, law -> pea, lea -> pie, nab -> ref, owl -> sap, paw -> tea
Shift k= 5: not -> sty
Shift k= 6: bin -> hot, boy -> hue, bug -> ham, bun -> hat, bus -> hay, dug -> jam, fin -> lot, gun -> mat
Shift k= 7: bee -> ill, cheer -> jolly, hew -> old, him -> opt, lit -> spa, mar -> thy, par -> why
Shift k= 8: add -> ill, bay -> jig, ego -> mow, god -> owl, hay -> pig, jay -> rig, law -> tie, log -> two
Shift k= 9: ire -> ran, irk -> rat, lie -> urn, tip -> cry
Shift k=10: but -> led, her -> rob, hut -> red, put -> zed, rut -> bed, wet -> god
Shift k=11: ape -> lap, hen -> spy, odd -> zoo, pet -> ape, pit -> ate, tab -> elm
Shift k=12: ash -> met, did -> pup, dig -> pus, dip -> pub, god -> sap, hip -> tub, hob -> tan, hop -> tab
Shift k=13: ant -> nag, bar -> one, fur -> she, gel -> try, green -> terra
Shift k=14: bus -> pig, dub -> rip, imp -> wad, met -> ash, pub -> dip, pup -> did, pus -> dig, sap -> god
Shift k=15: ape -> pet, ate -> pit, elm -> tab, lap -> ape, spy -> hen, zoo -> odd
Shift k=16: bed -> rut, god -> wet, led -> but, red -> hut, rob -> her, zed -> put
Shift k=17: cry -> tip, ran -> ire, rat -> irk, urn -> lie
Shift k=18: awe -> sow, ewe -> wow, ill -> add, jig -> bay, mow -> ego, owl -> god, pig -> hay, rig -> jay
Shift k=19: ill -> bee, jolly -> cheer, old -> hew, opt -> him, spa -> lit, thy -> mar, why -> par
Shift k=20: cut -> won, ham -> bug, hat -> bun, hay -> bus, hot -> bin, hue -> boy, jam -> dug, lot -> fin
Shift k=21: sty -> not
Shift k=22: fix -> bet, get -> cap, pea -> law, pet -> lap, pie -> lea, ref -> nab, sap -> owl, tea -> paw
Shift k=23: era -> box, hop -> elm, ode -> lab, sob -> ply
Shift k=24: gag -> eye, keg -> ice, two -> rum
Shift k=25: bee -> add, eve -> dud, foe -> end
Experiment: Composition and inverse of permutations#
A central algebraic operation is the composition of permutations: if we apply \(\sigma\) and then \(\tau\), the combined effect is \(\tau \circ \sigma\). Below we demonstrate composition, inverses, and verify the group axioms computationally.
import numpy as np
import string
alphabet = list(string.ascii_lowercase)
# Two shift ciphers
sigma_3 = ShiftCipher(3, alphabet)
sigma_5 = ShiftCipher(5, alphabet)
# Their composition should be a shift by 3+5=8
composed = sigma_3.compose(sigma_5)
sigma_8 = ShiftCipher(8, alphabet)
test_msg = "abcdefghijklmnopqrstuvwxyz"
print("Composition of shifts:")
print(f" sigma_3(sigma_5(x)): {composed.encrypt(test_msg)}")
print(f" sigma_8(x): {sigma_8.encrypt(test_msg)}")
print(f" Equal: {composed.encrypt(test_msg) == sigma_8.encrypt(test_msg)}")
print()
# Inverse: sigma_k composed with sigma_{-k} = identity
sigma_3_inv = sigma_3.inverse()
identity_check = sigma_3.compose(sigma_3_inv)
print("Inverse:")
print(f" sigma_3(sigma_3_inv(x)): {identity_check.encrypt(test_msg)}")
print(f" Is identity: {identity_check.encrypt(test_msg) == test_msg}")
print()
# Random permutation: compose with its inverse
rng = np.random.default_rng(123)
rand_perm = list(np.array(alphabet)[rng.permutation(26)])
sigma_rand = SubstitutionCipher(rand_perm, alphabet)
sigma_rand_inv = sigma_rand.inverse()
roundtrip = sigma_rand.compose(sigma_rand_inv)
print("Random permutation:")
print(f" sigma: {''.join(sigma_rand.permutation)}")
print(f" sigma^(-1): {''.join(sigma_rand_inv.permutation)}")
print(f" sigma(sigma^(-1)(x)) = id: {roundtrip.encrypt(test_msg) == test_msg}")
print(f" Order of sigma: {sigma_rand.order()}")
Composition of shifts:
sigma_3(sigma_5(x)): ijklmnopqrstuvwxyzabcdefgh
sigma_8(x): ijklmnopqrstuvwxyzabcdefgh
Equal: True
Inverse:
sigma_3(sigma_3_inv(x)): abcdefghijklmnopqrstuvwxyz
Is identity: True
Random permutation:
sigma: cxphylevkgzbaitusqjmrfowdn
sigma^(-1): mlaygvjdnsiftzwcruqophxbek
sigma(sigma^(-1)(x)) = id: True
Order of sigma: 26
Constructing involutions (self-invertible permutations)#
An involution is a permutation \(\sigma\) satisfying \(\sigma^2 = \text{id}\). Its cycle decomposition consists entirely of fixed points and transpositions (2-cycles). Below we construct involutions explicitly and verify their properties.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
import string
%matplotlib inline
alphabet = list(string.ascii_lowercase)
def make_involution_from_transpositions(swaps, alphabet):
"""Create an involution from a list of 2-element swaps.
Parameters
----------
swaps : list of tuples
Each tuple (a, b) means sigma(a) = b and sigma(b) = a.
Letters not in any swap are fixed points.
alphabet : list
The alphabet.
"""
perm = list(alphabet) # start with identity
idx = {ch: i for i, ch in enumerate(alphabet)}
for a, b in swaps:
perm[idx[a]] = b
perm[idx[b]] = a
return SubstitutionCipher(perm, alphabet)
# Example 1: Swap (a,z), (b,y), (c,x) -- an Atbash-like partial involution
swaps_1 = [('a', 'z'), ('b', 'y'), ('c', 'x'), ('d', 'w'), ('e', 'v'),
('f', 'u'), ('g', 't'), ('h', 's'), ('i', 'r'), ('j', 'q'),
('k', 'p'), ('l', 'o'), ('m', 'n')]
atbash = make_involution_from_transpositions(swaps_1, alphabet)
print("Atbash cipher (a<->z, b<->y, c<->x, ...):")
print(f" Permutation: {''.join(atbash.permutation)}")
print(f" Is involution: {atbash.is_involution()}")
print(f" Order: {atbash.order()}")
msg = "helloworld"
enc = atbash.encrypt(msg)
dec = atbash.encrypt(enc) # self-inverse!
print(f" encrypt('{msg}') = '{enc}'")
print(f" encrypt('{enc}') = '{dec}' (decrypts back!)")
print()
# Example 2: Partial involution -- only some letters are swapped
swaps_2 = [('a', 'b'), ('c', 'd'), ('e', 'f')]
partial_inv = make_involution_from_transpositions(swaps_2, alphabet)
print("Partial involution (a<->b, c<->d, e<->f, rest fixed):")
print(f" Is involution: {partial_inv.is_involution()}")
print(f" Order: {partial_inv.order()}")
msg2 = "abcdef"
print(f" encrypt('{msg2}') = '{partial_inv.encrypt(msg2)}'")
print(f" encrypt twice = '{partial_inv.encrypt(partial_inv.encrypt(msg2))}'")
print()
# Visualize the Atbash involution as a mapping diagram
fig, ax = plt.subplots(figsize=(14, 4))
plot_permutation_mapping(atbash, title="Atbash Cipher (Involution)", ax=ax)
plt.tight_layout()
plt.savefig('ch02_atbash_involution.png', dpi=150, bbox_inches='tight')
plt.show()
Atbash cipher (a<->z, b<->y, c<->x, ...):
Permutation: zyxwvutsrqponmlkjihgfedcba
Is involution: True
Order: 2
encrypt('helloworld') = 'svooldliow'
encrypt('svooldliow') = 'helloworld' (decrypts back!)
Partial involution (a<->b, c<->d, e<->f, rest fixed):
Is involution: True
Order: 2
encrypt('abcdef') = 'badcfe'
encrypt twice = 'abcdef'
2.4 Exercises#
Exercise 2.1 (Affine cipher)
The affine cipher encrypts a letter \(x \in \{0, 1, \ldots, 25\}\) as
for parameters \(a, b \in \mathbb{Z}_{26}\).
(a) Implement the affine cipher in Python (encryption and decryption).
(b) Determine which values of \(a\) give valid (invertible) ciphers. Justify your answer.
(c) How many valid affine ciphers exist for the 26-letter alphabet?
Hint
The mapping \(x \mapsto (ax + b) \bmod 26\) is a bijection if and only if \(a\) is
invertible modulo 26, i.e., \(\gcd(a, 26) = 1\). Recall that \(26 = 2 \times 13\),
so \(a\) must be odd and not a multiple of 13. Use pow(a, -1, 26) in Python
to compute the modular inverse of \(a\).
Exercise 2.2 (Self-invertible shifts)
Find all self-invertible shift ciphers for the 26-letter English alphabet. Generalize: for an alphabet of size \(n\), characterize which shifts \(k\) produce involutions.
Hint
A shift by \(k\) is an involution iff \(\sigma_k^2 = \text{id}\), i.e., \(2k \equiv 0 \pmod{n}\). This gives \(k = 0\) (the identity) and \(k = n/2\) when \(n\) is even. For \(n = 26\), the only non-trivial self-invertible shift is \(k = 13\) (ROT13). If \(n\) is odd, only the identity is self-invertible.
Exercise 2.3 (Inverse from cycle notation)
A permutation can be written in cycle notation: e.g., \((0\ 2\ 4)(1\ 3)\) means \(0 \to 2 \to 4 \to 0\) and \(1 \to 3 \to 1\).
Write a Python function inverse_from_cycles(cycles, n) that takes a list of cycles
(each cycle is a list of integers) and the size \(n\) of the permutation, and returns
the inverse permutation as a list.
Test your function on \((0\ 1\ 2\ 3\ 4)\) (a 5-cycle) and verify that composing the permutation with its inverse gives the identity.
Hint
To invert a cycle \((a_1, a_2, \ldots, a_r)\), reverse it: \((a_r, a_{r-1}, \ldots, a_1)\). Equivalently, in the inverse permutation, each \(a_{i+1}\) maps to \(a_i\) (instead of \(a_i\) mapping to \(a_{i+1}\)).
Build the permutation as a list perm where perm[i] is the image of i,
then for each cycle, set perm[cycle[j]] = cycle[j-1].
Exercise 2.4 (Involutions do not form a subgroup)
Prove that the set of involutions in \(S_n\) (for \(n \geq 3\)) does not form a subgroup of \(S_n\). Provide an explicit counterexample.
Hint
The set of involutions is not closed under composition. Consider \(S_3\) and the transpositions \(\sigma = (0\ 1)\) and \(\tau = (1\ 2)\). Both are involutions. Compute \(\sigma \circ \tau\) and show it is a 3-cycle (order 3), hence not an involution.
Concretely: \(\tau\) sends \(0 \to 0, 1 \to 2, 2 \to 1\), and \(\sigma\) sends \(0 \to 1, 1 \to 0, 2 \to 2\). Then \(\sigma \circ \tau\): \(0 \to 0 \to 1\), \(1 \to 2 \to 2\), \(2 \to 1 \to 0\). This is the cycle \((0\ 1\ 2)\) which has order 3.
Exercise 2.5 (Challenge: Counting involutions)
How many involutions exist in \(S_{26}\)? Let \(a(n)\) denote the number of involutions in \(S_n\).
(a) Prove the recurrence relation \(a(n) = a(n-1) + (n-1) \cdot a(n-2)\) with \(a(0) = 1\), \(a(1) = 1\).
(b) Write Python code to compute \(a(n)\) for \(n = 0, 1, \ldots, 26\).
(c) What fraction of all permutations in \(S_{26}\) are involutions?
Hint
Recurrence derivation: Consider element \(n\) in \(\{1, 2, \ldots, n\}\). Either \(n\) is a fixed point of the involution (contributing \(a(n-1)\) involutions on the remaining \(n-1\) elements), or \(n\) is swapped with one of the other \(n-1\) elements (and the remaining \(n-2\) elements form an involution, contributing \((n-1) \cdot a(n-2)\)).
def count_involutions(n):
if n <= 1:
return 1
a_prev2, a_prev1 = 1, 1
for k in range(2, n + 1):
a_curr = a_prev1 + (k - 1) * a_prev2
a_prev2, a_prev1 = a_prev1, a_curr
return a_curr
import numpy as np
import math
def count_involutions(n):
"""Count the number of involutions in S_n using the recurrence
a(n) = a(n-1) + (n-1) * a(n-2), with a(0) = a(1) = 1.
"""
if n <= 1:
return 1
a_prev2, a_prev1 = 1, 1 # a(0), a(1)
for k in range(2, n + 1):
a_curr = a_prev1 + (k - 1) * a_prev2
a_prev2, a_prev1 = a_prev1, a_curr
return a_curr
# Compute and display the sequence
print(f"{'n':>3} {'a(n) = # involutions in S_n':>35} {'n!':>35} {'a(n)/n!':>15}")
print("-" * 95)
for n in range(27):
a_n = count_involutions(n)
n_fact = math.factorial(n)
ratio = a_n / n_fact
print(f"{n:>3} {a_n:>35,d} {n_fact:>35,d} {ratio:>15.6e}")
print()
a_26 = count_involutions(26)
print(f"Number of involutions in S_26: {a_26:,d}")
print(f" = {a_26:.6e}")
print(f"Total permutations in S_26: {math.factorial(26):,d}")
print(f"Fraction: {a_26 / math.factorial(26):.6e}")
n a(n) = # involutions in S_n n! a(n)/n!
-----------------------------------------------------------------------------------------------
0 1 1 1.000000e+00
1 1 1 1.000000e+00
2 2 2 1.000000e+00
3 4 6 6.666667e-01
4 10 24 4.166667e-01
5 26 120 2.166667e-01
6 76 720 1.055556e-01
7 232 5,040 4.603175e-02
8 764 40,320 1.894841e-02
9 2,620 362,880 7.220018e-03
10 9,496 3,628,800 2.616843e-03
11 35,696 39,916,800 8.942601e-04
12 140,152 479,001,600 2.925919e-04
13 568,504 6,227,020,800 9.129631e-05
14 2,390,480 87,178,291,200 2.742059e-05
15 10,349,536 1,307,674,368,000 7.914460e-06
16 46,206,736 20,922,789,888,000 2.208440e-06
17 211,799,312 355,687,428,096,000 5.954647e-07
18 997,313,824 6,402,373,705,728,000 1.557725e-07
19 4,809,701,440 121,645,100,408,832,000 3.953880e-08
20 23,758,664,096 2,432,902,008,176,640,000 9.765566e-09
21 119,952,692,896 51,090,942,171,709,440,000 2.347827e-09
22 618,884,638,912 1,124,000,727,777,607,680,000 5.506088e-10
23 3,257,843,882,624 25,852,016,738,884,976,640,000 1.260189e-10
24 17,492,190,577,600 620,448,401,733,239,439,360,000 2.819282e-11
25 95,680,443,760,576 15,511,210,043,330,985,984,000,000 6.168471e-12
26 532,985,208,200,576 403,291,461,126,605,635,584,000,000 1.321588e-12
Number of involutions in S_26: 532,985,208,200,576
= 5.329852e+14
Total permutations in S_26: 403,291,461,126,605,635,584,000,000
Fraction: 1.321588e-12
2.5 Summary and Key Takeaways#
In this chapter we have established the mathematical foundations of substitution ciphers:
Permutations as ciphers. Every substitution cipher is determined by a permutation \(\sigma \in S_n\) acting on the alphabet. Encryption applies \(\sigma\) letter-by-letter; decryption applies \(\sigma^{-1}\).
The symmetric group \(S_n\). The set of all permutations of an \(n\)-element set forms a group of order \(n!\) under composition. This group structure governs the algebraic properties of substitution ciphers: composition of ciphers corresponds to composition of permutations, and decryption corresponds to inversion.
Shift ciphers as a subgroup. The shift (Caesar) ciphers form a cyclic subgroup of \(S_n\) of order \(n\), isomorphic to \(\mathbb{Z}_n\). Their keyspace (\(n\) keys) is far too small for security.
Involutions and self-invertibility. A cipher is self-invertible if and only if its permutation is an involution (\(\sigma^2 = \text{id}\)). The unique non-trivial self-invertible shift cipher on 26 letters is ROT13 (\(k=13\)). The Atbash cipher (reversing the alphabet) is another classical involution.
Keyspace size is not security. Although the general substitution cipher has an enormous keyspace (\(26! \approx 4 \times 10^{26}\)), it preserves letter frequencies. This structural weakness, identified by Al-Kindi in the 9th century, allows frequency analysis to break it regardless of keyspace size.
In the next chapter, we will study frequency analysis in detail and use it to mount practical attacks on substitution ciphers.
2.6 References#
Singh, S. (1999). The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. Doubleday. – An accessible and comprehensive history of cryptography, including detailed accounts of Caesar’s cipher, Al-Kindi’s frequency analysis, and the evolution of substitution ciphers.
Katz, J. and Lindell, Y. (2020). Introduction to Modern Cryptography, 3rd edition. CRC Press. – Chapter 1 provides rigorous definitions of classical ciphers (shift, substitution, affine) within a modern cryptographic framework, with formal proofs of their insecurity.
Hungerford, T.W. (2012). Abstract Algebra: An Introduction, 3rd edition. Cengage Learning. – Chapters 7–8 cover permutation groups, cycle notation, the symmetric group, and their algebraic properties in full mathematical detail.
Al-Kindi (9th century). A Manuscript on Deciphering Cryptographic Messages. – The earliest known work on cryptanalysis, introducing frequency analysis. A translation and commentary appear in: Al-Kadi, I.A. (1992). “The origins of cryptology: The Arab contributions,” Cryptologia, 16(2), 97–126.
Stinson, D.R. and Paterson, M. (2018). Cryptography: Theory and Practice, 4th edition. CRC Press. – Section 1.1 gives a thorough treatment of shift and substitution ciphers, with exercises on affine ciphers and involutions.