JURNAL TEKNIK POMITS Vol. 2, No. 1, (2013) ISSN: 2337-3539 (2301-9271 Print)
1
Implementasi Algoritma Rijndael dengan Menggunakan Kunci Enkripsi yang Berukuran Melebihi 256 bit Gracius Cagar Gunawan, Ahmad Saikhu, Rully Soelaiman Jurusan Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember (ITS) Jl. Arief Rahman Hakim, Surabaya 60111 Indonesia e-mail :
[email protected] Abstrak—Dalam dunia nyata, terdapat permasalahan keamanan informasi yang dapat diselesaikan dengan menggunakan enkripsi. Seiring dengan pertumbuhan teknologi, enkripsi dengan ukuran cipher key yang kecil semakin mudah dibongkar. Oleh karena itu, ukuran cipher key perlu ditingkatkan. Sampai saat ini, Advanced Encryption Standard yang dibentuk berdasarkan Algoritma Rijndael yang dapat menggunakan cipher key berukuran 256 bit masih dipakai. Dalam artikel ini, dilakukan studi dan implementasi algoritma enkripsi yang mampu menerima cipher key berukuran lebih dari 256 bit dengan bahasa C. Hasil uji coba menunjukkan program menghasilkan keluaran yang benar dan memiliki pertumbuhan waktu eksekusi secara linear, yaitu (Nb*Nk) dengan Nb adalah ukuran data masukan dan Nk adalah ukuran cipher key. Kata kunci—Advanced Encryption Rijndael, cipher key, enkripsi
Standard,
Algoritma
I. PENDAHULUAN ERANGAN-SERANGAN yang telah dilakukan untuk memecahkan enkripsi sangat banyak dan beragam. Pada tahun 1999, FIPS mengeluarkan standarisasi enkripsi yang disebut dengan DES [1]. DES cukup kebal terhadap serangan differential [2], tetapi DES yang hanya menggunakan 56 bit kunci enkripsi mudah ditembus dengan serangan brute force karena komputer tercanggih sekarang dapat mencoba 255 kunci enkripsi yang berbeda setiap detiknya. Oleh karena itu, pada tahun 2001, dibuatlah standarisasi enkripsi baru, yaitu Advanced Ecryption Standard (AES) [3]. AES diimplementasikan menggunakan sebuah algoritma enkripsi yang dibuat oleh Joan Daemen dan Vincent Rijmen yang dinamakan Algoritma Rijndael [4]. Algoritma tersebut menerima kunci enkripsi yang berukuran hingga 256 bit. Dengan kemampuan komputer sekarang, hampir mustahil AES untuk dapat dipecahkan menggunakan serangan brute force karena untuk memecahkan kunci enkripsi tersebut, waktu yang dibutuhkan adalah 273 detik. Seiring berjalannya waktu, nasib AES akan sama dengan DES. Menurut Hukum Moore [5], pertumbuhan kecepatan komputer adalah sebanyak dua kali lipat setiap delapan belas bulan. Pada akhirnya, sekitar dua ratus tahun lagi, AES akan mudah dipecahkan menggunakan brute force attack [6]. Namun, Hukum Moore hanyalah sebuah prediksi yang belum dapat dipastikan kebenarannya. Oleh karena itu, melalui artikel ini, ditawarkan sebuah solusi yaitu
implementasi Algoritma Rijndael yang dapat menerima kunci enkripsi yang berukuran melebihi 256 bit. II. TINJAUAN PUSTAKA A. Advanced Encryption Standard (AES) AES adalah algoritma enkripsi yang memiliki ukuran blok masukan sebesar 128 bit. Blok masukan yang sedang dalam proses enkripsi AES disebut dengan state. Masukan untuk AES berupa sebuah matriks berukuran 4x4 yang setiap sel dari matriks tersebut terisi dengan sebuah byte. Cara pengisian matriks yang digunakan sebagai masukan dari AES adalah dimulai dari baris 0 kolom 0, baris 1 kolom 0 sampai baris 3 kolom 0 dan dilanjutkan ke baris 0 kolom 1 dan seterusnya. Setelah masukan terbentuk dengan benar, proses enkripsi dimulai. Proses enkripsi tersebut membutuhkan variabelvariabel pada Tabel 1. Proses enkripsi AES adalah sesuai pada Gambar 1. Setelah semua proses enkripsi AES selesai, keluaran dari AES dapat diambil. Keluaran tersebut memiliki bentuk yang sama seperti masukannya, yaitu berupa matriks 4x4. Pengambilan keluaran dilakukan dengan cara yang sama seperti masukannya. A.1. AES Key Expansion Key expansion merupakan proses yang digunakan untuk memperpanjang cipher key. AES key expansion hanya dapat menerima cipher key yang berukuran 128 bit, 192 bit, atau 256 bit. Oleh karena itu, key expansion yang akan digunakan pada artikel ini adalah Rijndael key expansion. A.2. Add Round Key Add round key merupakan transformasi state dengan cara menjumlahkan matriks state dengan expanded key pada indeks tertentu. Add round key yang dijalankan pertama kali pada AES mengambil expanded key indeks ke-0. Round Round merupakan transformasi yang dilakukan sebanyak Nr-1 kali dalam proses enkripsi AES. Dalam transformasi ini, dilakukan empat buah proses yaitu proses sub bytes, shift rows, mix columns, dan add round key. Add round key yang dilakukan pada transformasi round ke-i menjumlahkan state dengan expanded key indeks ke-i. Transformasi round dapat dilihat pada Gambar 2. A.3.
JURNAL TEKNIK POMITS Vol. 2, No. 1, (2013) ISSN: 2337-3539 (2301-9271 Print)
matriks pada sebuah kolom. Perkalian tersebut merupakan perkalian pada Persamaan 3.
Tabel 1. Daftar variabel pada AES
Nama Variabel
Deskripsi Nb adalah ukuran blok masukan dalam satuan word. Satu word adalah empat byte. Nilai Nr pada AES selalu 4. Nk adalah ukuran cipher key dalam satuan word. Nilai Nk pada AES hanya dapat berupa empat, enam, atau delapan. Nr adalah banyaknya transformasi round dan final round yang akan dilakukan. Nilai Nr pada AES selalu Nk+6.
Nb Nk Nr
[ [
]
(3)
] [
]
A.4. Final Round Final round merupakan transformasi terakhir pada AES. Transformasi ini hampir sama dengan transformasi round, hanya mix columns tidak digunakan. Transformasi final round dapat dilihat pada Gambar 3.
Masukan K (cipher key), Nk, state Keluaran state 1 W KeyExpansion(K, Nk) 2 state AddRoundKey(W,0,state) 3 For i 1 to Nr-1 do begin 4 state Round(W,i,state) 5 End 6 state FinalRound(W,Nk,state) 7 Return state Gambar 1. Pseudocode AES
B.
Masukan W (expanded key), i, state Keluaran state 1 state SubBytes(state) 2 state ShiftRows(state) 3 state MixColumns(state) 4 state AddRoundKey(W,i,state) 5 Return state Gambar 2. Pseudocode round
A.3.1. Sub Bytes Sub bytes adalah proses transformasi sub byte terhadap seluruh byte pada state. Sub byte merupakan sebuah proses transformasi pada sebuah byte B menjadi B` dengan melibatkan invers, penjumlahan matriks bit, dan perkalian matriks bit. Invers dari suatu byte B, yaitu B-1 didefinisikan secara GF(28) menurut Persamaan 1. (
2
(1)
)
Setelah B-1 didapatkan, masukkan B-1 ke dalam Persamaan 2. Pada Persamaan 2, anggap bi merupakan bit ke-i dari B-1 dan b`i merupakan bit ke-i dari B`.
Rijndael Key Expansion Karena fungsi key expansion pada AES hanya mampu menangani 128 bit, 192 bit, dan 256 bit cipher key, maka key expansion pada AES tidak digunakan. Fungsi key expansion yang digunakan pada artikel ini adalah fungsi key expansion pada Algoritma Rijndael, yaitu fungsi key expansion yang mempu menerima kunci cipher berukuran kelipatan 32 bit antara 128 bit sampai 256 bit. Secara garis besar key expansion menyalin cipher key ke dalam bagian awal dari expanded key. Setelah itu, key expansion mengisi seluruh expanded key. Proses pengisian expanded key (W) oleh key expansion dijelaskan pada Gambar 4. Pada Gambar 4, terlihat sebuah operasi perpangkatan pada baris 9. Operasi tersebut dilakukan pada Gallois Field dengan ( ) . C.
Electronic Codebook (ECB) Fungsi AES memiliki ukuran blok sebesar 128 bit, sedangkan ukuran data tidak mungkin hanya sebesar 128 bit.. Oleh karena itu, diperlukan suatu modus operasi terhadap ukuran masukan yang dapat diterima oleh AES. Dalam artikel ini, modus operasi yang dilakukan adalah ECB. Konsep ECB secara garis besarnya adalah membagi masukan menjadi bagian-bagian dengan ukuran yang dapat diterima oleh pengenkripsi dan menggabungkannya kembali setelah setiap bagian terenkripsi. D.
(2)
[
]
[
]
[ ]
[ ]
A.3.2. Shift Rows Shift rows adalah tahap penggeseran setiap baris pada state dengan aturan baris ke-i pada state digeser ke arah kiri sejauh i. A.3.3. Mix Columns Mix columns adalah transformasi mix column terhadap setiap kolom pada state. Mix column merupakan perkalian
Dekripsi Dekripsi dimulai dari ECB yang membagi masukan, kemudian setiap bagian masukan didekripsi oleh inverse AES, dan terakhir ECB menyatukan kembali keluaran-keluaran dari inverse AES. Tahap-tahap dari inverse AES hampir sama dengan AES, di mana yang membedakan hanya add round key pertama yang mengambil bagian terakhir dari expanded key, bukan bagian pertama, inverse round menggantikan round, dan inverse final round menggantikan final round. D.1. Inverse Round Inverse round merukapan transformasi yang dilakukan sebanyak Nr-1 kali pada dekripsi. Tahap-tahap transformasi ini ada pada Gambar 5.
JURNAL TEKNIK POMITS Vol. 2, No. 1, (2013) ISSN: 2337-3539 (2301-9271 Print) Masukan W (expanded key), Nr, state Keluaran state 1 state SubBytes(state) 2 state ShiftRows(state) 3 state AddRoundKey(W,Nr,state) 4 Return state Gambar 3. Pseudocode final round Masukan K (cipher key), Nk Keluaran W (expanded key) 1 For j 0 to Nk-1 do begin 2 For i 0 to 3 do begin 3 W[i][j] K[i][j] 4 End 5 End 6 For j <- Nk to Nb(Nr+1)-1 do begin 7 If j%Nk=0 do begin 8 W[0][j]W[0][j-Nk]⨁sub_byte(W[1][j-1]) 9 W[0][j] W[0][j] ⨁ 0x02(j/Nk)-1 10 For i 1 to 3 then begin 11 W[i][j] W[i][j-Nk] 12 W[i][j]W[i][j]⨁sub_byte(W[(i+1)%4][j-1]) 13 End 14 End 15 Else if (Nk>6) and (j%Nk=4) then begin 16 For i 0 to 3 do begin 17 W[i][j]W[i][j-Nk]⨁sub_byte(W[i][j-1]) 18 End 19 End 20 Else begin 21 For i 0 to 3 then begin 22 W[i][j] W[i][j-Nk]⨁W[i][j-1] 23 End 24 End 25 End 26 Return W Gambar 4. Pseudocode key expansion Masukan W (expanded key), i, state Keluaran state 1 state InvShiftRows(state) 2 state InvSubBytes(state) 3 state AddRound_key(W,i,state) 4 state InvMixColumns(state) 5 Return state Gambar 5. Pseudocode inverse round Masukan W (expanded key), state Keluaran state 1 state InvShiftRows(state) 2 state InvSubBytes(state) 3 state AddRoundKey(W,0,state) 4 Return state Gambar 6. Pseudocode inverse final round
D.1.1. Inverse Shift Rows Inverse shift rows adalah tahap penggeseran baris ke-i pada state ke arah kanan sejauh i. D.1.2. Inverse Sub Bytes Inverse sub bytes adalah proses inverse sub byte, yaitu pembalikan dari transformasi sub byte, pada setiap byte dari
state. Pembalikan Persamaan 4.
3 ini
dapat
dilakukan
menggunakan
(4) [
[ ]
]
[
]
[ ]
Pada persamaan tersebut, B` merupakan invers byte dari masukan. B merupakan keluaran. b`i merupakan bit ke-i dari B`. bi merupakan bit ke-i dari B. D.1.3. Inverse Mix Columns Inverse mix columns adalah transformasi inverse mix column pada setiap kolom dari state. Inverse mix column membalik transformasi mix column dengan cara memindahkan ruas matriks pengali pada Persamaan 3 sehingga dapat dikatakan bahwa matriks pengali pada inverse mix columns adalah invers dari matriks pengali pada mix column. Akhirnya, Persamaan 5 terbentuk.
[ [
]
(5)
] [
]
D.2. Inverse Final Round Inverse final round merupakan transformasi terakhir dari dekripsi. Tahap transformasi ini ada pada Gambar 6. III. METODOLOGI PERANCANGAN Aplikasi dirancang berdasarkan tinjauan pustaka pada Bab II dengan beberapa modifikasi berikut. A.
ECB KeyExpansion dipanggil pada ECB, padahal seharusnya KeyExpansion merupakan fungsi yang terdapat dalam AES. Hal itu disebabkan karena untuk setiap AES yang dipanggil, cipher key yang digunakan sama. Akibatnya, pemanggilan KeyExpansion yang berkali-kali hanya akan memperlambat jalannya program. Oleh karena itu, KeyExpansion cukup dilakukan sekali saja, yaitu sebelum AES pertama kali dilakukan. Gambar 7 merupakan pseudocode dari fungsi ini. B.
Fungsi yang Masukan dan Keluarannya adalah Sebuah Byte Fungsi yang masukan dan keluarannya adalah sebuah byte diimplementasikan menggunakan sebuah larik yang berfungsi sebagai look-up table. Fungsi-fungsi yang diimplementasikan menggunakan cara tersebut adalah sub byte, fungsi perpangkatan dua yang disebut dengan RCon, fungsi perkalian dua yang disebut dengan XTime, dan inverse sub byte.
JURNAL TEKNIK POMITS Vol. 2, No. 1, (2013) ISSN: 2337-3539 (2301-9271 Print) Masukan K, Nk, B, blockSize Keluaran B 1 W KeyExpansion(K, Nk) 2 n blockSize/16 3 For j 0 to n-1 do begin 4 For i 0 to 15 do begin 5 state[i%4][i/4] B[i+16j] 6 End 7 state AES(W,Nk,state) 8 For i 0 to 15 do begin 9 B[i+16j] state[i%4][i/4] 10 End 11 End 12 Return B Gambar 7. Pseudocode ECB
C.
Mix Column dan Inverse Mix Column Fungsi MixColumn merupakan fungsi yang menjalankan mix column pada masukannya. Jika perkalian matriks pada Persamaan 3 langsung diimplementasikan, maka program akan membutuhkan waktu komputasi yang lama karena harus menghitung banyak perkalian atau membutuhkan memori yang cukup besar karena harus menyimpan tabel perkalian untuk 0x02 dan 0x03. Oleh karena itu, mix column harus diturunkan persamaannya. Penurunan persamaan itu dapat dilakukan menggunakan sifat perkalian pada Gallois Field bahwa setiap perkalian dapat diubah menjadi perkalian dengan 0x02. Pengubahan tersebut dapat dilihat pada Persamaan 6 dengan ai adalah sebuah kolom pada baris ke-i. (
(
)
)
(
)
(6)
Sama halnya dengan mix column, perkalian yang boleh digunakan oleh inverse mix column hanyalah perkalian dengan 0x02 dengan alasan optimasi. Perkalian tersebut dapat dilakukan dengan memanfaatkan sifat matriks pengali pada inverse mix column yang dapat dilihat pada Persamaan 7. Pada persamaan tersebut, A adalah matriks pengali untuk mix column dan A-1 adalah matriks pengali untuk inverse mix column.
[
]
(7)
Dari Persamaan 7, dapat dilihat bahwa matriks mix column merupakan faktor dari matriks inverse mix column. Oleh karena itu, fungsi inverse mix column memanggil fungsi mix column untuk membantu proses komputasi. IV. PENGUJIAN DAN EVALUASI Perangkat lunak akan diuji kebenaran dan kecepatannya. Pengujian dilakukan menggunakan bantuan SPOJ dan secara manual. A.
Pengumpulan ke SPOJ Uji coba dilakukan dengan menggugah kode program hasil implementasi artikel ini pada salah satu soal di SPOJ yang
4
berjudul "AES64KE" [7]. Jika hasil keluaran program sesuai dengan ketentuan pada soal, maka situs SPOJ akan menampilkan umpan balik berupa tulisan "Accepted", tetapi jika sebaliknya, maka akan muncul umpan balik berupa tulisan "Time Limit Exceeded", "Wrong Answer", atau "Runtime Error". Masukan yang digunakan pada uji coba ini memiliki batas ukuran cipher key dan data sebanyak 65536 bit, tetapi uji coba dilakukan berkali-kali sesuai dengan batasan tersebut. Dari uji coba ini, didapatkan bahwa kode program hasil implementasi artikel mendapat umpan balik "Accepted" seperti pada Gambar 8 yang berarti program berjalan dengan benar dengan menggunakan memori sebesar 3,7 Megabyte. Dalam pengumpulan kode sumber ke SPOJ tersebut, terlihat bahwa waktu proses program adalah 0,30 detik. Waktu proses tersebut bergantung pada tingkat kesibukan server [8]. B.
Pengujian Manual Pada pengujian kali ini, yang akan diuji adalah kebenaran dari proses dekripsi. Pengujian ini dilakukan dengan cara mengenkripsi sembarang berkas, kemudian mendekripsi berkas tersebut. Berkas yang digunakan adalah sebuah berkas acak berukuran 65536 kilobit. Cipher key yang digunakan adalah cipher key acak berukuran 65536 kilobit. Gambar 9 adalah bagian awal dari berkas yang akan dienkripsi. Gambar 10 adalah bagian awal dari cipher key. Gambar 11 adalah bagian awal berkas setelah dienkripsi. Gambar 12 adalah pembuktian bahwa berkas awal dan berkas setelah dienkripsi dan didekripsi adalah sama. Berkas pada Gambar 9, Gambar 10, dan Gambar 11 dibuka menggunakan Free Hex Editor Neo 4.97. Gambar 12 merupakan hasil dari perintah file compare (fc) pada Command Prompt. Berikutnya, akan diuji pengaruh ukuran masukan terhadap kecepatan program. Pertama-tama, ukuran cipher key yang digunakan selalu tetap, yaitu 4096 bit. Hasil percobaan dapat dilihat pada Tabel 2. Dari Tabel 2, terlihat bahwa bertambahnya waktu proses dipengaruhi oleh bertambahnya ukuran data yang akan dienkripsi. Pengaruh dari ukuran data terhadap waktu proses adalah linear. Berikutnya, ukuran data yang akan dienkripsi adalah 262144 bit. Hasil percobaan dapat dilihat pada Tabel 3. Berdasarkan Tabel 3, waktu proses juga dipengaruhi oleh bertambahnya ukuran cipher key. Pengaruh dari ukuran cipher key terhadap waktu proses adalah linear. V. KESIMPULAN Dari hasil uji coba yang telah dilakukan terhadap program enkripsi dan dekripsi AES dengan menggunakan Rijndael key expansion dapat diambil kesimpulan sebagai berikut: 1. Algoritma Rijndael dapat menerima ukuran cipher key yang lebih besar daripada 256 bit dan kebenaran enkripsi terjamin ketika ukuran cipher key kurang dari atau sama dengan 65536 bit. 2. Kecepatan enkripsi AES dipengaruhi secara linear oleh besar data dan besar cipher key sehingga kompleksitas waktunya adalah (Nb*Nk). 3. Penambahan cipher key lebih berefek terhadap waktu proses daripada penambahan data.
JURNAL TEKNIK POMITS Vol. 2, No. 1, (2013) ISSN: 2337-3539 (2301-9271 Print)
5
DAFTAR PUSTAKA Gambar 8. Umpan balik dari SPOJ
[1] Federal Information Processing Standards, DATA ENCRYPTION STANDARD (DES), 1999. [2] Howard M. Heys, A Tutorial on Linear and Differential Cryptanalysis, 2002. [3] Federal Information Processing Standards, ADVANCED ENCRYPTION STANDARD (AES), 2001. [4] Joan Daemen and Vincent Rijmen, The Design of Rijndael : AES - The Advanced Encryption Standard. Verlag, Germany: Springer, 2002.
Gambar 9. Bagian awal berkas data
[5] Murrae Bowden, Moore’s Law and the Technology S-Curve, 2004. [6] Vincent Rijmen, Aleksandra Sowa Hans Dobbertin, Advanced Encryption Standard - AES, 4th ed. Bonn, Germany, 2004. [7] SPOJ. Sphere Online Judge. [Online]. http://www.spoj.com/problems/AES64KE/ [8] SPOJ. Sphere Online Judge. [Online]. http://www.spoj.com/status/AES64KE,amagi/
Gambar 10. Bagian awal cipher key
Gambar 11. Bagian awal cipher text
Gambar 12. Hasil komparasi
Percobaan 1 2 3 4 5 6 7 8 9 10
Percobaan 1 2 3 4 5 6 7 8 9 10
Tabel 2. Pengaruh ukuran data terhadap waktu Ukuran Data (byte) Waktu (milidetik) 65536 327 131072 624 196608 905 262144 1216 327680 1544 393216 1825 458752 2106 524288 2449 589824 2730 655360 3010 Tabel 3. Pengaruh ukuran cipher key terhadap waktu Ukuran Cipher Key (byte) Waktu (milidetik) 1024 296 2048 592 3072 873 4096 1170 5120 1450 6144 1731 7168 2028 8192 2293 9216 2589 10240 2886
UCAPAN TERIMA KASIH Penulis G. C. G. mengucapkan terima kasih kepada Tuhan, orangtua, dosen pembimbing, seluruh dosen Teknik Informatika ITS, kerabat dekat, serta berbagai pihak yang telah membantu penulis dalam menyelesaikan penelitian ini.
