ANALISIS DAN PERBANDINGAN PENGGUNAAN METODE PEMBANGKITAN BILANGAN PRIMA FERMAT DAN LUCAS-LEHMER DALAM KRIPTOGRAFI ELGAMAL
SKRIPSI
RATNANINGTYAS YOGA WIJAYANTI 081401011
PROGRAM STUDI S1 ILMU KOMPUTER DEPARTEMEN ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2013
ANALISIS DAN PERBANDINGAN PENGGUNAAN METODE PEMBANGKITAN BILANGAN PRIMA FERMAT DAN LUCAS-LEHMER DALAM KRIPTOGRAFI ELGAMAL
SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Komputer
RATNANINGTYAS YOGA WIJAYANTI 081401011
PROGRAM STUDI S1 ILMU KOMPUTER DEPARTEMEN ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2013
PERSETUJUAN
Judul
Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: ANALISIS DAN PERBANDINGAN PENGGUNAAN METODE PEMBANGKITAN BILANGAN PRIMA FERMAT DAN LUCAS-LEHMER DALAM KRIPTOGRAFI ELGAMAL : SKRIPSI : RATNANINGTYAS YOGA WIJAYANTI : 081401011 : SARJANA (S1) ILMU KOMPUTER : ILMU KOMPUTER : ILMU KOMPUTER DAN TEKNOLOGI INFORMASI (FASILKOM-TI) UNIVERSITAS SUMATERA UTARA Diluluskan di Medan, 14 Februari 2013
Komisi Pembimbing
:
Pembimbing II,
Pembimbing I,
Amer Sharif, S.Si, M. Kom NIP. -
Dian Rachmawati, S.Si, M.Kom NIP. 198307232009122004
Diketahui/Disetujui oleh Program Studi S1 Ilmu Komputer Ketua,
Dr. Poltak Sihombing, M.Kom NIP. 196203171991031001
PERNYATAAN
ANALISIS DAN PERBANDINGAN PENGGUNAAN METODE PEMBANGKITAN BILANGAN PRIMA FERMAT DAN LUCAS-LEHMER DALAM KRIPTOGRAFI ELGAMAL
SKRIPSI
Saya menyatakan bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, 14 Februari 2013
RATNANINGTYAS YOGA WIJAYANTI 081401011
PENGHARGAAN
Puji dan syukur penulis panjatkan kepada Tuhan Yang Maha Pemurah dan Maha Penyayang dengan limpah karunia-Nya, skripsi ini berhasil diselesaikan dalam waktu yang telah ditetapkan, sebagai syarat untuk memperoleh gelar Sarjana Komputer, Program Studi Ilmu Komputer, Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara. Pada pengerjaan skripsi dengan judul Analisis dan Perbandingan Penggunaan Metode Pembangkitan Bilangan Prima Fermat dan Lucas-Lehmer dalam Kriptografi ElGamal, penulis menyadari banyak pihak yang telah membantu dalam proses pengerjaan skripsi ini. Dalam kesempatan ini, penulis mengucapkan terima kasih kepada: 1. Dekan Fakultas Ilmu Komputer dan Teknologi Informasi, Prof. Dr. Muhammad Zarlis dan Pembantu Dekan Fakultas Ilmu Komputer dan Teknologi Informasi, serta semua dosen dan semua pegawai di Program Studi S1 Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara; 2. Bapak Dr. Poltak Sihombing, M.Kom selaku Ketua Program Studi Ilmu Komputer dan Sekretaris Program Studi Ilmu Komputer, Ibu Maya Silvi Lydia, B.Sc, M.Sc Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara; 3. Ibu Dian Rachmawati, S.Si, M.Kom dan Bapak Amer Sharif, S.Si, M.Kom sebagai dosen pembimbing yang telah memberikan nasehat, arahan, dan saran kepada penulis dalam pengerjaan skripsi ini; 4. Bapak Prof. Dr. Iryanto, M.Si dan Bapak Dr. Poltak Sihombing, M.Kom selaku dosen penguji yang memberikan motivasi, kritik dan saran kepada penulis dalam penyempurnaan skripsi ini; 5. Ibunda Widiningsih, S.Ag dan Ayahanda Suratno yang selalu memberikan motivasi, perhatian, dan memberikan doa yang tulus serta pengorbanan yang tidak ternilai harganya; 6. Adik penulis Saraswati Yoga Andriyani yang selalu memberikan motivasi dan perhatian kepada penulis; 7. Pratama Ekky Putra, S.Kom yang tak pernah lupa memberikan motivasi, semangat, nasehat, dan perhatian kepada penulis; 8. Teman-teman seperjuangan mahasiswa S-1 Ilmu Komputer stambuk 2008 secara khusus kepada Mirnawati, Heny Muliana, S.Kom, Anny Maghfirah, Sadifa Asrofa, S.Kom, serta Octi Fadillah, S.Kom, Gustav Prameswara,
S.Kom, Saria Mahdi, Khairunnisa Lubis, S.Kom, dan Henni Haryani Lubis, S.Kom yang telah memberikan dukungan dan semangat kepada penulis; 9. Serta semua pihak yang telah membantu pengerjaan skripsi ini baik secara langsung maupun tidak langsung yang tidak dapat disebutkan satu per satu. Penulis menyadari bahwa skripsi ini masih jauh dari sempurna, maka penulis menerima kritik dan saran demi penyempurnaan skripsi ini. Semoga skripsi ini membawa manfaat bagi pengembangan ilmu. Medan, 14 Februari 2013
Ratnaningtyas Yoga Wijayanti
ABSTRAK
Keamanan pesan tertulis yang dikirimkan dari satu orang ke orang lain ketika berkomunikasi adalah hal yang penting. Dibutuhkan suatu penerapan untuk mengamankan isi dari pesan yang akan dikirim. Sasaran utama dari kajian ini adalah untuk membangun aplikasi yang dapat merahasiakan pesan yang dikirim. Penelitian ini dibangun dengan bahasa pemograman Java 2.0 dengan editornya adalah Netbeans 6.8 dan menggunakan algoritma kriptografi ElGamal untuk proses enkripsi dan dekripsinya, metode pembangkitan bilangan prima Fermat dan Lucas-Lehmer. Metode Fermat memastikan bilangan yang diperoleh prima, a p-1 mod p = 1, memiliki rentang 1-5000. Jika nilai p yang memiliki digit lebih dari 2 dan angka kedua dari belakang adalah 0 harus dihindari. Metode Lucas-Lehmer berlaku pada bilangan Mersenne (Mp = 2p-1) dengan s := s2 – 2 mod Mp. Bilangan prima yang digunakan lebih besar dari 255 dan nilai kuncinya tidak lebih dari 4 digit. Proses iterasi untuk menentukan kunci p yang tidak memiliki angka kedua dari belakang adalah 0 menyebabkan proses enkripsi metode Fermat lebih lama dibandingkan Lucas-Lehmer, untuk Fermat 5.346267 detik dibandingkan 0.13326 detik untuk Lucas-Lehmer. Pada proses dekripsi, didapatkan hasil rata-rata waktu dekripsi Fermat 0.0041 detik dibandingkan 0.0104 detik waktu dekripsi Lucas-Lehmer, disebabkan karena kunci p yang dipakai dalam Lucas-Lehmer rata-rata lebih besar daripada kunci yang dipakai dalam Fermat. Pada aplikasi ini, proses enkripsi yang lebih cepat adalah metode Lucas-Lehmer sedangkan untuk proses dekripsi yang lebih cepat adalah metode Fermat.
Kata Kunci: ElGamal, Fermat, Kriptografi, Lucas-Lehmer, Mersenne
THE ANALYSIS AND COMPARISON OF FERMAT AND LUCAS-LEHMER PRIME GENERATORS FOR ELGAMAL CRIPTOGRAPHY
ABSTRACT
Security of a written message from one person to another during communication is important. It takes an application to secure the contents of the message to be sent. The main objective of this study is to build an applications that can sent plaintexts. This study was implemented ElGamal cryphtography algorithms for encryption and decryption with Fermat and Lucas-Lehmer prime generator, using Java 2.0 programming language with the Netbeans IDE 6.8. The methods ensure that the Fermat prime numbers obtained, a p-1 mod p = 1, has a range of 1-5000. If the value of p has digits greather than 2 and the penultimate is 0 then it should be avoided. LucasLehmer method only applies to Mersenne numbers (Mp = 2p-1) with s := s2 – 2 mod Mp. Prime numbers used in the application are greater than 255 and the key value should not exceed 4 digits. The iteration to determine the key value of p which does not have 0 as the penultimate number resulted in the Fermat encryption method requiring longer time than Lucas-Lehmer, which is 5.346267 second for Fermat compared to 0.13326 second for Lucas-Lehmer. In the decryption process, the average time obtained for Fermat 0.0041 second for Fermat compared to 0.0104 second for Lucas-Lehmer because the p key used in the Lucas-Lehmer was average larger than the p key used in the Fermat. In this application, the encryption process is faster with the Lucas-Lehmer method, while decryption process is the faster with Fermat method.
Keyword: Cryphtography, ElGamal, Fermat, Lucas-Lehmer, Mersenne numbers
DAFTAR ISI
Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar Daftar Lampiran Bab 1
Bab 2
Pendahuluan 1.1 Latar Belakang Masalah 1.2 Rumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Metode Penelitian 1.7 Sistematika Penulisan Landasan Teori 2.1 Kriptografi 2.1.1 Pengertian Kriptografi 2.1.2 Terminologi Kriptografi 2.1.3 Jenis Algoritma Kriptografi 2.1.3.1 Algoritma Simetris 2.1.3.2 Algoritma Asimetris 2.1.4 Tujuan Kriptografi 2.2 Algoritma ElGamal 2.2.1 Proses Pembentukan Kunci 2.2.1.1 Bilangan Prima Aman 2.2.1.2 Elemen Primitif 2.2.1.3 Proses Pembentukan Kunci 2.2.2 Proses Enkripsi 2.2.3 Proses Dekripsi 2.3 Metode Pembangkit Bilangan Prima Fermat 2.4 Metode Pembangkit Bilangan Prima Lucas-Lehmer
Bab 3 Analisis Dan Perancangan 3.1 Analisis 3.1.1 Analisis Algoritma ElGamal 3.1.2 Analisis Bilangan Prima
ii iii iv vi vii viii x xi xii
1 2 2 3 3 3 4
6 6 7 8 8 10 12 13 14 14 15 16 17 20 22 25
28 29 37
3.1.3 Analisis Metode Pembangkit Bilangan Prima Fermat 3.1.3.1 Analisis Metode Fermat 3.1.3.2 Analisis Fernat Liar 3.1.4 Analisis Metode Pembangkit Bilangan Prima Lucas-Lehmer 3.2 Perancangan Flowchart 3.3 Perancangan DFD (Data Flow Diagram) 3.3.1 DFD Level 0 3.3.2 DFD Level 1 3.3.3 DFD Level 2 Proses Enkripsi 3.3.4 DFD Level 2 Proses Dekripsi 3.4 Perancangan User Interface 3.4.1 Tampilan Menu Utama 3.4.2 Tampilan Menu Proses Enkripsi 3.4.3 Tampilan Menu Proses Dekripsi Bab 4
Implementasi Dan Pengujian Sistem 4.1 Implementasi 4.2 Hasil dan Pembahasan 4.2.1 Enkripsi Menggunakan Metode Pembangkit Bilangan Prima Fermat dan Lucas-Lehmer 4.2.2 Dekripsi Menggunakan Metode Pembangkit Bilangan Prima Fermat dan Lucas-Lehmer 4.2.3 Pembahasan Konsep Kunci p pada Metode Pembangkitan Bilangan Prima Fermat 4.2.4 Pembahasan Keterbatasan Kunci Lucas-Lehmer 4.2.5 Pembahasan Konsep Terkaan Plainteks 4.3 Pengujian 4.4 Tampilan Aplikasi ElGaFerLuLe 4.4.1 Tampilan Awal Aplikasi ElGaFerLuLe 4.4.2 Tampilan Halaman Enkripsi pada Aplikasi ElGaFerLuLe 4.4.3 Tampilan Halaman Dekripsi pada Aplikasi ElGaFerLuLe
37 37 39 40 43 50 50 51 52 56 57 57 58 59
61 61 61 64 66 67 68 70 70 70 71 73
Bab 5 Penutup 5.1 Kesimpulan 5.2 Saran
76 77
Daftar Pustaka
78
DAFTAR TABEL
Tabel
Keterangan
Halaman
2.1
Konversi Karakter Pesan ke Kode ASCII
18
2.2
Proses Enkripsi
19
2.3
Proses Dekripsi
22
3.1
Kode Karakter
31
3.2
Proses Enkripsi
32
3.3
Proses Dekripsi
36
4.1
Hasil Enkripsi
62
4.2
Hasil Dekripsi
64
4.3
Bilangan Mersenne
67
4.4
Hasil Enkripsi dan Dekripsi
69
4.5
Hasil Terkaan Terhadap Plainteks
69
DAFTAR GAMBAR
Gambar 2.1 2.2 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.15 3.16 4.1 4.2 4.3 4.4
4.5 4.6 4.7 4.8
Keterangan Skema Kriptografi Simetri Skema Kriptografi Asimetri Flowchart Metode Pembangkit Bilangan Prima Fermat pada Algoritma ElGamal Flowchart Metode Pembangkit Bilangan Prima Lucas-Lehmer pada Algoritma ElGamal Flowchart Proses Enkripsi Algoritma ElGamal Flowchart Proses Dekripsi Algoritma ElGamal Flowchart Proses Metode Pembangkit Bilangan Prima Fermat Flowchart Proses Metode Pembangkit Bilangan Prima LucasLehmer DFD Level 0 DFD Level 1 Proses Enkripsi DFD Level 1 Proses Dekripsi DFD Level 2 Proses Enkripsi Menggunakan Metode Pembangkitan Bilangan Prima Fermat DFD Level 2 Proses Enkripsi Menggunakan Metode Pembangkitan Bilangan Prima Lucas-Lehmer DFD Level 2 Proses Dekripsi Tampilan Awal Aplikasi ElGaFerLuLe Tampilan Menu Proses Enkripsi Tampilan Menu Proses Dekripsi Tampilan Awal Aplikasi ElGaFerLuLe Tampilan Halaman Enkripsi pada Aplikasi ElGaFerLuLe Tampilan Halaman Enkripsi pada Aplikasi ElGaFerLuLe setelah Melakukan Proses Enkripsi Tampilan Halaman Enkripsi pada Aplikasi ElGaFerLuLe setelah Melakukan Proses Enkripsi dan Melakukan Simpan Hasil Tampilan Halaman Dekripsi Aplikasi ElGaFerLuLe Tampilan Halaman Dekripsi Aplikasi ElGaFerLuLe saat Membuka Hasil Enkripsi yang Telah Disimpan Tampilan Halaman Dekripsi Aplikasi ElGaFerLuLe setelah Melakukan Proses Dekripsi Tampilan Aplikasi ElGaFerLuLe saat User Memilih Tombol Keluar
Halaman 9 10 44 45 46 47 48 49 50 51 51 52 54 56 57 58 59 70 71 72 73
73 74 75 75
LAMPIRAN
Lampiran
Keterangan
Halaman
A
Listing Program
A-1
B
Tabel Kode Karakter
B-1
