Hill Şifreleme

Klasik şifreleme sistemlerinin istatistiksel frekans analizine yenik düşmesini engellemek için tasarlanan Hill Şifrelemesi, kriptografiye Lineer Cebiri (Matrisleri) sokan ilk büyük devrimdir.

Bu sistemde harfler tek başına değil, belirlenen bir $n$ uzunluğundaki sütun vektörleri halinde gruplanarak bir matris ile çarpılır.

Sistemin Formal Tanımı

Hill sisteminde işlemler $n$ boyutlu vektörler ve $n\times n$ boyutlu kare matrisler üzerinden yürütülür. (Notlarımızda kolaylık olması adına $n=2$, yani $2\times 2$ matrisler kullanacağız).

Tanım: Hill Şifrelemesinin Matematiksel Modeli

• Açık Metin ($\mathcal{P}$): Elemanları ${\mathbb{Z}}_{26}$'dan alınan $n$ boyutlu sütun vektörlerinin kümesi.
• Şifreli Metin ($\mathcal{C}$): Elemanları ${\mathbb{Z}}_{26}$'dan alınan $n$ boyutlu sütun vektörlerinin kümesi.
• Anahtar Uzayı ($\mathcal{K}$): Elemanları ${\mathbb{Z}}_{26}$'da olan ve mod 26'ya göre tersi alınabilen (invertible) tüm $n\times n$ boyutlu kare matrisler.
• Şifreleme Fonksiyonu ($\mathcal{E}$): Her $K\in \mathcal{K}$ anahtar matrisi ve $\mathbf{x}\in \mathcal{P}$ açık metin vektörü için:$$e_K(\mathbf{x})\equiv K\cdot \mathbf{x}(\mathrm{mod}26)$$
• Deşifreleme Fonksiyonu ($\mathcal{D}$): Her $\mathbf{y}\in \mathcal{C}$ şifreli metin vektörü için:$$d_K(\mathbf{y})\equiv K^{-1}\cdot \mathbf{y}(\mathrm{mod}26)$$

⚠️ Anahtar Seçme Koşulu: Determinant ve Ters Matris

Afin şifrelemesinde anahtarın birebir olabilmesi için $a$ değerinin $26$ ile aralarında asal olmasını istemiştik. Hill şifrelemesinde ise matrisin tersinin olabilmesi ($K^{-1}$'in hesaplanabilmesi) şarttır.

Bir matrisin tersinin formülü şu şekildedir:

$$K^{-1}=\frac{1}{det(K)}\cdot \text{adj}(K)(\mathrm{mod}26)$$

Bu formülün mod 26'da çalışabilmesi için kesirli kısımdaki $det(K)$ değerinin mod 26'da çarpımsal bir tersi olması gerekir.

📌 Geçerli Bir Hill Anahtarı İçin Altın Kural

Bir $K$ matrisinin Hill şifrelemesinde anahtar olarak kullanılabilmesi için determinantının $26$ ile aralarında asal olması zorunludur:

$$gcd(det(K),26)=1$$

Pratik bir deyişle; matrisin determinantı mod 26'da çift sayı olamaz (2'ye bölünür) ve $13$ olamaz (13'e bölünür). Eğer determinant bu kurala uymuyorsa, sistem o şifreyi bir daha asla geri açamaz!

📌 Dolgu (Padding) Kuralı

Eğer şifreleyeceğiniz mesajın harf sayısı, vektör boyutu olan $n$'in tam katı değilse, mesajın sonuna anlamsız harfler (genellikle 'X' veya 'Z') eklenerek bloklar tamamlanır.

📝 Çözümlü Uygulamalar

Aşağıdaki örneklerde işlemleri Harf - Sayı Dönüşüm Tablosunu kullanarak yapınız. Vektör boyutumuz $n=2$'dir.

Örnek: Açık metni "HELP" olan mesajı, aşağıda verilen K matrisi ile şifreleyiniz.

Anahtar Matris:

$$K=\left(\begin{array}{cc}3& 3\\ 2& 5\end{array}\right)$$

💡 Çözümü Göster / Gizle

Çözüm: Öncelikle anahtarın geçerli olup olmadığını determinant ile kontrol edelim: $det(K)=(3\cdot 5)-(3\cdot 2)=15-6=9$$gcd(9,26)=1$ olduğu için bu kusursuz bir anahtardır.

Metnimiz "HELP", 2'li bloklara ayrılır: HE ve LP.

1. Blok: HE ($7,4$)

$$\left(\begin{array}{cc}3& 3\\ 2& 5\end{array}\right)\left(\begin{array}{c}7\\ 4\end{array}\right)=\left(\begin{array}{c}3(7)+3(4)\\ 2(7)+5(4)\end{array}\right)=\left(\begin{array}{c}21+12\\ 14+20\end{array}\right)=\left(\begin{array}{c}33\\ 34\end{array}\right)$$

Mod 26'ya göre denklerini alalım:

$$\left(\begin{array}{c}33\\ 34\end{array}\right)\equiv \left(\begin{array}{c}7\\ 8\end{array}\right)(\mathrm{mod}26)$$

Tabloya göre $7=$ H, $8=$ I. (İlk şifreli blok: HI)

2. Blok: LP ($11,15$)

$$\left(\begin{array}{cc}3& 3\\ 2& 5\end{array}\right)\left(\begin{array}{c}11\\ 15\end{array}\right)=\left(\begin{array}{c}33+45\\ 22+75\end{array}\right)=\left(\begin{array}{c}78\\ 97\end{array}\right)$$

Mod 26'ya göre denklerini alalım: $78=26\cdot 3+0\equiv 0(\mathrm{mod}26)$$97=26\cdot 3+19\equiv 19(\mathrm{mod}26)$

$$\left(\begin{array}{c}78\\ 97\end{array}\right)\equiv \left(\begin{array}{c}0\\ 19\end{array}\right)(\mathrm{mod}26)$$

Tabloya göre $0=$ A, $19=$ T. (İkinci şifreli blok: AT)

Sonuç: HELP kelimesi Hill şifrelemesiyle HIAT olarak şifrelenir. (Dikkat edin: Açık metindeki 'E' ve 'L' tamamen farklı harflere dönüşürken, aralarındaki istatistiksel bağ matrisin içinde eridi gitti!)

$⊠$

Örnek: Şifreli "HIAT" metnini, aynı K anahtar matrisini kullanarak deşifre ediniz.

Anahtar Matris:

$$K=\left(\begin{array}{cc}3& 3\\ 2& 5\end{array}\right)$$

💡 Çözümü Göster / Gizle

Çözüm: Deşifreleme için $d_K(\mathbf{y})\equiv K^{-1}\cdot \mathbf{y}(\mathrm{mod}26)$ formülünü kullanacağız. Önce $K^{-1}$ ters matrisini bulmalıyız.

Adım 1: Determinantın Tersini Bulmak$det(K)=9$ bulmuştuk. 9'un mod 26'daki çarpımsal tersini ($9^{-1}$) arıyoruz: $9\cdot x\equiv 1(\mathrm{mod}26)⟹x=3$ (Çünkü $9\cdot 3=27\equiv 1$).

Adım 2: Adjoint (Ek) Matrisi Bulmak$2\times 2$ bir $\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)$ matrisinin ek matrisi $\left(\begin{array}{cc}d& -b\\ -c& a\end{array}\right)$'dır.

$$\text{adj}(K)=\left(\begin{array}{cc}5& -3\\ -2& 3\end{array}\right)$$

Adım 3: Ters Matrisi ($K^{-1}$) Oluşturmak

$$K^{-1}\equiv 3\cdot \left(\begin{array}{cc}5& -3\\ -2& 3\end{array}\right)=\left(\begin{array}{cc}15& -9\\ -6& 9\end{array}\right)(\mathrm{mod}26)$$

Eksi değerleri mod 26'da pozitife çevirelim ($-9\equiv -9+26=17$, $-6\equiv -6+26=20$):

$$K^{-1}\equiv \left(\begin{array}{cc}15& 17\\ 20& 9\end{array}\right)(\mathrm{mod}26)$$

Adım 4: Şifreli Blokları Ters Matris İle Çarpmak

1. Blok: HI ($7,8$)

$$\left(\begin{array}{cc}15& 17\\ 20& 9\end{array}\right)\left(\begin{array}{c}7\\ 8\end{array}\right)=\left(\begin{array}{c}105+136\\ 140+72\end{array}\right)=\left(\begin{array}{c}241\\ 212\end{array}\right)$$

$241\equiv 7(\mathrm{mod}26)⟹$ H$212\equiv 4(\mathrm{mod}26)⟹$ E

2. Blok: AT ($0,19$)

$$\left(\begin{array}{cc}15& 17\\ 20& 9\end{array}\right)\left(\begin{array}{c}0\\ 19\end{array}\right)=\left(\begin{array}{c}0+323\\ 0+171\end{array}\right)=\left(\begin{array}{c}323\\ 171\end{array}\right)$$

$323\equiv 11(\mathrm{mod}26)⟹$ L$171\equiv 15(\mathrm{mod}26)⟹$ P

Sonuç: Matris çarpımları ve mod 26 kuralları bizi tekrar orijinal HELP mesajına ulaştırdı!

$⊠$