Hill Cipher

Multiply blocks of letters by a matrix, modulo 26. The cipher is linear, which later makes it easy to break.

Polygraphicdemo

Objectives

Encrypt and decrypt a block with an n × n key matrix mod 26.
Determine whether a matrix is a usable key from its determinant mod 26.
Explain why linearity lets a known-plaintext attack recover the key.

25%

C = K ⋅ P mod 26; P = K⁻¹ ⋅ C mod 26; K usable only when gcd(det K, 26) = 1.

Block size

2 x 2

key matrix K

det K = (3×5 − 3×2) mod 26 = 9. Valid key K, since it is invertible.

K⁻¹ mod 26

Plaintext

First blocks, spelled out

P	as numbers	K ⋅ P mod 26	C
WE	[22, 4]	(3x22 + 3x4) mod 26 = 0 (2x22 + 5x4) mod 26 = 12	AM
HA	[7, 0]	(3x7 + 3x0) mod 26 = 21 (2x7 + 5x0) mod 26 = 14	VO
VE	[21, 4]	(3x21 + 3x4) mod 26 = 23 (2x21 + 5x4) mod 26 = 10	XK

Letters go in 2 at a time as a column vector. An odd tail is padded with X up to a multiple of 2.

ciphertext

AMVOX KKIXF MITUE ZAVVX MIYH

decrypted again with K⁻¹

WEHAV EAMOL EABOR TTHED EALX

Change one letter of the plaintext and watch 2 ciphertext letters move. That is Shannon’s diffusion. The larger the block, the wider it spreads.

Linearity is the weakness. Hill cipher resists statistical attacks, but it is a linear system, and each known plaintext block gives 2 equations, so 2 of them give the 4 you need to solve for K. A larger block helps only linearly, even though the keyspace grows exponentially.

step 1/4

CPE 645 / CS 685

Hill Cipher

Playfair Cipher

Vigenère Cipher