Chapter 2: Permutations and Substitution Ciphers (SageMath)#
Python Version Available
This notebook contains the SageMath implementation. A pure Python/NumPy version is available in Chapter 2: Permutations and Substitution.
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: Permutations in SageMath#
SageMath provides native algebraic structures for working with permutations. Instead of building classes from scratch with NumPy, we use:
Permutations(n)– the set of all permutations on \(\{1, 2, \ldots, n\}\)SymmetricGroup(n)– the symmetric group \(S_n\) as an algebraic groupPermutationGroupElement– elements of permutation groups with full group operations
This gives us composition (*), inversion (**(-1)), order (.order()), and cycle
decomposition (.cycle_tuples()) for free.
# Permutation groups in SageMath
# (adapted from the course video transcript)
# Permutations(n) gives the set of all permutations on {1, 2, ..., n}
G = Permutations(10)
G
Standard permutations of 10
# Encode a permutation as a list: sigma(1)=2, sigma(2)=3, ..., sigma(10)=1
sigma = G([2, 3, 4, 5, 6, 7, 8, 9, 10, 1])
# Evaluate the permutation at specific points
print("sigma(1) =", sigma(1))
print("sigma(2) =", sigma(2))
print()
# Full image of sigma
print("Full image:", [sigma(k) for k in range(1, 11)])
sigma(1) = 2
sigma(2) = 3
Full image: [2, 3, 4, 5, 6, 7, 8, 9, 10, 1]
# Cycle decomposition of sigma
# This is a cycle decomposition
sigma.cycle_tuples()
[(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)]
# Composition of permutations
sigma * sigma
[3, 4, 5, 6, 7, 8, 9, 10, 1, 2]
# SymmetricGroup gives a proper algebraic group object
G5 = SymmetricGroup(range(0, 5))
print("G5 =", G5)
print("A random element:", G5.random_element())
G5 = Symmetric group of order 5! as a permutation group
A random element: (0,4,1,3)
# Construct a specific permutation in the group
Plist = [0, 4, 3, 2, 1]
Pperm = PermutationGroupElement(Plist, G5)
print("Pperm =", Pperm)
print("Pperm^(-1) =", Pperm**(-1))
print("Order of Pperm:", Pperm.order())
print("Pperm(4) =", Pperm(4))
Pperm = (1,4)(2,3)
Pperm^(-1) = (1,4)(2,3)
Order of Pperm: 2
Pperm(4) = 1
Substitution and shift ciphers using SageMath permutations#
We now implement substitution and shift ciphers using SageMath’s native SymmetricGroup
and PermutationGroupElement. The design mirrors the mathematical definitions:
a substitution cipher wraps a group element, while the shift cipher is the special
case \(\sigma_k(x) = (x + k) \bmod n\).
class SubstitutionCipherSage:
"""General substitution cipher over a given alphabet using SageMath permutations."""
def __init__(self, perm_list, alphabet):
"""
Parameters
----------
perm_list : list
A list where perm_list[i] is the character that alphabet[i] maps to.
alphabet : list
The ordered list of characters in the alphabet.
"""
if sorted(perm_list) != sorted(alphabet):
raise ValueError("perm_list must be a rearrangement of alphabet")
self.alphabet = list(alphabet)
self.n = len(alphabet)
self._char_to_idx = {ch: i for i, ch in enumerate(self.alphabet)}
# Build a permutation in S_n (1-indexed for SageMath)
# sigma: alphabet[i] -> perm_list[i] means (i+1) -> (idx(perm_list[i])+1)
one_indexed = [self._char_to_idx[perm_list[i]] + 1 for i in range(self.n)]
self._perm = Permutation(one_indexed)
self.permutation = list(perm_list)
def encrypt_char(self, ch):
"""Encrypt a single character. Characters not in alphabet are unchanged."""
if ch not in self._char_to_idx:
return ch
i = self._char_to_idx[ch]
j = self._perm(i + 1) - 1 # convert to 1-indexed, apply, convert back
return self.alphabet[j]
def decrypt_char(self, ch):
"""Decrypt a single character. Characters not in alphabet are unchanged."""
if ch not in self._char_to_idx:
return ch
i = self._char_to_idx[ch]
j = self._perm.inverse()(i + 1) - 1
return self.alphabet[j]
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."""
return self._perm * self._perm == Permutation(list(range(1, self.n + 1)))
def order(self):
"""Order of the permutation (smallest k with sigma^k = id)."""
return self._perm.order()
def cycle_tuples(self):
"""Return the cycle decomposition of the underlying permutation."""
return self._perm.cycle_tuples()
def compose(self, other):
"""Return the composition self(other(x)) as a new SubstitutionCipherSage."""
new_perm = [self.encrypt_char(other.encrypt_char(ch)) for ch in self.alphabet]
return SubstitutionCipherSage(new_perm, self.alphabet)
def inverse(self):
"""Return the inverse cipher."""
inv_perm_sage = self._perm.inverse()
inv_list = [self.alphabet[inv_perm_sage(i + 1) - 1] for i in range(self.n)]
return SubstitutionCipherSage(inv_list, self.alphabet)
def __repr__(self):
return f"SubstitutionCipherSage(perm={''.join(self.permutation)}, n={self.n})"
class ShiftCipherSage(SubstitutionCipherSage):
"""Caesar/shift cipher: sigma_k(x) = (x + k) mod n."""
def __init__(self, shift, alphabet):
self.shift = shift % len(alphabet)
n = len(alphabet)
permutation = [alphabet[(i + shift) % n] for i in range(n)]
super().__init__(permutation, alphabet)
def __repr__(self):
return f"ShiftCipherSage(shift={self.shift}, n={self.n})"
# ---------------------------------------------------------------
# Demo: basic encryption and decryption
# ---------------------------------------------------------------
import string
alphabet = list(string.ascii_lowercase)
print("=" * 60)
print("SHIFT CIPHER DEMO")
print("=" * 60)
caesar = ShiftCipherSage(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(f"Cycles : {caesar.cycle_tuples()}")
print()
# ROT13 -- the classic self-invertible shift
rot13 = ShiftCipherSage(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 using SageMath
set_random_seed(42)
S26 = SymmetricGroup(26)
rand_elem = S26.random_element()
# Convert to a character permutation
perm_indices = [rand_elem(i) for i in range(1, 27)]
perm = [alphabet[j - 1] for j in perm_indices]
gen_cipher = SubstitutionCipherSage(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()}")
print(f"Cycles: {gen_cipher.cycle_tuples()}")
============================================================
SHIFT CIPHER DEMO
============================================================
Plaintext : attackatdawn
Shift : k = 3
Ciphertext: dwwdfndwgdzq
Decrypted : attackatdawn
Correct : True
Cycles : [(1, 4, 7, 10, 13, 16, 19, 22, 25, 2, 5, 8, 11, 14, 17, 20, 23, 26, 3, 6, 9, 12, 15, 18, 21, 24)]
ROT13 of 'helloworld': uryybjbeyq
ROT13 of 'uryybjbeyq': helloworld
ROT13 is involution: True
Order of ROT13: 2
============================================================
GENERAL SUBSTITUTION CIPHER DEMO
============================================================
Plaintext : thisisasecretmessage
Permutation: pxkwdgomvtzashiunyjbrlfqce
Ciphertext: bmvjvjpjdkydbsdjjpod
Decrypted : thisisasecretmessage
Correct : True
Is involution: False
Order: 153
Cycles: [(1, 16, 21, 18, 25, 3, 11, 26, 5, 4, 23, 6, 7, 15, 9, 22, 12), (2, 24, 17, 14, 8, 13, 19, 10, 20)]
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. SageMath provides
.order() and cycle-based involution checking natively.
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 = ShiftCipherSage(k, alphabet)
ord_k = cipher.order()
is_inv = cipher.is_involution()
g = 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.
In SageMath we use arrow2d(), text(), and graphics_array() for the visualization.
import string
def plot_permutation_mapping_sage(cipher, title="Permutation Mapping"):
"""Draw a mapping diagram using SageMath graphics primitives."""
n = cipher.n
alph = cipher.alphabet
y_top = 1.0
y_bot = 0.0
x_positions = [i / (n - 1) for i in range(n)]
char_to_x = {ch: x_positions[i] for i, ch in enumerate(alph)}
# Rainbow colors via the rainbow() function
colors = rainbow(n)
G = Graphics()
for i, ch in enumerate(alph):
target = cipher.encrypt_char(ch)
x_start = char_to_x[ch]
x_end = char_to_x[target]
G += arrow2d((x_start, y_top - 0.08), (x_end, y_bot + 0.08),
color=colors[i], width=1, arrowsize=2)
# Draw letter labels
for i, ch in enumerate(alph):
G += text(ch.upper(), (x_positions[i], y_top + 0.07),
fontsize=8, fontweight='bold', color='black')
G += text(ch.upper(), (x_positions[i], y_bot - 0.07),
fontsize=8, fontweight='bold', color='black')
G += text("Plain:", (-0.06, y_top + 0.07), fontsize=9, color='gray')
G += text("Cipher:", (-0.06, y_bot - 0.07), fontsize=9, color='gray')
G += text(title, (0.5, y_top + 0.18), fontsize=12, fontweight='bold', color='black')
return G
# --- Generate two ciphers for comparison ---
alphabet = list(string.ascii_lowercase)
# Shift cipher (Caesar, k=3)
shift_cipher = ShiftCipherSage(3, alphabet)
# Random substitution cipher
set_random_seed(2024)
S26 = SymmetricGroup(26)
rand_elem = S26.random_element()
perm_indices = [rand_elem(i) for i in range(1, 27)]
random_perm = [alphabet[j - 1] for j in perm_indices]
random_cipher = SubstitutionCipherSage(random_perm, alphabet)
G1 = plot_permutation_mapping_sage(shift_cipher, title="Shift Cipher (k = 3)")
G2 = plot_permutation_mapping_sage(random_cipher, title="Random Substitution Cipher")
show(graphics_array([G1, G2], nrows=2),
figsize=[14, 7], axes=False)
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. This is essentially the brute-force attack on a shift cipher: simply try all keys and look for readable plaintext.
import string
alphabet = list(string.ascii_lowercase)
sample_word = "cryptanalysis"
print(f'All 26 Shift Ciphers Applied to "{sample_word}"')
print("=" * 50)
print(f"{'Shift (k)':>10} {'Ciphertext':>20}")
print("-" * 50)
for k in range(26):
cipher = ShiftCipherSage(k, alphabet)
encrypted = cipher.encrypt(sample_word)
marker = ""
if k == 0:
marker = " <-- identity"
elif k == 13:
marker = " <-- ROT13"
print(f"{'k = ' + str(k):>10} {encrypted.upper():>20}{marker}")
All 26 Shift Ciphers Applied to "cryptanalysis"
==================================================
Shift (k) Ciphertext
--------------------------------------------------
k = 0 CRYPTANALYSIS <-- identity
k = 1 DSZQUBOBMZTJT
k = 2 ETARVCPCNAUKU
k = 3 FUBSWDQDOBVLV
k = 4 GVCTXEREPCWMW
k = 5 HWDUYFSFQDXNX
k = 6 IXEVZGTGREYOY
k = 7 JYFWAHUHSFZPZ
k = 8 KZGXBIVITGAQA
k = 9 LAHYCJWJUHBRB
k = 10 MBIZDKXKVICSC
k = 11 NCJAELYLWJDTD
k = 12 ODKBFMZMXKEUE
k = 13 PELCGNANYLFVF <-- ROT13
k = 14 QFMDHOBOZMGWG
k = 15 RGNEIPCPANHXH
k = 16 SHOFJQDQBOIYI
k = 17 TIPGKRERCPJZJ
k = 18 UJQHLSFSDQKAK
k = 19 VKRIMTGTERLBL
k = 20 WLSJNUHUFSMCM
k = 21 XMTKOVIVGTNDN
k = 22 YNULPWJWHUOEO
k = 23 ZOVMQXKXIVPFP
k = 24 APWNRYLYJWQGQ
k = 25 BQXOSZMZKXRHR
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. We use SageMath’s graphics primitives for the visualization.
# 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: euler_phi(26) = 12 choices for a
# b can be anything: 26 choices for b
# Total: 12 * 26 = 312
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 = factorial(n)
print(f"Shift cipher keyspace: {shift_keys}")
print(f"Affine cipher keyspace: {affine_keys}")
print(f"General substitution keyspace: {subst_keys}")
print(f" = {'{:.2e}'.format(float(RealField(50)(subst_keys)))}")
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)} = euler_phi(26) = {euler_phi(26)}")
print()
# Bar chart on log scale using SageMath graphics
labels = ['Shift\n(Caesar)', 'Affine', 'General\nSubstitution']
values = [shift_keys, affine_keys, subst_keys]
log_values = [RR(log(v, 10)) for v in values]
colors = ['#3498db', '#e67e22', '#e74c3c']
G = Graphics()
bar_width = 0.5
for i, (lv, col) in enumerate(zip(log_values, colors)):
G += polygon2d([(i - bar_width/2, 0), (i - bar_width/2, lv),
(i + bar_width/2, lv), (i + bar_width/2, 0)],
color=col, edgecolor='black')
# Annotate with actual value
if values[i] < 1000:
label_text = str(values[i])
else:
label_text = f"{'{:.2e}'.format(float(RealField(30)(values[i])))}"
G += text(label_text, (i, lv + 1.0), fontsize=9, fontweight='bold', color='black')
# Reference line at log10(2^128)
ref = RR(log(2**128, 10))
G += line2d([(-0.5, ref), (2.5, ref)], color='gray', linestyle='--', alpha=0.5)
G += text(r"$2^{128}$ (modern standard)", (1.8, ref + 1.0), fontsize=8, color='gray')
show(G, axes=True, figsize=[9, 6],
title='Keyspace Size Comparison (n = 26)',
axes_labels=[' ', r'$\log_{10}$(keyspace size)'],
ymin=0, ymax=max(log_values) + 3,
ticks=[[0, 1, 2], None],
tick_formatter=[labels, None])
Shift cipher keyspace: 26
Affine cipher keyspace: 312
General substitution keyspace: 403291461126605635584000000
= 4.03e+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 = euler_phi(26) = 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 word list.
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
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 using SageMath’s native group operations.
import string
alphabet = list(string.ascii_lowercase)
# Two shift ciphers
sigma_3 = ShiftCipherSage(3, alphabet)
sigma_5 = ShiftCipherSage(5, alphabet)
# Their composition should be a shift by 3+5=8
composed = sigma_3.compose(sigma_5)
sigma_8 = ShiftCipherSage(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()
# --- SageMath native permutation algebra ---
print("--- SageMath native permutation algebra ---")
G10 = SymmetricGroup(range(0, 10))
sigma = PermutationGroupElement([2, 3, 4, 5, 6, 7, 8, 9, 0, 1], G10)
print(f"sigma = {sigma}")
print(f"sigma^(-1) = {sigma**(-1)}")
print(f"sigma * sigma^(-1) = {sigma * sigma**(-1)}")
print(f"Order of sigma: {sigma.order()}")
print(f"Cycle tuples: {sigma.cycle_tuples()}")
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
--- SageMath native permutation algebra ---
sigma = (0,2,4,6,8)(1,3,5,7,9)
sigma^(-1) = (0,8,6,4,2)(1,9,7,5,3)
sigma * sigma^(-1) = ()
Order of sigma: 5
Cycle tuples: [(0, 2, 4, 6, 8), (1, 3, 5, 7, 9)]
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.
import string
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 SubstitutionCipherSage(perm, alphabet)
# Example 1: Atbash cipher -- reverse the alphabet (a<->z, b<->y, c<->x, ...)
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()}")
print(f" Cycles: {atbash.cycle_tuples()}")
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()}")
print(f" Cycles: {partial_inv.cycle_tuples()}")
msg2 = "abcdef"
print(f" encrypt('{msg2}') = '{partial_inv.encrypt(msg2)}'")
print(f" encrypt twice = '{partial_inv.encrypt(partial_inv.encrypt(msg2))}'")
Atbash cipher (a<->z, b<->y, c<->x, ...):
Permutation: zyxwvutsrqponmlkjihgfedcba
Is involution: True
Order: 2
Cycles: [(1, 26), (2, 25), (3, 24), (4, 23), (5, 22), (6, 21), (7, 20), (8, 19), (9, 18), (10, 17), (11, 16), (12, 15), (13, 14)]
encrypt('helloworld') = 'svooldliow'
encrypt('svooldliow') = 'helloworld' (decrypts back!)
Partial involution (a<->b, c<->d, e<->f, rest fixed):
Is involution: True
Order: 2
Cycles: [(1, 2), (3, 4), (5, 6), (7,), (8,), (9,), (10,), (11,), (12,), (13,), (14,), (15,), (16,), (17,), (18,), (19,), (20,), (21,), (22,), (23,), (24,), (25,), (26,)]
encrypt('abcdef') = 'badcfe'
encrypt twice = 'abcdef'
# Visualize the Atbash involution as a mapping diagram
G = plot_permutation_mapping_sage(atbash, title="Atbash Cipher (Involution)")
show(G, figsize=[14, 4], axes=False)
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 SageMath using Mod() or IntegerModRing().
(b) Determine which values of \(a\) give valid (invertible) ciphers. Use euler_phi().
(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. In SageMath, use
inverse_mod(a, 26) or Mod(a, 26)^(-1) to compute the modular inverse.
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)
SageMath provides Permutation with native cycle notation support. 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\).
Use SageMath’s Permutation to:
(a) Create the 5-cycle \((1\ 2\ 3\ 4\ 5)\) and compute its inverse using .inverse().
(b) Verify that composing the permutation with its inverse gives the identity.
(c) Explore the .cycle_type() and .to_cycles() methods.
Hint
# In SageMath:
sigma = Permutation((1, 2, 3, 4, 5))
sigma_inv = sigma.inverse()
print(sigma * sigma_inv) # should be the identity
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\). Use SageMath to 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.
S3 = SymmetricGroup(3)
sigma = S3("(1,2)")
tau = S3("(2,3)")
print((sigma * tau).order()) # should be 3, not 1 or 2
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 SageMath 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
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 = factorial(n)
ratio = RR(a_n) / RR(n_fact)
print(f"{n:>3} {a_n:>35} {n_fact:>35} {ratio:>15.6e}")
print()
a_26 = count_involutions(26)
print(f"Number of involutions in S_26: {a_26}")
print(f"Total permutations in S_26: {factorial(26)}")
print(f"Fraction: {RR(a_26) / RR(factorial(26)):.6e}")
n a(n) = # involutions in S_n n! a(n)/n!
-----------------------------------------------------------------------------------------------
0 1 1 1.000000e+0
1 1 1 1.000000e+0
2 2 2 1.000000e+0
3 4 6 6.666667e-1
4 10 24 4.166667e-1
5 26 120 2.166667e-1
6 76 720 1.055556e-1
7 232 5040 4.603175e-2
8 764 40320 1.894841e-2
9 2620 362880 7.220018e-3
10 9496 3628800 2.616843e-3
11 35696 39916800 8.942601e-4
12 140152 479001600 2.925919e-4
13 568504 6227020800 9.129631e-5
14 2390480 87178291200 2.742059e-5
15 10349536 1307674368000 7.914460e-6
16 46206736 20922789888000 2.208440e-6
17 211799312 355687428096000 5.954647e-7
18 997313824 6402373705728000 1.557725e-7
19 4809701440 121645100408832000 3.953880e-8
20 23758664096 2432902008176640000 9.765566e-9
21 119952692896 51090942171709440000 2.347827e-9
22 618884638912 1124000727777607680000 5.506088e-10
23 3257843882624 25852016738884976640000 1.260189e-10
24 17492190577600 620448401733239439360000 2.819282e-11
25 95680443760576 15511210043330985984000000 6.168471e-12
26 532985208200576 403291461126605635584000000 1.321588e-12
Number of involutions in S_26: 532985208200576
Total permutations in S_26: 403291461126605635584000000
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.