THE CIPHER LIBRARY · BERKAS PENYELIDIKAN 026

HillCipher.

Sebuah misteri di antara rak buku. Pecahkan sandi, ikuti jejak matriks, dan ungkap pesan rahasia dengan aljabar linear.

ANALISIS MATRIKS · MODULO 26 · THE DETECTIVE FILES
01 / THE FIELD NOTES

Catatan Teori

Kenali prinsip sandi Hill, aritmetika modulo, determinan, invers matriks, serta jejak sejarah dan kelemahan kriptografinya.

1. Gagasan dan Sejarah

Hill Cipher diperkenalkan matematikawan Lester S. Hill pada 1929. Ia adalah sandi substitusi poligrafik pertama yang praktis: bukan satu huruf, melainkan blok n huruf sekaligus dienkripsi lewat perkalian matriks. Setiap huruf hasil bergantung pada seluruh huruf dalam blok (difusi), sehingga analisis frekuensi huruf tunggal tidak lagi efektif.

2. Aritmetika Modular

a ≡ b (mod n) berarti n | (a − b). Alfabet dipetakan A=0, B=1, …, Z=25 sehingga semua hitungan berlangsung di ℤ₂₆. Sebuah bilangan a memiliki invers perkalian a⁻¹ bila dan hanya bila gcd(a, 26) = 1. Banyaknya adalah φ(26) = 12: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25 (lingkaran emas di bawah). Invers dicari dengan algoritma Euclid yang diperluas, atau dengan mencoba a·x ≡ 1.

3. Definisi Sandi

Kunci adalah matriks persegi K berukuran n×n dengan entri di ℤ₂₆. Plainteks dipecah menjadi blok vektor kolom P (huruf kurang diisi, misalnya X).

Enkripsi: C ≡ K·P (mod 26)    Dekripsi: P ≡ K⁻¹·C (mod 26)

4. Syarat Kunci yang Sah

Dekripsi mensyaratkan K punya invers mod 26, yaitu gcd(det K, 26) = 1. Karena 26 = 2·13, ini setara dengan: det K mod 26 ganjil dan bukan kelipatan 13. Bila tidak, dua plainteks berbeda dapat menghasilkan sandi yang sama sehingga pesan tak dapat dipulihkan secara unik.

5. Invers Matriks Modulo 26

Dari aljabar linear, K⁻¹ = (det K)⁻¹ · adj(K), dengan adj(K) transpos matriks kofaktor. Pada ℤ₂₆, pembagi 1/det diganti invers modular. Untuk n = 2:

6. Kunci 3×3: Determinan, Kofaktor, dan Invers

Untuk n = 3, satu blok berisi tiga huruf dan K berukuran 3×3. Determinannya diperoleh dengan ekspansi kofaktor sepanjang baris pertama:

K =
abc
def
ghj
,   det K = a(ej − fh) − b(dj − fg) + c(dh − eg)

Minor Mij adalah determinan 2×2 setelah baris i dan kolom j dihapus; kofaktornya Cij = (−1)i+jMij. Adjoin adalah transpos matriks kofaktor, dan K⁻¹ ≡ (det K)⁻¹ · adj K (mod 26). Klik sebuah entri untuk melihat minor dan kofaktornya (baris dan kolom redup dihapus):

7. Alur Visual Enkripsi

Contoh “HELP” dengan K = [[3,3],[2,5]]:

8. Kriptanalisis dan Keamanan

Ruang kunci. Untuk n = 2 terdapat |GL₂(ℤ₂₆)| = 6 · 26.208 = 157.248 matriks invertibel (hasil kali jumlah di ℤ₂ dan ℤ₁₃ lewat Teorema Sisa Cina), kecil untuk ukuran modern.

Serangan known-plaintext. Bila penyerang memiliki n pasang blok (plainteks P dan sandi C) dengan P invertibel mod 26, maka K ≡ C·P⁻¹ (mod 26). Inilah kelemahan fatal: sandi ini linear. Karena itu Hill Cipher dipelajari terutama sebagai contoh pemakaian aljabar linear dan sebagai pengantar difusi, bukan untuk pengamanan nyata.

Sifat penting. (i) Perubahan satu huruf mengubah seluruh blok (difusi lokal), tetapi tidak blok lain; (ii) blok identik menghasilkan sandi identik (seperti mode ECB); (iii) vektor nol selalu terpetakan ke nol.

Rujukan: Stallings, Cryptography and Network Security (bab sandi klasik); Paterson & Stinson, Cryptography: Theory and Practice (bab pengantar kriptografi); Larson, Elementary Linear Algebra, dan Spence–Insel–Friedberg (determinan, adjoin, invers matriks).