DES - Data Encryption Standard ve Feistel Ağı

DES, modern kriptografinin dönüm noktasıdır. 1970'lerde IBM tarafından "Lucifer" projesi adıyla geliştirilen ve 1977'de Amerikan Ulusal Standartlar Bürosu (NBS, günümüzdeki NIST) tarafından federal bir standart olarak kabul edilen simetrik (gizli) anahtarlı bir blok şifreleme algoritmasıdır.

Günümüzde 56 bitlik kısa anahtar boyutu nedeniyle kaba kuvvet (brute-force) saldırılarına karşı yetersiz kalıp yerini AES algoritmasına bırakmış olsa da, modern şifreleme mimarilerinin (Feistel Ağları, S-Box ve P-Box mantığı) temelini anlamak için DES'i öğrenmek bir kriptografi öğrencisi için zorunluluktur.

💻 Harflerden Bitlere Geçiş

Şu ana kadar gördüğümüz klasik şifrelemelerde (Sezar, Afin, Vigenère, Permütasyon) hep İngiliz alfabesi (${\mathbb{Z}}_{26}$) üzerinden karakterlerin veya sayıların yerini/kimliğini değiştirdik.

DES ile birlikte bu "insan odaklı" yapı tamamen terk edilir. Algoritma harflerin ne olduğunu bilmez; doğrudan bilgisayar işlemcisinin dilinde (0'lar ve 1'ler) çalışır. Açık metniniz (ister bir metin dosyası, ister bir fotoğraf, ister bir video olsun) önce makine diline çevrilir ve tamamen bit (binary) seviyesindeki işlemlerle (XOR, bit kaydırma, bit permütasyonları) şifrelenir.

🔑 Blok ve Anahtar Yapısı

DES algoritması veriyi bir bütün olarak değil, 64-bitlik bloklar halinde işler. Yani mesajınız ne kadar uzun olursa olsun, sistem bunu 64 bitlik parçalara böler ve her bir bloğu sırayla şifreler.

Algoritmanın kalbindeki anahtar yapısı ise kriptografi tarihindeki en ilginç tasarımlardan biridir:

• Girdi Anahtarı: DES algoritmasına dışarıdan verilen orijinal anahtar 64 bittir.
• Efektif (Gerçek) Anahtar Boyutu: Orijinal 64 bitlik anahtarın her 8. biti (8, 16, 24... 64) bir Eşlik Biti (Parity Bit) olarak hata kontrolü amacıyla kullanılır ve şifreleme işlemine dahil edilmez. Bu yüzden DES'in gerçek kriptografik gücü 56 bit ile sınırlıdır.

DES Anahtar Üretim Algoritması (Key Schedule)

DES algoritması, her biri 64 bitlik veri bloklarını şifrelemek için tam 16 döngü (round) kullanır. Şifrelemenin güvenli olabilmesi için bu 16 döngünün her birine, orijinal anahtardan türetilmiş farklı ve benzersiz 48 bitlik alt anahtarlar ($K_1,K_2,\dots ,K_{16}$) verilmesi gerekir.

İşte 64 bitlik tek bir kök anahtardan, 16 farklı mermi (alt anahtar) üreten bu fabrikaya Key Schedule (Anahtar Zamanlaması) denir. İşlem 3 temel aşamada gerçekleşir:

Adım 1: PC-1 (Eşlik Bitlerini Çöpe Atma ve İkiye Bölme)

$$K=b_1,b_2,b_3,\dots ,b_{63},b_{64}$$

Sisteme giren orijinal kök anahtar ($K$), 64 bitten oluşur. Ancak algoritma bu anahtarın her 8. bitini (8, 16, 24, 32, 40, 48, 56, 64) bir iletişim kontrolü olan Eşlik Biti (Parity Bit) olarak görür.

57	49	41	33	25	17	9
1	58	50	42	34	26	18
10	2	59	51	43	35	27
19	11	3	60	52	44	36
63	55	47	39	31	23	15
7	62	54	46	38	30	22
14	6	61	53	45	37	29
21	13	5	28	20	12	4

Anahtar dizisi PC-1 (Permuted Choice 1) matrisinden geçirilir. Bu matrisin içinde eşlik bitlerinin indeksleri bulunmaz; bu sayede 8 adet eşlik biti otomatik olarak çöpe atılır.

Tablonun Uygulanma Mantığı: Bu işlemi, önceki konularda işlediğimiz Ayrık Permütasyon Fonksiyonu ($\pi$) mantığıyla düşünmeliyiz. Orijinal 64-bitlik anahtar dizimizin bitlerini $b$, oluşacak yeni 56-bitlik dizinin bitlerini $b^{\prime }$ olarak tanımlayalım. PC-1 tablosu aslında bizim $\pi$ permütasyon anahtarımızdır ve bitlerin konum indeksleri ($\tau$) üzerinde çalışır.

Matematiksel olarak bu permütasyon işlemi şu şekilde ifade edilir:

$$b_{\tau }^{\prime }=b_{\pi (\tau )},\tau \in \{1,2,\dots ,56\}$$

Örneğin tablonun ilk elemanlarına göre:

• $$\pi (1)=57⟹k_1^{\prime }=k_{57}$$
• $$\pi (2)=49⟹k_2^{\prime }=k_{49}$$
• $$\dots$$

Elde edilen bu 56 bit, matrisin üst yarısı ($C_0$) ve alt yarısı ($D_0$) olacak şekilde doğrudan karıştırılarak ikiye bölünür.

Matematiksel olarak bu ayrışma şöyledir:

$$\begin{array}{rl}{K}_{64}& \stackrel{\pi \text{ permütasyonu uygulanır}}{\to }{K}_{56}\end{array}$$

Sonra bu 56 bitlik yeni anahtar ($K_{56}$) ortadan ikiye bölünür:

$$\begin{array}{rl}{K}_{56}& =\underset{C_0\text{ (Sol Yarı - 28 bit)}}{\underbrace{b_{57},b_{49},\dots ,b_{36}}}\underset{D_0\text{ (Sağ Yarı - 28 bit)}}{\underbrace{b_{63},b_{55},\dots ,b_4}}\end{array}$$

Adım 2: Dairesel Sola Kaydırma (Circular Left Shift)

Algoritma 16 döngü boyunca $C$ ve $D$ yarılarını kendi içlerinde sola doğru kaydırarak sürekli günceller. "Dairesel" olmasının esprisi şudur: Sınırın dışına çıkan bit silinmez, bloğun en sağına geri döner.

🔍 Görsel Örnek (1-bit Kaydırma): 8-bitlik örnek bir $X$ bloğumuz olsun: $\mathbf{1}0110011$ 1 bit sola kaydırıldığında, en soldaki $\mathbf{1}$ kopar ve en sağa kuyruk olur: Yeni $X$: $0110011\mathbf{1}$

Kaydırma miktarı döngünün numarasına göre sabittir:

• 1., 2., 9. ve 16. Döngülerde: Sadece 1 bit dairesel kaydırılır.
• Diğer tüm döngülerde: 2 bit dairesel kaydırılır.

Örneğin 1. ve 2. döngüler için yeni yarılar şu şekilde oluşur:$C_1=LeftShift(C_0,1)\text{ve}{D}_1=LeftShift(D_0,1)$$C_2=LeftShift(C_1,1)\text{ve}{D}_2=LeftShift(D_1,1)$

Adım 3: PC-2 (Sıkıştırma Permütasyonu)

Döngüye ait kaydırılmış $C_i$ ve $D_i$ yarıları yan yana getirilerek birleştirilir ($28+28=56\text{ bit}$). Ancak şifreleme çekirdeğimiz (Feistel fonksiyonu), her döngüde 48 bitlik bir anahtara ihtiyaç duymaktadır.

Bu noktada PC-2 (Permuted Choice 2) tablosu devreye girer. Bu tablo tıpkı bir filtre gibi davranarak; 56 bitlik diziyi karıştırır ve içinden önceden belirlenmiş 8 biti atarak (sıkıştırarak) o döngünün asıl silahı olan 48 bitlik $K_i$ alt anahtarını üretir.

PC-2 Matrisi (48-bit Seçim):

14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10, 23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2, 41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48, 44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32

Matematiksel dönüşümün jilet gibi özeti:

$$\begin{array}{rl}\underset{28\text{-bit}}{\underbrace{C_i}}||\underset{28\text{-bit}}{\underbrace{D_i}}& \stackrel{\text{Birleştirilir}}{\to }C{D}_i(56\text{-bit})\\ C{D}_i(56\text{-bit})& \stackrel{\text{PC-2 Filtresi}}{\to }{\mathbf{K}}_{\mathbf{i}}\mathbf{(}\mathbf{48}\text{-bit Alt Anahtar}\mathbf{)}\end{array}$$

Bu 3 adım, 16 döngünün tamamı için zincirleme olarak tekrarlanır ve şifreleme işleminde kullanılacak olan o meşhur 16 anahtar seti hazır hale getirilmiş olur.