i
SIMULASI PENCARIAN KUNCI PRIVAT DENGAN ALGORITMA SILVER-POHLIG-HELLMAN PADA ALGORITMA KRIPTOGRAFI ELGAMAL
DRAFT SKRIPSI
ARIFIN 101401024
PROGRAM STUDI S-1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015
Universitas Sumatera Utara
ii
SIMULASI PENCARIAN KUNCI PRIVAT DENGAN ALGORITMA SILVER-POHLIG-HELLMAN PADA ALGORITMA KRIPTOGRAFI ELGAMAL
DRAFT SKRIPSI
Diajukan untuk melengkapi tugas akhir dan memenuhi syarat memperoleh ijazah Sarjana Ilmu Komputer
ARIFIN 101401024
PROGRAM STUDI S-1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015
Universitas Sumatera Utara
iii
PERSETUJUAN
Judul
: SIMULASI
PENCARIAN
DENGAN
ALGORITMA
KUNCI
PRIVAT
SILVER-POHLIG-
HELLMAN PADA ALGORITMA KRIPTOGRAFI ELGAMAL Kategori
: SKRIPSI
Nama
: ARIFIN
Nomor Induk Mahasiswa
: 101401024
Program Studi
: SARJANA (S1) ILMU KOMPUTER
Departemen
: ILMU KOMPUTER
Fakultas
: ILMU KOMPUTER DAN TEKNOLOGI INFORMASI (FASILKOM-TI)
Komisi Pembimbing
:
Pembimbing 2
Pembimbing 1
M. Andri Budiman, ST, M.Comp.Sc, MEM MT, MM NIP.197510082008011011
Dr. Elviawaty Muisa Zamzami, ST, NIP.197007162005012002
Diketahui/Disetujui oleh Program Studi S1 Ilmu Komputer Ketua,
Dr. Poltak Sihombing, M.Kom NIP.196203171991021001
Universitas Sumatera Utara
iv
PERNYATAAN SIMULASI PENCARIAN KUNCI PRIVAT DENGAN ALGORITMA SILVER POHLIG HELLMAN PADA ALGORITMA KRIPTOGRAFI ELGAMAL
SKRIPSI
Saya menyatakan bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, April 2015
Arifin 101401024
Universitas Sumatera Utara
v
PENGHARGAAN
Segala puji dan syukur bagi Allah SWT, atas segala limpahan 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. Tidak lupa juga shalawat dan salam kepada tauladan umat Rasululloh Muhammad SAW. Ucapan terima kasih penulis sampaikan kepada: 1.
Ibu Dr. Elviawaty Muisa Zamzami, ST, MT, MM selaku dosen pembimbing I yang telah memberikan bimbingan, kritik, dan saran kepada penulis dalam menyelesaikan skripsi ini
2.
Bapak M. Andri Budiman, ST, M.Comp.Sc, MEM selaku dosen pembimbing II yang memberikan bimbingan, kritik, saran dan dukungan kepada penulis mulai dari tahap pengambilan judul skripsi hingga penulis menyelesaikan skripsi ini.
3.
Ibu Maya Silvi Lydia, B.Sc, M.Sc selaku Sekretaris Program Studi S1 Ilmu Komputer Universitas Sumatera Utara, dosen pembanding I, dan dosen pembimbing akademik yang telah memberikan kritik dan saran guna memperbaiki kesalahan yang ada pada skripsi ini
4.
Ibu Dian Rachmawati, S.Si, M.Kom selaku dosen pembanding II yang telah memberikan kritik dan saran guna memperbaiki kesalahan yang ada pada skripsi ini.
5.
Bapak Prof.Dr.Muhammad Zarlis, selaku Dekan Fakultas Ilmu Komputer dan Teknologi Informasi, Universitas Sumatera Utara
6.
Bapak Dr. Poltak Sihombing, M.Kom selaku Ketua Program Studi S1 Ilmu Komputer Universitas Sumatera Utara.
7.
Ibunda Rostina yang karenanya penulis bisa menjalani kehidupan hingga tahap ini dan Ayahanda Alm. Ari Suis Rawan, seorang ayah yang sangat bertanggung jawab dan telah menjadi penopang kehidupan keluarga hingga akhir hayatnya.
8.
Seluruh dosen dan pegawai Program studi S1 Ilmu Komputer Fasilkom-TI USU.
9.
Sahabat-sahabat terdekat 2010 Sutandi, Samsul, Azizah, Uun, Yayang, Wahyu, Gunalan, Saddam, Yudha, Edo, dan Adit yang selalu menemani penulis dalam perkuliahan.
Universitas Sumatera Utara
vi
10. Rekan-rekan asisten laboratorium khususnya Eko Verdianto, Ramruddin, Al Mizfar, Angga, Agung, Cholik, Asrul, Nihe, Risky, Heru, Andhika, Mifta, Gina, Dina, Indri yang telah lama menemani penulis dalam menjalani aktivitas laboratorium. 11. Keluarga IKLC, dan UKMI Al-Khuwarizmi yang telah memberikan tempat bagi penulis untuk diterima dan selalu memberikan semangat dalam menjalani perkuliahan. 12. Adik-adik praktikkan khususnya Lala, Fikri, Azwar, Ikhsan, Ismail, Tari, Nurul, Bunga, Kh Nisa dan lainnya yang telah berbagi canda tawa kepada penulis semasa kegiatan praktikum. Semoga Allah SWT melimpahkan berkah kepada semua pihak yang telah memberikan bantuan, perhatian, serta dukungan kepada penulis dalam menyelesaikan skripsi ini. Penulis menyadari bahwa skripsi ini masih jauh dari sempurna untuk itu penulis menerima kritik dan saran yang membangun agar dapat menyempurnakan skripsi ini. Akhirnya, semoga skripsi ini bermanfaat bagi pribadi, keluarga, masyarakat, organisasi dan negara.
Medan, April 2015
Penulis
Universitas Sumatera Utara
vii
ABSTRAK
Algoritma kriptografi ElGamal merupakan salah satu algoritma kriptografi asimetris yang menggunakan sepasang kunci, yaitu kunci publik yang digunakan dalam proses enkripsi pesan, dan kunci privat yang digunakan dalam proses dekripsi pesan. Kunci publik dapat diketahui oleh siapa saja yang ingin mengirimkan pesan secara terenkripsi kepada pemilik kunci, sedangkan kunci privat harus dirahasiakan sehingga pemilik kunci adalah satu-satunya orang yang dapat mendekripsi pesan yang telah terenkripsi. Keamanan algoritma kriptografi ElGamal didasarkan pada sulitnya memecahkan logaritma diskrit dalam sebuah grup perkalian yang besar. Algoritma Silver-Pohlig-Hellman merupakan salah satu algoritma yang digunakan untuk menyelesaikan permasalahan logaritma diskrit. Pada penelitian ini, penulis akan melakukan uji coba penggunaan algoritma Silver-Pohlig-Hellman dalam memecahkan kunci privat ElGamal berdasarkan kunci publik yang telah diketahui. Dalam penelitian ini, dilakukan pengujian pemecahan kunci privat terhadap kunci publik dengan panjang yang berbeda. Hasil dari pengujian menunjukkan bahwa semakin panjang kunci publik yang digunakan, maka akan semakin lama waktu yang dibutuhkan untuk memecahkan kunci privat menggunakan algoritma Silver-Pohlig-Hellman.
Kata kunci : Kriptografi, Kriptanalisis, Logaritma Diskrit, Hacking, ElGamal, SilverPohlig-Hellman.
Universitas Sumatera Utara
viii
SIMULATION OF PRIVATE KEY SEARCHING USING SILVER-POHLIGHELLMAN ALGORITHM ON ELGAMAL CRYPTOGRAPHY ALGORITHM
ABSTRACT ElGamal cryptography algorithm is one of the asymmetric cryptographic algorithm which uses a pair of keys; public key used in the message encryption process and private key used in the message decryption process. The public key can be known by anyone who wants to send an encrypted message to the key owner, while the private key must be kept secret so that the key owner is the only person that can decrypt the message which has been encrypted. Security of ElGamal cryptography algorithm is based on the difficulty of solving the discrete logarithm in a large group multiplication. Silver-Pohlig-Hellman Algorithm is one of the algorithms used to solve the discrete logarithm problem. In this study, the authors will do the test of the use of Silver-Pohlig-Hellman algorithm in solving the ElGamal private key based on the known public key. In the test, used the private key solving data collection from the different public key length. The results of the test showed that the longer the public key used, the longer it takes to solve the private key using the Silver-Pohlig-Hellman algorithm.
Keyword: Cryptography, Cryptanalisis, Discrete Log, Hacking, ElGamal, SilverPohlig-Hellman
Universitas Sumatera Utara
ix
DAFTAR ISI
PERSETUJUAN ........................................................................................................... iii PERNYATAAN ........................................................................................................... iv PENGHARGAAN ......................................................................................................... v ABSTRAK ................................................................................................................... vii ABSTRACT ................................................................................................................ viii DAFTAR ISI ................................................................................................................. ix DAFTAR TABEL ........................................................................................................ xii DAFTAR GAMBAR .................................................................................................. xiii DAFTAR LAMPIRAN ................................................................................................ xv BAB 1 ............................................................................................................................ 1 1.1 Latar Belakang ..................................................................................................... 1 1.2 Rumusan Masalah ................................................................................................ 2 1.3 Batasan Masalah ................................................................................................... 2 1.4 Tujuan Penelitian.................................................................................................. 2 1.5 Manfaat Penelitian................................................................................................ 2 1.6 Metodologi Penelitian .......................................................................................... 3 1.7 Sistematika Penulisan ........................................................................................... 4 BAB 2 ............................................................................................................................ 5 2.1 Kriptografi ............................................................................................................ 5 2.2 Sistem Kriptografi ................................................................................................ 5 2.3 Jenis Sistem Kriptografi Berdasarkan Kunci yang Digunakan ............................ 5 2.3.1 Sistem Kriptografi Kunci Simetris ................................................................ 6 2.3.2 Sistem Kriptografi Kunci Asimetris ............................................................. 6 2.4 Matematika untuk Sistem Kriptografi Asimetris ................................................. 7 2.4.1 Greatest Common Divisor (GCD) dan Algoritma Euclid ............................. 8 2.4.2. Relatif Prima ................................................................................................. 8 2.4.3 Aritmatika Modular dan Kongruensi ............................................................. 8 2.4.4 Inversi Modulo............................................................................................... 9
Universitas Sumatera Utara
x
2.4.5 Grup Perkalian ............................................................................................... 9 2.4.6 Bilangan Prima .............................................................................................. 9 2.4.7 Fermat‟s Little Theorem ................................................................................ 9 2.4.8 Fungsi ϕ Euler.............................................................................................. 10 2.4.9 Akar Primitif ................................................................................................ 10 2.4.10. Algoritma Miller-Rabin ............................................................................ 10 2.4.11 Discrete Log Problem ................................................................................ 11 2.4.12 Chinese Remainder Theorem .................................................................... 11 2.5 Sistem Kriptografi ElGamal ............................................................................... 11 2.5.1 Algoritma ElGamal ...................................................................................... 12 2.5.2 Contoh Penerapan Algoritma Kriptografi ElGamal .................................... 13 2.6 Kriptanalisis ....................................................................................................... 14 2.7 Algoritma Silver-Pohlig-Hellman ...................................................................... 15 2.8 Tinjauan Penelitian yang Relevan ...................................................................... 18 BAB 3 .......................................................................................................................... 19 3.1. Analisis Sistem .................................................................................................. 19 3.1.1. Analisis Masalah......................................................................................... 19 3.1.2. Analisis Kebutuhan Sistem ......................................................................... 20 3.1.3 Analisis Pemodelan Sistem.......................................................................... 21 3.2 Perancangan Sistem............................................................................................ 30 3.2.1. Rancangan Perancangan Graphical User Interface. ................................... 30 3.2.2. Pseudocode ................................................................................................. 37 BAB 4 .......................................................................................................................... 45 4.1 Implementasi Sistem .......................................................................................... 45 4.1.1 Tab Bangkitkan Kunci ................................................................................. 45 4.1.2 Tab Enkripsi................................................................................................. 46 4.1.3 Tab Dekripsi ................................................................................................ 47 4.1.4 Tab Hack ...................................................................................................... 48 4.2. Pengujian Sistem ............................................................................................... 48 4.2.1 Pengujian Proses Pembangkitan Kunci ....................................................... 49 4.2.2 Pengujian Proses Enkripsi Pesan ................................................................. 50 4.2.3 Pengujian Proses Dekripsi Pesan ................................................................. 51 4.2.4 Pengujian Proses Hacking Kunci Privat. ..................................................... 53
Universitas Sumatera Utara
xi
4.3 Perbandingan Panjang Digit Kunci dengan Lama Waktu Hack ........................ 55 4.3.1. Grafik Rata-rata Waktu Pemecahan Kunci terhadap Panjang Kunci p ...... 58 BAB 5 .......................................................................................................................... 60 5.1 Kesimpulan......................................................................................................... 60 5.2 Saran ................................................................................................................... 60 DAFTAR PUSTAKA .................................................................................................. 62
Universitas Sumatera Utara
xii
DAFTAR TABEL
Tabel 2.1 Kode ASCII dari plaintext ........................................................................... 13 Tabel 2.2 Ciphertext 2, hasil enkripsi dari plaintext „mundur‟ .................................... 14 Tabel 2.3 Hasil dekripsi dari ciphertext ....................................................................... 14 Tabel 4.1 Hasil enkripsi pesan „utara‟ ......................................................................... 51 Tabel 4.2 Hasil dekripsi ciphertext .............................................................................. 52 Tabel 4.3 Pengujian pemecahan kunci dengan panjang kunci 4 digit ......................... 55 Tabel 4.4 Pengujian pemecahan kunci dengan panjang kunci 6 digit ......................... 56 Tabel 4.5 Pengujian pemecahan kunci dengan panjang kunci 8 digit ......................... 56 Tabel 4.6 Pengujian pemecahan kunci dengan panjang kunci 10 digit ....................... 57 Tabel 4.7 Pengujian pemecahan kunci dengan panjang kunci 12 digit ....................... 57 Tabel 4.8 Rata-rata Pemecahan Kunci terhadap Panjang kunci p ............................... 58
Universitas Sumatera Utara
xiii
DAFTAR GAMBAR
Gambar 2.1 Diagram sistem kriptografi kunci simetris ................................................. 6 Gambar 2.2 Diagram sistem kriptografi kunci asimetris ............................................... 7 Gambar 2.3 Diagram proses sistem kriptografi ElGamal ............................................ 12 Gambar 3.1 Diagram Ishikawa Masalah Penelitian ..................................................... 19 Gambar 3.2 Model Sistem ........................................... Error! Bookmark not defined. Gambar 3.3 Use case diagram. .................................... Error! Bookmark not defined. Gambar 3.4 Sequence diagram bangkitkan kunci ....... Error! Bookmark not defined. Gambar 3.5 Sequence diagram Enkripsi Pesan ........... Error! Bookmark not defined. Gambar 3.6 Sequence diagram Dekripsi Pesan ........... Error! Bookmark not defined. Gambar 3.7 Sequence diagram Hack ........................... Error! Bookmark not defined. Gambar 3.8 Diagram Aktivitas Bangkitkan Kunci ...... Error! Bookmark not defined. Gambar 3.9 Diagram Aktivitas Enkripsi Pesan ........... Error! Bookmark not defined. Gambar 3.10 Diagram Aktivitas Dekripsi Ciphertext . Error! Bookmark not defined. Gambar 3.11 Diagram Aktivitas Pecahkan Kunci Privat ........... Error! Bookmark not defined. Gambar 3.12 Rancangan Tampilan Tab Bangkitkan Kunci ....... Error! Bookmark not defined. Gambar 3.13 Rancangan Tampilan Tab Enkripsi ........................................................ 34 Gambar 3.14 Rancangan Tampilan Tab Dekripsi ........................................................ 35 Gambar 3.15 Rancangan Tampilan Tab Hack ............................................................. 36 Gambar 4.1 Tab Generate Key .................................................................................... 45 Gambar 4.2 Tab Enkripsi ............................................................................................. 46 Gambar 4.3 Tab Dekripsi ............................................................................................. 47 Gambar 4.4 Tab Hack .................................................................................................. 48 Gambar 4.5 Pengujian pembangkitan kunci ElGamal ................................................. 49 Gambar 4.6 Pengujian enkripsi pesan ElGamal........................................................... 50 Gambar 4.7 Pengujian dekripsi pesan ElGamal........................................................... 52 Gambar 4.8 Pengujian hack kunci ElGamal ................................................................ 53 Gambar 4.9 Grafik Waktu Pembangkitan Kunci ......................................................... 58 Gambar 4.10 Grafik Waktu Pemecahan Kunci Privat ................................................. 59
Universitas Sumatera Utara
xiv
Universitas Sumatera Utara
xv
DAFTAR LAMPIRAN
A. Listing Program B. Curriculum Vitae
A-1 B-1
Universitas Sumatera Utara
