Breaking the ADFGVX Cipher

Breaking the ADFGVX Cipher

Introduction

The ADFGVX cipher was the German army’s field cipher in 1918, and for a few months it was genuinely hard. It does two different things to a message. First it fractionates, turning each letter into a pair of symbols drawn from just six letters, A, D, F, G, V and X, chosen because they are hard to confuse in Morse code. Then it shuffles those symbols with a columnar transposition, which tears the two halves of each letter apart and scatters them across the message.

Neither step is strong alone. A plain substitution falls to frequency analysis, and a plain transposition falls to anagramming. Together they reinforce each other, because the transposition hides the substitution’s statistics and the substitution hides the transposition’s. The French cryptanalyst Georges Painvin broke it by hand in 1918, under enormous pressure, as German armies drove toward Paris. This guide runs the modern automated version of his attack: peel off the transposition first, then solve the substitution, and recover the whole message from the ciphertext alone.

Table of Contents

• How ADFGVX Works
• Why Two Weak Steps Make a Strong One
• Stage One: Recover the Transposition
• Stage Two: Solve the Substitution
• Interactive Visualizer
• A Worked Example
• Python Implementation
• Limitations
• Security Status
• FAQ
• References

How ADFGVX Works

Encryption starts with a 6 by 6 square holding all 26 letters and all 10 digits, 36 cells in total, with its rows and columns labelled A, D, F, G, V, X. Each plaintext character is replaced by the labels of its row and column, so every character becomes two symbols. A 100-letter message becomes a 200-symbol stream over a six-letter alphabet. This is the fractionation step.

Then comes the transposition. The symbol stream is written into a grid row by row, under a keyword, and the columns are read out in the alphabetical order of the keyword’s letters. Because the two symbols of each original letter sit side by side before the transposition, and land in different columns after it, they end up far apart in the ciphertext. Decryption reverses both steps: undo the transposition to rebuild the symbol stream, then read the symbols in pairs back through the square.

Why Two Weak Steps Make a Strong One

Attack the substitution directly and the transposition defeats you, because the symbols that should be paired are no longer adjacent. Attack the transposition directly and the substitution defeats you, because the symbols carry no obvious language structure to anagram against. The two layers protect each other, which is exactly why the combination held up when either half alone would not have.

The way through is to separate the layers and beat them one at a time. The key insight is that the transposition can be recovered without knowing the square at all, using a statistic that does not care which symbol stands for which letter. Once the transposition is undone, the square is all that remains, and recovering it is an ordinary substitution problem. Two manageable attacks in sequence beat the one hard combination.

Stage One: Recover the Transposition

The index of coincidence measures how often two symbols chosen at random turn out to be equal. It depends only on how uneven the symbol frequencies are, not on the labels, so swapping every symbol for another leaves it unchanged. That is what makes it perfect here. When the transposition is undone correctly, the symbol stream pairs up into real character codes whose frequencies are as lopsided as the plaintext’s letters, giving a high index of coincidence. When the column order is wrong, the pairing is scrambled and the value drops toward random.

So the attack hunts for the column order that maximizes the index of coincidence of the paired-up stream. A simulated annealing search over the possible column orders, scored by that single number, climbs straight to the right transposition. It never touches the square, because the index of coincidence is blind to the substitution. For a known keyword length the search is small and fast, and the correct order stands out clearly.

Stage Two: Solve the Substitution

With the transposition undone, the symbol stream rebuilds into the original character codes, each a pair of ADFGVX letters standing for one plaintext character. That is a simple monoalphabetic substitution: every code always means the same character. The square that produced it is just the lookup table, so recovering the square and decrypting the message are the same task.

A second simulated annealing search solves it, this time over the 36-cell square, scored by how English the resulting text looks using quadgram statistics. The same method that breaks an ordinary substitution cipher applies without change. Given a few hundred letters, it recovers the square and the plaintext cleanly. Characters that never appear in the message, such as unused digits, simply stay unknown, which does not affect the recovered text at all.

Interactive Visualizer

The visualizer above runs the real two-stage attack on real ADFGVX ciphertext. It first searches for the transposition, showing the index of coincidence climbing as the column order falls into place, then switches to the substitution solve and shows the decryption sharpening from noise into English. Every step uses the genuine cipher and genuine statistics, with nothing faked, and neither the square nor the keyword is supplied.

Edit the message, the square keyword, or the transposition keyword and run it again. As long as there is enough text, a few hundred letters, both stages lock on. The keyword length is taken as known, which is the one assumption the search leans on, and shorter messages make the statistics noisier.

A Worked Example

The hidden settings are a square built from the keyword KAISERWILHELM and a transposition keyword GERMANY, which has seven letters. The attacker sees only the stream of A, D, F, G, V and X:

ciphertext: AXAFFVAVGVDVDAGXAFADAXAXDAAFFGGVDVAFADADADDVFXGDGXAFFXDFAXAV ...

Stage one recovers the column reading order, stage two recovers the square, and the message, 330 letters long, comes back in full:

recovered column order : [4, 1, 0, 3, 5, 2, 6]
recovered square       : KAISERWLHMBCDFG...NOP.TUVQY...
letters correct        : 330/330
decryption             : THEGERMANSPRINGOFFENSIVEOFNINETEENEIGHTEEN...

Every letter comes back. The recovered square matches the real one in every cell that the message actually used; the handful of cells for characters that never appeared, like most of the digits, are left filled with whatever the search settled on, because the plaintext never tested them. The wall of six letters was a fractionated substitution hiding behind a transposition, and taking the two apart in order dissolved it.

Python Implementation

The code is self-contained and runnable, given the shared quadgram table. It builds ADFGVX, recovers the transposition by maximizing the index of coincidence, then solves the substitution with quadgram-scored annealing. A small reproducible PRNG, matching the visualizer, makes the worked example repeat exactly.

# adfgvx_breaker.py
#
# Two-stage ciphertext-only attack on ADFGVX. Each letter becomes two symbols from "ADFGVX" via a 6x6
# square (fractionation), then a keyed columnar transposition scatters the symbols. The layers protect
# each other, so the attack separates them: (1) recover the transposition by maximizing the index of
# coincidence of the re-paired symbol stream, which is INVARIANT to the unknown square; (2) what remains
# is a monoalphabetic substitution on the character codes, solved with quadgram-scored annealing. The
# transposition keyword length (period) is assumed known. Needs the shared quadgram table quadgrams.txt.
import math
import re

SYMS = "ADFGVX"
ALPHABET36 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"


def imul(a, b):
    return ((a & 0xFFFFFFFF) * (b & 0xFFFFFFFF)) & 0xFFFFFFFF


def mulberry32(seed):                              # matches the JS visualizer for reproducibility
    a = seed & 0xFFFFFFFF

    def rnd():
        nonlocal a
        a = (a + 0x6D2B79F5) & 0xFFFFFFFF
        t = imul(a ^ (a >> 15), 1 | a)
        t = ((t + imul(t ^ (t >> 7), 61 | t)) ^ t) & 0xFFFFFFFF
        return ((t ^ (t >> 14)) & 0xFFFFFFFF) / 4294967296.0
    return rnd


def make_square(keyword):
    seen = []
    for ch in (keyword.upper() + ALPHABET36):
        if ch in ALPHABET36 and ch not in seen:
            seen.append(ch)
    return "".join(seen)


def clean(text):
    return "".join(c for c in text.upper() if c in ALPHABET36)


def key_order(keyword):
    kw = keyword.upper()
    return sorted(range(len(kw)), key=lambda i: (kw[i], i))


def substitute(plain, square):
    pos = {c: (i // 6, i % 6) for i, c in enumerate(square)}
    return "".join(SYMS[pos[c][0]] + SYMS[pos[c][1]] for c in plain)


def transpose(s, keyword):
    cols = len(keyword)
    columns = [[] for _ in range(cols)]
    for i, ch in enumerate(s):
        columns[i % cols].append(ch)
    return "".join("".join(columns[c]) for c in key_order(keyword))


def adfgvx_encrypt(plaintext, square, keyword):
    return transpose(substitute(clean(plaintext), square), keyword)


def untranspose_by_order(ct, cols, order):
    total = len(ct)
    base, extra = divmod(total, cols)
    col_len = [base + 1 if i < extra else base for i in range(cols)]
    columns = [None] * cols
    idx = 0
    for c in order:
        columns[c] = ct[idx:idx + col_len[c]]
        idx += col_len[c]
    out, ptr = [], [0] * cols
    for i in range(total):
        c = i % cols
        out.append(columns[c][ptr[c]])
        ptr[c] += 1
    return "".join(out)


DATA = open("quadgrams.txt").read()
TOTAL = 4224127912
FLOOR = math.log10(0.01 / TOTAL)
QLOG = {m.group(1): math.log10(int(m.group(2)) / TOTAL) for m in re.finditer(r"([A-Z]{4})(\d+)", DATA)}


def qscore(s):
    return sum(QLOG.get(s[i:i + 4], FLOOR) for i in range(len(s) - 3))


def digraph_codes(s):
    return [SYMS.index(s[i]) * 6 + SYMS.index(s[i + 1]) for i in range(0, len(s) - 1, 2)]


def ic_codes(codes):
    n = len(codes)
    if n < 2:
        return 0.0
    counts = {}
    for x in codes:
        counts[x] = counts.get(x, 0) + 1
    return sum(c * (c - 1) for c in counts.values()) / (n * (n - 1))


def recover_transposition(ct, cols, rnd, restarts=12, iters=4000, T0=0.02):
    def score(order):
        return ic_codes(digraph_codes(untranspose_by_order(ct, cols, order)))
    best_order, best_s = None, -1
    for _ in range(restarts):
        order = list(range(cols))
        for i in range(cols - 1, 0, -1):
            j = int(rnd() * (i + 1))
            order[i], order[j] = order[j], order[i]
        cur_s = score(order)
        for it in range(iters):
            a, b = int(rnd() * cols), int(rnd() * cols)
            if a == b:
                continue
            order[a], order[b] = order[b], order[a]
            s = score(order)
            temp = T0 * (1 - it / iters)
            if s - cur_s > 0 or (temp > 1e-9 and rnd() < math.exp((s - cur_s) / temp)):
                cur_s = s
            else:
                order[a], order[b] = order[b], order[a]
        if cur_s > best_s:
            best_s, best_order = cur_s, order[:]
    return best_order


def solve_substitution(codes, rnd, restarts=12, iters=6000, T0=8.0):
    def decode(sq):
        return "".join(sq[c] for c in codes)
    threshold = -7.5 * max(1, len(codes) - 3)
    best_s, best_sq = -1e18, None
    for _ in range(restarts):
        sq = list(ALPHABET36)
        for i in range(35, 0, -1):
            j = int(rnd() * (i + 1))
            sq[i], sq[j] = sq[j], sq[i]
        cur = "".join(sq)
        cur_s = qscore(decode(cur))
        for it in range(iters):
            a, b = int(rnd() * 36), int(rnd() * 36)
            if a == b:
                continue
            lst = list(cur)
            lst[a], lst[b] = lst[b], lst[a]
            cand = "".join(lst)
            cs = qscore(decode(cand))
            temp = T0 * (1 - it / iters)
            if cs - cur_s > 0 or (temp > 1e-6 and rnd() < math.exp((cs - cur_s) / temp)):
                cur, cur_s = cand, cs
        improved = True
        while improved:
            improved = False
            for a in range(36):
                for b in range(a + 1, 36):
                    lst = list(cur)
                    lst[a], lst[b] = lst[b], lst[a]
                    cand = "".join(lst)
                    cs = qscore(decode(cand))
                    if cs > cur_s:
                        cur, cur_s = cand, cs
                        improved = True
        if cur_s > best_s:
            best_s, best_sq = cur_s, cur
        if best_s > threshold:
            break
    return best_sq


def break_adfgvx(ct, period, seed=12345):
    rnd = mulberry32(seed)
    order = recover_transposition(ct, period, rnd)
    s = untranspose_by_order(ct, period, order)
    codes = digraph_codes(s)
    square = solve_substitution(codes, rnd)
    return order, square, "".join(square[c] for c in codes)


if __name__ == "__main__":
    sq = make_square("KAISERWILHELM")
    kw = "GERMANY"
    pt = clean(
        "the german spring offensive of nineteen eighteen relied on surprise and the german field "
        "cipher protected the radio orders that moved whole armies toward paris in march and april "
        "the french cryptanalyst georges painvin broke the cipher by comparing messages that began "
        "in the same way and the breakthrough let the allies read the german plans before the final "
        "great assault on paris that summer")
    ct = adfgvx_encrypt(pt, sq, kw)
    print("period:", len(kw), " ciphertext letters:", len(ct))

    order, square, plain = break_adfgvx(ct, len(kw), seed=12345)
    correct = sum(a == b for a, b in zip(plain, pt))
    print("recovered order :", order)
    print("letters correct :", f"{correct}/{len(pt)}")
    print("decryption      :", plain[:56])
    print("MATCH:", plain == pt)

Running it prints the worked example:

period: 7  ciphertext letters: 660
recovered order : [4, 1, 0, 3, 5, 2, 6]
letters correct : 330/330
decryption      : THEGERMANSPRINGOFFENSIVEOFNINETEENEIGHTEENRELIEDONSURPR
MATCH: True

Limitations

The attack is a real ciphertext-only break, but it relies on a few conditions:

• The keyword length is assumed known. The transposition search runs for a given period. In practice an attacker tries each candidate length and keeps the one whose best transposition reaches the highest index of coincidence, which multiplies the work by the number of lengths tried.
• It needs enough text. Both the index of coincidence and the quadgram solve are statistical. A few hundred letters is comfortable; a short message can leave the transposition ambiguous or the substitution underdetermined.
• Both stages are searches, not certainties. Simulated annealing can settle into a local trap, so the attack uses several restarts and keeps the best. Any single run can miss, especially on short or unusual text.
• Painvin had it far harder. The historical break leaned on multiple messages sent in the same key with similar openings, and on painstaking hand analysis, not on computers. This guide shows the clean modern method on a single message, which is a different and much easier setting than 1918.

Security Status

• ADFGVX is a classical cipher with no modern security. It was a serious obstacle in 1918 and a triumph to break by hand, but today the two stages fall to a laptop in seconds. It belongs to history and to puzzles, not to protecting anything real.
• Combining a substitution with a transposition is not enough. The design is sound in spirit, mixing two different kinds of operation, but both stages leak structure that survives the other. Modern ciphers combine many rounds of substitution and permutation precisely so that no such statistic survives to separate the layers.
• The lesson is that layers must not be separable. ADFGVX fell because its two steps could be attacked one at a time, the transposition through a substitution-blind statistic and the substitution afterward. A strong cipher makes every part depend on every other, so there is no order in which to peel it apart.

FAQ

Why only the letters A, D, F, G, V and X?

They were chosen because their Morse code patterns are very different from one another, which made transmission errors easy to spot and hard to make. The cipher’s name is just those six label letters. An earlier version, ADFGX, used a 5 by 5 square with no digits.

Why attack the transposition before the substitution?

Because the transposition can be undone without knowing the square. The index of coincidence depends only on how uneven the symbol frequencies are, not on what the symbols mean, so it reveals the right column order while the substitution is still unknown. Once the transposition is gone, the substitution is an ordinary, easy problem.

How does the index of coincidence ignore the square?

Relabelling every symbol, which is what the unknown square does, does not change how often two symbols match. The index of coincidence counts matches, so it is identical before and after any substitution. That invariance is exactly why it can judge the transposition without the square.

Does the attack recover the keywords themselves?

It recovers the column reading order and the contents of the square, which is everything needed to decrypt. The original keywords that generated them are not always uniquely recoverable, but they are not needed, since the order and the square already decrypt the message.

Is this how Painvin broke it in 1918?

The idea of separating substitution from transposition is the same, but his method was different and far more demanding. He exploited many messages sent in the same key with stereotyped beginnings, and did the analysis by hand against the clock. The single-message statistical attack shown here is a modern convenience he did not have.

References

1. Kahn, David. “The Codebreakers,” 1967 (Painvin’s break of ADFGVX and the 1918 context).

2. Childs, J. Rives. “General Solution of the ADFGVX Cipher System,” 1934 (an early systematic solution).

3. Lasry, George, et al. “Cryptanalysis of ADFGVX,” 2017 (modern automated attacks on the cipher).

4. The ADFGVX cipher guide on this site, whose cipher this breaker attacks: /blog/adfgvx-cipher/