PERBANDINGAN BEBERAPA SKEMA PEMBAGIAN RAHASIA DAN IMPLEMENTASI SKEMA PEMBAGIAN RAHASIA BRICKELL
Tugas Akhir
oleh : Heti Rahmawati Putri 10103047
Program Studi Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Teknologi Bandung 2008
PERBANDINGAN BEBERAPA SKEMA PEMBAGIAN RAHASIA DAN IMPLEMENTASI SKEMA PEMBAGIAN RAHASIA BRICKELL
Tugas Akhir Diajukan sebagai persyaratan untuk memperoleh gelar sarjana di Program Studi Matematika ITB
Oleh Heti Rahmawati Putri 10103047
Bandung, 30 Januari 2008 Disetujui oleh Pembimbing
Dr. Rinovia Simanjuntak NIP. 132206222
Program Studi Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Teknologi Bandung 2008
Untuk keluarga ku tersayang….
Satu gerbang terbuka sudah Menyisakan banyak rintangan dan tapak jalan Yang masih harus dilalui Tanpa menyerah Menuju masa depan Untuk mengejar keagunganNya….
ABSTRAK Skema Pembagian rahasia adalah metode yang digunakan untuk membagi rahasia diantara sejumlah partisipan yang berada dalam suatu sistem, sehingga setiap partisipan diharuskan bekerja sama untuk mendapatkan kembali rahasia tersebut. Rahasia yang menjadi titik utama, diketahui oleh mereka hanya sebagai potongan informasi yang secara langsung tidak terlihat berkaitan dengan rahasia.
Dalam tulisan tugas akhir ini dijelaskan dan dibandingkan empat skema pembagian rahasia yaitu skema pembagian rahasia Shamir, skema pembagian rahasia menggunakan persegi Latin, skema pembagian rahasia dengan graf total sisi ajaib, dan skema pembagian rahasia dengan ruang vektor Brickell. Di akhir, skema pembagian rahasia dengan ruang vektor Brickell ini diimplementasikan dalam suatu program.
Kata kunci :
skema pembagian rahasia, persegi Latin, pelabelan total sisi ajaib, himpunan kritis, ruang vektor Brickell.
iv
ABSTRACT A secret sharing scheme is a method of sharing a secret among participants in a system such way that each of participants must cooperate to reveal the secret. The secret, which is the main point, is known by them as a piece of information be directly unconnected with the secret.
In this paper, it will be explained and compared four secret sharing schemes. The first one is Shamir`s secret sharing schemes. The second one is secret sharing schemes based on Latin squares. The third one is secret sharing schemes based on edge-magic total graphs, and the fourth one is by Brickell`s vector space. The last, secret sharing schemes based on Brickell`s vector space is implemented within a program.
Keywords : secret sharing schemes, Latin squares, edge-magic total labelings, critical sets, Brickell`s vector space.
v
PRAKATA Bismillahirrahmanirrahim Alhamdulillahi Rabbil`alamin, segala puji bagi Allah SWT, karena berkat Rahmat dan KaruniaNya akhirnya penulis dapat menyelesaikan tugas akhir ini dengan sebaikbaiknya.
Tugas Akhir yang penulis susun dan kerjakan ini menguraikan beberapa skema pembagian rahasia besesrta kekurangan dan kelebihannya. Di akhir, salah satu skema penulis implementasikan dalam bahasa pemrograman Delphi.
Pada kesempatan ini penulis ingin mengucapkan terima kasih yang sebesar-besarnya kepada : 1. Kedua orang tua penulis, yang selalu memberikan penulis limpahan kasih sayang, dukungan, dan do`a kepada penulis. 2. Ibu Dr. Rinovia Simanjuntak selaku pembimbing dan wali yang telah memberikan bimbingan dan arahan yang sangat berharga kepada penulis. 3. Bapak Dr. Djoko Suprijanto, Dr. Saladin Utunggadewa, dan Ibu Dr. Hilda Assiyatun yang telah bersedia menjadi dosen penguji penulis dalam tugas akhir ini. 4. Abang-abang dan adik kandung penulis yang telah memberikan motivasi, arahan, dan kasih sayang kepada penulis. 5. Teman-teman MA 2003 seperjuangan, MA 2004, dan MA 2005. Terima kasih atas masukan-masukan, dukungan, dan persaudaraannya selama ini yang memberikan kekuatan bagi penulis. 6. Seluruh dosen dan pegawai TU di Program Studi Matematika, yang selalu membantu, mengarahkan, dan memberikan berbagai pengetahuan kepada penulis. 7. Teman-teman penghuni kos yang lama maupun yang baru, telah menjadi teman bermain dan berbagi dalam keseharian penulis.
vi
8. Teman-teman serta sahabat seperjuangan yang tidak akan dapat penulis tuliskan satu persatu, yang telah hadir dalam relung sejarah hidup penulis, atas perhatian dan kebersamaannya selama ini.
Akhir kata, penulis menyadari bahwa penulisan tugas akhir ini masih jauh dari sempurna. Karena itu, penulis menantikan saran dan kritik yang bermanfaat untuk menyempurnakan tugas akhir ini. Semoga tugas akhir ini dapat memberikan sumbangan pengetahuan kepada pembaca.
Wassalam Bandung, Januari 2008
Heti Rahmawati Putri
vii
DAFTAR ISI Abstrak ...........................................................................................................
iv
Abstract ..........................................................................................................
v
Prakata ...........................................................................................................
vi
Daftar Isi ........................................................................................................ viii Daftar Gambar...............................................................................................
x
Bab 1 Pendahuluan ......................................................................................
1
1.1
Latar Belakang ..................................................................................................
1
1.2
Ruang Lingkup Kajian ......................................................................................
2
1.3
Tujuan Penulisan ..............................................................................................
3
1.4 Sistematika Pembahasan ........................................................................ ..........
3
Bab 2 Landasan Teori ..................................................................................
4
2.1
Persegi Latin ....................................................................................................
4
2.2
Pelabelan Total Sisi Ajaib (PTSA) ...................................................................
5
2.3
Ruang Vektor ....................................................................................................
7
Bab 3 Beberapa Skema Pembagian Rahasia ............................................
9
3.1
Skema Pembagian Rahasia Shamir ..................................................................
10
3.1.1
Kelebihan dari Skema Shamir ..............................................................
13
3.1.2
Kekurangan dari Skema Shamir ...........................................................
15
3.2 Skema Pembagian Rahasia dengan Menggunakan Persegi Latin ....................
15
3.2.1
Kelebihan dari Skema Pembagian Rahasia dengan Persegi Latin .......
18
3.2.2
Kekurangan dari Skema Pembagian Rahasia dengan Persegi Latin ....
19
3.3 Skema Pembagian Rahasia dengan Menggunakan Graf Total Sisi Ajaib ........
20
3.3.1
Kelebihan dari Skema Pembagian Rahasia dengan Menggunakan Graf TSA ..............................................................................................
viii
25
3.3.2
Kekurangan dari Skema Pembagian Rahasia dengan Menggunakan Graf TSA ............................................................ .................................
26
3.4 Skema Pembagian Rahasia dengan Ruang Vektor Brickell .............................
27
3.4.1
Kelebihan dari Skema Pembagian Rahasia dengan Ruang Vektor Brickell ............................................................. ...................................
3.4.2
29
Kekurangan dari Skema Pembagian Rahasia dengan Ruang Vektor Brickell ................................................................................................
30
Bab 4 Implementasi Skema Brickell ............................................................
31
4.1
Algoritma Skema Pembagian Rahasia dengan Ruang Vektor Brickell ...........
34
4.1.1
Algoritma Distribusi Share ...................................................................
34
4.1.2 Algoritma Rekonstruksi Rahasia ..........................................................
35
Aspek Keamanan dan Evaluasi Program .........................................................
36
Bab 5 Kesimpulan .........................................................................................
38
Daftar Pustaka ..............................................................................................
39
Lampiran ................................................................................................................
40
4.2
ix
DAFTAR GAMBAR Gambar 2.1 Persegi Latin L dan ketiga persegi Latin parsial dari L ..................
5
Gambar 2.2 Persegi Latin L dan La serta persegi Latin parsial L3 ......................
5
Gambar 2.3 Graf Total Sisi Ajaib P3a dengan himpunan kritis dan bukan himpunan kritisnya ............................................................................
6
Gambar 2.4 Graf Total Sisi Ajaib P3a dan P3b beserta graf bagian dari keduanya ...........................................................................................
7
Gambar 3.1 Persegi Latin L dan persegi Latin parsial L1 dan L2 ........................
16
Gambar 3.2 Tahapan melengkapi himpunan kritis dari persegi Latin L ..............
17
Gambar 3.3 Persegi Latin L dan persegi Latin parsial B1 ....................................
17
Gambar 3.4 Dua persegi Latin yang dibentuk dari satu persegi Latin parsial yang sama ..........................................................................................
18
Gambar 3.5 Persegi Latin parsial P1 dan alternatif entri dalam melengkapi P1 .......................................................................................................
19
Gambar 3.6 Graf posisi dari S4 .............................................................................
21
Gambar 3.7 Graf posisi dan graf Total Sisi Ajaib beserta himpunan kritisnya ....
22
Gambar 3.8 Graf posisi dan graf berlabel tak lengkap ........................................
23
Gambar 3.9 Graf posisi dan graf berlabel tak lengkap dari graf Total Sisi Ajaib S4 .............................................................................................
24
Gambar 3.10 Tahapan dalam melengkapi graf berlabel tak lengkap menjadi graf TSA ............................................................................................
25
Gambar 4.1 Tampilan dari implementasi Skema Brickell dalam bahasa pemrograman Delphi ........................................................................
x
31
