ANALISIS DAN IMPLEMENTASI SKEMA PEMBAGIAN RAHASIA YANG DIVERIFIKASI DENGAN MENGGUNAKAN SKEMA FELDMAN
ERJODI CAHYO NUGROHO
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2014
PERNYATAAN MENGENAI SKRIPSI DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA Dengan ini saya menyatakan bahwa skripsi berjudul Analisis dan Implementasi Skema Pembagian Rahasia yang Diverifikasi dengan Menggunakan Skema Feldman adalah benar karya saya dengan arahan dari dosen pembimbing dan belum diajukan dalam bentuk apa pun kepada perguruan tinggi mana pun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir skripsi ini. Dengan ini saya melimpahkan hak cipta dari karya tulis saya kepada Institut Pertanian Bogor. Bogor, Agustus 2014 Erjodi Cahyo Nugroho NIM G54100020
ABSTRAK ERJODI CAHYO NUGROHO. Analisis dan Implementasi Skema Pembagian Rahasia yang Diverifikasi dengan Menggunakan Skema Feldman. Dibimbing oleh SUGI GURITMAN dan MUHAMMAD ILYAS. Informasi yang bersifat rahasia membutuhkan penjagaan supaya tidak dapat diakses oleh pihak yang tidak berkepentingan. Salah satu cara untuk menjaganya adalah dengan menggunakan skema pembagian rahasia. Skema pembagian rahasia yang diverifikasi merupakan perkembangan dari skema pembagian rahasia. Skema Shamir adalah salah satu contoh dari skema pembagian rahasia yang didasari oleh interpolasi Lagrange. Skema Feldman merupakan perbaikan dari kelemahan yang dimiliki oleh skema Shamir. Skema Feldman juga merupakan salah satu contoh dari skema pembagian rahasia yang diverifikasi. Penelitian ini bertujuan untuk menjelaskan cara kerja pembagian rahasia menggunakan skema Feldman, menerapkan skema Feldman dalam pembagian rahasia menggunakan perangkat lunak Wolfram Mathematica 10, dan menganalisis keamanan skema Feldman. Tahapan skema Feldman terdiri atas dua bagian yaitu pembagian kunci dan penyusunan kunci. Tahap pembagian kunci terdiri atas tahap penentuan parameter dan tahap distribusi, sedangkan tahap penyusunan kunci terdiri atas tahap verifikasi dan tahap penyusunan ulang. Skema Feldman memiliki kebocoran mengenai rahasianya karena nilai dari komitmen yang diberikan secara umum. Hal tersebut tidak terlalu dipermasalahkan, karena upaya mendapatkan rahasia dari kebocoran tersebut harus menggunakan logaritma diskret yang masih tak layak untuk dipecahkan. Kata kunci: interpolasi Lagrange, logaritma diskret, skema pembagian rahasia, skema pembagian rahasia yang diverifikasi
ABSTRACT ERJODI CAHYO NUGROHO. Analysis and Implementation Feldman Verifiable Secret Sharing Scheme. Supervised by SUGI GURITMAN and MUHAMMAD ILYAS. Confidential information requires a protection such that it cannot be accessed by unauthorized parties. One way to keep it safe is by employing a secret sharing scheme such as Shamir’s scheme which developed based on Lagrange interpolation. Verifiable secret sharing scheme is an improvement of secret sharing scheme, such as Feldman’s scheme which overcomes the weakness of Shamir’s scheme. The purposes of this study are to describe the secret sharing mechanism by using the Feldman’s scheme, to apply Feldman’s scheme in sharing secret by using Mathematica 10, and to analyze the security aspect of Feldman’s scheme. Feldman’s scheme consists of two stages, namely key distribution and key preparation. Key distribution comprises the step of determining parameters and distribution phase, whereas key preparation consists of verification and reconstruction phases. Even though Feldman’s scheme might have a leak about the secret because of the value from commitments given in general, it is not too problematic, because to get the secrets from the leak we must perform a discrete logarithm which is infeasible from the perspective of computation. Keywords: discrete logarithm, Lagrange interpolation, secret sharing scheme, verifiable secret sharing scheme
ANALISIS DAN IMPLEMENTASI SKEMA PEMBAGIAN RAHASIA YANG DIVERIFIKASI DENGAN MENGGUNAKAN SKEMA FELDMAN
ERJODI CAHYO NUGROHO
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2014
Judul Skripsi : Analisis dan Implementasi Skema Pembagian Rahasia yang Diverifikasi dengan Menggunakan Skema Feldman Nama : Erjodi Cahyo Nugroho NIM : G54100020
Disetujui oleh
Dr Sugi Guritman Pembimbing I
Muhammad Ilyas, MSi, MSc Pembimbing II
Diketahui oleh
Dr Toni Bakhtiar, MSc Ketua Departemen
Tanggal Lulus:
PRAKATA Puji dan syukur penulis panjatkan kepada Allah subhanahu wa ta’ala atas segala karunianya sehingga penulis dapat menyelesaikan skripsi yang berjudul “Analisis dan Implementasi Skema Pembagian Rahasia yang Diverifikasi dengan Menggunakan Skema Feldman”. Shalawat serta salam senantiasa diucapkan kepada Nabi Muhammad SAW sebagai pemimpin dan suri tauladan terbaik bagi umatnya. Terima kasih penulis ucapkan kepada Dr Sugi Suritman dan Muhammad Ilyas, MSi, MSc selaku pembimbing atas bimbingan dan arahannya kepada penulis dalam pembuatan skripsi ini, serta Ruhiyat, MSi selaku dosen penguji atas saran dan masukannya untuk perbaikan skripsi ini. Ungkapan terima kasih juga disampaikan kepada orang tua saya Ir Endi Supriyono dan Dra Reiza Kurnia Rinanti, adik-adik tersayang Errizqi Dwi Cahyo dan Ferdiansyah Ersatiyo, dan juga seluruh keluarga atas dukungan, doa, dan kasih sayangnya. Penulis juga mengucapkan terima kasih kepada para sahabat Aisatul Mustaqimah, Rossy Febriani, Fachriadi Fadhillah, Aditya Dwi AP, M Adam Azhari, Steven, Dian Permana, Rangga G, Fahri Aditya, M Buchari, teman sebimbingan M Masykur dan Ego PS, teman-teman Matematika 47, dan Shutter atas segala bantuan dan dukungannya. Semoga karya ilmiah ini bermanfaat.
Bogor, Agustus 2014 Erjodi Cahyo Nugroho
DAFTAR ISI DAFTAR TABEL
vi
DAFTAR GAMBAR
vi
DAFTAR LAMPIRAN
vi
PENDAHULUAN
1
Latar Belakang
1
Tujuan Penelitian
1
TINJAUAN PUSTAKA
2
HASIL DAN PEMBAHASAN
5
Skema Pembagian Rahasia Sederhana Menggunakan Penjumlahan Modular
5
Skema Ambang Batas
6
Skema Ambang Batas Shamir
6
Skema Feldman
7
Implementasi Skema Feldman
10
Analisis Keamanan Skema Feldman
12
SIMPULAN DAN SARAN
12
Simpulan
12
Saran
13
DAFTAR PUSTAKA
13
LAMPIRAN
14
RIWAYAT HIDUP
15
DAFTAR GAMBAR 1 2 3 4 5 6 7
Langkah pembentukan shares Hasil keluaran parameter Hasil keluaran pasangan share Langkah verifikasi Keluaran yang dihasilkan benar Langkah penyusunan ulang Kode rahasia yang disimpan
10 10 11 11 11 11 12
DAFTAR LAMPIRAN 1 2 3
Tahap pembentukan share pada skema Feldman Tahap verifikasi skema Feldman Tahap penyusunan ulang skema Feldman
14 14 14
PENDAHULUAN
Latar Belakang Perkembangan teknologi yang kian pesat menyebabkan penyebaran informasi menjadi lebih mudah. Informasi dapat dikategorikan ke dalam dua sifat yaitu informasi umum dan rahasia. Informasi umum adalah suatu informasi yang dapat diakses dan ditujukan kepada semua orang atau publik, sedangkan informasi rahasia adalah sebuah informasi yang hanya dapat diakses atau ditujukan kepada pihak-pihak tertentu yang bersifat pribadi atau rahasia. Pada informasi umum, tidak diperlukan penjagaan informasi yang diberikan karena ditujukan untuk semua orang, berbeda dengan informasi yang bersifat rahasia. Informasi ini membutuhkan penjagaan agar tidak dapat diakses oleh pihak lain yang tidak berkepentingan dalam mengakses informasi tersebut. Sebuah kunci kriptografik digunakan untuk menjaga informasi yang bersifat rahasia. Kunci inilah yang akan dicari oleh pihak yang tidak memiliki akses untuk mendapatkan informasi rahasia. Oleh sebab itu, kunci kriptografik ini harus disimpan. Salah satu cara untuk menyimpan kunci kriptografik adalah dengan membuat salinannya di tempat lain. Hal ini dilakukan untuk mengurangi resiko kehilangan kunci tersebut. Namun, besar kemungkinan kunci tersebut dapat terbongkar. Apabila kunci kriptografik hanya disimpan dalam satu tempat, maka resiko terbongkarnya akan berkurang tetapi resiko kehilangannya akan meningkat. Oleh sebab itu, perlu adanya sebuah metode dalam menyimpan kunci kriptografi tersebut agar tetap terjaga kerahasiaan informasi di dalamnya. Skema pembagian rahasia merupakan salah satu cara untuk mengatasi permasalahan dalam penyimpanan kunci kriptografik. Kunci kriptografik akan dipecah menjadi beberapa bagian dan dibagikan kepada beberapa orang yang terpercaya. Jika beberapa orang tersebut berkumpul dan menggabungkan bagiannya, maka dapat membangkitkan kunci kriptografik. Sehingga diharapkan penggunaan metode skema pembagian rahasia ini dapat bermanfaat bagi penyimpanan kunci kriptografik dan membantu menjaga informasi rahasia tertentu. Skema pembagian rahasia ini telah diterapkan untuk menjaga perintah peluncuran nuklir di Amerika. Perintah dari presiden dan mentri pertahanan dibutuhkan untuk melakukan peluncuran nuklir. Pada karya ilmiah ini akan dibahas mengenai mekanisme pembagian rahasia menggunakan skema Feldman, penerapan skema Feldman dalam pembagian rahasia menggunakan perangkat lunak Wolfram Mathematica 10, dan analisis keamanan skema Feldman. Tujuan Penelitian 1. 2.
Tujuan dari karya ilmiah ini adalah: Menjelaskan dasar-dasar teori yang digunakan dalam skema Feldman. Menjelaskan cara kerja skema Feldman dalam skema pembagian rahasia yang diverifikasi.
2 3. 4.
Menerapkan penggunaan skema Feldman untuk membagi menggunakan perangkat lunak Wolfram Mathematica 10. Menganalisis keamanan skema Feldman.
rahasia
TINJAUAN PUSTAKA Pada bab ini akan diberikan definisi-definisi mengenai kriptografi, aljabar dan aritmetika modular. Kriptografi Definisi Kriptografi Studi teknik matematika yang berkaitan dengan aspek keamanan informasi seperti kerahasiaan, integritas data, autentikasi entitas, dan autentikasi asal data (Menezes et al. 1996). Definisi Teks Asli/Plaintext Pesan atau data dalam betuk aslinya yang dapat terbaca. Teks asli adalah masukan bagi algoritme enkripsi (Sadikin 2012). Definisi Kunci Rahasia/Secret Key Kunci rahasia yang juga merupakan masukan bagi algoritme enkripsi merupakan nilai yang bebas terhadap teks asli dan menentukan hasil keluaran algoritme enkripsi (Sadikin 2012). Definisi Teks Sandi/Chipertext Teks sandi dapat dianggap sebagai pesan dalam bentuk tersembunyi. Algoritme enkripsi yang baik akan menghasilkan teks sandi yang terlihat acak (Sadikin 2012). Definisi Algoritme Enkripsi Algoritme enkripsi memiliki dua masukan teks asli dan kunci rahasia. Algoritme enkripsi melakukan transformasi terhadap teks asli sehingga menghasilkan teks sandi (Sadikin 2012). Definisi Algoritme Dekripsi Algoritme dekripsi memiliki dua masukan yaitu teks sandi dan kunci rahasia. Algoritme dekripsi memulihkan kembali teks sandi menjadi teks asli bila kunci rahasia yang dipakai algoritme dekripsi sama dengan kunci rahasia yang dipakai algoritme enkripsi (Sadikin 2012). Definisi Kelompok/Party Seseorang atau sesuatu yang mengirim, menerima, dan memanipulasi informasi (Menezes et al. 1996).
3 Definisi Protokol/Protocol Algoritme multi-party yang didefinisikan oleh urutan langkah–langkah yang secara tepat menentukan tindakan yang diperlukan dari dua party atau lebih untuk mencapai tujuan tertentu (Menezes et al. 1996). Definisi Pembentukan Kunci/Key Establishment Suatu proses atau protokol yang berkenaan dengan tersedianya kunci bersama bagi dua party atau lebih untuk tujuan kriptografi (Menezes et al. 1996). Definisi Skema Pembagian Rahasia/Secret Sharing Scheme Protokol multi-party yang berkaitan dengan pembentukan kunci (Menezes et al. 1996). Definisi Rasio Rasio dari user adalah rasio antara panjang rahasia dengan panjang share yang dimiliki user tersebut. Rasio dari skema pembagian rahasia adalah rasio terkecil dari semua rasio user (Menezes et al. 1996). Aljabar Definisi Operasi Biner Suatu pemetaan pada himpunan S, * : S × S S (Menezes et al. 1996). Definisi Grup Himpunan G dengan operasi biner * pada G yang memenuhi tiga aksioma berikut: 1. Operasi * bersifat asosiatif, yaitu ( ) ( ) 2. Terdapat elemen identitas 1 G, sedemikian rupa sehingga 3.
( a G )(! a-1 G), a-1 disebut invers dari a, sehingga memenuhi
Selanjutnya, suatu grup dikatakan grup abelian/komutatif jika ketiga aksioma di atas dipenuhi dan juga aksioma berikut: 4. (Menezes et al. 1996). Definisi Grup Hingga Grup yang memiliki jumlah elemen berhingga. Order dari sebuah grup menyatakan banyaknya himpunan dari grup tersebut (Menezes et al. 1996). Definisi Grup Perkalian Grup perkalian dari adalah
(
* bila n prima, maka (Menezes et al. 1996).
*
)
+ +
4 Definisi Grup Siklik Sebuah grup G disebut grup siklik apabila ada elemen a G sehingga untuk setiap b G, terdapat integer i sehingga b = ai. Elemen a disebut pembangkit grup G. Notasi untuk grup yang dihasilkan oleh pembangkit a ditulis G = a (Sadikin 2012). Definisi Order Jika , order dari a dilambangkan dengan positif terkecil t sedemikian sehingga (
( ) adalah bilangan bulat ) (Menezes et al. 1996).
Definisi Subgrup Subgrup adalah suatu grup yang termuat di dalam grup (di bawah operasi yang sama) (Sadikin 2012). Definisi Ring Himpunan R dengan dua sembarang operasi biner, dinotasikan + (penjumlahan) dan (perkalian) pada R, yang memenuhi beberapa aksioma berikut: 1. (R,+) adalah grup abelian dengan identitas 0 2. Operasi bersifat asosiatif, yaitu ( ) ( ) 3. Terdapat suatu elemen identitas terhadap perkalian, dinotasikan 1, dengan 1 0, sehingga Operasi bersifat distributif terhadap +, yaitu: ( ) ( ) ( ) ( ) dan ( ) ( ) . Selanjutnya, suatu ring disebut ring komutatif apabila memenuhi keempat aksioma di atas dan juga aksioma berikut: 5. (Menezes et al. 1996). 4.
Definisi Lapangan/Field Ring komutatif dimana semua elemen tak-nolnya memiliki invers terhadap perkalian (Menezes et al. 1996). Definisi Polinomial atas Ring R Jika R adalah ring komutatif, maka polinomial dengan peubah tak tentu atas ring R adalah sebuah ekspresi dari bentuk ( ) di mana setiap dan . Elemen disebut koefisien dari di ( ). Bilangan integer terbesar di mana disebut derajat dari ( ) dinotasikan dengan ( ) (Menezes et al. 1996). Definisi Interpolasi Menduga nilai fungsi yang hilang dengan cara mengambil nilai rata – rata dari nilai fungsi yang telah diketahui (Mathews & Fink 1999).
5
Definisi Interpolasi Lagrange Sebuah rumus untuk mendapatkan polinomial berderajat n yang menginterpolasi sebuah fungsi ( ) pada titik-titik : ( )
∑ ( )∏
(Kudryavtsev & Samarin 2011). Definisi Logaritma Diskret Jika adalah grup siklik berorder dan α adalah pembangkit dari serta . Logaritma diskret dari β dengan basis α dinotasikan dengan adalah bilangan bulat yang tunggal, , sedemikian sehingga (Menezes et al. 1996). Aritmatika Modular Definisi Kongruen Jika dan bilangan bulat, maka disebut kongruen terhadap modulo ditulis dengan ( ), jika membagi ( ) (Menezes et al. 1996). Definisi Bilangan Bulat modulo Bilangan bulat modulo dinotasikan dengan merupakan sebuah himpunan bilangan bulat * +. Penjumlahan dan perkalian di dihitung dalam modulo (Menezes et al. 1996). Definisi Invers Perkalian Untuk , invers perkalian dari modulo adalah bilangan bulat sedemikian sehingga ( ). Jika terdapat nilai , maka nilai tersebut unik dan dikatakan invertible (Menezes et al. 1996).
HASIL DAN PEMBAHASAN Dalam bab pembahasan ini akan dijelaskan bagaimana terbentuknya skema Feldman. Selanjutnya akan diberikan analisis keamanan beserta implementasi skema Feldman menggunakan program Wolfram Mathematica 9. Skema Pembagian Rahasia Sederhana Menggunakan Penjumlahan Modular Secara sederhana, skema pembagian rahasia merupakan sebuah skema yang menjelaskan cara bagaimana dealer membagikan sebuah bilangan rahasia S dengan ukuran r-bit kepada n buah parties, sehingga setiap party Pi mendapat bagian Si. Rahasia S dapat dibangkitkan kembali dengan mengumpulkan bagian Si sebanyak n dari tiap party. Pembagian rahasia akan lebih baik apabila rahasia dibagikan dengan ukuran yang sama sesuai dengan rahasianya. Hal ini memberikan pengamanan yang lebih
6 baik jika dibandingkan dengan mempartisi kunci r-bit menjadi t bagian atau menjadi r/t-bit untuk setiap bagiannya. Sebagai contoh, untuk r = 56 dan t = 2, jika dua parties diberikan kunci 28-bit untuk masing - masing, pencarian oleh satu party hanya mebutuhkan 228 percobaan, sedangkan jika setiap party diberikan kunci 56-bit percobaan yang perlu dilakukan sebanyak 256. Operasi penjumlahan modular dapat digunakan dalam membagi rahasia menjadi bagian dengan ukuran yang sama. Misalkan sebuah rahasia S akan dibagi kepada n buah parties. Bangkitkan sebanyak n – 1 bilangan acak yang saling bebas, dengan m merupakan bilangan bulat yang lebih besar dari S. Party sampai diberikan bagian , ∑ sedangkan untuk party diberikan bagian ( ) . Rahasia dapat disusun kembali dengan cara menghitung (∑ ) . Skema Ambang Batas Skema ambang batas adalah metode dimana dealer terpercaya atau trusted party membagi rahasia S menjadi beberapa bagian kemudian secara aman mendistribusikan bagian kepada party , sedemikian sehingga dalam menyusun kembali rahasia S diperlukan sebanyak t atau lebih bagian . Jika dalam penyusunan hanya terkumpul sebanyak t-1 bagian , maka rahasia S tidak dapat diketahui. Oleh sebab itu, pengumpulan bagian sebanyak t atau lebih menjadi penting dalam proses penyusunan ulang rahasia. Skema Ambang Batas Shamir Skema ambang batas Shamir didasari oleh interpolasi Lagrange. Dari konsep interpolasi Lagrange ini didapatkan bahwa suatu polinomial satu peubah berderajat t-1 secara unik dapat didefinisikan dari t titik yang berbeda. Skema ambang batas Shamir memiliki beberapa kelebihan, yaitu 1. Perfect Jika bagian yang diberikan kurang dari t, maka tidak ada informasi sedikitpun yang dapat diketahui mengenai rahasia. 2. Ideal Rasio dari skema pembagian rahasia adalah 1. 3. Extendable for new user Bagian baru untuk party baru dapat dikomputasikan dan dibagikan tanpa memengaruhi bagian dari party yang lama. Skema ini juga memiliki kelemahan, yaitu 1. Kepercayaan penuh ada pada dealer, sehingga ada kemungkinan dealer memberikan bagian yang salah atau tidak konsisten kepada tiap party, dan setiap party tidak mengetahui apakah bagian yang mereka dapatkan itu benar atau tidak. 2. Ketika ada party yang curang dalam proses penyusunan ulang, rahasia tidak dapat disusun kembali. Party lain tidak akan mengetahui bahwa ada party yang melakukan kecurangan.
7 Skema Feldman Adanya kelemahan dari skema ambang batas Shamir menyebabkan Feldman membuat skema yang baru untuk menutupi kelemahan yang ada. Skema Feldman merupakan salah satu contoh dari skema pembagian rahasia yang dapat diverifikasi. Skema Feldman ini dapat memeriksa apakah bagian yang diberikan oleh dealer kepada party benar atau tidak sehingga tidak terjadi kesalahan bagian dari dealer kepada party. Selain itu, dapat juga memeriksa apakah bagian yang diberikan oleh party untuk penyusunan ulang benar atau tidak sehingga rahasia dapat disusun kembali. Berawal dari sebuah rahasia yang merupakan sebuah bilangan bulat yang dibagi menjadi shares yang akan diberikan kepada beberapa party. Dalam membagi rahasia kita menggunakan jasa seorang dealer. Dealer tersebut bisa saja melakukan kesalahan dalam perhitungan shares. Oleh karena itu, dibutuhkan sebuah parameter (komitmen) yang akan digunakan untuk mengetahui kebenaran shares tersebut. Dalam menyusun ulang sebuah rahasia diperlukan berkumpulnya beberapa party untuk menggabungkan share mereka dengan menggunakan interpolasi Lagrange. Skema pembagian rahasia dapat dilakukan dengan beberapa cara, salah satunya adalah skema Feldman. Menurut Fu-tai et al. (2002) skema Feldman memiliki tahapan-tahapan yang harus dilalui dalam menyelesaikan skema pembagian data rahasia tersebut. Adapun tahapan-tahapannya adalah sebagai berikut. Tahap penentuan parameter Parameter yang akan digunakan pada tahapan tahapan selanjutnya adalah 1. S merupakan Secret atau rahasia yang akan dibagi. Nilai dari S tidak diketahui oleh siapapun. 2. merupakan Shares atau bagian dari rahasia yang dibagikan kepada party ke-i. 3. merupakan komitmen. 4. p merupakan bilangan prima yang lebih besar dari S dan q merupakan bilangan prima yang habis membagi p-1. 5. g merupakan bilangan dengan order q di 6. Nilai p, q, g, dan diberikan secara umum. 7. t merupakan threshold (jumlah pasangan share minimal yang dibutuhkan untuk mendapatkan nilai dari rahasia yang telah dibagi) dan n merupakan jumlah parties. Sebagai contoh kasus jika kita ingin menyembunyikan sebuah informasi berharga dalam sebuah tempat yang memiliki 6 digit angka sebagai kata sandinya yaitu 519014 dan akan dibagikan kepada 14 orang serta dibutuhkan 5 orang untuk memperoleh kata sandinya, maka skema Feldman dapat dijalankan dengan nilai . Setelah itu kita membutuhkan nilai dan yang akan digunakan pada tahapan selanjutnya. Nilai dibangkitkan secara acak dan didapatkan , lalu dapat dihitung nilai yaitu 6228373. Setelah itu nilai dapat dicari yaitu 303599.
8
Tahap distribusi Pada tahap ini akan dilakukan pemecahan rahasia menjadi shares yang akan diberikan kepada n parties dan juga perhitungan nilai komitmen. 1. Dealer menentukan polinomial ( ) ∑ atas secara acak dengan merupakan sebuah rahasia yang akan dibagi kepada party . () 2. Mengirim nilai i dan shares secara rahasia 3. Menghitung nilai komitmen , . Ilustrasi tahap distribusi dengan contoh kasus di atas. 1. Tentukan polinomial berderajat empat yaitu ( )
2. Untuk
( ) ( )
. akan dicari
( ) yang selanjutnya dibagikan kepada semua party secara rahasia. 3. Hitung nilai komitmen .
Tahap verifikasi Pada tahap ini akan dilakukan perhitungan untuk mengetahui kebenaran dari sebuah share. Setiap party memeriksa apakah ∏ ∏ . Jika , maka share salah. Ilustrasi tahap verifikasi dengan contoh kasus di atas. Pada perhitungan ) ( sebenarnya party pertama mendapat pasangan nilai ( ), tetapi dealer bisa saja melakukan kecurangan dengan memberi nilai yang salah yaitu ( ) ( ) maka akan dilakukan verifikasi terhadap nilai yang salah tersebut. ∏
∏ Terlihat bahwa sehingga pasangan nilai ( ) ( ) adalah terbukti salah. Sedangkan jika dilakukan perhitungan dengan pasangan nilai sebenarnya didapat
9
(
∏ ) adalah benar.
Sehingga ) (
yang berarti bahwa pasangan nilai
Tahap penyusunan ulang Tahap penyusunan ulang merupakan tahap terakhir dalam skema Feldman. Pada tahap ini akan menjelaskan bagaimana cara untuk mengetahui rahasia. 1. Pada saat t party bekerja sama untuk menyusun ulang rahasia, setiap party memberikan share-nya kepada party lain untuk memeriksa kebenaran dari share-nya dengan memeriksa apakah ∏ . 2. Jika semua shares telah benar, party yang bekerja sama dapat menyusun ulang rahasia dengan menggunakan interpolasi Lagrange ( ) ∑ ∏ ) dengan pasangan titik ( ( ) sehingga akan terbentuk kembali polinomial ( ) ∑ Hal tersebut dapat terjadi karena pasangan titik ( ) didapatkan dari fungsi polinomial ( ) yang telah didapatkan sebelumnya. ( ) ∑ Karena maka ( ) ( ) , sehingga dapat dinyatakan sebagai ∑ ∏ di mana . Ilustrasi tahap penyusunan ulang dengan contoh kasus di atas. 1. Misalkan dan ingin bekerja sama untuk menyusun ulang rahasia yang telah dipecah, maka setiap pasangan nilai yang diberikan akan diverifikasi mengenai kebenarannya menggunakan tahap verifikasi. Jika pasangan nilai yang diberikan adalah benar maka rahasia tersebut dapat dicari dengan menghitung nilai ( ) ) ( )( ) 2. Pasangan nilai yang diketahui adalah ( ( )( ) ( )( ) ( ) dan ( ) ( ), maka akan dihitung nilai . ∏
∏
∏
Setelah nilai
didapatkan, maka nilai
dapat dihitung
10 ( ) ∑ ( (
) ( (
)
) )
Implementasi Skema Feldman Pada bab ini akan dijelaskan bagaimana skema Feldman dapat diaplikasikan menggunakan perangkat lunak Wolfram Mathematica 9 dengan contoh yang sama seperti yang tertera pada bab sebelumnya. Pada gambar 1 akan dijelaskan bagaimana langkah memasukkan nilai sebagai berikut.
Gambar 1 Langkah pembentukan shares Pada Gambar 2 dapat dilihat output berupa nilai diberikan secara umum.
dan
yang
Gambar 2 Hasil keluaran parameter ) yang akan diberikan secara rahasia kepada setiap Pasangan nilai share ( party. Hal tersebut dapat dilihat pada Gambar 3.
11
Gambar 3 Hasil keluaran pasangan share Pada tahap selanjutnya akan dilakukan proses verifikasi. Tahap verifikasi dilakukan untuk mengetahui apakah pasangan nilai share yang diberikan benar atau tidak yang ditunjukkan pada Gambar 4.
Gambar 4 Langkah verifikasi Apabila pada langkah verifikasi telah dilakukan, maka akan diketahui apakah pasangan share benar atau tidak. Pada Gambar 5 menunjukkan jawaban pasangan nilai share jika benar pada keluarannya.
Gambar 5 Keluaran yang dihasilkan benar Pada tahapan terakhir akan dilakukan tahapan penyusunan ulang untuk dilakukan penggabungan lima pasang share untuk mendapatkan kata sandi yang telah dibagi sebelumnya. Tahapan penyusunan ulang dapat dilihat pada gambar 6 sebagai berikut.
Gambar 6 Langkah penyusunan ulang
12 Setelah melewati tahapan penyusunan ulang maka akan diketahui kode rahasia yang disimpan. Hal tersebut dapat terjadi apabila didapatkan nilai dari kata sandi jika pasangan share yang diberikan benar yang ditunjukkan pada Gambar 7.
Gambar 7 Kode rahasia yang disimpan Analisis Keamanan Skema Feldman Dari perhitungan nilai komitmen di atas dapat terjadi kebocoran mengenai rahasianya karena dihitung nilai . Dengan mengubah bentuk menjadi dengan adalah bilangan bulat positif, lalu dengan menggunakan logaritma diskret nilai dari dapat dicari karena nilai dan diberikan secara umum. Hal tersebut dapat diatasi dengan memilih nilai yang memiliki ukuran yang lebih panjang sehingga pencarian menggunakan logaritma diskret menjadi lebih rumit untuk dilakukan. Dengan menggunakan contoh yang sama seperti contoh pada bab sebelumnya didapatkan nilai dari . Selain itu juga diketahui nilai dan . Jika ada seseorang yang mengetahui cara untuk mencari nilai adalah , dengan mensubtitusi nilai maka akan didapatkan . Hal pertama yang harus dilakukan adalah mengubah bentuk menjadi , dengan menggunakan logaritma diskret dapat dihitung nilai ( ) dengan adalah bilangan bulat positif. Hal ini dapat dihitung tetapi akan membutuhkan waktu komputasi yang sangat lama karena tidak ada metode umum yang efisien untuk menghitung logaritma diskret di komputer konvensional.
SIMPULAN DAN SARAN Simpulan Skema Feldman merupakan perbaikan dari kekurangan yang dimiliki oleh skema Shamir, oleh karena itu skema Feldman juga didasari oleh interpolasi Lagrange. Perhitungan yang dilakukan dalam skema Feldman banyak menggunakan perhitungan aritmetika modular. Tahapan skema Feldman dibagi menjadi dua bagian yaitu pembagian kunci dan penyusunan kunci. Tahap pembagian kunci terdiri dari tahap penentuan parameter dan tahap distribusi, sedangkan tahap penyusunan kunci terdiri dari tahap verifikasi dan tahap penyusunan ulang. Setelah dilakukan analisis keamanan pada skema Feldman didapatkan sebuah kebocoran informasi rahasia dari perhitungan komitmen. Kebocoran informasi rahasia tersebut menyebabkan rahasia dapat dicari menggunakan logaritma diskret.
13
Saran Pada perhitungan komitmen yang dilakukan pada tahap distribusi didapatkan sebuah kebocoran informasi rahasia. Oleh karena itu, sebaiknya dicari nilai p yang cukup panjang sedemikian sehingga jika dilakukan perhitungan rahasia menggunakan logaritma diskret akan membutuhkan waktu yang sangat lama untuk menyelesaikannya.
DAFTAR PUSTAKA Fu-tai Z, Fang-guo Z, Yu-min W. 2002. A Secure and Efficient General VSS Protocol.13(07):1187-1192. Kudryavtsev LD, Samarin MK. Encyclopedia of Mathematics: Lagrange Interpolation Formula. [diunduh 2014 Februari 12]. Tersedia pada: http://www.encyclopediaofmath.org/index.php?title=Lagrange_interpolati on_formula&oldid=17497. Mathews JH, Fink KD. 1999. Numerical Methods Using MATLAB Fourth Edition. New Jersey (US): Pearson Education, Inc. Menezes A, Oorschot Pv, Vanstone S. 1996. Handbook of Applied Cryptography. New York (US): CRC Pr. Sadikin R. 2012. Kriptografi Untuk Keamanan Jaringan. Yogyakarta (ID): ANDI.
14 Lampiran 1 Tahap pembentukan share pada skema Feldman
Lampiran 2 Tahap verifikasi skema Feldman
Lampiran 3 Tahap penyusunan ulang skema Feldman
15
RIWAYAT HIDUP Penulis dilahirkan di Jakarta pada tanggal 18 Maret 1994 sebagai anak pertama dari tiga bersaudara, dengan ayah bernama Ir Endi Supriyono dan ibu bernama Dra Reiza Kurnia Rinanti. Penulis memulai pendidikannya pada tahun 1999 di SDNP Kompleks IKIP DKI Jakarta dan lulus pada tahun 2004. Melanjutkan pendidikannya di SMP Negeri 92 Jakarta Timur dan lulus pada tahun 2007. Pada tahun 2010, penulis lulus dari SMA Negeri 12 Jakarta Timur dan pada tahun yang sama diterima di Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor melalui jalur Undangan Seleksi Masuk IPB (USMI). Penulis juga terdaftar sebagai mahasiswa penerima beasiswa Peningkatan Prestasi Akademik (PPA) yang diadakan oleh IPB. Selama mengikuti perkuliahan di IPB, penulis pernah menjadi pengurus GUMATIKA divisi Math Event pada tahun 2012. Penulis aktif dalam komunitas fotografi Shutter IPB divisi Hunting dan Materi (Humer) periode 2013/2014 dan aktif dalam beberapa kepanitian di kampus dan di organisasi. Penulis pernah menjadi asisten dosen mata kuliah Kalkulus II pada tahun ajaran 2012/2013 dan mata kuliah Pemrograman Linear pada tahun ajaran 2013/2014. Pada tahun 2013 penulis menjadi juara 3 perlombaan SPIRIT cabang fotografi.
