16.2 Substitution Ciphers

One simple encryption method is called a substitution cipher.

A simple example of a substitution cipher is called the Caesar cipher, sometimes called a shift cipher. In this approach, each letter is replaced with a letter some fixed number of positions later in the alphabet. For example, if we use a shift of 3, then the letter A would be replaced with D, the letter 3 positions later in the alphabet. The entire mapping would look like: [1]

import string
ALPHA = string.ascii_uppercase

MESSAGE = "We ride at noon"      # EDIT
SHIFT = 3                        # EDIT: the encryption KEY

def caesar(text, shift):
    out = ""
    for ch in text.upper():
        if ch in ALPHA:
            out += ALPHA[(ALPHA.index(ch) + shift) % 26]
        elif ch.isdigit():
            out += ch
    return out

def blocks(s, n=3):
    return " ".join(s[i:i + n] for i in range(0, len(s), n))

print(f"the mapping for a shift of {SHIFT}")
print("   Original: " + " ".join(ALPHA))
print("   Maps to:  " + " ".join(caesar(ALPHA, SHIFT)))

secret = caesar(MESSAGE, SHIFT)
print(f"\nplaintext   {MESSAGE}")
print(f"encrypted   {secret}")
print(f"in blocks   {blocks(secret)}      <- hides the word lengths")
print(f"decrypted   {caesar(secret, -SHIFT)}   (same machine, shift {-SHIFT})")
print(f"round trip works? {caesar(secret, -SHIFT) == caesar(MESSAGE, 0)}")

print("\nthe book's other two messages, decrypted:")
for cipher, key, note in (("GZDKNKYDXMFWJXA", 5, "= 'Buy fifty shares' plus a filler letter"),
                          ("BNWMVXWNH", 9, "= 'Send money'")):
    print(f"   {blocks(cipher):<22} shift {key:>2}  ->  {caesar(cipher, -key):<18} {note}")

print("\nwhy the message gets chopped into equal blocks:")
print("   keeping word breaks:  " + " ".join(caesar(w, SHIFT) for w in "I am a spy".split()))
print("   in blocks of three:   " + blocks(caesar("I am a spy", SHIFT)))
print("   a one-letter word in the first version can only be an encrypted A or I")
# Try it: change SHIFT to 13. Encrypt twice with 13 and you get back where you started.

Original: $A B C D E F G H I J K L M N O P Q R S T U V W X Y Z$

Maps to: $D E F G H I J K L M N O P Q R S T U V W X Y Z A B C$

Example 2

Decrypt the message GZD KNK YDX MFW JXA if it was encrypted using a shift cipher with shift of 5.

Show solution

We start by writing out the character mapping by shifting the alphabet, with A mapping to F, five characters later in the alphabet.

Original: $A B C D E F G H I J K L M N O P Q R S T U V W X Y Z$

Maps to: $F G H I J K L M N O P Q R S T U V W X Y Z A B C D E$

We now work backwards to decrypt the message. The first letter G is mapped to by B, so B is the first character of the original message. Continuing, our decrypted message is

BUY FIF TYS HAR ESA.

Removing spaces we get BUYFIFTYSHARESA. In this case, it appears an extra character was added to the end to make the groups of three come out even, and that the original message was “Buy fifty shares.”

Woodcut of an Alberti cipher disk: a fixed outer ring of 24 cells holding the capitals A, B, C, D, E, F, G, I, L, M, N, O, P, Q, R, S, T, V, X and Z followed by the digits 1, 2, 3 and 4, and inside it a rotatable ring of 24 lowercase letters in scrambled, non-alphabetical order. Turning the inner wheel lines a different lowercase letter up against each capital, which is what sets the cipher shift.

Notice that in both the ciphers above, the extra part of the alphabet wraps around to the beginning. Because of this, a handy version of the shift cipher is a cipher disc, such as the Alberti cipher disk shown here[2] from the 1400s. In a cipher disc, the inner wheel could be turned to change the cipher shift. This same approach is used for “secret decoder rings.”

The security of a cryptographic method is very important to the person relying on their message being kept secret. The security depends on two factors:

The security of the method being used
The security of the encryption key used

In the case of a shift cipher, the method is “a shift cipher is used.” The encryption key is the specific amount of shift used.

Suppose an army is using a shift cipher to send their messages, and one of their officers is captured by their enemy. It is likely the method and encryption key could become compromised. It is relatively hard to change encryption methods, but relatively easy to change encryption keys.

During World War II, the Germans’ Enigma encryption machines were captured, but having details on the encryption method only slightly helped the Allies, since the encryption keys were still unknown and hard to discover. Ultimately, the security of a message cannot rely on the method being kept secret; it needs to rely on the key being kept secret.

With that in mind, let’s analyze the security of the Caesar cipher.

Example 3

Suppose you intercept a message, and you know the sender is using a Caesar cipher, but do not know the shift being used. The message begins EQZP. How hard would it be to decrypt this message?

Show solution

Since there are only 25 possible shifts, we would only have to try 25 different possibilities to see which one produces results that make sense. While that would be tedious, one person could easily do this by hand in a few minutes. A modern computer could try all possibilities in under a second.

Shift	Message	Shift	Message	Shift	Message	Shift	Message
1	DPYO	7	XJSI	13	RDMC	19	LXGW
2	COXN	8	WIRH	14	QCLB	20	KWFV
3	BNWM	9	VHQG	15	PBKA	21	JVEU
4	AMVL	10	UGPF	16	OAJZ	22	IUDT
5	ZLUK	11	TFOE	17	NZIY	23	HTCS
6	YKTJ	1 2	SEND	18	MYHX	24	GSBR
						25	FRAQ

In this case, a shift of 12 (A mapping to M) decrypts EQZP to SEND. Because of this ease of trying all possible encryption keys, the Caesar cipher is not a very secure encryption method.

Note

Brute Force Attack

A brute force attack is a method for breaking encryption by trying all possible encryption keys.

import math
import string
ALPHA = string.ascii_uppercase

CIPHERTEXT = "EQZP"     # EDIT: intercepted message, Caesar cipher, shift unknown

def unshift(text, shift):
    return "".join(ALPHA[(ALPHA.index(c) - shift) % 26] if c in ALPHA else c
                   for c in text.upper())

candidates = [(s, unshift(CIPHERTEXT, s)) for s in range(1, 26)]

print(f"intercepted: {CIPHERTEXT}     there are only 25 keys, so just try them all\n")
rows = 7
for r in range(rows):
    line = ""
    for col in range(4):
        i = r + col * rows
        if i < len(candidates):
            s, guess = candidates[i]
            line += f"   {s:>2}  {guess:<12}"
    print(line)

WORDS = {"SEND", "MONEY", "ATTACK", "RETREAT", "BUY", "SELL", "HELLO", "NOON", "MEET"}
hits = [(s, g) for s, g in candidates if g in WORDS]
print("\nwhich one is English?")
for s, g in hits:
    print(f"   shift {s} gives {g}  <- that is the key")
if not hits:
    print("   none of the 25 matched the little word list - read them yourself, "
          "a human spots English instantly")

print(f"\ncost of the attack: {len(candidates)} tries.")
print("   a person can do that in a few minutes; a computer does it in well under a second")
print("   security cannot come from hiding the METHOD, only from the KEY being hard to find")
print(f"   a random substitution of the 26 letters has 26! = {math.factorial(26):.3g} keys,")
print(f"   and adding the digits 0-9 gives 35! = {math.factorial(35):.3g} - about 10^40")
# Try it: paste in your own ciphertext from the Caesar cell above and break it.

To make a brute force attack harder, we could make a more complex substitution cipher by using something other than a shift of the alphabet. By choosing a random mapping, we could get a more secure cipher, with the tradeoff that the encryption key is harder to describe; the key would now be the entire mapping, rather than just the shift amount.

While there were only 25 possible shift cipher keys (35 if we had included numbers), there are about 10⁴⁰ possible substitution ciphers[3]. That’s much more than a trillion trillions. It would be essentially impossible, even with supercomputers, to try every possible combination. Having a huge number of possible encryption keys is one important part of key security.

Unfortunately, this cipher is still not secure, because of a technique called frequency analysis, discovered by Arab mathematician Al-Kindi in the 9^th century. English and other languages have certain letters than show up more often in writing than others.[4] For example, the letter E shows up the most frequently in English. The chart to the right shows the typical distribution of characters.

import string
from collections import Counter
ALPHA = string.ascii_uppercase

# Typical letter frequencies in English text, in percent.
ENGLISH = dict(zip(ALPHA, [8.2, 1.5, 2.8, 4.3, 12.7, 2.2, 2.0, 6.1, 7.0, 0.15, 0.77, 4.0,
                           2.4, 6.7, 7.5, 1.9, 0.095, 6.0, 6.3, 9.1, 2.8, 0.98, 2.4, 0.15,
                           2.0, 0.074]))

PLAINTEXT = ("The security of any encryption method should depend only on the "
             "encryption key being difficult to discover")     # EDIT
SECRET_SHIFT = 12                                              # EDIT

clean = "".join(c for c in PLAINTEXT.upper() if c in ALPHA)
cipher = "".join(ALPHA[(ALPHA.index(c) + SECRET_SHIFT) % 26] for c in clean)
print(f"intercepted ({len(cipher)} letters):\n   {cipher[:78]}...\n")

counts = Counter(cipher)
print("most common letters in the ciphertext vs most common letters in English")
top = counts.most_common(5)
eng_top = sorted(ENGLISH, key=ENGLISH.get, reverse=True)[:5]
for (c, n), e in zip(top, eng_top):
    print(f"   {c} appears {n:>3} times ({n / len(cipher):5.1%})     English favourite: "
          f"{e} ({ENGLISH[e]:.1f}%)")
print(f"   guess from the top letter alone: {top[0][0]} stands for E, "
      f"so the shift is {(ALPHA.index(top[0][0]) - 4) % 26}")

# Score every shift: how far is its letter profile from English?
scored = []
for s in range(26):
    guess = "".join(ALPHA[(ALPHA.index(c) - s) % 26] for c in cipher)
    g = Counter(guess)
    chi = sum((g.get(L, 0) - len(cipher) * ENGLISH[L] / 100) ** 2
              / (len(cipher) * ENGLISH[L] / 100) for L in ALPHA)
    scored.append((chi, s, guess))
scored.sort()

print("\nthe three shifts that look most like English (lower score = better fit)")
for chi, s, guess in scored[:3]:
    print(f"   shift {s:>2}  score {chi:>8.1f}   {guess[:56]}")
best = scored[0]
print(f"\nbroken automatically: the key is {best[1]} (the real key was {SECRET_SHIFT})"
      f"   correct? {best[1] == SECRET_SHIFT}")
print(f"   {best[2]}")
print("\nThis is why a plain shift - and even a random substitution - is not secure:")
print("   the cipher never changes E's disguise, so E's fingerprint survives encryption.")

In addition to looking at individual letters, certain pairs of letters show up more frequently, such as the pair “th.” By analyzing how often different letters and letter pairs show up an encrypted message, the substitution mapping used can be deduced[5].

[1] en.Wikipedia.org/w/index.php?title=File:Caesar3.svg&page=1. PD

[2] en.Wikipedia.org/wiki/File:Alberti_cipher_disk.JPG

[3] There are 35 choices for what A maps to, then 34 choices for what B maps to, and so on, so the total number of possibilities is 35*34*33*…*2*1 = 35! = about 10⁴⁰

[4] en.Wikipedia.org/w/index.php?title=File:English_letter_frequency_(alphabetic).svg&page=1 PD

[5] For an example of how this is done, see en.Wikipedia.org/wiki/Frequency_analysis

Adapted from Math in Society by David Lippman, hosted on LibreTexts (math.libretexts.org) and licensed under CC BY-SA 3.0. Changes were made. License: CC-BY-SA-3.0.