Herkese merhaba, bugün sizlere günümüz internet dünyasında çokça kullanılan bir şifreleme algoritmasından bahsedeceğim. Lisans dönemimin son yılında “Data Communication” dersinin projesi kapsamında proje arkadaşım Ahmet Doruk Başkan ile beraber “Advanced Encryption Standard” algoritmasını Python ile gerçeklemiş ve bir haberleşme kanalında test etmiştik. İki yazılık bu seride, algoritmanın her adımında neler yapıldığından detaylı olarak bahsettikten sonra Python dili ve Sublime Text arayüzü kullanılarak bu algoritmanın nasıl gerçekleneceğini anlatacağım. Son olarak da projede geliştirdiğimiz bir yöntem vasıtasıyla mesajların bu algoritma ile nasıl şifreleneceğini adım adım açıklayacağım. Bu yazımda şifreleme algoritmasının matematiksel detaylarını anlatacağım. İkinci yazımda da Python gerçeklemesini göstereceğim. Tabi bir şifreleme işleminin anlamlı olması için onun geri çözülebilmesi gerekiyor, ancak bu işlem şifreleme tarafını anladıktan sonra oldukça kolay olduğu için çözme algoritmasını sadece ikinci yazımda gerçekleme olarak anlatacağım. Gelin kısaca bu algoritma neymiş onu öğrenelim.

1. AES NEDİR ?

Rijndael algoritması olarak da bilinen bu algoritma Ocak 1997’de Amerika Birleşik Devletleri Milli Standartlar ve Teknoloji Enstitüsü (NIST)’nün bir şifreleme algoritması oluşturulması için başlattığı yarışma sırasında ortaya çıkmıştır. NIST’in 09 Ağustos 1999 tarihli internet haberinde bu yarışma şu şekilde tanımlanmaktadır:

You can think of it as the Olympics of information scrambling.

Türkçe’ye çevirecek olursak, “Bu yarışmayı veri şifreleme olimpiyatları olarak düşünebilirsiniz.” denmektedir. Bu yarışma sonunda ortaya çıkacak olan algoritma ile 21. yüzyılın sanal ticaret ve veri haberleşmesinin çok daha güvenilir hale getirilmesi amaçlanmıştır. Şifreleme algoritmalarının elektronik e-postalardan gizli kişisel bilgilere, ATM’lerden gizli devlet bilgilerine kadar birçok yerde kullanıldığı göz önünde bulundurulduğunda bu yarışmanın önemi biraz daha iyi anlaşılabilir.  Ağustos 1998’de 12 farklı ülkeden 15 adet aday seçilmiştir. Bu 15 farklı algoritma üzerine uzmanlar çeşitli saldırılar düzenleyerek bu algoritmaların zayıf yönlerini ve eksikliklerini test etmişlerdir. Ağustos 1999’da da 5 finalist belirlenmiştir. Bu finalistlerden birisi olan Rijndael (ismini geliştiricileri Vincent Rijmen ve Joan Daemen’den almıştır) 128, 192 ve 256 bit bloklar olmak üzere üç farklı gereksinimi sağlaması, yazılımsal ve donanımsal olarak kolayca gerçeklenebilir olması ve hızlıca şifreleme & çözme işlemlerini gerçekleştirebilir olması açısından 2000 yılında AES olarak belirlenmiştir. Böylece AES, DES (Data Encryption Standard)’in yerini alarak kullanıma başlamıştır.

2. ALGORİTMA

128-bit Rijndael algoritmasını incelemeye başlamadan önce çok kısa olarak Galois Field kavramından bahsetmem gerekiyor. İsmini Evariste Galois’den alan bu kavram sonlu sayıda eleman barındıran matematiksel bir alanı ifade eder. Bu alanda 0 ve 1 bitleri polinomların kat sayılarını oluşturmaktadır ve bu alanda bir çarpım yine bir polinom meydana getirir. Örnek verilecek olursa, Rijndael algoritmasında 8-bitlik polinomlar kullanılır ve GF(2⁸) olarak gösterilir. Bu durumda (a₁a₂a₃a₄a₅a₆a₇a₈) veri dizisi GF(2⁸)‘de şu şekilde ifade edilebilir:

a₁x⁷ + a₂x⁶ + a₃x⁵ + a₄x⁴ + a₅x³ + a₆x² + a₇x + a₈

Galois Field kullanımı ileride daha aydınlatıcı olacaktır. Şimdilik bu kadar bilgi bizim için yeterlidir. Öncelikle algoritmanın genel yapısına bakalım. İnternette bunun üzerine birçok kaynak bulabilirsiniz. Ancak neredeyse hepsinde, algoritma yüz üstü geçilmiş ve yazılıma dökülmesi için gereken bazı detaylar işlenmemiştir. Ben önemli noktaları tek tek açıklayarak işinizi kolaylaştırmaya çalışacağım.

Yukarıdaki algoritma şemasını incelediğimizde adımları açıkça görebiliriz. Burada Input Matrix bizim şifrelemek istediğimiz veridir. Örnek bir Input Matrix solda verilmiştir. Cipher Matrix de şifrelemede kullanılacak olan bir şifre matrisidir. Cipher Matrix (Cipher Key) örneği de sağda verilmiştir. Round Key ise her turda elde edilen yeni şifredir. İlk olarak veriyi şifreyle ikili sistemde topladıktan sonra dokuz tur SubBytes, ShiftRows, MixColumns ve AddRoundKey işlemlerinden geçiriyoruz. Burada dokuz turun ilkinde Round Key matrisini, Cipher Key kullanarak elde ettikten sonra her turun Round Key matrisini bir önceki turun Round Key matrisi yardımıyla buluyoruz. Onuncu turda MixColumns işlemi uygulanmaz. İsterseniz sırasıyla bu işlemlerin ne olduğunu inceleyelim.

2.1 SubBytes

Yazı boyunca yukarıda paylaştığım kaynaktaki örnek üzerinden uygulamalı ilerleyeceğimiz için  her işlem sonucunda çıkanları iyice takip etmemiz gerekiyor. Yukarıda da bahsettiğim gibi SubBytes uygulanmadan önce veri matrisi ile şifre matrisini ikili sistemde topluyoruz. İkili sistemde toplamanın XOR işlemine karşı geldiğini unutmayalım. Bu toplama işlemi sonucunda soldaki matrisi elde ediyoruz. Şimdi SubBytes işlemine geçebiliriz. Bu işlem oldukça kolaydır. Yapmamız gereken tek şey SubBytes uygulamak istediğimiz matristeki her elemanı S-Box dediğimiz bir tablonun ilgili elemanı ile değiştirmektir. Öncelikle S-Box tablosunu paylaşayım:

SubBytes uygulamak istediğimiz matristeki bir elemanı tablodaki karşılığıyla değiştirmek için o elemanın indislerine ayrı ayrı bakıyoruz. Birinci indis tablodaki sırayı ifade ederken, ikinci indis de sütunu ifade eder. Örneğin veri matrisi ile şifre matrisinin toplanması sonu elde edilen matrisi inceleyelim. Bu matrisin ilk elemanı olan 19′S-Box matrisinin 1 satırı ve 9 sütunundaki eleman ile değiştireceğiz ve sonuç olarak d4 elde etmiş olacağız. Bu şekilde tüm elemanlarda değişiklik yaptığımızda sağda verilen matrisi elde edeceğiz.

2.2 ShiftRows

Bu işlem de SubBytes gibi oldukça basit bir yapıya sahiptir. ShiftRows uygulamak istediğimiz matrisin birinci satırını değiştirmiyor iken ikinci satırını bir birim sola, üçüncü satırını iki birim sola ve dördüncü satırını da üç birim sola kaydırıyoruz. Örnekten devam edecek olursak birinci satır aynen

→ d4 e0 b8 1e

olarak kalırken ikinci satırı bir birim sola kaydırarak

→ bf b4 41 27

olarak değiştiriyoruz. Üçüncü satırı

→ 5d 52 11 98

olarak değiştiriyoruz ve son satırı da

→ 30 ae f1 e5

olarak değiştiriyoruz. Sonuçta elde ettiğimiz matris sağda verilmiştir.

2.3 MixColumns

Bu işlem diğerlerine göre biraz daha karışık gelebilir. Burada Galois Field kullanarak çarpma işlemi gerçekleştireceğiz. İnternette araştırırsanız bu aşamada kullanılan çarpma işlemleri çok açıklayıcı olarak verilmemiştir. Birçok yerde sadece Galois Field çarpma işlemi kullanıldığı ve hangi çarpma işleminin yapılacağı söylenir. Nasıl yapılacağı ile ilgili bilgi bulmakta zorlanabilirsiniz. Galois Field’da çarpma işlemlerinin detaylarını inceleyerek bu işlemi yapmaya çalışırsanız da bir sonuca varamayabilirsiniz zira oldukça karmaşık hesaplamalar meydana geliyor. Ancak Doruk ile uzun araştırmalarımız sonucunda bu noktada açıklayıcı anlatım veren bir kaynak bulduk ve kendimiz de bir takım çıkarımlar yaparak bu işlemde tam olarak ne yapmamız gerektiğini nihayet elde ettik..

Burada isimden de anlayabileceğimiz üzere sütunlar üzerinden işlem yapacağız. MixColumns uygulamak istediğimiz matrisin her sütununu MixColumns matrisi ile çarpacağız ve sonuçta elde ettiğimiz sütun matrisi ile değiştireceğiz. MixColumns matrisi:

şeklindedir. ShiftRows sonunda elde ettiğimiz matrise MixColumns işlemi uygulayacak olursak, ilk sütun için:

çarpma işleminin sonucunda (4 x 4) x (4 x 1) = (4 x 1) boyutlu sütun matrisi elde edeceğiz ve ilk sütunun yerine yazacağız. Burada vektörel çarpımın gereği olarak ilk eleman olan s0′ı bulmak için:

→ {02} x {d4} + {03} x {bf} + {01} x {5d} + {01} x {30} = s0

işlemini yapacağız ve benzer şekilde s1, s2 ve s3 elemanlarını da bulacağız. Buraya kadar her şey oldukça kolay, ancak hexadecimal sayıların çarpımı birazcık karışık gelebilir. Örneğin {02} x {d4} işlemine bir göz atalım. Bu işlemi adım adım çözeceğiz:

  1. Sütun matristen aldığımız hexadecimal sayıyı ikili (binary) formata getiriyoruz:

→ {d4} = {1101 0100}

   2. Elde ettiğimiz ikili sayıyı 1 birim sola kaydırıyoruz. Ancak buradaki kaydırma işleminde ShiftRows için kaydırma işlemlerinden farklı olarak en soldaki eleman sağa gelmiyor, onun yerine en sağa 0 ekleniyor. Bu işlem ingilizcede left-shift olarak bilinir ve << ile gösterilir. İlk adımda elde ettiğimiz ikili formattaki sayıyı bir birim sola kaydırırarak aşağıdaki sayıyı elde ediyoruz:

→ {1101 0100} << 1 = {1010 1000}

   3. Bu adımın sonucu ilk adımda elde ettiğimiz ikili formattaki sayının en solundaki basamağına bağlı olarak değişir. Şöyle ki, eğer bu basamak 1 ise 2. adımda elde ettiğimiz ikili sayıyı {0001 1011} ile toplayarak çarpma işlemini tamamlamış oluruz. Eğer 0 ise 2. adımda elde ettiğimiz ikili sayı direkt olarak çarpma işleminin sonucudur. Bizim örneğimizde 1. adımda elde ettiğimiz sayının en sol basamağı 1’dir, bu yüzden:

→ {1010 1000} XOR {0001 1011} = {1011 0011} = b3

sonucunu elde etmiş oluruz. Böylece {02} ile çarpma işlemini öğrenmiş olduk. Şimdi {03} x {bf} işlemine bir göz atalım. Burada aslında {02} ile çarpma işleminden faydalanacağımız için yeni bir işlem yapmayacağız diyebiliriz. Yine adım adım gidecek olursak:

  1. {03} hexadecimal sayısını {02} ve {01}’in toplamı cinsinden yazdığımızda işimiz az önceki çarpmaya benzeyecektir.

→ {03} = {11} = {10} XOR {01} = {02} XOR {01}

      2. Bu durumda çarpma işlemimiz aşağıdaki hale dönüşecektir:

→ {03} x {bf} = ({02} XOR {01}) x {bf} = ({02} x {bf}) XOR ({01} x {bf})

      3. Bu adımda {02} x {bf} işlemini yukarıda anlattığımız gibi yaparsak:

→ {bf} = {1011 1111}

→ {1011 1111} << 1 = {0111 1110}

→ {0111 1110} XOR {0001 1011} = {0110 0101}

sonucunu elde ederiz.

      4. Son adımda da {01} x {bf} işlemini yapmamız gerekiyor ki bu bize {bf}’nin kendisini verir:

→ {01} x {bf} = {bf} = {1011 1111}

Bu durumda sonucu:

→ {0110 0101} XOR {1011 1111} = {1101 1010} = {da}

olarak elde ediyoruz. Geriye kalan iki çarpma işlemimiz de 1 ile çarpma olduğu için sonuçları sayıların kendilerini verir. Elde edilecek sütunun ilk elemanı olan s0′ı bulmak için geriye kalan son şey ise az önce yaptığımız çarpma işlemlerinin sonuçlarını toplamaktır:

→ s0 = b3 + da + 5d + 30

Toplamayı yapabilmek için tüm hexadecimal sayıları ikili formata çeviriyoruz ve sonrasında XOR işleminden geçiriyoruz. Böylece s0′ı aşağıdaki gibi elde ediyoruz:

→ s0 = {1011 0011} XOR {1101 1010} XOR {0101 1101} XOR {0011 0000} = {0000 0100} = {04}

s1s2 ve s3 de aynı şekilde bularak birinci sütunu tamamen elde edebiliriz. Bu çarpım işlemini tüm sütunlara uyguladığımızda da MixColumns çıkışı olarak solda verilen matrisi elde ediyoruz.

2.4 AddRoundKey

Geldik bu şifreleme yöntemini gerçek anlamda kırmayı zorlaştıran işleme. AddRoundKey, aslında sadece iki matrisin toplanmasından ibarettir. İlk tur başlamadan veri matrisi ile şifre matrisinin toplanması, sonrasındaki dokuz tur boyunca her tur MixColumns çıkışındaki matris ile o turda elde edilen yeni şifre matrisinin toplanması ve son olarak da onuncu turda ShiftRows çıkışındaki matris ile onuncu turda elde edilen şifre matrisinin toplanması birer  AddRoundKey işlemleridir. Bunu özel kılansa, her turda yeni bir şifre matrisinin bir önceki tura göre belirlenmesidir. Her turda yeni şifrenin nasıl oluşturulduğuna geçmeden önce, AddRoundKey işlemini ilk tur öncesindeki toplama işlemi üzerinden anlayabiliriz:

İlk turun şifre matrisinin Cipher Key’e göre ve diğer her turun şifre matrisinin bir önceki tura göre belirlenmesi işlemine Key Schedule denmektedir. O zaman hemen nasıl çalıştığını öğrenelim.

Key Schedule

Her şifre oluşturma sırasında Rcon matrisi olarak isimlendirilen bir matrisi kullanacağız:

Yine her sütun için ayrı ayrı çalışacağız. Örneğimizden devam edecek olursak, öncelikle Cipher Key ile ilk turda kullanacağımız şifre matrisini (Round Keyelde edeceğiz. Bunun için 3 adım izleyeceğiz:

A. RotWords

Bu adımda Cipher Key matrisinin son sütununu bir birim yukarı kaydırıyoruz. Böylece, ShiftRows işlemine benzer bir biçimde en üstteki sayıyı en alta almış oluyoruz:

B. SubBytes

(2.1) bölümünde anlattığım SubBytes işleminin tamamen aynısıdır. RotWords uyguladığımız sütun matrisinin elemanlarını (2.1)’de paylaştığım S-Box tablosundan ilgili elemanlar ile değiştiriyoruz:

C. XOR

Son olarak da Cipher Key matrisinin birinci sütununu, B’nin sonucunda elde ettiğimiz sütun matrisini ve Rcon matrisinin birinci sütununu topluyoruz ve yeni Round Key matrisinin ilk sütununu elde etmiş oluyoruz:

Diğer üç sütunun elde edilmesi, ilk sütuna göre oldukça kolaydır. İkinci sütunu bulmak için az önce elde ettiğimiz ilk sütun ile Cipher Key matrisinin ikinci sütununu topluyoruz:

Üçüncü sütunu elde etmek için ikinci sütun ile Cipher Key matrisinin üçüncü sütununu topluyoruz:

Son olarak da dördüncü sütunu elde etmek için üçüncü sütun ile Cipher Key matrisinin dördüncü sütununu topluyoruz:

Böylece ilk turda AddRoundKey işleminde kullanılacak olan Round Key matrisini aşağıdaki gibi elde etmiş olduk:

Bu şekilde her turda bir önceki turun Round Key matrisini kullanarak yeni Round Key matrisini elde edeceğiz ve o turun AddRoundKey işleminde kullanacağız. Burada dikkat edilmesi gereken nokta, her turda Round Key matrisinin birinci sütunlarını bulurken Rcon matrisinin o tura ilişkin sütun matrisini kullanmalıyız. Daha açıklayıcı olmak gerekirse, birinci turda kullanılacak olan Round Key matrisini, Cipher Key matrisini kullanarak bulmak için yukarıda Rcon matrisinin birinci sütununu kullandık. İkinci turda kullanılacak olan Round Key matrisini, birinci turda kullanılan Round Key matrisinden bulmak için de Rcon matrisinin ikinci sütununu kullanacağız. Bu süreç her turda benzer biçimde ilerleyecektir. Böylece Key Schedule ile beraber algoritmanın tüm aşamalarını ve serimin de ilk yazısını tamamlamış oldum. Algoritmanın yazılımsal olarak gerçekleneceği yazımda tekrar görüşmek dileğiyle, teknolojiyle kalın 🙂

RSS
LinkedIn
Share
Instagram
Twitter
Visit Us
Follow Me