protokol perjanjian kunci berdasarkan masalah...
TRANSCRIPT
PROTOKOL PERJANJIAN KUNCI BERDASARKAN
MASALAH TRIPEL DEKOMPOSISI ATAS MONOID
NON-KOMUTATIF MATRIKS
SKRIPSI
Untuk Memenuhi Sebagian Persyaratan Mencapai Derajat Sarjana S-1
Program Studi Matematika
Diajukan oleh:
Helvi Alviani
12610002
Kepada
PROGRAM STUDI MATEMATIKA
FAKULTAS SAINS DAN TEKNOLOGI
UNIVERSITAS ISLAM NEGERI SUNAN KALIJAGA
YOGYAKARTA
2016
iv
v
HALAMAN PERSEMBAHAN
Karya ini ku persembahkan untuk bapak dan mamah tercinta
yang telah membesarkan, mendo’akan dan selalu memberikanku
semangat. Berkat do’a dan kerja keras kalian tugas ini dapat
terselesaikan.
Kepada kedua adikku, Reva dan Galuh yang senantiasa menjadi
motivasiku untuk dapat menyelesaikan tugas akhir ini.
Kepada keluarga besar matematika 12 dan kampusku tercinta
UIN Sunan kalijaga Yogyakarta.
vi
MOTTO
“Karena sesungguhnya sesudah kesulitan itu ada kemudahan,
sesungguhnya sesudah kesulitan itu ada kemudahan”.
(Q. S. Al-Insyiraah: 5-6)
“Dan bahwa manusia hanya memperoleh apa yang telah diusahakannya,
dan sesungguhnya usahanya itu kelak akan diperlihatkan (kepadanya),
kemudian akan diberi balasan kepadanya dengan balasan yang paling
sempurna”.
(Q.S. An-Najm 39-41)
“Kembalilah kepada kedua orang tuamu, lalu buat keduanya tertawa
sebagaimana engkau telah membuatnya menangis”.
(H. R. Abu Dawud)
vii
KATA PENGANTAR
Puji syukur kehadirat Allah SWT yang telah memberikan rahmat, taufik
dan hidayah-Nya, sehingga penulis dapat menyelesaikan penulisan skripsi yang
berjudul “Protokol Perjanjian Kunci Berdasarkan Masalah Tripel Dekomposisi
atas Monoid Non-Komutatif Matriks” ini dengan semaksimal mungkin. Shalawat
dan salam senantiasa tercurah kepada baginda Muhammad SAW, teladan bagi
seluruh umat manusia.
Penulis menyadari bahwa proses penulisan skripsi ini tidak terlepas dari
dukungan, motivasi, dan bimbingan dari berbagai pihak. Oleh karena itu, penulis
mengucapkan rasa terima kasih yang sebesar-besarnya kepada:
1. Ibu Dr. Maizer Said Nahdi, M.Si selaku Dekan Fakultas Sains dan
Teknologi Universitas Islam Negeri Sunan Kalijaga.
2. Bapak Dr. M. Wakhid Musthofa, M.Si selaku Ketua Program Studi
Matematika Fakultas Sains dan Teknologi Universitas Islam Negeri Sunan
Kalijaga.
3. Ibu Dr. Khurul Wardati, M.Si dan Bapak M. Zaki Riyanto, M.Sc selaku
pembimbing skripsi yang telah berkenan memberikan bimbingan serta
arahan sehingga penulis dapat menyelesaikan skripsi ini dengan baik.
4. Bapak Muchammad Abrori, M.Kom selaku dosen pembimbing akademik
yang telah memberikan pengarahan kepada penulis selama kuliah.
viii
5. Bapak/Ibu Dosen dan Staf Fakultas Sains dan Teknologi Universitas Islam
Negeri Sunan Kalijaga Yogyakarta atas ilmu, bimbingan dan pelayanan
selama perkuliahan dan penyusunan skripsi ini selesai.
6. Bapak dan Mamahku serta kedua adikku tercinta yang selalu memberikan
semangat, dukungan dan do’a yang tiada henti.
7. Wahyudhi Santoso Prawoto yang selalu memberikan motivasi dan masukan
dalam penyusunan skripsi ini.
8. Teman-teman matematika angkatan 2012 atas kebersamaan yang tak mudah
dilupakan dan semua pihak yang turut membantu hingga selesainya skripsi
ini yang tidak dapat penulis sebutkan satu persatu, terima kasih.
Penulis menyadari masih banyak kesalahan dan kekurangan dalam
penulisan skripsi ini, untuk itu diharapkan saran dan kritik yang bersifat
membangun demi kesempurnaan skripsi ini. Namun demikian, penulis tetap
berharap semoga skripsi ini dapat bermanfaat dan dapat membantu memberi suatu
informasi yang baru bagi semua orang yang membacanya.
Yogyakarta, 14 Juni 2016
Penulis,
Helvi Alviani
NIM.12610002
ix
DAFTAR ISI
HALAMAN JUDUL .............................................................................................. i
HALAMAN PERSETUJUAN ............................................................................. ii
HALAMAN PENGESAHAN ............................................................................. iii
SURAT PERNYATAAN KEASLIAN ............................................................... iv
HALAMAN PERSEMBAHAN ........................................................................... v
MOTTO ................................................................................................................ vi
KATA PENGANTAR ........................................................................................ vii
DAFTAR ISI ........................................................................................................ ix
DAFTAR GAMBAR .......................................................................................... xii
DAFTAR TABEL .............................................................................................. xiii
DAFTAR LAMPIRAN ..................................................................................... xiv
DAFTAR LAMBANG ........................................................................................ xv
ABSTRAK .......................................................................................................... xvi
ABSTRACT ...................................................................................................... xvii
BAB I PENDAHULUAN....................................................................................... 1
1.1. Latar Belakang ..................................................................................... 1
1.2. Batasan Masalah ................................................................................... 5
1.3. Rumusan Masalah ................................................................................ 5
1.4. Tujuan Penelitian ................................................................................. 5
1.5. Manfaat Penelitian ............................................................................... 6
1.6. Tinjauan Pustaka ................................................................................. 6
1.7. Metode Penelitian ................................................................................. 9
1.8. Sistematika Penulisan ........................................................................ 11
x
BAB II LANDASAN TEORI .............................................................................. 12
2.1. Kriptografi........................................................................................... 12
2.1.1. Definsi Kriptografi ...................................................................... 12
2.1.2. Sejarah Kriptografi ..................................................................... 13
2.1.3. Tujuan Kriptografi ..................................................................... 15
2.1.4. Algoritma Kriptografi ................................................................. 16
2.1.5. Sistem Kriptografi ....................................................................... 17
2.2. Dasar Struktur Aljabar ..................................................................... 19
2.2.1. Teori Bilangan ............................................................................. 19
2.2.2. Monoid ......................................................................................... 30
2.2.3. Grup ............................................................................................. 34
2.2.4. Ring .............................................................................................. 44
2.2.5. Lapangan ..................................................................................... 47
2.2.6. Monoid Matriks atas Ring ......................................................... 47
2.2.7. Grup Matriks atas lapangan Hingga ........................................ 55
BAB III PEMBAHASAN ................................................................................... 59
3.1. Protokol Perjanjian Kunci ................................................................ 59
3.2. Protokol Perjanjian Kunci dan Masalah Tripel Dekomposisi ...... 62
3.3. Perhitungan Protokol Kunci Masalah Tripel Dekomposisi ........... 65
3.4. Cipher Hill ......................................................................................... 107
3.5. Cipher Hill atas Grup Permutasi ..................................................... 110
3.6. Cipher Hill atas 𝑮𝑳𝒏(ℤ𝒑) .................................................................. 114
3.7. Affine Cipher .................................................................................... 117
3.8. Affine Cipher atas Monoid 𝑴𝒏(ℤ𝒎) ................................................ 118
xi
BAB IV IMPLEMNTASI DAN UJI COBA PROGRAM .............................. 122
4.1. Sarana Implementasi ....................................................................... 122
4.2. Implementasi Algoritma Protokol Perjanjian Kunci atas Monoid
Matriks .............................................................................................. 123
4.3. Uji Coba Program ............................................................................ 124
4.3.1. Program Perhitungan Protokol Perjanjian Kunci atas Monoid
Matriks ....................................................................................... 125
4.3.2. Program Perhitungan Cipher Hill atas 𝑮𝑳𝒏(ℤ𝒑) .................... 150
4.3.3. Program Perhitungan Affine Cipher atas 𝑴𝒏(ℤ𝒎) ................ 152
BAB V PENUTUP ............................................................................................. 156
5.1. Kesimpulan ....................................................................................... 156
5.2. Saran .................................................................................................. 159
DAFTAR PUSTAKA ........................................................................................ 160
LAMPIRAN ...................................................................................................... 162
xii
DAFTAR GAMBAR
Gambar 1.1. Alur Penelitian ................................................................................ 10
Gambar 1.2. Alur Sistematika Penelitian ..............................................................11
Gambar 2.1. Al-Kindi .......................................................................................... 13
Gambar 2.2. Skema Sistem Kriptografi Simetris ................................................. 19
Gambar 4.1. Tampilan Utama Maple 18 ............................................................ 123
Gambar 4.2. Program Perhitungan Perjanjian Kunci atas 𝑆8 ............................. 127
Gambar 4.3. Program Perhitungan Perjanjian Kunci atas 𝐺𝐿3(ℤ257)................ 133
Gambar 4.4. Program Perhitungan Perjanjian Kunci 𝐾1 atas 𝑀3(ℤ256) ............. 140
Gambar 4.5. Program Perhitungan Perjanjian Kunci 𝐾2 atas 𝑀3(ℤ256) ............ 147
Gambar 4.6. Program Perhitungan Cipher Hill atas 𝐺𝐿3(ℤ257) ......................... 151
Gambar 4.7. Program Perhitungan Affine Cipher atas 𝑀3(ℤ256) ...................... 154
xiii
DAFTAR TABEL
Tabel 1.1. Tinjauan Pustaka ................................................................................... 8
Tabel 2.1. Perhitungan dengan algoritma Euclide yang diperluas ........................ 29
Tabel 3.1. Skema Algoritma Protokol Perjanjian Kunci Diffie-Hellman ............. 60
Tabel 3.2. Contoh Protokol Perjanjian Kunci Diffie-Hellman .............................. 61
Tabel 3.3. Skema Algoritma Perjanjian Kunci Masalah Tripel Dekomposisi ..... 64
Tabel 3.4. Korespondensi Karakter dengan Bilangan ......................................... 109
Tabel 3.5. Proses Enkripsi Affine cipher ............................................................. 118
Tabel 3.6. Proses Dekripsi Affine cipher ............................................................ 118
Tabel 4.1. Spesifikasi perangkat Keras ............................................................... 122
Tabel 4.2. Spesifikasi Perangkat Lunak .............................................................. 123
xiv
DAFTAR LAMPIRAN
Lampiran 1. Tabel ASCII .................................................................................. 162
xv
DAFTAR LAMBANG
ℤ : Himpunan semua bilangan bulat.
ℤ≥0 : Himpunan semua bilangan bulat yang dimulai dari nol.
𝐴 ⊆ 𝑋 : 𝐴 himpunan bagian (subset) atau sama dengan 𝑋.
gcd(𝑎, 𝑏) : Pembagi persekutuan terbesar dari 𝑎 dan 𝑏.
(𝑀, . ) : Monoid atas operasi penjumlahan.
(𝐺,+) : Grup atas operasi penjumlahan.
(𝐺, . ) : Grup atas operasi perkalian.
(𝑅,+, . ) : Ring dengan dua operasi biner penjumlahan dan perkalian.
ℤ𝑚 : Himpunan bilangan bulat modulo 𝑚.
ℤ𝑝 : Himpunan bilangan bulat modulo prima 𝑝.
ℤ𝑝∗ : Grup perkalian modulo prima 𝑝.
𝐶𝑀(𝑥) : Centralizer dari 𝑥 pada 𝑀.
𝐴 ∖ 𝐵 : Selisih himpunan 𝐴 dan 𝐵.
𝑀𝑛(𝑅) : Matriks berukuran 𝑛 × 𝑛 atas ring 𝑅.
𝑀𝑛(ℤ𝑚) : Monoid matriks berukuran 𝑛 × 𝑛 atas ring ℤ𝑚.
𝐺𝐿𝑛(𝐹) : Grup matriks invertibel berukuran 𝑛 × 𝑛 atas lapangan 𝐹.
𝐺𝐿𝑛(ℤ𝑝) : Grup matriks invertibel berukuran 𝑛 × 𝑛 atas lapangan ℤ𝑝.
xvi
PROTOKOL PERJANJIAN KUNCI BERDASARKAN MASALAH
TRIPEL DEKOMPOSISI ATAS MONOID NON-KOMUTATIF MATRIKS
Oleh: Helvi Alviani
Abstrak
Jalur komunikasi yang dilakukan melalui internet sangat rentan terhadap
ancaman penyadapan. Ancaman tersebut dapat dihindari dengan merubah terlebih
dahulu pesan rahasia yang dikirim dengan proses enkripsi dan dekripsi. Kedua
proses tersebut dapat dijalankan apabila kedua pihak yang berkomunikasi
menyepakati kunci rahasia yang sama. Namun, terdapat suatu permasalahan ketika
kedua pihak yang saling berkomunikasi tidak dapat menyepakati kunci rahasia
bersama melalui jalur komunikasi yang aman. Salah satu solusi utuk mengatasi
permasalahan distribusi kunci tersebut adalah dengan protokol perjanjian kunci.
Protokol perjanjian kunci pertama kali dikenalkan oleh Diffie-Hellman,
yang menitikberatkan pada masalah logaritma diskrit atas grup siklik. Struktur
aljabar yang digunakan oleh Diffie Hellman bersifat komutatif. Protokol perjanjian
kunci kemudian dikembangkan pada struktur aljabar non-komutatif, yang tingkat
keamanannya diletakkan pada masalah matematis yang ada pada struktur aljabar
non-komutatif. Contohnya adalah protokol perjanjian kunci menggunakan monoid
non-komutatif matriks. Adapun monoid yang digunakan adalah grup permutasi 𝑆𝑛,
grup matriks invertibel 𝑛 × 𝑛 atas lapangan bilangan prima (𝐺𝐿𝑛(ℤ𝑝)) dan monoid
matriks 𝑛 × 𝑛 atas ring berhingga 𝑀𝑛(ℤ𝑚). Keamanan protokol perjanjian kunci
ini terletak pada masalah tripel dekomposisi.
Masalah tripel dekomposisi merupakan masalah faktorisasi dimana kedua
belah pihak harus menyepakati monoid non-komutatif matriks dan dua himpunan
subset dari monoid yang selanjutnya akan digunakan dalam pembuatan kunci
rahasia. Kedua himpunan subset dari monoid tersebut harus memenuhi sifat
invertibel dan komutatif. Kunci rahasia yang diperoleh kemudian diaplikasikan
pada suatu sistem kriptografi simetris yaitu sistem kriptografi cipher Hill dan
affine cipher.
Kata Kunci : kriptografi, monoid non-komutatif, protokol perjanjian kunci,
masalah tripel dekomposisi
xvii
KEY AGREEMENT PROTOCOL BASED ON THE TRIPLE
DECOMPOSITION PROBLEM OVER NON-COMMUTATIVE MONOID
MATRIX
By: Helvi Alviani
Abstract
The channel of communication such as internet are particularly vulnerable to
the threat of eavesdropping. In other to avoid the bug, a secret message sent is first
converted through the encryption and decryption process. Both processes can be
run when both communicating parties agree on the same secret key. However, there
is a problem when both parties that communicate each other can not agree on a
shared secret key through a secure channel. One of solutions to overcome the
problems of key distribution is the key agreement protocol.
The first key agreement protocol was introduced by Diffie-Hellman, which
focuses on the discrete logarithm problem of a cyclic group. Algebraic structure
that was used by Diffie Hellman has a commutative properties. Then the key
agreement protocol was developed over non-commutative structure, that is based
on the security level of mathematical problems that exist in the non-commutative
algebraic structure. An example is the key agreement protocols using non-
commutative monoid matrix. The example of monoid that used is a permutation
group 𝑆𝑛, general linear group 𝐺𝐿𝑛(ℤ𝑝) and monoid matrix over a finite ring
𝑀𝑛(ℤ𝑚). The security of this key agreement protocol is based on the triple
decomposition problem.
Triple decomposition problem is a problem of factoring in which both sides
have to agree on non-commutative monoid matrix and two sets subsets of monoid
which would be used in the generate of the secret key. Two sets of subsets of the
monoid must satisfy invertible and commutative properties. The secret key that is
obtained is then applied to a system of symmetric cryptography is a cipher Hill and
affine cipher cryptographic system.
Keyword: cryptography, key agreement protocol, non-commutative monoid, triple
decomposition problem
1
BAB I
PENDAHULUAN
1.1. Latar Belakang
Manusia dituntut untuk bisa berkomunikasi dengan sesama dalam
menjalankan kehidupan sehari-hari. Selain menjadi makhluk individu, manusia
juga merupakan makhluk sosial yang sangat membutuhkan interaksi dengan orang
lain. Sebagaimana dijelaskan dalam Al-Quran surat Al-Hujarat ayat 13, yaitu:
Artinya: “Hai manusia, sesungguhnya Kami menciptakan kamu dari seorang laki-
laki dan seorang perempuan dan menjadikan kamu berbangsa-bangsa dan bersuku-
suku supaya kamu saling kenal-mengenal. Sesungguhnya orang yang paling mulia
di antara kamu di sisi Allah ialah orang yang paling takwa di antara kamu.
Sesungguhnya Allah Maha Mengetahui lagi Maha Mengenal”.
Komunikasi membantu manusia untuk dapat berbagi informasi satu sama
lain. Seiring dengan berkembangnya teknologi, proses komunikasi yang terjadi
antar manusia semakin bervariasi. Salah satu contohnya adalah komunikasi
dengan menggunakan jalur internet. Namun, jalur internet tidak terlalu aman
karena merupakan jalur komuniksi umum yang dapat digunakan oleh setiap orang,
sehingga rawan terhadap penyadapan.
Keamanan dalam melakukan proses komunikasi, terlebih yang bersifat
rahasia menjadi faktor utama yang harus dipenuhi. Hal ini dikarenakan,
2
komunikasi secara rahasia hanya mengijinkan pihak-pihak tertentu untuk dapat
mengakses informasi. Apabila jalur komunikasi yang dipilih merupakan jalur yang
tidak aman, maka ada kemungkinan pihak lain dapat mengakses informasi rahasia
tersebut. Sehingga, dibutuhkan keamanan yang tinggi agar informasi rahasia tidak
jatuh kepada pihak lain yang berkepentingan untuk mengetahuinya.
Kriptografi memberikan solusi untuk menyelesaikan permasalahan pada
keamanan informasi. Konsep kriptografi sempat digunakan pada peradaban Islam
sekitar tahun 9 M oleh seorang ilmuwan bernama Abu Yusuf Ya’qub ibn ‘ Ishaq
As-Shabbah Al Kindi atau dikenal dengan Al-Kindi. Al-Kindi menulis kitab
tentang seni memecahkan kode yang berjudul Risalah fi istikhraj al-Mu’amma
(Manuskrip untuk memecahkan pesan-pesan kriptografi). Kriptografi sendiri
berasal dari bahasa Yunani, terdiri dari dua kata, yaitu cryptos dan graphein.
Cryptos berarti rahasia dan graphein berarti tulisan. Sehingga secara bahasa,
kriptografi adalah tulisan rahasia. Sedangkan menurut istilah, kriptografi
merupakan suatu ilmu yang mempelajari teknik-teknik matematika yang
berhubungan dengan aspek keamanan informasi, seperti kerahasiaan data,
keabsahan data, integritas data, dan serta autentikasi data (Menezes, Oorcshot, dan
Vanstone, 1996). Kriptografi bertujuan agar informasi rahasia tidak dapat dibaca
oleh pihak yang tidak berhak mengetahuinya. Sehingga informasi rahasia yang
dikirim melalu jalur komunikasi yang tidak aman dapat dipertanggung jawabkan
oleh pihak pengirim.
Algoritma kriptografi modern terdiri dari tiga fungsi dasar, yaitu enkripsi,
dekripsi, dan key. Enkripsi merupakan suatu proses penyandian yang melakukan
3
perubahan suatu pesan, dari yang dapat dimengerti, disebut dengan plainteks,
menjadi suatu kode yang sulit dimengerti, disebut dengan cipherteks. Sedangkan
proses kebalikannya, untuk mengubah cipherteks menjadi plainteks disebut
dekripsi (Riyanto, 2007). Proses enkripsi dan dekripsi bertujuan untuk menjaga
pesan agar tidak mudah dipecahkan oleh pihak ketiga. Syarat untuk menjalankan
kedua proses tersebut, yaitu dibutuhkan suatu kunci rahasia yang hanya diketahui
oleh pihak yang melakukan komunikasi.
Suatu sistem kriptografi yang mengharuskan kedua belah pihak
menggunakan kunci rahasia yang sama adalah sistem kriptografi simetris.
Permasalahan yang kemudian muncul adalah kedua belah pihak harus
menyepakati kunci yang sama, sedangkan jalur komunikasi yang digunakan oleh
keduanya bukan jalur komunikasi yang aman. Solusi dari permasalahan tersebut,
salah satunya adalah dengan menggunakan protokol perjanjian kunci. Tujuan dari
protokol ini adalah untuk membantu kedua belah pihak membuat dan menyepakati
kunci rahasia yang sama tanpa diketahui oleh pihak ketiga.
Protokol perjanjian kunci pertama kali diperkenalkan oleh Whitfield Difiie
dan Martin Hellman (1976). Struktur aljabar yang digunakan oleh keduanya
merupakan struktur aljabar komutatif, yaitu grup siklik. Keamanan dari protokol
Diffie-Hellman ini terletak pada masalah logaritma diskrit atas grup siklik
berhingga. Namun, adanya ancaman dari komputer kuantum di masa depan
memungkinkan masalah logaritma diskrit dapat terpecahkan. Sehingga, beberapa
peneliti mulai mengembangkan protokol perjanjian kunci berdasarkan struktur
4
aljabar non-komutatif yang tingkat keamanannya diharapkan lebih tinggi dan sulit
dipecahkan.
Berdasarkan Jurnal Yesem Kurt Peker (2014), beberapa peneliti yang telah
mengembangkan protokol perjanjian kunci pada struktur aljabar non-komutatif,
diantaranya adalah I. Anshel, M. Anshel, B. Fisher dan D. Goldfeld (2001) yang
mengembangkan protokol perjanjian kunci menggunakan grup non-komutatif
yang tingkat keamanannya diletakkan pada masalah konjugasi. Peneliti
selanjutnya, yaitu J. Cha, K. Ko, S. Lee, J. Han dan J. Cheon (2001)
mengembangkan protokol perjanjian kunci baru menggunakan grup non-
komutatif, yaitu grup Braid. M. Yagisawa (2012) mengembangkan protokol
perjanjian kunci menggunakan persamaan kuadrat multivariat atas ring non-
komutatif. Yesem Kurt Peker (2014) mengembangkan protokol perjanjian kunci
menggunakan permasalahan tripel dekomposisi atas grup Braid.
Penelitian ini akan mengkaji dan mengembangkan protokol perjanjian kunci
yang telah dikembangkan oleh Yesem Kurt Peker (2014), yaitu mengatasi masalah
keamanan informasi dengan pembuatan kunci rahasia yang didasarkan pada
masalah tripel dekomposisi atas suatu monoid non-komutatif. Yesem Kurt Peker
(2014) menggunakan monoid non-komutatif yaitu grup braid yang merupakan
grup tak berhingga. Adapaun monoid non-komutatif yang digunakan dalam
penelitian ini adalah monoid berhingga diantaranya adalah grup permutasi, grup
matriks invertibel atas lapangan bilangan bulat modulo 𝑝 dengan 𝑝 adalah bilangan
prima, dan monoid matriks atas ring berhingga.
5
1.2. Batasan Masalah
Pembatasan masalah dalam suatu penelitian sangat diperlukan, guna
memfokuskan pada pembahasan objek yang dituju. Berdasarkan pada latar
belakang masalah, penelitian ini akan difokuskan untuk membahas prosedur dalam
protokol perjanjian kunci atas monoid non-komutatif matriks dengan tingkat
keamanan yang diletakkan pada masalah tripel dekomposisi.
1.3. Rumusan Masalah
Berdasarkan latar belakang yang telah dipaparkan, maka dirumusukan
permasalahan-permasalahan sebagai berikut:
1. Bagaimana konsep matematis yang melandasi prosedur perjanjian kunci
pada sistem kriptografi simetris?
2. Bagaimana langkah-langkah dan perhitungan untuk memperoleh kunci
rahasia menggunakan protokol perjanjian kunci dengan masalah tripel
dekomposisi atas monoid non-komutatif matriks?
3. Bagaimana proses enkripsi dan dekripsi menggunakan sistem kriptografi
simetris atas monoid non-komutatif matriks?
4. Bagaimana implementasi perhitungan protokol perjanjian kunci dan proses
enkripsi serta dekripsi dengan menggunakan program MAPLE?
1.4. Tujuan Penelitian
Tujuan penulis dalam penyusunan tugas akhir ini adalah sebagai berikut:
1. Mengkaji konsep matematis yang melandasi protokol perjanjian kunci pada
sistem kriptografi simetris.
6
2. Mengkaji langkah-langkah dan perhitungan untuk memperoleh kunci
rahasia menggunakan protokol perjanjian kunci atas monoid non-komutatif
matriks.
3. Mengkaji proses enkripsi dan dekripsi menggunakan sistem kriptografi
simetris atas monoid non-komutatif matriks.
4. Mengkaji proses perhitungan protokol perjanjian kunci dan proses enkripsi
serta dekripsi dengan menggunakan program MAPLE.
1.5. Manfaat Penelitian
Beberapa manfaat dari penelitian ini adalah sebagai berikut:
1. Memberikan solusi dalam memperoleh kunci rahasia yang akan digunakan
dalam pengiriman pesan.
2. Memberikan kemudahan dalam perhitungan protokol perjanjian kunci dan
proses enkripsi serta dekripsi dengan menggunakan program MAPLE.
3. Sebagai dasar bagi peneliti selanjutnya dalam mengembangkan protokol
perjanjian kunci.
1.6. Tinjauan Pustaka
Referensi utama dalam penyusunan tugas akhir ini adalah jurnal dari Yesem
Kurt Peker (2014) yang berjudul A New Key Agreement Scheme Based on the
Tripel Decomposition Problem. Jurnal tersebut menjelaskan mengenai protokol
perjanjian kunci dengan tingkat keamanan yang diletakkan pada masalah tripel
dekomposisi. Adapun masalah tripel dekomposisi sendiri didefinisikan pada suatu
monoid non-komutatif. Contoh monoid non-komutatif yang digunakan adalah
grup braid. Persamaan penelitian yang ditulis oleh Yesem Kurt Peker dengan
7
penelitian yang dilakukan penulis terletak pada masalah keamanan yang
digunakan dalam pembuatan kunci rahasia, yaitu masalah tripel dekomposisi.
Perbedaannya terletak pada contoh monoid yang digunakan dalam protokol
perjanjian kunci. Penulis menggunakan grup permutasi, grup matriks invertibel
atas lapangan bilangan bulat modulo prima 𝐺𝐿𝑛(ℤ𝑝), dan monoid matriks atas ring
berhingga 𝑀𝑛(ℤ𝑚) sebagai contoh monoid non-komutatif.
Peneliti lain yang telah meneliti terkait protokol perjanjian kunci diantaranya
adalah Agustin Rahayuningsih dan Fadhil Andika Rahman (2015) mahasiswa
Prodi Matematika Fakultas Sains dan Teknologi Universitas Islam Negeri Sunan
Kalijaga. Agustin Rahayuningsih (2015) melakukan penelitian terkait protokol
perjanjian kunci dalam tugas akhirnya yang berjudul Protokol Perjanjian Kunci
Berdasarkan Masalah Konjugasi Pada Matriks Atas Lapangan Hingga. Penelitian
ini membahas mengenai protokol perjanjian kunci menggunakan grup matriks atas
lapangan hingga 𝐺𝐹(𝑝𝑚) dengan tingkat keamanan yang diletakkan pada masalah
konjugasi. Sedangkan Fadhil Andika Rahman (2015) meneliti terkait protokol
pertukaran kunci dalam tugas akhirnya yang berjudul Protokol Pertukaran Kunci
Berdasarkan Masalah Dekomposisi Simetris Atas Ring Non-Komutatif End
(ℤ𝑝 × ℤ𝑝2). Penelitian ini menjelaskan mengenai protokol pertukaran kunci atas
ring non-komutatif dengan tingkat keamanan yang diletakkan pada masalah
dekomposisi simetris. Contoh ring yang digunakan adalah ring endomorfisma
(ℤ𝑝 × ℤ𝑝2) dengan 𝑝 adalah bilangan prima. Perbedaan penelitian yang ditulis
oleh Agustin Rahayuningsih dan Fadhil Andika Rahman dengan penelitian yang
dilakukan penulis terletak pada masalah keamanan dan struktur aljabar yang
8
digunakan dalam pembuatan kunci rahasia. Penulis menggunakan masalah tripel
dekompoisi atas monoid non-komutatif dalam pembuatan kunci rahasia.
Perbedaaan dan persamaan penelitian yang dilakukan penulis dengan
penelitian sebelumnya dapat dilihat pada tabel berikut.
Tabel 1.1. Tinjauan Pustaka
No Nama Peneliti Judul Penelitian Persamaan Perbedaan
1. Yesem Kurt
Peker (2014)
A New Key
Agreement Scheme
Based on the Tripel
Decomposition
Problem
Masalah
keamanan
yang
digunakan,
yaitu
masalah
tripel
dekomposisi
Struktur
aljabar yang
digunakan,
yaitu grup
braid
2.
Agustin
Rahayuningsih
(2015)
Protokol Perjanjian
Kunci Berdasarkan
Masalah Konjugasi
Pada Matriks atas
Lapangan Higga
Metode yang
digunakan
untuk
memperoleh
kunci
rahasia,
yaitu
protokol
perjanjian
kunci
Masalah
keamanan
dan struktur
aljabar yang
digunakan,
yaitu
masalah
konjugasi
pada matriks
atas
lapangan
hingga
3.
Fadhil Andika
Rahman
(2015)
Protokol Pertukaran
Kunci Berdasarkan
Masalah
Dekomposisi
Simetris atas Ring
Non-komutatif End
(ℤ𝑝 × ℤ𝑝2)
Metode yang
digunakan
untuk
memperoleh
kunci
rahasia,
yaitu
protokol
perjanjian
kunci
Masalah
keamanan
dan struktur
aljabar yang
digunakan,
yaitu
masalah
dekomposisi
simetris atas
ring non-
komutatif
9
4. Helvi Alviani
(2016)
Protokol Perjanjian
Kunci Berdasarkan
Masalah Tripel
Dekomposisi atas
Monoid Non-
Komutatif Matriks
Masalah
keamanan
yang
digunakan,
yaitu
masalah
tripel
dekomposisi
Struktur
aljabar yang
digunakan,
yaitu
monoid non-
komutatif
matriks
Penyusunan tugas akhir ini juga membutuhkan beberapa materi mengenai
kriptografi dan struktur aljabar yang didapat dari beberapa literatur, yaitu
Menezes, Oorschot dan Vanstone (1996), D. S. Malik (2007), dan Kenneth H.
Rosen (2011).
1.7. Metode Penelitian
Metode yang digunakan pada penyusunan tugas akhir ini adalah metode
studi literatur. Pengumpulan data diperoleh dengan cara membahas dan
menjabarkan materi-materi dan teorema-teorema yang terdapat dalam sumber
buku, jurnal, catatan kuliah, dan internet. Secara umum data yang dikaji dalam
masalah komunikasi pada penulisan tugas akhir ini, terdiri dari dua bagian yaitu
kriptografi dan struktur aljabar.
Pembahasan kriptografi diawali pada sistem kriptografi simetris yaitu cipher
Hill dan affine cipher. Permasalahan dari sistem kriptografi simetris tersebut yaitu
masalah distribusi kunci rahasia antara dua pihak yang berkomunikasi. Solusi
untuk menyelesaikan permasalahan tersebut adalah protokol perjanjian kunci.
Sedangkan pada struktur aljabar, data penelitian di awali dengan membahas materi
teori bilangan yang kemudian mendukung materi monoid dan ring. Struktur
10
monoid kemudian membentuk grup yaitu grup permutasi dan struktur ring
kemudian membentuk lapangan. Monoid dan ring membentuk struktur baru yaitu
monoid matriks atas ring. Grup dan lapangan juga membentuk struktur baru yaitu
grup matriks atas lapangan. Berdasarkan penjelasan tersebut, maka langkah
terakhir penulis dalam melakukan penelitian ini adalah menyelesaikan masalah
distribusi kunci dengan protokol perjanjian kunci yang tingkat keamanannya
diletakkan pada masalah tripel dekomposisi atas monoid matriks non-komutatif.
Langkah-langkah penulis dalam menyusun tugas akhir ini dapat dijelaskan pada
diagram berikut:
Gambar 1.1. Alur Penelitian
Grup Matriks
Atas Lapangan
Struktur Aljabar
Teori Bilangan
Grup
Ring
Lapangan Grup Permutasi
Monoid Matriks
Atas Ring
Cipher
Hill
Masalah Distribusi Kunci
Protokol Perjanjian Kunci
Kriptografi
Sistem Kriptografi
Simetris
Protokol Perjanjian Kunci Berdasarkan Masalah Tripel Dekomposisi
Atas Monoid Non-Komutatif Matriks
Monoid
Affine
Cipher
11
1.8. Sistematika Penulisan
Penyusunan tugas akhir ini dibagi ke dalam lima bab yang disusun secara
runtun dan sistematis dengan rincian masing-masing bab dijelaskan secara umum
oleh penulis, yaitu BAB I sebagai pendahuluan, BAB II sebagai dasar teori, BAB
III sebagai pembahasan, BAB IV sebagai uji coba program, dan BAB V sebagai
penutup. Alur sistematika penelitian dari penulis dapat dijelaskan secara umum
dalam bagan dibawah ini.
Gambar 1.2. Alur Sistematika Penulisan
BAB I: Bab ini membahas mengenai latar belakang, perumusan masalah,
batasan masalah, tujuan penulisan tugas akhir, tinjauan pustaka, metode
penelitian, dan serta sistematika penelitian.
BAB II: Bab ini membahas mengenai landasan teori yang terdiri dari
kriptografi secara umum dan dasar struktur aljabar.
BAB III: Bab ini membahas mengenai protokol perjanjian kunci dan contoh
proses perhitungan protokol serta penggunaan kunci rahasia pada sistem
kriptografi simetris.
BAB IV: Bab ini membahas mengenai implementasi dan uji coba pada
progam MAPLE.
BAB V: Bab ini menyampaikan kesimpulan umum yang merupakan jawaban
dari rumusan masalah yang terdapat pada bab I, dan saran dari penulis
mengenai penelitian yang dilakukan.
156
BAB V
PENUTUP
5.1. Kesimpulan
Berdasarkan pembahasan mengenai protokol perjanjian kunci masalah tripel
dekomposisi atas monoid matriks non-komutatif, maka dapat diambil beberapa
kesimpulan sebagai berikut:
1. Pada prosedur perhitungan protokol perjanjian kunci atas monoid matriks
non-komutatif diperlukan beberapa konsep matematis yaitu kriptografi dan
dasar struktur aljabar seperti teori bilangan, monoid, grup, ring dan lapangan.
2. Keamanan dari protokol perjanjian kunci ini diletakkan pada masalah tripel
dekomposisi yaitu Diberikan suatu monoid non-komutatif 𝐺, dan 𝑋, 𝑌, 𝐴
adalah subset dari 𝐺 dimana elemen-elemen dari 𝑋 𝑑𝑎𝑛 𝑌 invertibel dan
komutatif. Selanjutnya diberikan 𝑢 ∈ 𝐺. Masalah tripel dekomposisi
didefinisikan sebagai masalah dalam menemukan 𝑥 ∈ 𝑋, 𝑎 ∈ 𝐴 𝑑𝑎𝑛 𝑦 ∈ 𝑌
sedemikian hingga 𝑢 = 𝑥𝑎𝑦 ∈ 𝐺. Adapun algroitma dalam pembuatan kunci
rahasia bersama adalah, pertama Alice dan Bob menyepakati monoid 𝐺 dan
himpunan subset dari 𝐺 yaitu 𝐴 = {𝐴1, 𝐴2, 𝐴3, 𝑋1, 𝑋2} dan
𝐵 = {𝐵1, 𝐵2, 𝐵3, 𝑌1, 𝑌2} yang memenuhi syarat invertibel dan komutatif.
Kemudian Alice dan Bob memilih himpunan subset yang akan digunakan.
Misalkan Alice memilih himpunan 𝐴 dan Bob memilih himpunan 𝐵. Alice
memilih secara rahasia 𝑎1 ∈ A1, 𝑎2 ∈ A2, 𝑎3 ∈ A3 , 𝑥1 ∈ X1, 𝑥2 ∈ X2 dan Bob
juga memilih secara rahasia 𝑏1 ∈ B1, 𝑏2 ∈ B2, 𝑏3 ∈ B3 , 𝑦1 ∈ Y1, 𝑦2 ∈ Y2.
Selanjutnya Alice menghitung kunci publiknya yaitu 𝑢 = 𝑎1𝑥1,
157
𝑣 = 𝑥1−1𝑎2𝑥2, 𝑤 = 𝑥2
−1𝑎3 dan Bob juga menghitung kunci publiknya yaitu
𝑝 = 𝑏1𝑦1, 𝑞 = 𝑦1−1𝑏2𝑦2, 𝑟 = 𝑦2
−1𝑏3. Alice mengirimkan kunci publik
(𝑢, 𝑣, 𝑤) kepada Bob dan Bob juga mengirimkan kunci publik (𝑝, 𝑞, 𝑟)
kepada Alice. Langkah selanjutnya, yaitu Alice menghitung kunci rahasianya
𝐾𝐴 = 𝑎1𝑝𝑎2𝑞𝑎3𝑟 dan Bob juga menghitung kunci rahasianya
𝐾𝐵 = 𝑢𝑏1𝑣𝑏2𝑤𝑏3. Sehingga diperoleh 𝐾𝐴 = 𝐾𝐵.
3. Sistem kriptografi yang digunakan dalam penelitian ini adalah sitem
kriptografi cipher Hill atas 𝑆𝑛, cipher Hill atas 𝐺𝐿𝑛(ℤ𝑝) dan sistem
kriptografi affine cipher atas 𝑀𝑛(ℤ𝑚). Adapun alur dari proses enkripsi dan
dekripsi dari masing-masing sistem adalah sebagai berikut:
a. Cipher Hill atas 𝑆𝑛
Proses enkripsi dan dekripsi pada cipher Hill atas 𝑆𝑛 dimulai dengan
Alice dan Bob menyepakati suatu bilangan 𝑛 dan kunci rahasia bersama yaitu
𝒦 = 𝑆𝑛 = {𝜋 = (1,2, … . . , 𝑛) → (1,2, … . . , 𝑛)|𝜋: 𝑏𝑖𝑗𝑒𝑘𝑡𝑖𝑓}. Selanjutnya
plainteks yang akan dikirimkan dipartisi sebanyak 𝑛 bagian dan dirubah
kedalam bentuk biner sesuai dengan tabel ASCII. Kemudian Alice melakukan
proses enkripsi yaitu:
𝑒𝜋(𝑥1, 𝑥2, … . . , 𝑥𝑛) = (𝑥𝜋(1), 𝑥𝜋(2), … . . , 𝑥𝜋(𝑛)).
dan mengirimkan cipherteks kepada Bob dan Bob melakukan proses dekripsi
untuk memperoleh plainteks yaitu:
𝑑𝜋(𝑦1, 𝑦2, … . . , 𝑦𝑛) = (𝑦𝜋−1(1), 𝑦𝜋−1(2), … . . , 𝑦𝜋−1(𝑛)).
158
b. Cipher Hill atas 𝐺𝐿𝑛(ℤ𝑝)
Proses enkripsi dan dekripsi pada cipher Hill atas 𝐺𝐿𝑛(ℤ𝑝) dimulai
dengan Alice dan Bob menyepakati suatu bilangan prima 𝑝 dan bilangan bulat
𝑛 serta kunci rahasia bersama yaitu 𝒦 = {𝐾 ∈ 𝐺𝐿𝑛(ℤ𝑝)| det(𝐾) ≠ 0}.
Selanjutnya plainteks yang akan dikirimkan dirubah kedalam bentuk angka
sesuai dengan tabel ASCII dan dikonstruksi dalam bentuk matriks berukuran
𝑛 × 1. Kemudian Alice melakukan proses enkripsi yaitu
𝑒𝑘(𝑥) = 𝑥𝐾(𝑚𝑜𝑑 𝑝) dan mengirimkan cipherteks kepada Bob dan Bob
melakukan proses dekripsi untuk memperoleh plainteks yaitu
𝑑𝑘(𝑦) = 𝑦𝐾−1 (𝑚𝑜𝑑 𝑝).
c. Affine Cipher atas 𝑀𝑛(ℤ𝑚)
Proses enkripsi dan dekripsi pada Affine cipher atas 𝑀𝑛(ℤ𝑚) dimulai
dengan Alice dan Bob menyepakati suatu bilangan bulat 𝑛 dan 𝑚 serta kunci
rahasia bersama yaitu 𝒦 = {(𝐾1, 𝐾2) ∈ 𝑀𝑛(ℤ𝑚)| gcd(det (𝐾1), 𝑚) = 1}.
Selanjutnya, plainteks yang akan dikirimkan dirubah kedalam bentuk angka
sesuai dengan tabel ASCII dan dikonstruksi dalam bentuk matriks berukuran
𝑛 × 𝑛. Kemudian Alice melakukan proses enkripsi yaitu
𝑒𝐾(𝑋) = (𝐾1𝑋 + 𝐾2) 𝑚𝑜𝑑 𝑚 dan mengirimkan cipherteks kepada Bob dan
Bob melakukan proses dekripsi untuk memperoleh plainteks yaitu
𝑑𝑘(𝑌) = 𝐴−1(𝑌 − 𝐵) 𝑚𝑜𝑑 𝑚.
4. Dalam melakukan perhitungan pembuatan kunci dan proses ekripsi dan
dekripsi digunakan program MAPLE 18 yang bertujuan untuk mempermudah
dan mempercepat proses perhitungan. Adapun perintah yang digunakan
159
merupakan perintah sederhana yang terdapat pada program MAPLE 18
seperti yang sudah dijelaskan pada BAB IV.
5.2. Saran
Berdasarkan penelitian yang telah penulis lakukan maka dapat disampaikan
beberapa saran sebagai berikut:
1. Protokol perjanjian kunci dengan masalah tripel dekomposisi merupakan
salah satu contoh dari metode perjanjian kunci, diharapkan ada penelitian
selanjutnya tentang metode perjanjian kunci dengan masalah keamanan yang
lebih tinggi dan lebih efektif.
2. Masalah tripel dekomposisi pada penelitian ini hanya dibatasi pada monoid
non-komutatif matriks, diharapkan kepada peneliti selanjutnya yang ingin
meneliti lebih jauh mengenai masalah ini untuk menggunakan struktur aljabar
yang lebih kompleks.
3. Program yang digunakan penulis merupakan program yang sederhana yang
telah tersedia pada MAPLE 18, sehingga diharapkan kepada peneliti
selanjutnya yang ingin meneliti lebih dalam mengenai masalah ini untuk
membuat program dengan bahasa pemrograman sendiri.
160
DAFTAR PUSTAKA
Brown, William C., 1993, Matrices over Commutative Rings, Mercel Dekker, Inc.,
USA.
Buchmann, Johannes A., 2000, Introduction to Cryptography, Springer-Verlag
New York, Inc., USA.
Dummit, David S., Foote, Richard M., 2004, Abstarct algebra, Jhon Wiley and
Sons, Inc., USA.
Fraleigh, John B., 2003, A First Course in Abstract Algebra, Seventh Edition,
Addison-Wesley Publishing Company, Inc., USA.
Menezes, Oorschot, and Vanstone, 1996, Handbook of Applied Cryptography, CRC
Press, Inc., USA.
Myasnikov, Shpilrain, and Ushakov, 2008, Grup Based Cryptography, Birkhäuser
Verlag, Berlin.
Paar, Christof and Pelzl, Jan, 2009, Understanding Cryptography, Springer-Verlag
New York, Inc., USA.
Rahayuningsih, Agustin, 2015, Protokol Perjanjian Kunci Berdasarkan Masalah
Konjugasi Pada Matriks Atas Lapangan Hingga, Skripsi. Yogyakarta:
Jurusan Matematika Fakultas Sains dan Teknologi UIN Sunan Kalijaga.
Rahman, Fadhil A, 2015, Protokol Pertukaran Kunci Berdasarkan Masalah
Dekomposisi Simetris Atas Ring Non-Komutatif End (ℤ𝑝 × ℤ𝑝2), Skripsi.
Yogyakarta: Jurusan Matematika Fakultas Sains dan Teknologi UIN Sunan
Kalijaga.
Riyanto, M. Zaki, 2007, Pengamanan Pesan Rahasia Menggunakan Algoritma
Kriptografi Elgamal atas Grup Pergandaan ℤ𝑝∗, Skripsi. Yogyakarta:
Jurusan Matematika Fakultas Ilmu Alam dan Matematika UGM.
Riyanto, M. Zaki, 2011, Protokol Perjanjian Kunci Berdasarkan Masalah
Konjugasi atas Grup Non-Komutatif, prosiding seminar nasional
161
matematika dan pendidikan matematika 2011. Universitas Negeri
Yogyakarta.
Rosen, Kenneth H., 2011, Elementary Number Theory and Its Application, Sixth
Edition., Pearson Education, Inc., USA.
Schneier, Bruce, 1996, Applied Cryptography, Second Edition: Protocol,
Algorithms and Source Code in C, Jhon Wiley and Sons, Inc.
Shor, Peter W., 1997, Polynomial-Time Algorithms for Prime Factorization and
Discrete Logarithms on a Quantum Computer, Society for Industrial and
Applied Mathematics Philadelphia, PA, USA.
Stinson, D.R., 1995, Cryptography Theory and Practice, CRC Press, Inc., Florida.
Malik, D.S, Moderson, Jhon N, and Sen, M.K., 2007, An Introduction to Abstract
Algebra, Creighton University, USA.
Peker, Y.K., 2014, A New Key Agreement Scheme Based on The Tripel
Decomposition Problem, International Journal of Network Security, vol. 16,
no. 6, pp. 426-436, Nov. 2014.
162
LAMPIRAN
Lampiran 1. Tabel ASCII
163
DAFTAR RIWAYAT HIDUP
Nama lengkap : Helvi Alviani
Tempat tanggal lahir : Ciamis, 22 Desember 1993
Alamat : Dsn. Sukarenah RT/RW 003/007, Desa/Kec.
Padaherang, Kab. Pangandaran, Jawa Barat.
Hp : 0858 7822 5142
Fakultas/ jurusan : Sains dan Teknologi
Alamat email : [email protected]
Riwayat pendidikan : TK Pertiwi 1998-2000
SD Negeri 1 Padaherang 2000- 2006
SMP Negeri 1 Padaherang 2006-2009
SMA Negeri 1 Banjarsari 2009- 2012
UIN Sunan Kalijaga 2012 -2016