Breaking Hill

The cipher is linear. Two known plaintext blocks give two equations, and the key is C times the inverse of P, modulo 26.

CryptanalysisKnown plaintextdemo

Objectives

Walk a message for a block pair whose matrix inverts mod 26.
Recover a 2x2 key from four letters of known plaintext.
Explain why a non-linear round step is the fix, and a longer key is not.

33%

C = K·P, and therefore K = C·P⁻¹ mod 26.

This is the one cipher of the week that needs no statistics at all. It is linear, so m known blocks are m equations in the key. The attacker holds a plaintext/ciphertext pair, which is the second row of the attack table and the most ordinary thing in the world: headers, greetings, file formats.

key matrix K

det K = 9, gcd(det K, 26) = 1. K inverts mod 26, so the receiver can decrypt.

Known plaintext

ciphertext

AMVOX KKIXF MITUE ZAVVX MIYH

Walk the message until a pair inverts

i	known pair	det P	gcd(det P, 26)	usable
0	WE HA	24	2	no
1	HA VE	2	2	no
2	VE AM	18	2	no
3	AM OL	14	2	no
4	OL EA	8	2	no
5	EA BO	4	2	no
6	BO RT	15	1	yes
7	RT TH	18	2	no
8	TH ED	3	1	yes
9	ED EA	14	2	no
10	EA LX	14	2	no

A pair works only when gcd(det P, 26) = 1. Half of them die on a parity, and one in thirteen more on the 13, so the attacker skips past the failures at no cost whatsoever.

The solve, from blocks 6 and 7

P⁻¹

K = C·P⁻¹

That is the key, from four letters of known plaintext. No search, no statistics, no guess: just K = C·P⁻¹ mod 26. Linearity is the whole vulnerability, and it is why every modern round contains a step that is deliberately not linear.

step 1/3

CPE 645 / CS 685

Breaking Hill

Breaking Playfair

Index of Coincidence