IMPLEMENTASI ELLIPTIC CURVE ELGAMAL PUBLIC KEY CRYPTOSYSTEM SEBAGAI PENGAMAN DISTRIBUSI KUNCI DARI BLOCK CIPHER AES SKRIPSI

IMPLEMENTASI ELLIPTIC CURVE ELGAMAL PUBLIC KEY CRYPTOSYSTEM SEBAGAI PENGAMAN DISTRIBUSI KUNCI DARI BLOCK CIPHER AES

SKRIPSI

MUHAMMAD REZA NASUTION 101401028

PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015

Universitas Sumatera Utara


SKRIPSI

Diajukan untuk melengkapi tugas akhir dan memenuhi syarat mencapai gelar Sarjana Komputer

MUHAMMAD REZA NASUTION 101401028

PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015


ii

PERSETUJUAN

Judul

: IMPLEMENTASI ELLIPTIC CURVE ELGAMAL PUBLIC KEY CRYPTOSYSTEM SEBAGAI PENGAMAN DISTRIBUSI KUNCI DARI BLOCK CIPHER AES

Kategori

: SKRIPSI

Nama

: MUHAMMAD REZA NASUTION

Nomor Induk Mahasiswa

: 101401028

Program Studi

: S1 ILMU KOMPUTER

Fakultas

: ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA Diluluskan di Medan, Juli 2015

Komisi Pembimbing

:

Pembimbing 2

Pembimbing 1

Herriyance, ST., M.Kom

M. Andri Budiman, ST., M.Comp.Sc., MEM

NIP. 198010242010121002

NIP. 197510082008011011

Diketahui/disetujui oleh Program Studi S1 Ilmu Komputer Ketua,

Dr. Poltak Sihombing, M.Kom NIP. 196203171991031001


iii

PERNYATAAN


SKRIPSI

Saya mengakui bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing telah disebutkan sumbernya.

Medan, Juli 2015

Muhammad Reza Nasution 101401028


iv

PENGHARGAAN

Alhamdulillah. Puji dan syukur kehadirat Allah SWT yang dengan rahmat dan karunia-Nya penulis dapat menyelesaikan penyusunan skripsi ini, sebagai syarat untuk memperoleh gelar Sarjana Komputer pada Program Studi S1 Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara. Pada pengerjaan skripsi dengan judul Implementasi Elliptic Curve ElGamal Public Key Cryptosystem sebagai Pengaman Distribusi Kunci dari Block Cipher AES, penulis menyadari bahwa banyak pihak-pihak yang turut membantu, baik dari keluarga, sahabat, dan orang-orang terkasihi yang memotivasi dalam proses pengerjaannya. Dalam kesempatan ini, penulis mengucapkan terima kasih kepada: 1. Bapak Prof. Subhilhar MA, Ph.D selaku Pejabat Rektor Universitas Sumatera Utara. 2. Bapak Prof. Dr. Muhammad Zarlis selaku Dekan Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara. 3. Bapak Dr. Poltak Sihombing, M.Kom selaku Ketua Program Studi S1 Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara dan Dosen Pembanding I. 4. Bapak M. Andri Budiman, ST., M.Comp.Sc., MEM selaku Dosen Pembimbing I yang telah banyak memberikan masukan dan saran kepada penulis dalam mendesain algoritma kriptografi yang diangkat menjadi judul skripsi ini. 5. Bapak Herriyance, ST., M.Kom selaku Dosen Pembimbing II yang telah banyak memberikan arahan, kritik dan saran kepada penulis dalam pengerjaan skripsi ini. 6. Ibu Maya Silvi Lydia B.Sc., M.Sc. selaku Dosen Pembanding II yang telah banyak memberikan arahan dan masukan yang sangat berharga kepada penulis. 7. Ayahanda Darwin Nasution dan Ibunda Wini Astuti yang mana telah banyak memberikan kasih sayang, semangat, serta dorongan kepada penulis. 8. Seluruh tenaga pengajar dan pegawai di Fakultas Ilmu Komputer dan Teknologi Informasi USU, terutama kepada Ibu Dian Rachmawati, S.Si., M.Kom yang telah memberikan ide pemilihan judul skripsi ini.


v

9. Kekasih tercinta Indah Dwi Yanti Purba yang selalu memberikan dorongan motivasi dan semangat demi terselesainya skripsi ini. 10. Teman-teman seperjuangan, khususnya kepada Ahmad Rasyidi, Mego Suntoro, Dwi Rizky Ananda, Imam Matra, Irwansyah, Safriatullah, Andri Agasi, Arif Tri Hidayat, Arifin, Wahyu Eko Putra, serta seluruh Stambuk 2010 yang tidak dapat disebut satu-persatu, yang telah banyak membantu dalam selesainya pengerjaan skripsi ini. 11. Semua pihak yang terlibat langsung maupun tidak langsung yang tidak dapat penulis ucapkan satu demi satu yang telah membantu penyelesaian laporan ini. Semoga Allah SWT melimpahkan berkah kepada kalian semua yang telah memberikan bantuan, perhatian, serta dukungan kepada penulis dalam menyelesaikan skripsi ini.

Medan, Juli 2015 Penulis,

Muhammad Reza Nasution


vi

ABSTRAK

Kriptografi kunci publik (asimetri) yang umum digunakan, seperti RSA dan ElGamal membutuhkan kunci privat minimal sebesar 1024 sampai dengan 3072 bit untuk bisa mengenkripsi pesan dengan aman (Paar, 2010). Dengan ukuran kunci sebesar ini, tentu tidak efisien jika komputasi diterapkan pada hardware dengan spesifikasi terbatas. Kriptografi kunci publik yang berdasarkan pada kurva eliptik, seperti kriptografi ElGamal Kurva Eliptik hadir dengan kelebihan ukuran kunci privat yang jauh lebih kecil, namun menghasilkan tingkat keamanan yang sama. Pesan rahasia yang dienkripsi menggunakan kriptografi kurva eliptik sebesar 160 bit setara keamanannya dengan kunci RSA sebesar 1024 bit, di mana perbandingannya sekitar 1:6 (Paar, 2010). Dengan kelebihan ini, implementasi algoritma kriptografi kurva eliptik dapat menghemat penggunaan resource dan waktu proses yang cukup besar, sehingga dapat dijalankan pada smartphone yang saat ini banyak digunakan oleh masyarakat. Di sisi lain, kriptografi asimetri memerlukan waktu enkripsi yang jauh lebih besar dibandingkan dengan kriptografi simetri. Namun saat pengiriman, pesan acak hasil enkripsi menggunakan kriptografi simetri harus dikirim beserta kuncinya (bersifat rahasia) agar dapat didekripsi kembali. Dengan menerapkan kombinasi dari kriptografi simetri yang unggul dalam kecepatan proses dan kriptografi asimetri yang unggul dalam tingkat keamanan akan menghasilkan sistem keamanan data yang handal, di mana pesan yang akan dikirim dienkripsi terlebih dahulu menggunakan algoritma kriptografi AES (Advanced Encryption Standard), kemudian kuncinya akan dienkripsi kembali menggunakan algoritma kriptografi ElGamal Kurva Eliptik, sehingga pesan acak dan kunci acak yang dihasilkan dapat dikirim dengan aman. Hasil pengujian sistem dengan pesan sebesar 3.2 MB yang dienkripsi menggunakan kunci sebesar 32 byte, dan persamaan kurva eliptik 𝐴 = 190460112, 𝐵 = 187944061, dan 𝔽𝑝 = 682782445026322639, memerlukan waktu sekitar 19 detik. Kata kunci: Kriptografi Kurva Eliptik, ElGamal Kurva Eliptik, Rijndael, AES, MillerRabin.


vii

IMPLEMENTATION OF ELLIPTIC CURVE ELGAMAL PUBLIC KEY CRYPTOSYSTEM AS KEY EXCHANGE OF AES (ADVANCED ENCRYPTION STANDARD) BLOCK CIPHER

ABSTRACT

Public key cryptography (asymmetric) is commonly used, such as RSA and ElGamal requires a minimum private key of 1024 up to 3072 bits to be able encrypting messages securely (Paar 2010). With a key measure of this magnitude, certainly not efficient when applied to computing hardware with limited specifications. Public key cryptography based on elliptic curves, such as Elliptic Curve cryptography ElGamal comes with oversized private keys are much smaller, but it produces the same level of security. Secret message encrypted using elliptic curve cryptography equivalent of 160 bits of security with RSA keys of 1024 bits, in which the ratio of about 1: 6 (Paar 2010). With these advantages, the implementation of elliptic curve cryptography algorithms can save resource usage and processing time is quite large, so it can run on a smartphone that is currently widely used by the public. On the other hand, asymmetric cryptography encryption takes far greater than the symmetric cryptography. But when shipping, cipher encrypted using symmetric cryptography should be sent along with the key (confidential) that can be decrypted back. By applying a combination of symmetric cryptography is superior in asymmetric cryptographic processing speed and superior in security levels will produce reliable data security system, in which the messages to be sent encrypted first using a cryptographic algorithm AES (Advanced Encryption Standard), then the key will be encrypted re-use Elliptic Curve ElGamal cryptographic algorithm, so that the cipher and cipher-key can be sent securely. Results of testing the system with the message of 3.2 MB which is encrypted using a key of 32 bytes, and an elliptic curve 𝐴 = 190460112, 𝐵 = 187944061, and 𝐹𝑝 = 682782445026322639, takes about 19 seconds. Keywords: Elliptic Curve Cryptography, Elliptic Curve ElGamal, Rijndael, Advanced Encryption Standard, Miller-Rabin.


viii

DAFTAR ISI

Hal PERSETUJUAN ............................................................................................................ ii PERNYATAAN ........................................................................................................... iii PENGHARGAAN ........................................................................................................ iv ABSTRAK .................................................................................................................... vi ABSTRACT ................................................................................................................. vii DAFTAR ISI ............................................................................................................... viii DAFTAR TABEL ......................................................................................................... xi DAFTAR GAMBAR ................................................................................................... xii DAFTAR LAMPIRAN ............................................................................................... xiv BAB 1: PENDAHULUAN 1.1. Latar Belakang ................................................................................................... 1 1.2. Rumusan Masalah .............................................................................................. 2 1.3. Ruang Lingkup Penelitian.................................................................................. 3 1.4. Tujuan Penelitian ............................................................................................... 3 1.5. Manfaat Penelitian ............................................................................................. 3 1.6. Metodologi Penelitian ........................................................................................ 4 1.7. Sistematika Penulisan ........................................................................................ 4 BAB 2: TINJAUAN PUSTAKA 2.1. Kriptografi.......................................................................................................... 6 2.1.1. Konsep acak (random) ................................................................................. 7 2.1.2. Manajemen kunci ......................................................................................... 8 2.2. Matematika Dasar dalam Kriptografi ................................................................ 8 2.2.1. Keterbagian dan GCD (Greatest Common Divisors) .................................. 9 2.2.2. Aritmatika modular .................................................................................... 12 2.2.3. Bilangan prima, faktorisasi prima, dan finite field.................................... 15 2.3. AES (Advanced Encryption Standard) ............................................................ 16 2.3.1. Matematika pengantar ............................................................................... 17 2.3.2. State, cipher key dan jumlah putaran ........................................................ 20


ix

2.3.3. Enkripsi ...................................................................................................... 21 2.3.4. Dekripsi ...................................................................................................... 25 2.3.5. Key sechedule............................................................................................. 28 2.4. Algoritma Percobaan Bilangan Prima Miller-Rabin........................................ 29 2.5. Elliptic Curve (Kurva Eliptik) ......................................................................... 31 2.5.1. Kurva eliptik dalam finite field .................................................................. 36 2.5.2. Masalah logaritma diskrit kurva eliptik .................................................... 38 2.6. Elliptic Curve ElGamal Public Key Cryptosystem .......................................... 39 BAB 3: ANALISIS DAN PERANCANGAN SISTEM 3.1. Analisis Sistem................................................................................................. 41 3.1.1. Analisis masalah ........................................................................................ 41 3.1.2. Analisis kebutuhan ..................................................................................... 42 3.1.3. Analisis proses ........................................................................................... 42 3.2. Pemodelan Sistem ............................................................................................ 48 3.2.1. Use-case diagram ...................................................................................... 48 3.2.2. Activity diagram ......................................................................................... 55 3.2.3. Sequence diagram ...................................................................................... 56 3.3. Perancangan Sistem ......................................................................................... 56 3.3.1. Perancangan sistem pangkalan data (database) ....................................... 56 3.3.2. Perancangan proses sistem........................................................................ 57 3.3.3. Perancangan antar-muka sistem ............................................................... 58 BAB 4: IMPLEMENTASI DAN PENGUJIAN SISTEM 4.1. Implementasi Sistem ........................................................................................ 65 4.1.1. MainActivity ............................................................................................... 65 4.1.2. MessageFragment ...................................................................................... 66 4.1.3. FileActivity ................................................................................................. 67 4.1.4. MyTopSecretFragment .............................................................................. 67 4.1.5. SettingActivity ............................................................................................ 68 4.1.6. FeedbackFragment .................................................................................... 69 4.1.7. InputKeyDialog .......................................................................................... 69 4.2. Pengujian Sistem.............................................................................................. 70 4.2.1. Pengujian enkripsi teks (plain-text) dan file .............................................. 70 4.2.2. Pengujian pembuatan parameter dan kunci publik ................................... 72 4.2.3. Pengujian enkripsi kunci Rijndael ............................................................. 74


x

4.2.4. Pengujian dekripsi kunci acak (cipher-key) .............................................. 76 4.2.5. Pengujian dekripsi naskah acak (cipher-text dan cipher-file) ................... 76 4.3. Hasil Pengujian ................................................................................................ 78 4.3.1. Hasil pengujian algoritma kriptografi Rijndael ........................................ 78 4.3.2. Hasil pengujian algoritma kriptografi ElGamal kurva eliptik .................. 83 BAB 5: KESIMPULAN DAN SARAN 5.1. Kesimpulan ...................................................................................................... 87 5.2. Saran ................................................................................................................ 88 DAFTAR PUSTAKA .................................................................................................. 89


xi

DAFTAR TABEL

Hal. Tabel 2.1. Tabel 2.2. Tabel 2.3. Tabel 2.4. Tabel 2.5. Tabel 2.6. Tabel 2.7. Tabel 3.1. Tabel 3.2.

Penjumlahan dan perkalian dalam modulo 5 Perkalian group of units modulo 24 Contoh representasi state (𝑁𝑏 = 6) dan cipher key (𝑁𝑘 = 4) Jumlah putaran 𝑁𝑟 sebagai fungsi blok terhadap panjang kunci AES S-Box Besarnya pergeseran baris pada shiftRows terhadap panjang blok AES S-𝐵𝑜𝑥′ Naratif Use-Case Enkripsi Pesan Rahasia dengan AES Naratif Use-Case Mengirim Pesan Acak (Cipher) dan Kunci Acak (Cipher-key) Tabel 3.3. Naratif Use-Case Membangkitkan Kunci Privat Tabel 3.4. Naratif Use-Case Membangkitkan Kunci Publik Tabel 3.5. Naratif Use-Case Membangkitkan Bilangan Prima dengan Metode Miller-Rabin Tabel 3.6. Naratif Use-Case Enkripsi Kunci dengan ElGamal Kurva Eliptik Tabel 3.7. Naratif Use-Case Dekripsi Kunci Acak dengan ElGamal Kurva Eliptik Tabel 3.8. Naratif Use-Case Dekripsi Pesan Acak (Cipher) dengan AES Tabel 4.1. Representasi blok dari kunci dan pesan Tabel 4.2. Expanded key yang dihasilkan dari proses key schedule Tabel 4.3. Proses enkripsi pada Blok 1 Tabel 4.4. Cipher yang dihasilkan proses enkripsi Rijndael Tabel 4.5. Hasil pengujian kecepatan enkripsi/ dekripsi algoritma Rijndael Tabel 4.6. Cipher 𝐶1 dan 𝐶2 yang dihasilkan proses enkripsi ElGamal kurva eliptik Tabel 4.7. Hasil pengujian kecepatan enkripsi/ dekripsi algoritma ElGamal kurva eliptik terhadap ukuran file Tabel 4.8. Hasil pengujian kecepatan enkripsi/ dekripsi algoritma ElGamal kurva eliptik terhadap panjang bit finite field 𝔽𝑝

14 14 21 21 22 22 27 49 50 51 51 52 52 53 54 79 79 79 81 82 83 83 85


xii

DAFTAR GAMBAR

Hal. Gambar 2.1. Gambar 2.2. Gambar 2.3. Gambar 2.4. Gambar 2.5. Gambar 2.6. Gambar 2.7. Gambar 3.1. Gambar 3.2.

Flowchart algoritma enkripsi AES Flowchart algoritma dekripsi AES Dua contoh kurva eliptik Hukum penambahan pada kurva eliptik Penambahan titik 𝑃 dengan dirinya sendiri Garis vertikal 𝐿 yang melalui 𝑃(𝑎, 𝑏) dan 𝑃′(𝑎, −𝑏) Sistem kriptografi kunci publik ElGamal kurva eliptik Diagram Ishikawa untuk menganalisis masalah Analisis proses terhadap input yang diterima dan output yang dihasilkan Gambar 3.3. Blok dari kunci "Muhammad_RezΔNst" Gambar 3.4. Flowchart proses Rijndael Gambar 3.5. Diagram use-case sistem keamanan data Gambar 3.6. Diagram activity sistem keamanan data Gambar 3.7. Diagram sequence sistem keamanan data Gambar 3.8. Entity Relationship Diagram (ERD) sistem keamanan data Gambar 3.9. Physical DFD sistem keamanan data Gambar 3.10. Desain MainActivity Gambar 3.11. Desain MessageFragment Gambar 3.12. Desain FileActivity Gambar 3.13. Desain MyTopSecretFragment Gambar 3.14. Desain SettingActivity Gambar 3.15. Desain FeedbackFragment Gambar 3.16. Desain KeyInputDialog Gambar 4.1. MainActivity yang memiliki navigation drawer dan option menu Gambar 4.2. MessageFrament yang muncul saat memilih menu Message Gambar 4.3. FileActivity yang menampilkan seluruh file Gambar 4.4. MyTopSecretFragment yang menampilkan seluruh cipher-file Gambar 4.5. SettingActivity untuk melakukan pengaturan Gambar 4.6. FeedbackFragment untuk mengirim umpan-balik pengguna Gambar 4.7. InputKeyDialog untuk menerima input kunci Rijndael Gambar 4.8. Proses enkripsi teks (plain-text) pada MessageFragment Gambar 4.9. Proses enkripsi file pada FileActivity Gambar 4.10. Enkripsi file 𝑡𝑒𝑠𝑡. 𝑡𝑥𝑡 menghasilkan cipher-file 𝑡𝑒𝑠𝑡. 𝑧𝑎𝑖𝑛 Gambar 4.11. Proses pengiriman permintaan parameter publik dari pengirim Gambar 4.12. Pengiriman permintaan parameter publik melalui e-mail

25 26 31 31 33 34 40 41 43 44 46 49 55 56 57 58 59 60 61 62 63 63 64 66 66 67 68 68 69 69 71 71 72 73 73


xiii

Gambar 4.13. Pembangkitan parameter publik dengan tingkat keamanan Normal Gambar 4.14. Pengiriman pesan acak (cipher-text) kepada penerima Gambar 4.15. E-mail yang berisi pesan acak (cipher-text) dan kunci acak (cipher-key) Gambar 4.16. Hasil dekripsi pesan rahasia mendapatkan kembali pesan asli Gambar 4.17. Proses dekripsi teks acak mendapatkan kembali teks asli Gambar 4.18. Proses dekripsi file acak mendapatkan kembali file asli Gambar 4.19. Grafik perbandingan kecepatan enkripsi dan dekripsi algoritma kriptografi Rijndael terhadap ukuran file dan blok 𝑁𝑏 Gambar 4.20. Grafik perbandingan kecepatan enkripsi dan dekripsi algoritma kriptografi ElGamal kurva eliptik terhadap ukuran file Gambar 4.21. Grafik perbandingan kecepatan enkripsi dan dekripsi algoritma kriptografi ElGamal kurva eliptik terhadap besar finite field 𝔽𝑝

74 75 75 76 77 78 83 85 86


xiv

DAFTAR LAMPIRAN

Hal. Source Codes Curriculum Vitae

90 105


IMPLEMENTASI ELLIPTIC CURVE ELGAMAL PUBLIC KEY CRYPTOSYSTEM SEBAGAI PENGAMAN DISTRIBUSI KUNCI DARI BLOCK CIPHER AES SKRIPSI

Recommend Documents