16.4 Advanced shared symmetric-key methods

Both the substitution and transposition methods discussed so far are shared symmetric-key methods, meaning that both sender and receiver would have to have agreed upon the same secret encryption key before any methods could be sent.

All of the methods so far have been susceptible to frequency analysis since each letter is always mapped to the same encrypted character. More advanced methods get around this weakness. For example, the Enigma machines used in World War II had wheels that rotated. Each wheel was a substitution cipher, but the rotation would cause the substitution used to shift after each character.

For a simplified example, in the initial setup, the wheel might provide the mapping

• Original: $$\mathrm{A}\mathrm{B}\mathrm{C}\mathrm{D}\mathrm{E}\mathrm{F}\mathrm{G}\mathrm{H}\mathrm{I}\mathrm{J}\mathrm{K}\mathrm{L}\mathrm{M}\mathrm{N}\mathrm{O}\mathrm{P}\mathrm{Q}\mathrm{R}\mathrm{S}\mathrm{T}\mathrm{U}\mathrm{V}\mathrm{W}\mathrm{X}\mathrm{Y}\mathrm{Z}0123456789$$
• Maps to: $$2\mathrm{B}\mathrm{Q}\mathrm{F}5\mathrm{W}\mathrm{R}\mathrm{T}\mathrm{D}8\mathrm{I}\mathrm{J}6\mathrm{H}\mathrm{L}\mathrm{C}\mathrm{O}\mathrm{S}\mathrm{U}\mathrm{V}\mathrm{K}3\mathrm{A}0\mathrm{X}9\mathrm{Y}\mathrm{Z}\mathrm{N}1\mathrm{G}4\mathrm{M}\mathrm{E}7\mathrm{P}$$

After the first character is encrypted, the wheel rotates, shifting the mapping one space, resulting in a new shifted mapping:

• Original: $$\mathrm{A}\mathrm{B}\mathrm{C}\mathrm{D}\mathrm{E}\mathrm{F}\mathrm{G}\mathrm{H}\mathrm{I}\mathrm{J}\mathrm{K}\mathrm{L}\mathrm{M}\mathrm{N}\mathrm{O}\mathrm{P}\mathrm{Q}\mathrm{R}\mathrm{S}\mathrm{T}\mathrm{U}\mathrm{V}\mathrm{W}\mathrm{X}\mathrm{Y}\mathrm{Z}0123456789$$
• Maps to: $$\mathrm{P}2\mathrm{B}\mathrm{Q}\mathrm{F}5\mathrm{W}\mathrm{R}\mathrm{T}\mathrm{D}8\mathrm{I}\mathrm{J}6\mathrm{H}\mathrm{L}\mathrm{C}\mathrm{O}\mathrm{S}\mathrm{U}\mathrm{V}\mathrm{K}3\mathrm{A}0\mathrm{X}9\mathrm{Y}\mathrm{Z}\mathrm{N}1\mathrm{G}4\mathrm{M}\mathrm{E}7$$

Using this approach, no letter gets encrypted as the same character over and over.

import string
from collections import defaultdict
ALPHA = string.ascii_uppercase

MESSAGE = "See me"       # EDIT
START_SHIFT = 3          # EDIT: the wheel's starting position
STEP = 1                 # EDIT: how far the wheel turns after each character

def rotate_encrypt(text, start, step):
    rows, out, shift = [], "", start
    for ch in text.upper():
        if ch not in ALPHA:
            continue
        enc = ALPHA[(ALPHA.index(ch) + shift) % 26]
        rows.append((ch, shift, enc))
        out += enc
        shift += step
    return rows, out

def rotate_decrypt(text, start, step):
    out, shift = "", start
    for ch in text.upper():
        if ch not in ALPHA:
            continue
        out += ALPHA[(ALPHA.index(ch) - shift) % 26]
        shift += step
    return out

rows, secret = rotate_encrypt(MESSAGE, START_SHIFT, STEP)
print(f"{'letter':>7}{'wheel shift':>13}{'becomes':>9}")
for ch, shift, enc in rows:
    print(f"{ch:>7}{shift:>13}{enc:>9}")
print(f"\n{MESSAGE!r} encrypts to {secret}")
print(f"decrypts back to {rotate_decrypt(secret, START_SHIFT, STEP)}")
print(f"the book's KIQRV with start 3 -> {rotate_decrypt('KIQRV', 3, 1)}")

seen = defaultdict(set)
for ch, _, enc in rows:
    seen[ch].add(enc)
print("\nwhat each plaintext letter turned into:")
for ch in sorted(seen):
    print(f"   {ch} -> {', '.join(sorted(seen[ch]))}")

long_msg = "eeeeeeeeeeeeeeeeeeeeeeeeee"
_, all_e = rotate_encrypt(long_msg, START_SHIFT, STEP)
print(f"\n26 E's in a row encrypt to:\n   {all_e}")
print(f"   {len(set(all_e))} different characters - frequency analysis has nothing to bite on")
print("   (set STEP = 0 and re-run: the wheel stops turning and it collapses to a "
      "plain Caesar cipher)")

The actual Engima machines used in WWII were more complex. Each wheel consisted of a complex substitution cipher, and multiple wheels were used in a chain[1]. The specific wheels used, order of the wheels, and starting position of the wheels formed the encryption key. While captured Engima devices provided the Allied forces details on the encryption method, the keys still had to be broken to decrypt messages.

These code breaking efforts led to the development of some of the first electronic computers by Alan Turing at Bletchley Park in the United Kingdom. This is generally considered the beginnings of modern computing[2].

In the 1970s, the U.S. government had a competition and ultimately approved an algorithm deemed DES (Data Encryption Standard) to be used for encrypting government data. It became the standard encryption algorithm used. This method used a combination of multiple substitution and transposition steps, along with other steps in which the encryption key is mixed with the message. This method uses an encryption key with length 56 bits, meaning there are 2⁵⁶ possible keys.

This number of keys make a brute force attack extremely difficult and costly, but not impossible. In 1998, a team was able to find the decryption key for a message in 2 days, using about $250,000 worth of hardware. However, the price and time will go down as computer power increases.

From 1997 to 2001 the government held another competition, ultimately adopting a new method, deemed AES (Advanced Encryption Standard). This method uses encryption keys with 128, 192, or 256 bits, providing up to 2²⁵⁶ possible keys, making brute force attacks essentially impossible.

[1] http://en.wikipedia.org/wiki/File:En...abet_rings.jpg

[2] For a good overview, see http://www.youtube.com/watch?v=5nK_ft0Lf1s

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.