Breaking a Product Cipher

Index of coincidence and chi-square at every stage, unmoved, and letter counts identical to one substitution applied twice.

CryptanalysisCompositiondemo

Objectives

Measure both statistics at each stage of a two-round product cipher.
Show that the transposition contributes nothing the histogram can see.
Say what a modern round adds that alternating these two stages does not.

25%

Substitute, transpose, repeat. Every letter count comes through untouched.

Plaintext

Rails

Every stage, measured

stage	IC	χ²
plaintext	0.0634	27.5
round 1, substitution	0.0634	4033.8
round 1, rail fence	0.0634	4033.8
round 2, substitution	0.0634	5476.1
round 2, rail fence	0.0634	5476.1

Substitution renames letters. Transposition moves them. Neither changes how many of each there are, so two rounds later the index of coincidence has not moved a digit.

The letter counts after two rounds

ciphertext

H ×38 Q ×36 Y ×36 M ×33 W ×26 D ×25 X ×22 A ×21

the same substitution applied twice, no transposition

H ×38 Q ×36 Y ×36 M ×33 W ×26 D ×25 X ×22 A ×21

Identical, and so is the chi-square: 5476.1 against 5476.1. The transposition contributed nothing the histogram can see, so the histogram is still a renamed English one.

Search the rails, climb the letters

Substitution is positionwise and the rail fence permutes positions, so the two commute and the whole cipher is one substitution applied twice on top of one transposition applied twice. Undo the rails for a candidate count and what is left is a single monoalphabetic substitution. The attacker never recovers K, only K applied twice, and the message needs nothing more.

7 rail counts, 12 restarts each

Nothing is solved yet. The attack tries every rail count from 2 to 8, and for each one hill climbs the substitution: swap two letters of a candidate key, keep the swap when the trigram score improves, restart when it sticks.

Combining the two stages raised the work factor. It closed neither leak. The key is a letter permutation and a rail count, so the attacker searches the rails and hill-climbs the letters. What DES and AES add is not more rounds of this: it is a keyed non-linear round step, which a fixed letter map never was.

step 1/4

CPE 645 / CS 685

Breaking a Product Cipher

Breaking Columnar Transposition

Steganalysis