PROTOKOL PEMILIHAN ELEKTRONIK DENGAN MENGGUNAKAN PASANGAN BILINEAR Tugas Akhir Disusun untuk memenuhi persyaratan kelulusan Program Studi Matematika Institut Teknologi Bandung
Oleh : PATRICK JUN W P G 10103067
PROGRAM STUDI MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT TEKNOLOGI BANDUNG 2010
LEMBAR PENGESAHAN Protokol Pemilihan Elektronik Dengan Menggunakan Pasangan Bilinear Diajukan sebagai syarat kelulusan Program Studi Matematika Institut Teknologi Bandung
Bandung, September 2010 Telah diperiksa dan disetujui oleh
Dr. Rinovia M. G. Simanjuntak Dosen Pembimbing
PROGRAM STUDI MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT TEKNOLOGI BANDUNG 2010
Untuk Amanda Ruth Epiphany Ginting, adikku Aku tahu & percaya Tuhan punya rencana yang luar biasa untukmu, menjadi abangmu adalah suatu kebanggaan bagiku
Mazmur 81 : 2 -17
Abstract Election in conventional way considered to take a lengthy ammount of time and substantial funding. The rapid development in information technology makes experts and many group of people offer a new way in election, which is doing election electronically or called Electronic Voting. Electronic Voting is an election system using electronic technology. To develop the electronic voting system, it is necessary to develop a protocol that is completely secure and guaranteed the terms of election. Thus, Cryptography is a tool that is required to make it happen. This final project proposed a secure protocol using bilinear pairing. The protocol itself implements encryption and decryption methods in ID-based cryptosystem, using pasangan bilinear as the main tool.
Key word : electronic voting, bilinear pairing, ID-based cryptosystem
i
Abstrak
Pemilihan umum dengan cara konvensional dinilai terlalu lambat dan memakan dana yang cukup besar. Perkembangan teknologi informasi yang semakin pesat membuat para ahli dan beberapa kalangan menawarkan pemilihan umum secara elektronik. Pemilihan Elektronik adalah sistem pemilihan umum yang menggunakan teknologi elektronik. Namun untuk membuat Sistem Pemilihan Elektronik diperlukan protokol yang benar-benar aman dan terjamin sesuai dengan syarat-syarat pemilihan umum.
Dengan
demikian
kriptografi
adalah
alat
yang
diperlukan
untuk
mewujudkannya. Dalam tugas akhir ini diusulkan sebuah protokol yang aman dengan menggunakan pasangan bilinear. Protokol itu sendiri mengimplementasikan metode enkripsi dan dekripsi dalam ID based cryptosystem di mana ID based crysptosystem menggunakan pasangan bilinear sebagai alat utama.
Kata kunci : pemilihan elektronik, ID based cryptosystem,pasangan bilinear.
ii
PRAKATA Segala kemuliaan, hormat dan syukur hanyalah bagi Tuhan Yesus Kristus, karena atas kasih karunia-Nyalah saya dapat menyelesaikan Tugas Akhir ini. Buku Tugas Akhir dengan judul “Protokol Pemilihan Elektronik Dengan Menggunakan Pasangan Bilinear” ini disusun sebagai laporan tugas akhir sarjana yang saya kerjakan untuk dapat menyeleasaikan studi dan memperoleh gelar kesarjanaan strata satu (S-1) di Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Teknologi Bandung. Dalam kesempatan ini saya ingin menyampaikan rasa terima kasih yang mendalam kepada : 1. Bapak dan Mamak, untuk segala hal yang telah kalian tanamkan dan didik di dalam diriku dan juga untuk kasih dan doa kalian yang tiada henti. Terima kasih juga atas kepercayaan yang kalian berikan selama aku menyelesaikan tugas akhir ini, aku sangat mengasihi kalian. Amanda dan Edith, adik-adikku, suatu kebanggaan menjadi abang kalian. Dengan cara kalian yang unik aku tahu kalian sangat mengasihi aku, dan kalian tahu aku juga. Aku percaya yang terbaik masih ada di depan kita. 2. Ibu Dr. Rinovia M. G. Simanjuntak selaku pembimbing tugas akhir yang telah memberikan waktu, bimbingan, pandangan dan pengarahan kepada saya selama pengerjaan tugas akhir ini. 3. Ibu Prof. Dr. Pudji A. W., selaku dosen wali akademik atas bimbingan dan motivasinya bagi saya. 4. Bapak Dr. Djoko Suprijanto dan Bapak Dr. Nana Nawawi Gaos selaku penguji tugas akhir, terima kasih atas kritik dan saran untuk tugas akhir saya. 5. Abang Hery Kemit, atas bantuan dan kerelaannya untuk meluangkan waktu sampai rela kurang tidur demi mengajari saya, terima kasih juga buat semua cerita-cerita yang memotivasi dan membangun. 6. Segenap dosen di Jurusan Matematika ITB, atas didikan, ajaran dan motivasinya. Untuk Ibu Dyah, karyawan Tata Usaha dan semua staf Jurusan Matematika atas bantuannya selama saya kuliah.
iii
7. Segenap keluarga besar Ginting dan Pinem, Mama, Mami, Kila, Bibi, Pa Uda, Pa Tua, Mak Tua dan semua sepupu, buat doa dan motivasinya. 8. Eka, Inov untuk dukungan dan doa, Nana, „sama dengan titik koma‟, makasi ya na buat semuanya. Bang Thom, Bang Ones, kapan kita kumpul-kumpul lagi? Wanda, Haga, Gintar, Eben dan Jeffry, maaf kalau selama ini kita kehilangan waktu cerita-cerita dan sharing, tapi kalian selalu ada dalam doaku. 9. Keluargaku, PERMATA GBKP Bandung Pusat dan Bandung Timur, tempat bertumbuh dan mengenal Tuhan. PD HOPE untuk kebersamaan dan semua doadoa yang kita naikkan, saatnya akan tiba kita akan melihat doa-doa kita menjadi kenyataan. Tim Musik GBKP Bandung Pusat, Kak Tari, Hana dan Bang Andre, pelan tapi pasti, Tuhan pimpin kita melakukan kehendak-Nya. 10. Teman-teman kos, Benny, Joy, Bang Firman, Jimmy, Bang Ananias, Roy, Desta, Jose, Bobby, Bang Agus, Bang Alex, Bang Ariadin, Bang Roy, Bang Fritz dan Bang Satar, buat ketawa-ketawa dan cerita-ceritanya. 11. Semua anggota HIMATIKA, atas kebersamaaannya selama masa kuliah. Teman-teman matematika 03, khususnya Pangihutan, Samuel, Eben, Lidya, Hendrik, Taufik, Willem, Riswan, Yohanna, Lona, Vania, Ryan. Tidak lupa juga untuk mahasiswa-mahasiswa „ajaib‟, Pandu, Sugara, Iwan, Dian, Mossar, Daniel, we`ve made it!. 12. Semua pihak yang turut membantu penyelesaian tugas akhir ini yang tidak dapat saya sebutkan satu persatu.
Saya menyadari bahwa tugas akhir ini masih jauh dari sempurna, walaupun saya sudah berusaha untuk menyelesaikannya dengan sebaik-baiknya. Oleh karena itu, kritik dan saran dari para pembaca adalah hal yang sangat berharga demi penyempurnaan Tugas Akhir ini. Akhirnya saya berharap semoga tugas akhir ini dapat bermanfaat bagi penulis dan pembaca pada umumnya.
Bandung, September 2010
Patrick Jun W. P. G. iv
DAFTAR ISI Abstract ......................................................................................................................... i Abstrak ......................................................................................................................... ii PRAKATA .................................................................................................................. iii DAFTAR ISI ................................................................................................................ v DAFTAR GAMBAR .................................................................................................. vii DAFTAR TABEL....................................................................................................... vii BAB I : PENDAHULUAN ........................................................................................... 1 1.1.
Latar Belakang ................................................................................................ 1
1.2.
Rumusan Masalah ........................................................................................... 2
1.3.
Tujuan Penulisan ............................................................................................ 2
1.4.
Sistematika Penulisan ..................................................................................... 2
BAB II : TEORI DASAR.............................................................................................. 4 2.1.
Group ............................................................................................................. 4
2.1.1.
Grup Abelian ........................................................................................... 4
2.1.2.
Grup siklis ............................................................................................... 4
2.1.3.
Subgroup ................................................................................................. 6
2.1.4.
Orde ........................................................................................................ 6
2.2.
Gelanggang ..................................................................................................... 6
2.3.
Lapangan ........................................................................................................ 7
2.3.1.
Lapangan Hingga ..................................................................................... 8
BAB III : PENGERTIAN DAN SEJARAH SINGKAT KRIPTOGRAFI .................... 13 3.1.
Sejarah Kriptografi ....................................................................................... 13
3.2.
Jenis-jenis Sistem Enkripsi............................................................................ 15
3.2.1.
Kriptografi Kunci Simetri ...................................................................... 16
3.2.2.
Kriptografi Kunci Nirsimetri .................................................................. 17
3.3.
Fungsi Hash Kriptografi ................................................................................ 19
BAB IV : KURVA ELIPTIK DAN ID-BASED CRYPTOSYSTEM ........................... 21 4.1.
Kurva Eliptik ................................................................................................ 21
4.2.1.
Operasi Grup Pada Kurva Eliptik ........................................................... 21
v
4.2.2.
Zero dan Pole Dari Fungsi Rasional ....................................................... 22
4.2.3.
Orde Zero pada Fungsi Linear ................................................................ 23
4.2.4.
Orde Pole pada Fungsi Linear ................................................................ 24
4.2.4.
Divisor................................................................................................... 25
4.2.5.
Pasangan bilinear ................................................................................... 28
4.3.
Pasangan Weil .............................................................................................. 28
4.4.
ID Based Cryptosystem ................................................................................ 31
BAB V : PROTOKOL PEMILIHAN ELEKTRONIK DENGAN MENGGUNAKAN PASANGAN BILINEAR ........................................................................................... 33 4.1.
Tahap Awal .................................................................................................. 33
4.2.
Protokol ........................................................................................................ 34
4.2.1.
Langkah Satu : Persiapan ....................................................................... 34
4.2.2.
Langkah Dua : Administrasi .................................................................. 35
4.2.3.
Langkah Tiga : Pemilihan ...................................................................... 36
4.2.4.
Langkah Empat : Pengumpulan.............................................................. 36
4.2.5.
Langkah Lima : Membuka Kartu Suara.................................................. 38
4.2.6.
Langkah Enam : Penghitungan ............................................................... 38
4.3.
Simulasi Protokol.......................................................................................... 40
4.3.1.
Tahap Awal ........................................................................................... 40
4.3.2.
Antarmuka ............................................................................................. 41
4.3.3.
Transaksi Data ....................................................................................... 44
4.4.
Serangan-serangan Yang Dapat Diatasi Dalam Protokol Ini. ......................... 47
BAB VI : KESIMPULAN DAN SARAN .................................................................. 49 5.2.
Kesimpulan................................................................................................... 49
5.2.
Saran ............................................................................................................ 51
DAFTAR PUSTAKA ................................................................................................. 52 LAMPIRAN A ........................................................................................................... 53 LAMPIRAN B ............................................................................................................ 69
vi
DAFTAR GAMBAR Gambar 3.1 (a) Sebuah scytale; (b) Pesan ditulis secara horizontal, baris per baris.
14
Gambar 3.2 Mesin enkrips Enigma......................................................................
15
Gambar 3.3 Skema kriptografi simetri..................................................................
17
Gambar 3.4 Skema kriptografi nirsimetri.............................................................
17
Gambar 4.1 Halaman muka..................................................................................
41
Gambar 4.2 Kartu suara.......................................................................................
42
Gambar 4.3 Kartu suara yang telah diklik............................................................
42
Gambar 4.4 Konfirmasi telah memilih dan pemberitahuan nomor rec#................
43
Gambar 4.5 Memasukkan nomor record..............................................................
43
Gambar 4.6 Bukti Suara.......................................................................................
44
.
DAFTAR TABEL Tabel 4.1 Tabel transaksi data pada langkah satu..................................................
34
Tabel 4.2 Tabel transaksi data pada langkah dua...................................................
35
Tabel 4.3 Tabel transaksi data pada langkah tiga...................................................
36
Tabel 4.4 Tabel transaksi data pada langkah empat...............................................
38
Tabel 4.5 Tabel transaksi data pada langkah lima..................................................
38
Tabel 4.6 Tabel transaksi data pada langkah enam................................................
39
vii
