AES -Advanced Encryption Standard-

Pada tahun 1972 dan 1974 National Bureau of Standards (sekarang dikenal dengan nama National Institute of Standards and Technology, NIST) menerbitkan permintaan kepada publik untuk pembuatan standar enkripsi. Hasil dari permintaan pada saat itu adalah DES (Data Encryption Standard), yang banyak digunakan di dunia. DES adalah sebuat algoritma kriptografi simetrik dengan panjang kunci 56 bit dan blok data 64 bit.

Hingga tahun 1990-an, algoritma kriptografi yang banyak dipakai adalah Data Encryption Standard (DES). Algoritma ini dipakai oleh NIST sebagai standar enkripsi data Federal Amerika Serikat. DES termasuk

dalam algoritma enkripsi yang sifatnya cipher block, yang berarti DES mengubah data masukan menjadi blok-blok 64-bit dan kemudian menggunakan kunci enkripsi sebesar 56-bit. Setelah mengalami proses enkripsi maka akan menghasilkan output blok 64-bit. 

Seiring dengan perkembangan teknologi, kunci DES yang sebesar 56-bit dianggap sudah tidak memadai lagi. Pada tahun 1998, 70 ribu komputer di Internet berhasil membobol satu kunci DES dalam waktu 96 hari. Tahun 1999 kejadian yang sama terjadi lagi dalam waktu lebih cepat yaitu hanya dalam waktu 22 hari. Pada tanggal 16 Juni 1999, sebuah mesin seharga 250 ribu dolar dapat dengan mudah memecahkan 25% kunci DES dalam waktu kira-kira 2,3 hari atau diperkirakan dapat memecahkan kunci DES dalam waktu 4,5 hari. 

Adanya kenyataan bahwa algoritma kriptografi DES tidak lagi aman, maka NIST mulai memikirkan sebuah algoritma kriptografi lain sebagai pengganti DES. Untuk itu diadakan kontes Internasional dimana pesertanya adalah ahli kriptografi dari seluruh dunia. Adapun diadakan secara terbuka dimaksudkan agar algoritma yang baru bukan dari produk badan pemerintah yang dapat dengan sengaja menanamkan backdoor pada algoritmanya. Backdoor ini dicurigai membuat plaintext dapat langsung dibaca tanpa harus menggunakan kunci.

Pada tahun 1997 kontes pemilihan suatu standar algoritma kriptografi baru pengganti DES dimulai dan diikuti oleh 21 peserta dari seluruh dunia. Algoritma yang akan dipilih selain harus memenuhi beberapa kriteria, yaitu :

1. Faktor keamanan, meliputi :
• Keamanan yang aktual : membandingkan dengan algoritma yang telah ada baik dari segi kunci dan ukuran block.
• Randomness : Random yang luas, output algoritma tidak bisa dibedakan dengan random permutasi dari input block.
• Soundness : berbasis pada matematika untuk keamanan algoritma.
• Faktor Keamanan lainya : diluncurkan untuk publik untuk mengetahui apakah algoritma ini bisa dipecahkan dengan berbagai serangan dan mengadakan kompetisi siapa yang bisa memecahkan algoritma tesebut. Dari hal ini diketahui apakah algoritma ini aman atau tidak.
2. Faktor biaya, meliputi :
• Persyaratan Lisensi : NITS meminta siapa yang akan jadi pemenang dari kompetisi, maka algoritma tersebut akan dipublikasikan di internet secara gratis.
• Perhitungan yang efesien: evaluasi dari perhitungan yang efesien terhadap software dan hardware yang murah.
• Persyaratan memory : implementasi dari persyaratan memory untuk software dan hardware dengan seminimum mungkin.
3. Faktor karakteristik implementasi, yaitu :
• Fleksibel : Kandidat harus memiliki sifat yabg sangat fleksible untuk semua pengguna dan memiliki sedikit praktek pada aplikasinya.
• Software dan hardware yang seimbang : kandidat algoritma tidak hanya sesuai dengan hardware yang ada di pasaran, tapi juga harus seimbang dengan software yang ada.
• Sederhana : harus mempunyai disain yang sederhana.

Algoritma ini akan dinamakan Advanced Encryption Standard (AES).

Dari persyaratan diatas maka, didapatkan 15 calon tahap I pada bulan juni 1998, yang berasal dari Amerika, Kanada, Belgia, Perancis, Jerman, Norwegia, Inggris, Korea, Israel, Jepang, Costa Rica, dan Australia. 10 Algoritma yang ada pemilihan tahap I gugur karena dianggap kurang aman dan kurang efektif. Setelah melewati tahap seleksi yang ketat, pada tahun 1999 hanya tinggal 5 calon yaitu :

1. Algoritma Serpent (Ross Anderson-University of Cambridge, Eli Biham- Technion, Lars Knudsen-University of California San Diego dari Inggris, Israel dan Norwegia),
2. MARS (IBM Amerika),
3. Twofish (Bruce Schneier, John Kelsey, dan Niels Ferguson-Counterpane Internet Security Inc, Doug Whiting-Hi/fn Inc, David Wagner-University of California Berkeley, Chris Hall-Princeton University dari Amerika),
4. Rijndael (Dr. Vincent Rijmen-Katholieke Universiteit Leuven dan Dr. Joan Daemen-Proton World International dari Belgia)
5. RC6 (RSA Amerika).

Setahun kemudian pada tahun 2000, algoritma Rijndael terpilih sebagai algoritma kriptografi yang selain aman juga efisien dalam implementasinya dan dinobatkan sebagai AES. Nama Rijndael sendiri berasal dari gabungan nama penemunya.

Blok dan Kunci Algoritma Rijndael

Rijndael termasuk dalam jenis algoritma kriptografi yang sifatnya simetri dan cipher block. Dengan demikian algoritma ini mempergunakan kunci yang sama saat enkripsi dan dekripsi serta masukan dan keluarannya berupa blok dengan jumlah bit tertentu.

Rijndael mendukung berbagai variasi ukuran blok dan kunci yang akan digunakan. Namun Rijndael mempunyai ukuran blok dan kunci yang tetap sebesar 128, 192, 256 bit. Pemilihan ukuran blok data dan kunci akan menentukan jumlah proses yang harus dilalui untuk proses enkripsi dan dekripsi. Berikut adalah perbandingan jumlah proses yang harus dilalui untuk masing-masing masukan.

Spesifikasi Algoritma Rijndael

Input dan output dari algoritma AES terdiri dari urutan data sebesar 128 bit. Urutan data yang sudah terbentuk dalam satu kelompok 128 bit tersebut disebut juga sebagai blok data atau plaintext yang nantinya akan dienkripsi menjadi ciphertext. Cipher key dari AES terdiri dari key dengan panjang 128 bit, 192 bit, atau 256 bit.

Urutan bit diberi nomor urut dari 0 sampai dengan n-1 dimana n adalah nomor urutan. Urutan data 8 bit secara berurutan disebut sebagai byte dimana byte ini adalah unit dasar dari operasi yang akan dilakukan pada blok data. Jumlah n-bit yang ada bergantung pada panjang key yang digunakan dimana pada panjang key = 128 bits, 0 ≤ n < 16; panjang key = 192 bits, 0 ≤ n < 24; panjang key = 256 bits, 0 ≤ n < 32.

Dalam algoritma AES, data sepanjang 128 bit akan dibagi-bagi menjadi array byte dimana setiap array byte ini terdiri dari 8 bit data input yang saling berurutan. Array byte ini direpresentasikan dalam bentuk :

a0 a1 a2 ... a15

Dimana:

a0 = { input0, input1,..., input7 }

a1 = { input8, input9,..., input15 }

a15 = { input120, input121,..., input127 }

an = { input8n, input8n+1,..., input8n+7 }

Urutan bit dapat pada algoritma AES direpresentasikan sebagai satu dimensi array dari 8-bit sub-urutan yang disebut byte. Semua nilai byte dalam algoritma AES akan disajikan sebagai rangkaian bit individu (nilai 0 atau 1) urutan {b7, b6, b5, b4, b3, b2, b1, b0}. Byte tersebut diterjemahkan sebagai elemen field terbatas dengan representasi polynomial :

Sebagai contoh, {01100011} diidentifikasikan sebagai elemen field terbatas : 6+ 5+ +1 Selain bit, semua nilai byte dalam algoritma AES juga dapat disajikan dengan menggunakan notasi heksadesimal, dimana setiap 4 bit dinotasikan menjadi sebuah karakter, seperti berikut :

Operasi algoritma AES dilakukan pada sebuah state dimana state sendiri adalah sebuah array byte dua dimensi. Setiap state pasti mempunyai jumlah baris yang tetap, yaitu 4 baris, sedangkan jumlah kolom tergantung dari besarnya blok data. Baris pada state mempunyai indeks nomor row (r) dimana 0 ≤ r < 4, sedangkan kolom mempunyai indeks nomor column (c) dimana 0 ≤ c < Nb. Nb sendiri adalah besarnya blok data dibagi 32.

Pada saat permulaan, input bit pertama kali akan disusun menjadi suatu array byte dimana panjang dari array byte yang digunakan pada AES adalah sepanjang 8 bit data. Array byte inilah yang nantinya akan dimasukkan atau dikopi ke dalam state dengan urutan :

s[r,c] = in[r+4c] untuk 0 ≤ r < 4 dan 0 ≤ c < Nb

sedangkan dari state akan dikopi ke output dengan urutan :

out[r+4c] = s[r,c] untuk 0 ≤ r < 4 dan 0 ≤ c < Nb

Pengantar Matematis

Seluruh byte dalam algoritma AES diinterpretasikan sebagai elemen finite field. Elemen finite field ini dapat dikalikan dan dijumlahkan, tetapi hasil dari penjumlahan dan perkalian elemen finite field sangat berbeda dengan hasil dari penjumlahan dan perkalian bilangan biasa.

Penjumlahan

Penjumlahan dari dua elemen dalam suatu finite field dilakukan dengan menjumlahkan koefisien dari pangkat polinom yang bersesuaian dari dua elemen tersebut. Penjumlahan dilakukan dengan operasi XOR dan dinotasikan dengan Å. Dengan operasi ini, maka 1Å1 = 0, 1Å0 = 1, 0Å1 = 1, dan 0Å0 = 1. Pengurangan

dari polinomial identik dengan penjumlahan polinomial.

Sebagai alternatif, penjumlahan elemen-elemen pada finite field dapat dijelaskan sebagai penjumlahan modulo 2 dari bit yang bersesuaian dalam byte. Untuk 2 byte {a7a6a5a4a3a2a1a0} dan {b7b6b5b4b3b2b1b0}, hasil penjumlahannya adalah {c7c6c5c4c3c2c1c0} dimana setiap ci = aiÅbi. Contoh dari operasi penjumlahan adalah sebagai berikut :

(x6+x4+x2+x+1)Å(x7+x+1) = x7+x6+x4+x2 (notasi polinomial)

{01010111}Å{10000011} = {11010100} (notasi biner)

{57}Å{83} = {d4} (notasi hexadesimal)

Perkalian

Dalam representasi polinomial, perkalian dalam GF(28) yang dinotasikan dengan • mengacu pada perkalian modulo polinomial sebuah irreducible polynomial yang berderajat 8. Sebuah polinom bersifat irreducible jika satu-satunya pembagi adalah dirinya sendiri dan 1. Untuk algoritma AES, irreducible polynomial ini adalah :

m(x) = x8 + x4 + x3 + x + 1

atau dalam notasi hexadesimal adalah {01}{1b}. Sebagai contoh, {57}•{83} = {c1}, karena

(x6 + x4 + x2 + x + 1) • (x7 + x + 1) = x13 + x11 + x9 + x8 + x7 + x7 + x5 + x3 + x2 + x + x6 + x4 + x2 + 1 = x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1

dan

x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + x + 1 modulo (x8 + x4 + x3 + x + 1) = x7 + x6 + 1

Pengurangan modular oleh m(x) memastikan bahwa hasilnya akan berupa polinomial biner dengan derajat kurang dari 8, sehingga dapat dipresentasikan dengan 1 byte saja.

Algoritma AES

Blok-blok data masukan dan kunci dioperasikan dalam bentuk array. Setiap anggota array sebelum menghasilkan keluaran ciphertext dinamakan dengan state. Setiap state akan mengalami proses yang secara garis besar terdiri dari empat tahap yaitu, AddRoundKey, SubBytes, ShiftRows, dan MixColumns. Kecuali tahap MixColumns, ketiga tahap lainnya akan diulang pada setiap proses sedangkan tahap MixColumns tidak akan dilakukan pada tahap terakhir.

Proses dekripsi adalah kebalikan dari dekripsi. Karena terjadi beberapa tahap dalam proses enkripsi, maka diperlukan subkey-subkey yang akan dipakai pada tiap tahap. Pengembangan jumlah kunci yang akan dipakai diperlukan karena kebutuhan subkey-subkey yang akan dipakai dapat mencapai ribuan bit, sedangkan kunci yang disediakan secara default hanya 128-256 bit. Jumlah total kunci yang diperlukan sebagai subkey adalah sebanyak Nb(Nr+1), dimana Nb adalah besarnya blok data dalam satuan word. Sedangkan Nr adalah jumlah tahapan yang harus dilalui dalam satuan word. Sebagai contoh, apabila digunakan 128 bit (4 word) blok data dan 128 bit (4 word) kunci maka akan dilakukan 10 kali proses. Dengan demikian dari rumus didapatkan 4(10+1)=44 word=1408 bit kunci. Untuk melakukan pengembangan jumlah kunci yang akan dipakai dari kunci utama maka dilakukan key schedule.

Ekspansi Kunci

Algoritma AES mengambil kunci cipher, K, dan melakukan rutin ekspansi kunci (key expansion) untuk membentuk key schedule. Ekspansi kunci yang diperlukan AES Nb(Nr+1) word, sehingga bisa digunakan AES 128 bit maka, 4(10+1) = 40 word = 44 x 32 bit = 1408 bit sub key. Ekspansi dari 128 menjadi 1408 bit subkey. Proses ini disebut dengan key schedule. Subkey ini diperlukan karena setiap round merupakan suatu nilai inisial dari Nb word untuk Nr = 0 dan 2 untuk Nr = 1,3 untuk Nr = 2,….., yang berisi array linier empat byte word (w), 0=1 Nb(Nr + 1).

Contoh dari ekspansi kunci seperti di bawah ini :

• RotWord() engambil input empat-byte word [ dan membentuk cyclic permutasi seperti [a1,a2,a3,a0]’
• Sub word() mengambil input empat-byte word dan menggunakan S-Box sehingga didapat empat byte output dari prosedur.
• Rcon() menghasilkan round yang tetap dari word array dan berisi nilai yang diberikan oleh [[xid1, {00}, {00}, {00}, {00}] dengan xid1 dari I ke 1.

Rcon[i] = [[xid1, {00}, {00}, {00}, {00}]

Rcon [1] = [x0, {00}, {00}, {00}, {00}] = [{01}, {00}, {00}, {00}] = 01000000

Rcon [2] = [x1, {00}, {00}, {00}, {00}] = 02000000

Rcon [3] = [x2, {00}, {00}, {00}, {00}] = 04000000

Rcon [4] = [x3, {00}, {00}, {00}, {00}] = 08000000

Rcon [5] = [x4, {00}, {00}, {00}, {00}] = 10000000

Rcon [6] = [x5, {00}, {00}, {00}, {00}] = 20000000

Rcon [7] = [x6, {00}, {00}. {00}, {00}] = 40000000

Rcon [8] = [x7, {00}, {00}, {00}, {00}] = 80000000

Rcon [9] = [x8, {00}, {00}, {00}, {00}] = [x7] · x, {00}, {00}, {00}] = 1b000000

        x7 · x = xtime(x7) = xtime(80) = {leftshift(80)} · “ {1b} = 1b

Rcon [10] = [x9, {00}, {00}, {00}] = [x8 · x, {00}, {00}, {00}] = 36000000

Rcon [11] = [x10, {00}, {00}, {00}] = [x9 · x, {00}, {00}, {00}] = 6c000000

Rcon [12] = [x11, {00}, {00}, {00}] = [x10 · x, {00}, {00}, {00}] = d8000000

Rcon [13] = [x12, {00}, {00}, {00}] = [x11 · x, {00}, {00}, {00}] = ab000000

       X11 · x = xtime(x11) = xtime (d8)= {leftshift (d8)} · “ {1b} = ab

Rcon[ i ] adalah suatu komponen dari round tetap word array dalam perhitungan ekspansi key routine. Pseudocode dari proses ekspansi key dapat dilihat seperti pada berikut ini :

KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)], Nk)

begin

word temp

i = 0

while (i < Nk)

    w[i] = word(key[4*i], key[4*i+1], key[4*i+2], key[4*i+3])

    i = i +1

end while

i = Nk

while (i < Nb*(Nr+1))

   temp = w[i -1]

   if (i mod Nk = 0)

     temp = SubWord(RotWord(temp)) 

     xor Rcon[i/Nk]

   else if (Nk > 6 and i mod Nk = 4) 

     temp = SubWord(temp)

   end if

   w[i]=w[i-Nk] xor temp

   i = i + 1

end while

end

Dari pseudocode dapat dilihat bahwa word ke Nk pertama pada ekspansi kunci berisi kunci cipher. Setiap word berikutnya, w[i], sama dengan XOR dari word sebelumnya, w[i-1] dan word Nk yang ada pada posisi sebelumnya, w[i-Nk]. Untuk word pada posisi yang merupakan kelipatan Nk, sebuah transformasi diaplikasikan pada w[i-1] sebelum XOR, lalu dilanjutkan oleh XOR dengan konstanta round, Rcon[i]. Transformasi ini terdiri dari pergeseran siklik dari byte data dalam suatu word RotWord, lalu diikuti aplikasi dari lookup tabel untuk semua 4 byte data dari word SubWord.

Proses Enkripsi

Enkripsi dengan menggunakan AES
Secara umum enkripsi dengan algoritma AES sebagai berikut :

1. Pertama kita melakukan XOR plainteks/ state dengan roundkey.
2. Setelah selesai melakukan XOR plainteks dengan roundkey, kita lakukan substitusi dengan s-Box
3. Setelah itu hasil dari substitusi dengan S-Box Selesai kita lakukan shift row
4. Setelah hasil shift row di dapat, maka langkah selanjutnya yaitu melakukan Mix Column dengan cara megalikan matrik
5. Setelah perhitungan Mix Column selesai maka kita melakukan addround key. Yaitu melakukan XOR state dengan roundkey. Lakukan samapai iterasi 10, namun pada saat iterasi ke 10, setelah melakukan step shift row tidak melakukan Mix Colum. Namun langsung melakukan XOR hasil state saat shift row dengan round key.

Sub-bytes

Proses SubBytes () memetakan setiap byte dari array State dengan menggunakan tabel substitusi S-Box. Tidak seperti Des S-box berbeda pada setiap putaran, AES hanya mempunyai satu buah S-Box. Tabel yang digunakan adalah seperti pada gambar dibawah ini :

Cara pensubstitusian adalah untuk setiap byte pada array state, misalkan S[r,c] = xy, yang dalam hal ini xy adalah digit heksadesimal dari nilai S’[r,c], maka nilai substitusinya, yang dinyatakan dengan S’[r,c], adalah elemen di dalam S-Box yang merupakan perpotongan baris x dengan kolom y. Gambar 10, memperlihatkan transformasi SubBytes.

Shiftrows()

Proses ShiftRows() ini adalah proses yang sangat sederhana. Pada ShiftRows() melakukan pergerseran wrapping (sikklik) pada 3 baris terkhir dari array state. Jumlah pergeseran bergantung nilai baris (r). Baris r = 1 digeser sejauh 1 byte, baris r = 2 digeser 2 byte, dan baris r = 3 digeser sejauh 3 byte. Baris r = 0 tidak digeser. Contoh :

• Geser baris 0 byte : Karena 0 byte maka tidak melakukan pergeseran dan state-pun tetap sama.

   

• Geser baris 1 byte :

• Hasil pergeseran 1 byte dan geser lagi 2 byte :

• Hasil pergeseran 2 byte dan geser lagi 3 byte :

• Hasil pergeseran 3 byte

MixCollums()

Transformasi menggunakan MixColumns() adalah proses ketiga dalam satu Ronde enkripsi AES. Di sini, kolom-kolom pada array state akan diperlukan sebagai suatu polynomial yang berada dalam GF(28) dan akan dikalikan dengan modulo x4 + 1 , dengan suatu polynomial tertentu :

a(x) = {03}x3 + {01}x2 + {01}x + {02}

Transformasi ini dinyatakan sebagai perkalian matriks :

 Hasil substitusi

Hasil substitusi dikalikan matriks mixColumns

Hasil Dari perkalian substitusi dengan matriks MixColumn

Keterangan cara pencarian :

Semua state dilakukan dengan cara yang sama seperti diatas, dan diperoleh hasil perkalian state awal dengan matriks sebagai berikut :

Dan lakukan hal yang sama sampai iterasi ke-10, namun tidak dilakukan MixColum lagi, melainkan langsung melakukan XOR hasil dari shifRow dengan RoundKey.

AddRoundKey()

Pada proses AddRoundKey() maka 128 bit hasil state akan di-XOR-kan dengan Kunci Ronde, yaitu kunci hasil dari proses Expand Key. Pada awal enkripsi, 128 bit plaintext akan di-XOR-kan dengan 128 bit kunci yang asli. Kemudian 128 bit plaintext akan mengalami prosesproses : SubBytes(), ShiftRows() dan MixColumns(). Pada proses AddRoundKey(), 128 bit yang sudah melalui tiga tersebut akan di-XOR-kan dengan kunci ronde hasil Ekspand Key yang pertama. Hasil AddRoundKey() ini adalah state pada ronde 1. State 1 ini akan mengalami ketiga proses tersebut kembal. Pada AddRoundKey() yang berikut, maka 128 bit yang sudah mengalami perubahan pada ketiga proses tersebut kembali akan di-XOR-kan dengan kunci hasil Ekspand Key kedua dan seterusnya.

Proses Dekripsi

Proses yang dilakukan dalam dekripsi adalah InvAddRows, InvShiftRows, InvSubByte, InvAddRow, InvMixColumns. Menggunakan kunci ronde yang sama dengan proses enkripsi. Urutan proses dalam setiap ronde adalah InvAddRows, InvShiftRows, InvSubByte, InvAddRow, InvMixColumns

InvAddRows()

Transformasi InvAddRows sama dengan transformasi AddRows yaitu menggunakan operasi XOR. Akan dilakukan proses XOR antara chipertext dengan kunci round yang digunakan pada saat enkripsi.

Contoh :

InvShiftRows()

Proses InvShiftRow adalah kebalikan dari proses ShiftRow. Dimana dimulai dari baris paling bawah.

Proses :

InvSubBytes()

Proses InvSubBytes sama dengan Proses SubBytes, namun tabel yang digunakan berbeda. Tabel

yang digunakan adalah tabel inverse S-Box :

InverseMixCollums()

Transformasi InvMixColumns sama dengan MixColumns(), dimana perbedaanya adalah a(x)

yang digunakan adalah inversnya(a-1) yaitu :

Semua state dilakukan dengan cara yang sama seperti diatas, dan diperoleh hasil perkalian state awal dengan matriks sebagai berikut :

Dan lakukan hal yang sama sampai iterasi ke-10, namun tidak dilakukan MixColum lagi, melainkan langsung melakukan XOR hasil dari shifRow dengan RoundKey.