Breaking the Bifid Cipher with Simulated Annealing

Breaking the Bifid Cipher with Simulated Annealing

Introduction

The Bifid cipher, invented by Felix Delastelle around 1900, was clever for its time. It turns each letter into a pair of coordinates in a 5x5 Polybius square, then shuffles the rows and columns of a whole block together before reading them back out. That shuffling, called fractionation, makes every ciphertext letter depend on two different plaintext letters, which smears out the single-letter frequencies that give simple substitution away.

Smearing frequencies is not the same as destroying structure. The underlying language is still English, and the key is still just one 25-letter square. Given the period, a search that scores candidate decryptions by how English they look will climb straight to the key. This guide runs that search, a simulated annealing hill climb over the square, and recovers a 669-letter message with no crib and no known plaintext.

Table of Contents

• How Bifid Fractionates
• Why It Resists Frequency Analysis
• The Attack: Hill Climbing the Square
• Scoring with Quadgrams
• Interactive Visualizer
• A Worked Example
• Python Implementation
• Limitations
• Security Status
• FAQ
• References

How Bifid Fractionates

Bifid starts with a Polybius square, a 5x5 grid holding 25 letters, with I and J sharing a cell. A keyword fills the grid first, then the rest of the alphabet. Each letter has a row and a column, both from 1 to 5. Encryption of a block of period letters goes in three steps:

1. Write the row number of each letter in order, then the column number of each letter in order, underneath.
2. Read that whole sequence of coordinates straight across, row numbers first and then column numbers.
3. Regroup the sequence into pairs, and turn each pair back into a letter through the square.

Because the rows of the whole block are written before any columns, the first ciphertext letter is built from the row of one plaintext letter and the row of another. The coordinates have been split apart and recombined, which is the fractionation that gives the cipher its name and its strength.

Why It Resists Frequency Analysis

In a simple substitution cipher, the letter E always maps to one fixed symbol, so counting symbols breaks it. Bifid defeats that. A single plaintext letter contributes its row to one ciphertext letter and its column to another, so one plaintext E influences two outputs, and each output mixes pieces of two different inputs. The clean one-to-one mapping is gone, and so are the flat single-letter counts an analyst would normally exploit.

What survives is the statistics of the language at a deeper level. The correct square produces readable English, full of common quadgrams like TION and THAT. Any wrong square produces noise, where those quadgrams almost never appear. That gap between English and noise is a signal, and the attack is built entirely around measuring it.

The Attack: Hill Climbing the Square

The key is a permutation of 25 letters, so there are 25-factorial possible squares, far too many to try. Simulated annealing searches that space without enumerating it:

1. Start random. Fill the square with a random permutation and decrypt the ciphertext with it, using the known period.
2. Score it. Measure how English the decryption looks, with a quadgram statistic described below.
3. Swap and test. Swap two letters in the square, decrypt again, and compare the new score.
4. Accept by temperature. Always keep a better square. Keep a worse one with a probability that starts high and cools toward zero, which lets the search escape local traps early and settle precisely later.
5. Polish and repeat. After the annealing, do a greedy pass that keeps only improving swaps. Run several random restarts and keep the best, since not every start finds the key.

Each accepted swap nudges the square toward one that decrypts to English. Because Bifid has equivalent squares that decrypt identically, the search often lands on a square different from the original keyword square, but one that recovers the exact same plaintext.

Scoring with Quadgrams

The score measures how closely a candidate decryption matches English letter patterns, using quadgrams, which are runs of four letters. A table of the 8,000 most common English quadgrams carries how often each appears. The score of a text is the sum, over every four-letter window, of the log probability of that quadgram, with a small floor value for quadgrams not in the table.

English text piles up high scores, because its common quadgrams are frequent and probable. Garbled text scores far lower, since its four-letter windows are mostly rare or absent. The annealing simply chases a higher score, and the only square that pushes the score up to the level of real English is the right one, or an equivalent of it.

Interactive Visualizer

The visualizer above runs the real attack. It uses genuine Bifid and a real quadgram table, and the search is a seeded simulated annealing so you can watch it converge. Click to start, and the decryption shifts from noise toward English as the square settles, with the score climbing and the recovered square filling in. Nothing is faked, and the key is never read from the plaintext.

The default ciphertext is 669 letters at period 7. With that much text the attack is reliable, usually recovering the whole message in the first restart. Shorter messages are harder, and the search may need more restarts or fail, which is the honest edge of a statistical attack.

A Worked Example

The plaintext is a 669-letter passage about the cipher itself, encrypted with a square built from the keyword CRYPTOGRAM at period 7. The attacker sees only the ciphertext and the period:

key square : CRYPTOGAMBDEFHIKLNQSUVWXZ   (hidden from the attacker)
period     : 7
ciphertext : YEFILZIDDFCTQGVNSFIWGKFOAVYOXHHDDIEYHISGHYDFOCGT ...

A single annealing restart, seeded for reproducibility, recovers the message in full:

restarts used  : 1
recovered sq   : GOBMARCTPYVUZXWLKSQNEDIHF
score          : -3986.0
letters correct: 669/669
decryption     : THEBIFIDCIPHERWASINVENTEDAROUNDNINETEENHUNDREDBYTHEFRENCHMAN...

Every letter comes back. The recovered square GOBMARCTPYVUZXWLKSQNEDIHF is not the original keyword square, but an equivalent one that decrypts the ciphertext identically, which is why the plaintext is perfect even though the squares differ. The score of -3986 is exactly the score of the real plaintext, the signal that the search has arrived.

Python Implementation

The code is self-contained and runnable, given the shared quadgram table. It builds Bifid, scores with quadgrams, and runs the annealing search with a small reproducible PRNG so the worked example repeats exactly.

# bifid_breaker.py
#
# Ciphertext-only attack on the Bifid cipher, given the period. Bifid fractionates each letter into
# Polybius-square coordinates and shuffles rows and columns, so single-letter frequencies vanish. But the
# plaintext is still English, so a simulated-annealing hill climb over the 25-letter square, scored by
# English quadgram statistics, climbs to the key. The PRNG is mulberry32, matching the JS visualizer, so
# the worked example is reproducible. Needs the shared top-8000 quadgram table in quadgrams.txt.
import math
import re

ALPHA = "ABCDEFGHIKLMNOPQRSTUVWXYZ"          # 25 letters, J folded into I


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


def mulberry32(seed):
    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() + ALPHA):
        ch = "I" if ch == "J" else ch
        if ch in ALPHA and ch not in seen:
            seen.append(ch)
    return "".join(seen)


def clean(text):
    return "".join("I" if c == "J" else c for c in text.upper() if c.isalpha())


def bifid_encrypt(plain, square, period):
    pos = {c: (i // 5, i % 5) for i, c in enumerate(square)}
    out = []
    for i in range(0, len(plain), period):
        block = plain[i:i + period]
        seq = [pos[c][0] for c in block] + [pos[c][1] for c in block]
        for k in range(0, len(seq), 2):
            out.append(square[seq[k] * 5 + seq[k + 1]])
    return "".join(out)


def bifid_decrypt(cipher, square, period):
    pos = {c: (i // 5, i % 5) for i, c in enumerate(square)}
    out = []
    for i in range(0, len(cipher), period):
        block = cipher[i:i + period]
        seq = []
        for c in block:
            r, col = pos[c]
            seq += [r, col]
        half = len(block)
        for r, c in zip(seq[:half], seq[half:]):
            out.append(square[r * 5 + c])
    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 score(s):
    return sum(QLOG.get(s[i:i + 4], FLOOR) for i in range(len(s) - 3))


def one_restart(cipher, period, rnd, iters, T0):
    sq = list(ALPHA)
    for i in range(24, 0, -1):                       # Fisher-Yates shuffle
        j = int(rnd() * (i + 1))
        sq[i], sq[j] = sq[j], sq[i]
    cur = "".join(sq)
    cur_s = score(bifid_decrypt(cipher, cur, period))
    for it in range(iters):
        a, b = int(rnd() * 25), int(rnd() * 25)
        if a == b:
            continue
        lst = list(cur)
        lst[a], lst[b] = lst[b], lst[a]
        cand = "".join(lst)
        cs = score(bifid_decrypt(cipher, cand, period))
        d = cs - cur_s
        temp = T0 * (1 - it / iters)
        if d > 0 or (temp > 0.001 and rnd() < math.exp(d / temp)):
            cur, cur_s = cand, cs
    improved = True                                  # greedy polish
    while improved:
        improved = False
        for a in range(25):
            for b in range(a + 1, 25):
                lst = list(cur)
                lst[a], lst[b] = lst[b], lst[a]
                cand = "".join(lst)
                cs = score(bifid_decrypt(cipher, cand, period))
                if cs > cur_s:
                    cur, cur_s = cand, cs
                    improved = True
    return cur_s, cur


def break_bifid(cipher, period, seed=12345, max_restarts=12, iters=20000, T0=20.0):
    rnd = mulberry32(seed)
    threshold = -6.5 * max(1, len(cipher) - 3)       # "this looks like English" cutoff
    best_s, best_sq, used = -1e18, None, 0
    for _ in range(max_restarts):
        s, sq = one_restart(cipher, period, rnd, iters, T0)
        used += 1
        if s > best_s:
            best_s, best_sq = s, sq
        if best_s > threshold:                       # early stop once recovered
            break
    return best_sq, best_s, used


if __name__ == "__main__":
    assert bifid_encrypt("FLEEATONCE", "BGWKZQPNDSIOAXEFCLUMTHYVR", 10) == "UAEOLWRINS"
    key = make_square("CRYPTOGRAM")
    period = 7
    pt = clean(
        "the bifid cipher was invented around nineteen hundred by the frenchman felix delastelle "
        "and it combines a polybius square with a transposition step called fractionation each "
        "plaintext letter is first turned into a pair of coordinates in the square and then the "
        "rows and columns of a whole block are written out separately and recombined so that every "
        "ciphertext letter ends up depending on two different plaintext letters this spreading of "
        "information is what gives the cipher its strength against simple frequency analysis but the "
        "method is not strong by modern standards because with a known period and a few hundred "
        "letters of ciphertext a hill climbing search over the possible squares guided by the "
        "statistics of english quadgrams will gradually settle onto the real key and reveal the message")
    ct = bifid_encrypt(pt, key, period)
    print("period:", period, "ciphertext letters:", len(ct))

    sq, sc, used = break_bifid(ct, period, seed=12345)
    dec = bifid_decrypt(ct, sq, period)
    correct = sum(a == b for a, b in zip(dec, pt))
    print("restarts used  :", used)
    print("recovered sq   :", sq)
    print("score          :", round(sc, 1))
    print("letters correct:", f"{correct}/{len(pt)}")
    print("decryption     :", dec[:60])
    print("MATCH:", dec == pt)

Running it prints the worked example:

period: 7 ciphertext letters: 669
restarts used  : 1
recovered sq   : GOBMARCTPYVUZXWLKSQNEDIHF
score          : -3986.0
letters correct: 669/669
decryption     : THEBIFIDCIPHERWASINVENTEDAROUNDNINETEENHUNDREDBYTHEFRENCHMAN
MATCH: True

Limitations

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

• The period must be known. This search assumes the period is given. In practice an attacker tries each candidate period and keeps the one whose best decryption scores highest, which multiplies the work by the number of periods tried.
• It needs enough text. The quadgram signal has to rise above the noise. The 669-letter example recovers reliably, but a short message of a few dozen letters may not give the search enough to lock onto, and it can fail or need many restarts.
• It is statistical, not certain. Simulated annealing can land in a local trap, which is why the attack uses several restarts and keeps the best. Any single run can miss, even on long text.
• It recovers an equivalent square. Bifid has squares that decrypt identically, so the recovered square often differs from the original keyword square while producing the exact same plaintext. The message is fully recovered, but the literal keyword may not be.

Security Status

• Bifid is a classical cipher with no modern security. It was a reasonable hand cipher in 1900, but quadgram hill climbing breaks it on a laptop in seconds. It should be treated as a puzzle, never as protection for anything real.
• Fractionation alone is not enough. Spreading letters across outputs raises the bar over simple substitution, but it does not remove the language statistics that the attack feeds on. Secure ciphers destroy those statistics completely, which hand ciphers cannot do.
• The method is general. The same simulated-annealing-with-quadgrams approach breaks Playfair, the four-square and two-square ciphers, and column transposition. Any classical cipher whose key is a small permutation and whose output preserves language statistics falls to the same tool.

FAQ

What is the period in Bifid?

The period is the block size. Bifid processes the message in groups of that many letters, fractionating each group on its own. A larger period spreads coordinates across more letters, but the cipher still falls to the same attack once the period is known.

Why does the attack need the period?

Decryption depends on the block size, so the search must know how to group the ciphertext before it can score a candidate. Without the period, the attacker runs the whole search once per candidate period and keeps the result that scores most like English.

Why simulated annealing instead of trying every key?

There are 25-factorial possible squares, about 10 to the 25th power, which is impossible to enumerate. Annealing navigates that space by following the quadgram score uphill, accepting occasional downhill moves early to avoid traps, so it finds the key without ever listing all the options.

Why is the recovered square different from the keyword?

Bifid has equivalent squares that produce identical encryption, so more than one square decrypts the ciphertext to the same plaintext. The search finds one of those equivalents. The message comes back perfectly, even though the square may not match the original keyword.

How much ciphertext does it take?

A few hundred letters is comfortable, and the 669-letter example recovers in a single restart. Below roughly a hundred letters the quadgram signal weakens, and the attack becomes unreliable, needing more restarts or more text.

References

1. Delastelle, Félix. “Traité Élémentaire de Cryptographie,” 1902 (the original description of the Bifid cipher).

2. Practical Cryptography. “Cryptanalysis of the Bifid cipher” (the simulated-annealing-with-quadgrams method this guide follows).

3. The Bifid cipher guide on this site, whose cipher this breaker attacks: /blog/bifid-cipher/

4. The four-square breaker on this site, which uses the same annealing approach on two squares: /blog/four_square_breaker_guide/