Hill Cipher là mật mã khối đa bảng (polyalphabetic block cipher) do Lester S. Hill phát minh năm 1929. Nó sử dụng phép nhân ma trận modulo 26 để mã hóa: mỗi khối m ký tự plaintext P thành ciphertext C theo công thức C = K·P mod 26, trong đó K là ma trận khóa vuông m×m khả nghịch.
Cơ chế tấn công Known-Plaintext
Giả sử kẻ tấn công có m cặp plaintext-ciphertext tương ứng (Pᵢ, Cᵢ) với i = 1..m. Ghép các vector cột thành ma trận:
C = [C₁ C₂ … Cₘ], P = [P₁ P₂ … Pₘ]
Khi đó: C = K·P (mod 26) ⇒ K = C·P⁻¹ (mod 26)
Nếu ma trận P khả nghịch modulo 26 (định thức nguyên tố cùng nhau với 26), kẻ tấn công tính nghịch đảo P⁻¹ và suy ra khóa K chỉ với O(m³) phép toán — cực nhanh.
Tại sao Hill Cipher bị động?
- Tuyến tính: Phép mã hóa là ánh xạ tuyến tính trên ℤ₂₆. Mọi sự kết hợp tuyến tính của plaintext phản ánh trực tiếp lên ciphertext.
- Không có sự khuếch tán (diffusion) mạnh: Mỗi ký tự ciphertext chỉ phụ thuộc tuyến tính vào m ký tự plaintext trong cùng khối.
- Không có sự gây nhiễu loạn (confusion): Khóa xuất hiện trực tiếp trong phương trình tuyến tính.
Mở rộng: Chosen-Plaintext Attack
Nếu kẻ tấn công có thể chọn plaintext, họ chỉ cần chọn m vector đơn vị (cột của ma trận đơn vị) để trực tiếp thu được các cột của ma trận khóa K — không cần nghịch đảo ma trận.
Bài học
Hill Cipher minh họa rõ ràng nguyên tắc của Shannon: mật mã an toàn cần cả confusion (thay thế phi tuyến) và diffusion (hoán vị/khối lớn). Các mật mã khối hiện đại (AES, DES) dùng S-box phi tuyến, nhiều vòng lặp, và key schedule phức tạp để chống lại tấn công này.