demos/neural_ca_reversible_cipher.py

"""neural_ca  --  a reversible cellular automaton as a perfect cipher.

The Margolus block rule is a bijection of the lattice, so iterating it forward
diffuses a bitmap into noise and iterating the exact same rule backward restores
it bit-for-bit. That makes the automaton a block cipher whose key is the pair
(number of steps, starting partition phase): the right key inverts the diffusion
perfectly, and a key off by a single step returns noise. No information is ever
destroyed, so decryption is exact rather than approximate.

    python demos/neural_ca_reversible_cipher.py
"""
import os, sys
HERE = os.path.dirname(os.path.abspath(__file__))
REPO = os.path.dirname(HERE)
sys.path.insert(0, os.path.join(REPO, "src"))
import ca

# a recognizable plaintext bitmap (a heart), padded into a larger lattice
ART = [
    "  ###   ###  ",
    " ##### ##### ",
    "#############",
    "#############",
    "#############",
    " ########### ",
    "  #########  ",
    "   #######   ",
    "    #####    ",
    "     ###     ",
    "      #      ",
]
PAD_X, PAD_Y = 6, 4


def make_grid():
    # the Margolus partition tiles 2x2 blocks toroidally, so H and W must be even
    h = len(ART) + 2 * PAD_Y
    w = len(ART[0]) + 2 * PAD_X
    h += h & 1
    w += w & 1
    g = [[0] * w for _ in range(h)]
    for y, row in enumerate(ART):
        for x, ch in enumerate(row):
            if ch == "#":
                g[y + PAD_Y][x + PAD_X] = 1
    return g


def render(g):
    return "\n".join("".join("#" if c else "." for c in row) for row in g)


def hamming(a, b):
    return sum(a[y][x] != b[y][x] for y in range(len(a)) for x in range(len(a[0])))


if __name__ == "__main__":
    plain = make_grid()
    KEY_STEPS, KEY_PHASE = 200, 0

    cipher = ca.run(plain, KEY_STEPS, KEY_PHASE)
    recovered = ca.run_back(cipher, KEY_STEPS, KEY_PHASE)
    wrong = ca.run_back(cipher, KEY_STEPS - 1, KEY_PHASE)   # key off by one step

    n = sum(map(sum, plain))
    print("neural_ca: reversible-automaton cipher")
    print("=" * 46)
    print(f"key = ({KEY_STEPS} steps, phase {KEY_PHASE}); {n} set bits (conserved "
          f"throughout: {sum(map(sum, cipher)) == n})\n")

    print("PLAINTEXT:")
    print(render(plain))
    print(f"\nCIPHERTEXT after {KEY_STEPS} forward steps (diffused to noise):")
    print(render(cipher))
    print(f"\nDECRYPTED with the correct key:")
    print(render(recovered))
    print(f"  exact recovery: {recovered == plain}  (Hamming distance 0)")
    print(f"\nDECRYPTED with a wrong key (off by one step):")
    print(render(wrong))
    print(f"  still scrambled: {hamming(wrong, plain)} of {len(plain)*len(plain[0])} "
          f"cells differ from the plaintext")
    print("\nEvery step is a bijection, so the ciphertext holds exactly the")
    print("information of the plaintext -- no more, no less. Only the exact")
    print("reverse trajectory recovers it.")