AES ve Rijndeal Şifreleme

Yazan: Mustafa Gökmen

Modern kriptoloji genel olarak ikiye ayrılmaktadır, simetrik ve asimetrik kriptoloji. Asimetrik şifreleme açık anahtar ilkesine dayanmaktadır. Gizlenmek istenen metin herkesin bildiği bir anahtar ile şifrelenir ve ancak gizli anahtarla çözülebilir. Simetrik algoritmalarda ise tek bir gizli anahtar bulunur; şifreleme ve şifre çözme için bu anahtara ihtiyaç duyulur. Simetrik şifreleme, blok şifreleme ve dizi şifreleme olmak üzere iki ana başlığa ayrılabilir. Bu çalışma kapsamında bir blok şifreleme türü olan Gelişmiş Şifreleme Standardı (Advanced Encryption Standard – AES) kullanılmıştır.

AES Şifreleme Algoritması

Ocak 1997’de NIST, yeni bir şifreleme standardının geliştirilmesi için bir çalışma başlatmıştır. Geliştirilecek yeni şifreleme standardının mevcut standart olan DES’in yerini alması düşünülmüştür. Çünkü DES’in 64 bitlik anahtar uzayı, gelişen teknoloji ve artan işlemci hızları karşısında güvenirliğini yitirmeye başlamıştı.

NIST tarafından, yeni şifreleme standardını belirlemek amacıyla bir yarışma düzenlenmiş ve Eylül 1997’de algoritmalar için resmi çağrıda bulunulmuştur. Ağustos 1998’de 15 aday algoritmanın (1.Tur) değerlendirilmeye alındığı duyurulmuş ve Nisan 1999’da gerçekleşen 2. Tur seçimlerinde algoritma sayısı 5’e indirilmiştir. Seçilen bu 5 finalist aşağıda sıralanmıştır.

IBM’in geliştirdiği MARS (Multiplication, Addition, Rotation and Substitution),

Ronald Riverst’in geliştirdiği RC6,

Belçikalı takım tarafından geliştirilen Rijndael,

İngiltere, İsrail ve Norveç’ten üyeleri olan bir takımın ortak olarak geliştirdiği Serpent,

Bruce Schneier tarafından geliştirilen Twofish.

Dört yıl boyunca süren değerlendirme ve eleme süreci sonrasında, Ekim 2000’de sonuç açıklanmış ve NIST, Joan Daemen ve Vincent Rijmen tarafından tasarlanan, Rijndael algoritmasının Gelişmiş Şifreleme Standardı (AES) olarak kullanılacağını ilan etmiştir.

Algoritmanın Genel Yapısı

AES algoritmasında giriş, çıkış ve matrisler 128 bitliktir. Matris 4 satır, 4 sütun (4×4), 16 bölmeden oluşur. Bu matrise ‘durum’ denmektedir. Durumun her bölmesine bir baytlık veri düşer. Her satırda 32 bitlik bir kelimeyi meydana getirir.

AES algoritması, 128 bit veri bloklarını 128, 192 veya 256 bit anahtar seçenekleri ile şifreleyen bir blok şifre algoritmasıdır. Anahtar uzunluğu bit sayıları arasındaki farklılık AES tur döngülerinin sayısını değiştirmektedir.

Tablo 1: Tur Sayısının Anahtar Uzunluğuna Göre Değişimi

		Kelime Uzunluğu	Tur Sayısı
AES-128		4	10
AES-192		6	12
AES-256		8	14

Bu çalışmada anahtar uzunluğu 128 bit olduğundan 10 turluk işlem gerekmektedir. Aşağıdaki şekilde algoritmanın genel yapısı 10 tur ile birlikte gösterilmiştir.

Şekil 1: AES Algoritması Genel Görünüm

Her bir turda 4 farklı alt işlem gerçekleştirilir. Bunlar sırası ile bayt değiştirme, satır kaydırma, sütun karıştırma ve tur anahtarı ile toplamadır. 10 tur sonrasında giren veri şifrelenmiş olarak dışarı çıkmaktadır. İlk tura anahtar ilk haliyle katılmakta diğer turlarda yeni üretilen anahtarlar sokulmaktadır.

Şifreli Metinin Oluşumu

Girişten gelen metin 128 bitlik parçalara bölünür. Her parça durum matrisine yerleştirilir. Durum matrisi oluşturulduktan sonra, artık üzerinde tüm işlemler yapılabilir duruma gelmiş demektir. Aynı şekilde önceden alınan 128 bitlik anahtarda bu durum matrisi halinde işlem görür. Giriş metninin yazıldığı durum matrisi ilk olarak anahtar ile toplanır.

Şekil 2: Girişin Alındığı 4×4’lük Durum Matrisi

Ardından algoritmanın temeli sayılabilecek bir tur işlemine tabi tutulur. Bu tur işleminin içeriği sıradaki başlıklarda detaylı anlatılmıştır.

Bayt Değiştirme

İlk işlem algoritmanın tek doğrusal olmayan işlemi olan bayt değiştirmedir. Durum matrisinin her elemanı, değerleri önceden hesaplanarak oluşturulmuş S-kutusundaki değerlerle değiştirilir.

Şekil 3: S-Kutusundaki Değer ile Bayt Değişimi

Tablo 2: S-Kutusu Değerleri

	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	63	7C	77	7B	F2	6B	6F	C5	30	01	67	2B	FE	D7	AB	76
1	CA	82	C9	7D	FA	59	47	F0	AD	D4	A2	AF	9C	A4	72	C0
2	B7	FD	93	26	36	3F	F7	CC	34	A5	E5	F1	71	D8	31	15
3	04	C7	23	C3	18	96	05	9A	07	12	80	E2	EB	27	B2	75
4	09	83	2C	1A	1B	6E	5A	A0	52	3B	D6	B3	29	E3	2F	84
5	53	D1	00	ED	20	FC	B1	5B	6A	CB	BE	39	4A	4C	58	CF
6	D0	EF	AA	FB	43	4D	33	85	45	F9	02	7F	50	3C	9F	A8
7	51	A3	40	8F	92	9D	38	F5	BC	B6	DA	21	10	FF	F3	D2
8	CD	0C	13	EC	5F	97	44	17	C4	A7	7E	3D	64	5D	19	73
9	60	81	4F	DC	22	2A	90	88	46	EE	B8	14	DE	5E	0B	DB
A	E0	32	3A	0A	49	06	24	5C	C2	D3	AC	62	91	95	E4	79
B	E7	C8	37	6D	8D	D5	4E	A9	6C	56	F4	EA	65	7A	AE	08
C	BA	78	25	2E	1C	A6	B4	C6	E8	DD	74	1F	4B	BD	8B	8A
D	70	3E	B5	66	48	03	F6	0E	61	35	57	B9	86	C1	1D	9E
E	E1	F8	98	11	69	D9	8E	94	9B	1E	87	E9	CE	55	28	DF
F	8C	A1	89	0D	BF	E6	42	68	41	99	2D	0F	B0	54	BB	16

Örnek verecek olursak bir bölmedeki değerimiz S0={05} olsun. Dikey olarak ‘0’ ı, yatay olarak ise ‘5’ bulup kesiştirdiğimiz de S’0={6B} sonucunu bulabiliriz.

Satır Kaydırma

Satır kaydırma işleminde satırlar sırasıyla çevrimsel şekilde kaydırılırlar. Yani ilk satır değiştirilmez, ikinci satır da sola 1 ötelenir, üçüncü satır sola 2 ötelenir ve son satır sola 3 ötelenir. Taşan bölmeler kaydırmanın başına eklenir.

Şekil 4: Satır Kaydırma İşlemi

Sütun Karıştırma

Bu işlemde eski sütunun elemanları kullanılarak yeni sütun elde edilmektedir. Bu yapılırken yeni sütunun elemanları eski sütunun her elemanı hesaba katılarak tek tek hesaplanır. Yapılan hesap çarpma ve toplama işleminden oluşur. Çarpma işleminde belirli bir sabit sayı (a(x)) kullanılır.

a(x)={03}x³+{01}x²+{01}x+{02}

è

s'(x)=a(x)*s(x)

Şekil 5: Sütun Karıştırma İşlemi

Bu matris işlemlerini açtığımızda aşağıdaki denklemler ortaya çıkar.

İşlem Örneği:

Şekil 6: Sütun Karıştırma Örneği

S₀‘={04} ‘ü bulalım:

İlk önce formülde yer alan 4 XOR işlemini parçalara ayırarak, işlemleri ayıralım.

{02}*S₀ = {02}*{D4}

{02} = 0000 0010 = x

{D4} = 1101 0100 = x⁷+x⁶+x⁴+x²

{02}*{D4} = (x)*(x⁷+x⁶+x⁴+x²) = x⁸+x⁷+x⁵+x³ Burada x⁸ olduğu için indirgeme işlemi gerçekleştirilecektir. Bu işlemde ise, x⁸ ve üzeri derecede bulunan yerler indirgenerek yeni denklem elde edilir.

NOT: 8. Dereceden indirgenemez polinomun böleni tekdir ve sadece kendisidir. AES için bu polinom gösterimi ise; m(x)=( x⁸+ x⁴+ x³+x+1)

=(x⁴+x³+x+1)+x⁷+x⁵+x³
= x⁷+x⁵+ x⁴+x+1 = 1011 0011 (aynı olan değerler toplama işleminde 0 sonucunun vereceğinden renkli işaretli olanları almadık)

{03}*S₁ = {03}*{BF}
{03} = 0000 0011 = x+1
{BF} = 1011 1111 = x⁷+x⁵+x⁴+x³+x²+x+1

{03}*{BF} = (x+1)*(x⁷+x⁵+x⁴+x³+x²+x+1) = x⁸+x⁶+x⁵+x⁴+x³+x²+x+x⁷+x⁵+x⁴+x³+x²+x+1

=(x⁴+x³+x+1)+x⁷+x⁶+1 = 1101 1010

S₂ = {5D} = 0101 1101

S₃ = {30} = 0011 0000

Bu 4 işlem sonucunu XOR işlemine sokarız.

S₁‘={66} ‘ü bulalım:

S₀ = {D4} = 1101 0100

{02}*S₁ = {02}*{BF}
{02} = 0000 0010 = x
{BF} = 1011 1111 = x⁷+x⁵+x⁴+x³+x²+x+1

{02}*{BF} = (x)*(x⁷+x⁵+x⁴+x³+x²+x+1) = x⁸+x⁶+x⁵+x⁴+x³+x²+x

=(x⁴+x³+x+1)+x⁶+x⁵+x⁴+x³+x²+x = 0110 0101

{03}*S₂ = {03}*{5D}
{03} = 0000 0011 = x+1
{5D} = 0101 1101 = x⁶+x⁴+x³+x²+1

{03}*{5D} = (x+1)*(x⁶+x⁴+x³+x²+1) = x⁷+x⁵+x⁴+x³+x+x⁶+x⁴+x³+x²+1 = 1110 0111

S₃ = {30} = 0011 0000

Bu 4 işlem sonucunu XOR işlemine sokarız.

İşlemler bu şekilde devam ederek sütun karıştırma işlemindeki 16 bölme de doldurulur.

Tur Anahtarıyla Toplama

Her turda daha önce saydığımız işlemlerle birlikte bir de tur anahtarı oluşturma işlemi yapılmaktadır ve her turda sonuçta oluşan durum ile o tur için hazırlanmış olan yeni anahtar toplama işlemine tabi tutulur. Bu işlem sonlu alanlarda yapılan toplama işlemidir ve bit mertebesinde özel veya işlemine karşılık düşer. 128 bitlik durum matrisi ile 128 bitlik ara anahtar değeri bit bit özel veya elamanı ile toplanır.

Şekil 7: Tur Anahtarı ile Toplama İşlemi

Anahtar Üretme

AES algoritması anahtarı alır ve bir dizi işlemden geçirerek işlem sayısı kadar anahtar oluşturur. Bu sayı 128 bitlik uzunluk için 10’dur. 10 farklı anahtar oluşturulur ve oluşan son anahtar şifreyi çözmede kullanılan ilk anahtar haline gelir. Çözerken de aynı işlemler benzer olarak tersten yürütülerek kullanılır. Anahtar üretmede her yeni oluşturulan yeni anahtar kendinden önceki anahtarlar kullanılarak elde edilir.

Şekil 8: Anahtar Üretimi

Şekilde de görüldüğü üzere, yeni anahtarın oluşmasındaki temel işlem bir önceki sütun ile dört önceki sütunun toplanmasıdır. Ancak bir istisna nokta var ki o da her 4’ün katı olan sütunda toplamadan önce bir dizi işlemden (T İşlemi) daha geçirilir. Bu işlemler öteleme, S kutusundan geçirme ve Rc(x) vektörü ile toplama işlemidir.

Tablo 3: Rc(x) Vektörleri

Şekil 9: T-İşlemi

Anahtar Üretimi Örneği

Aşağıda bir anahtar üretim örneği verilmiştir.

Anahtar: 2B 7E 15 16 28 AE D2 A6 AB F7 15 88 09 CF 4F 3C

Şekil 10: Anahtar Üretim Örneği

Tablo 4: Anahtar Üretim İşlemleri

Şifreli Metni Çözme

AES algoritmasında oluşturulan şifreli metin kolaylıkla, ters işlemlerle tekrar çözülerek giriş metni elde edilebilmektedir. Bu çözme işi için yapılan işlemler ters satır kaydırma, ters S kutusundan geçirme, ters sütun karıştırma ve tur anahtarı ile toplama işlemidir.

Ters Satır Kaydırma İşlemi

Şifreleme yaparken kullanılan satır kaydırma işleminin sola değil de sağa kaydırarak yapılmasıdır.

Şekil 11: Ters Satır Kaydırma İşlemi

Ters S-Kutusundan Geçirme İşlemi

Bu kez de değişim uygulanan S-kutusundaki bir değişiklik yapılmaktadır. Eski değerlere geri dönebilmek için S-kutusunu oluşturan değerler farklı bir metotla hesaplanır. Sonuç olarak oluşan kutu; normal S-kutusunda elde ettiğimiz değeri tekrar girişine uyguladığımızda bize ilk değeri geri verecek şekilde düzenlenmiş halinden ibarettir.

Tablo 5: Ters S-Kutusu Değerleri

Ters Sütun Karıştırma İşlemi

Bu işlemde sütunlar şifreleme sırasındaki sütun karıştırma işleminden farklı bir sabit polinomla çarpılır. Bu polinom ve işlemler aşağıda gösterilmiştir.

a(x)={0B}x³+{0D}x²+{09}x+{0E}

è

Şekil 12: Ters Sütun Karıştırma İşlemi

Çözme İşleminde Tur Anahtarı ile Toplama

Bit bit özel veya işleminden ibaret olması sebebi ile tekrar özel veya işlemine tabi tutulması eski haline dönmesine sebep olmaktadır. Sonuç olarak şifreleme işlemindeki tur anahtarı ile toplama işleminin aynısı yürütülür.

Ters Anahtar Üretimi

Şifreleme işleminde oluşan son anahtar, çözme işleminin ilk anahtarı olarak kullanılır. Anahtar üretiminin tersi işlemler ile ters anahtar üretimi gerçekleştirilir. Şekilde gördüğümüz gibi önce elimizdeki anahtarın sütunlarını kayıt altına alırız.

Şekil 13: Ters Anahtar Üretimi

Sütunlara baştan itibaren w0, w1, w2, w3 dersek; önce w2 ve w3’ü özel veya ile toplar yeni w0 değerini elde ederiz. Aynı şekilde w1 ve w2 işleminin sonucu da yeni w1 değerini verir. Bu şekilde geriye doğru giderek yeni durum oluşturulur. Son olarak yeni oluşan w0 sütununu 1 sola öteledikten sonra her sütunu S-kutusundan geçiririz ve ters Rc katsayısı ile çarparız. Böylece yeni anahtar oluşmuş olur.

Tablo 6: Ters Rc(x) Vektörleri

AES Şifreleme Adımları Örneği

128 bit uzunluğuna sahip bir blok ve anahtar için şifreleme adımları gösterilmiştir.

Giriş Bloğu: 32 43 F6 A8 88 5A 30 8D 31 31 98 A2 E0 37 07 34

Anahtar: 2B 7E 15 16 28 AE D2 A6 AB F7 15 88 09 CF 4F 3C

Şekil 14: AES Şifreleme Adımları Örneği

Sonuç

Bu çalışmada, son derece basit bir tasarıma sahip, bilinen tüm saldırı tiplerine karşı güvenli, hızlı ve akıllı kartlardan sunuculara kadar birçok platformda uygulamaya elverişli olan ve Gelişmiş Şifreleme Standardı (AES) olarak kabul edilen, bir blok şifre algoritması olan Rijndael algoritmasıyla detaylı olarak incelenmiştir.

Kriptografik açıdan son derece büyük önem taşıyan AES algoritmasının matematiksel özellikleri, metin ve anahtar uzunlukları, tur sayıları, tur dönüşümü ve bu dönüşümü oluşturan katmanlar, anahtar oluşturma algoritması, şifreleme ve şifre çözme blokları hakkında detaylı bilgi sunulmuştur.

Kaynakça

197, F. (2001). Advanced Encryption Standard. National Institute of Standarts and Technology (NIST).

Daemen, J. v. (2002). The Design of Rijhndael AES-The Advanced Encryption Standart.