BAB
I
PENDAHULUAN
1.1. Latar Belakang Dalam sejarah kehidupan manusia, sepanjang mereka saling berinteraksi sa-
tu dengan yang lain, akan terdapat suatu "rahasia" (secret), baik yang dimiliki oleh manusia itu sendiri maupun yang dimiliki bersama manusia
lain. Banyak diantara
mereka yang memiliki rahasia dengan setia mepertahankannya agff tidak diketahui
pihak lain, yang pada akhirnya sampai rela mengorbankan nyawanya demi rahasia tersebut. Bagi sebagian orang, yang dengan kedudukannya/posisinya, bersedia/mau mendistribusikan secara parsial !'rahasia" yang dimilikinya kepada sekelompok orang
lain (secara terbatas) dengan tujuan agar pada saat rahasia yang dimilikinya dibutuhkan untuk menjalankan aktivitas tertentu dan dia tidak ada di tempat, maka sekelompok
orang yang menerima bagian parsial rahasianya dapat mengumpulkan rahasia-rahasia
yang mereka miliki kemudian menggunakannya sebagai aktivasi dalam menjalankan aktivitas kelompok tersebut. Dalam menjaga kerahasiaan terdapat suatu prinsip yang
terkenal dalam dunia analog yaitu kepercayaan tereduksi (reduced trust) , yang artinya agar suatu "rahasia" itu tetap terjaga maka akan semakin baik apabila masingmasing entitas (orang-orang di sekitar) mempunyai semakin sedikit pengetahuan/in-
formasi atau kekuatan yang dimiliki untuk memahami rahasia tersebut. Prinsip inilah yang merupakan fllosofi dasar yang menurut Malkhi 126l dapatjuga diimplementasikan dalam dunia digital. Skema Pembagian Rahasia (Secret Sharing Scheme) merupakan suatu metode
mendistribusikan rahasia (secret/passworfi kepada sekelompok peserta (participants
) dengan cara masing-masing
peserta diberi suatu bagian dari rahasia (share) sede-
mikian sehingga hanya sekelompok (subset) tertentu dari para peserta tersebut yang dapat memecahkan rahasia dengan cara menggabungkan semua share yang mereka
dapatkan. Secara formal, dalam skema pembagian rahasia terdapat seorang dealer
dan
participant Qtlayer) sebanyak rz. Dealer tersebut memberikan rahasia kepada
peserta tetapi hanya yang memenuhi kondisi tertentu. Masing-masing peserta dibe-
ri
suatu share sedemikian sehingga setiap kelompok peserta yang beranggotakan
t
(untuk thresholQ atau secara bersama-sama dapat merekonstruksi rahasia tersebut sedangkan bagi kelompok peserta yang beranggotakan kurang dari
, tidak akan dapat
merekonstruksi rahasia. Skema pembagian rahasia pertama kali diperkenalkan secara
terpisah oleh Blakley [8] dan Shamir [35] pada tahun 1979 sebagai salah satu penyelesaian dalam menjaga keamanan kunci kriptografi. Dalam beberapa kasus sering
dijumpai adanya satu kunci saja(master key) yang dapat digunakan untuk mengakses obyek rahasia. Sehingga yang menjadi masalah utama adalah "bagaimana menyimpan kunci tersebut di tempat yang aman untuk menghindari kerusakan, kehilangan, maupun penyalahgunaannya". Pada umumnya hal ini sangatlah tidak bisa diandalkan, apabila master kay tersebut hilang atau rusak maka semua informasi yang akan diakses melalui master key tidak akan tersedia lagi. Salah satu kemungkinan untuk mengatasi masalah ini adalah membuat duplikat kunci tersebut dan menyimpannya
di tempat terpisah yang aman, atau memberikan duplikatnya kepada orang yang dapat dipercaya. Dalam hal ini keamanan sistem menjadi lemah atau mudah bocor, seperti yang diungkapkan dalam l3l,1261,1271,1351, dan [39]. Salah satu cara un-
tuk mengatasi permasalahan tersebut adalah dengan metode skema pembagian rahasia (Secret Sharing Scheme), yaitu memecah master l<ey tersebat menjadi beberapa
bagian kemudian membagi-bagikannya kepada beberapa orang yang dapat dipercaya dan untuk dapat mengakses kembali obyek rahasia tersebut dibutuhkan kehadiran beberapa orang penerima bagianlpecahan master key yang merupakan anggota dari access structure. Skema pembagian rahasia dapat juga digunakan untuk situasilkeadaan yang membutuhkan pengamanan untuk mengakses resource (tempat/datalalat)
penting oleh orang-orang tertentu/terbatas. Dalam hal ini, untuk melakukan aktivasi/eksekusi memerlukan persetujuan dari beberapa orang. Seperti halnya untuk membuka peti uang di bank, peluncuran pelur kendalilnuklir, maupun membuka berkas catatan kesehatan pasien rumah sakit.
3
Pada awalnya skema pembagian rahasia hanya memperhatikan pada banyak-
nya peserta yang dapat mengakses atau merekonstruksi kembali kunci rahasia. Skema pembagian rahasia semacam ini dikenal dengan nama skema pembagian rahasia
threshold (threshold secret sharing scheme). Kemudian berkembang berbagai skema pembagian rahasia yang memilihi access structure lebih kompleks dibandingkan dengan yang
dimiliki
skema threshold. Diantaranya adalah weight threshold secret
scherne, hierarchical, multilevel secret sharing scheme, compartmented secret sha-
ring scheme, perfect secret sharing scheme, ideal secrete sharing scheme.
1.2.
Permasalahan Skema pembagian rahasia merupakan salah satu alternatif untuk meng-
amankan kunci dalam kriptografl. Konstruksi-konstruksi skema pembagian rahasia
perlu dikembangkan agar rahasia tidak mudah untuk dipecahkan. Dengan semakin berkembangnya ilmu pengetahuan dan teknologi komputasi, beberapa pertanyaan yang berkembang pada saat ini diantaranya:
1, Metode-metode konstruksi skema pembagian rahasia dengan teori aljabar linear apakah yang masih bisa dikembangkan?
2. Bagaimanakah
konsep acces structure dikaitkan dengan teori himpunan?
3. Bagaimana mengkonsffuksikan
skema pembagian rahasia yang paling sesuai
dengan kebutuhan?
4. Bagaimanakah model-model yang terbentuk
dapat diterapkan pada dunia nya-
ta?
Sejauh yang penulis ketahui baik dari jurnat-jurnal yang ada maupun informasi
y*g
didapat dari internet dan buku-buku yang terkait, belum ditemui adanya penelitian tentang perluasan skema pembagian rahasia Shamir dengan memodifikasi atau menambahkan suatu suku pada suku banyak yang dirahasiakan dan lapangan perluasannya. Penelitian ini perlu dilakukan karena dengan berkembangnya ilmu pengetahuan dan berkembangnya teknologi komputasi menuntut untuk bekerja pada sistem
4
yang lebih luas. Adapun masalah yang akan dibahas dalam disertasi ini meliputi cara mengkonstruksikan suatu model skema pembagian rahasia berupa (t,n)-threshold scheme,
t I
n, yaitu suatu model yang mempunyai sifat kunci rahasia selalu da-
I peserta dari keseluruhan n peserta yang terlibat. Dealer memilih secara random suku banyak berderajat t -- L berbentuk t-t : (*) f D-,.(ro + niq) atas lapangan GF(q"). Dealer memilih 2as sebagai kunpat dipecahkan oleh kehadiran minimal
d:o
ci rahasia dan menjaganya agar kunci ini tidak diketahui oleh n peserta. Para peserta hanya menerima dari dealer bagian rahasia yang harus mereka jaga terhadap peserta
yang lain yaiu
(ri, f (xr)),i:1,,2,,n.
Akan diteliti bagaimana suku banyak
/(r)
benar-benar selalu dapat dikon-
struksikan ktmbali oleh setiap f peserta yang berkumpul setelah masing-masing memberikan/menggabungkan bagian rahasianya. Dengan dapat dikonstruksikan kembali suku banyak tersebut berarti kunci rahasia 2as dapat dipecahkan oleh
t peserta terse-
but, Berbeda dengan skema Shamir yang dalam merekonstruksi kembali suku ba-
nyak rahasia dapat menggunakan metode interpolasi Lagrange, dalam penelitian ini terdapat kendala yang diakibatkan oleh kompleksnya suku-suku penyusun suku ba-
nyak. Sehingga metode interpolasipun menjadi sukar untuk dilakukan. Hal ini mendorong peneliti untuk melakukan beberapa simulasi pemrograman dan melakukan pelabelan kembali pada anggota-anggota lapangannya.
1.3.
Maksud dan T[juan Penyususunan disertasi
ini mempunyai dua tujuan, yaitu
tujuan khusus. Tujuan umum penelitian ini meliputi
tuJuan umum dan
:
1. Berperan aktif dalam penelitian bidang aljabar.
2. Ikut berpartisipasi di dalam
pengembangan ilmu pengetahuan dasar khususnya
ilmu dasar, yaitu bidang matematika.
3. Ikut memberikan
sumbangan pemikiran terhadap terapan ilmu pengetahuan da-
sar, terutama bidang aljabar.
Sedangkan tujuan ktrusus penelitian ini untuk mengembangkan model pegkonstruksian skema pembagian rahasia secara umum. Beberapa topik yang akan dikembangkan
diantaranya sebagai berikut:
1. Mengembangkan dan memperoleh suatu metode untuk kostruksi skema pembagian rahasia secara umum dengan Matrik Proyeksi.
2. Mengembangkan
pada butir 1 untuk skema threshold (threshold scheme) mau-
pun skema ramp (ramp scheme).
3. Mengembangkan
metode kontruksi Shamir dengan memperumum fungsi suku
banyak atas lapangan hingga yang lebih luas.
4. Mengaplikasikan teori konstruksi yang terbentuk
1.4.
pada permasalahn real.
Tinjauan Pustaka Skema pembagian rahasia, yang pertama kali diperkenalkan secara terpisah
oleh Blakley [8] dan Shamir [35] pada tahun 1979, pada mulanya digunakan sebagai solusi dari masalah pengamanan kunci-kunci kriptograpi. Dalam skema Shamir
(t,n)-threshold
scheme, setiap
t
peserta dapat merekonstruksi kunci rahasia
K,
te-
tapi bagi kelompok peserta dengan banyak anggota kurang dari t tidak akan pernah dapat merekonstruksi kunci
at
K.
Skema
Zo, untuk suatu bilangan prima
ini menggunakan perhitungan dalam lapang-
p.
Kunci rahasia
K
diambil sebagai anggota
lapangan. Dealer (orang yang akan membagi kunci rahasia) secara random memi-
lih ,
- 1 anggota Zo, katakan at,a2,...,at-y, kemudian membentuk suku banyak f (x) : K + afi * azr2 + ... + at-rnt-r (mod p). Dealer memilih secara random
anggota 16 dalam Zo dan menghitung f (*u,
f (*u))
kepada peserta ke
maka suku banyak
f (r)
@).
Kemudian dealer membagikan share
i. Jika k peserta berkumpul dan memberikan
sharenya,
dapat direkonstruksikan dengan menggunakan rumus inter-
polasi Lagrange. Suku konstan, yang merupakan kunci rahasia, bisa didapat dengan
6
menghitung nilai suku banyak pada saat
r:
0. Jika terdapat kurang dan k peserta
yang menggabungkan sharenya maka suku banyak yang dapat dibentuk belum ten-
tu tunggal. Sehingga suku konstan (kunci rahasia) bisa sebarang anggota lapangan. Dengan kata lain kunci rahasia belum tentu dapat dipecahkan.
Model skema pembagian rahasia yang dikonstrulaikan oleh Blakley [8] didasarkan pada pemilihan kunci rahasia yang diambil dari anggota ruang vektor
sedangkan share-sharenya sebarang
n hyperplane yang berbeda berdimensi k
yang memuat kunci rahasia. Hyperplane berdimensi k
tuk {r1, fr2,...,r* e GFt lar.frt sebarang anggota dalam
I
GFt,
az.rz+
...
-
- |
1 berupa himpunan berben-
+ a*.frk: 0),dengan d1.,a2,...ar,,0
G,Fr. Kunci rahasia bisa didapat dengan memotongkan k
share (bidang hyperplane).
Berbagai pengembangan skema pembagian rahasia dilakukan. Diantaranya oleh Brickell t10l untuk ideal secret sharing scheme. Kemudian dilanjutkan oleh Be-
imel dan Chor [5] untuk universal ideal secret sharing scheme yang digunakan untuk melengkapi bukti pada bagian syarat perlu pada ideal secret sharing scheme sehingga didapat pernyataan syarat perlu dan cukup agar suatu access structure merupakan
ideal universal adalah access structure merupakan ideal atas secret biner dan ternier. Sedangkan Miller dalam 128,291memanfaatkan skema pembagian rahasia dalam menjaga keamanan data base. Pada tahun 1991, Brickell dan Davenport [11] mengusulkan suatu model un-
tuk skema pembagian rahasia berdasarkan suatu matriks. Mereka mendefinisikan skema pembagia rahasia sebagai matriks berhingga yang identik. Matrik
M mempunyain *
1
M
dengan tidak ada dua baris
kolom. Kolom pertama berkorespondensi
dengan dealer, sedangkan kolom-kolom sisanya berkorespondensi dengan pesertapeserta. Elemen pada baris ke
Untuk setiap
r
dan kolom ke p pada
M dinotasikan
i € {0, 1,2,3, ...,n} didefinisikan S(r) : {M,tlr
dengan M (r, p).
suatu baris dari
M},
yaitu S(p) merupakan himpunan elemen-elemen yang ada pada kolom p. Himpunan kunci-kuncinya adalah setiap
i,l I
o
^9
:
^9(0)
dan himpunan share-nya adalah
^9r
:
S(e) untuk
I n. Dealer memilih kunci K e S dan suatu baris r dari M sede-
: K. Sehingga share-share yarLg dibagikan pada pesertake adalah M4 untak setiap I < i < n. Matrik M diinformasikan secara terbuka, tetapi mikian sehingga M,,3
r
i,
dirahasiakan. Metode-metode konstruksi yang ditekankan pada kombinatorial dilakukan oleh
Stinson [36] pada tahun 1992. Masalah utama yang diperhatikan adalah konstruksi perfect secret sharing scheme, untuk access structure tertentu, dengan kemungkinan
information rate yarlg maksimum. Pada tahun 1997, Csirmaz dalarn [15, 16] membuktikan bahwa untuk setiap bilangan bulat positif structure untuk
n
n
dapat ditemukan suatu access
peserta sehingga sebarang perfect secret sharing scheme harus
memberikan share kepada pesertanya sekurang-kurangnya sekitar
ofo kali
ukuran
kunci (rahasia)nya. Ia juga menunjukkan bahwa kemungkinan hasil terbaik yang bisa didapat dengan menggunakan teori informasi yang dipakai adalah n kali ukuran kun-
ci (rahasia)nya. Um dan Delp [40] mengusulkan penggunaan teknik perfect
secret
sharing scheme untuk konstruksi percabangan kunci. Konstruksi skema pembagian rahasia dengan komputasi aljabar juga dilakukan. Diantaranya oleh Mingsheng dan kawan-kawan [30]. Konstruksi dilakukan berdasarkan pada algoritma pembagian dan basis Grobner.
Mencari hubungan antara skema pembagian rahasia dengan matroid telah di-
lakukan. Matroid
I :
(I4
/)
adalah himpunan berhingga
merupakan koleksi himpunan-himpunan bagian
duiV
V
dan himpunan
I
yang
yang memenuhi sifat-sifat
l.AeI 2.
Jtka
X€I
danY C
X makaY € I
X,Y anggota-anggota.I sehinggaYu{r}eI.
3. Jika
dengan
lxl : lyl + 1 maka terdapat r € X -Y
Seymor [34] menunjukkan bahwa tidak semuamatroid merupakan secret sha-
ring matroid, dengan mengambil contoh Vamos matroid bukan merupakan skema pembagian rahasia. Demikian juga Cramer dan kawan-kawan [14] melakukan peng-
kajian yang berkaitan dengan hubungan antara code, matroid, dan suatu kelas skema
pembagian rahasia, yantl multiplicative linear secret sharing scheme. Sedangkan
panAf dan PadrA$ t18l mencari hubungan keterkaitan antara information rate
dan
access structure dan berhasil membuktikan bahwa apabila information rare suatu ske-
ma pembagian rahasia lebih besar dari fr maka access structurenya berkaitan dengan suatu matroid. Hal yang sama juga dilakukan oleh Nikova dan
Nikov [31, 32f . Mere-
ka membangun skema pembagian rahasia berdasar pada matroid dan error correcting
code,kemadian mencari hubungan antara ideal secret sharing scheme, matroid, dan
error correcting code. Hal yang
sama
juga ditunjukkan oleh Dijk [17] dan Rudra
t331.
Permasalahan untuk mendesain skema pembagian rahasia yang mempunyai sifat tambahan, yaitu kelompok minoritas yang terpilih dapat melarang sebarang himpunan dari para peserta untuk merekonstruksikan kunci rahasia, dikembangkan oleh
Blundo dan kawan-kawan [9]. Pengembangan dilakukan setelah Bentelspacher [7] memberikan suatu algoritma, yang berdasarkan geometri proyektif, untuk mengkonstuksikan threshold scheme yang mempunyai sifat kelompok minoritas teqpilih mempunyai kemampuan untuk melarang mengkonstruksi kunci rahasia. Modiflkasi dila-
kukan dengan menggunakan alat teori error conecting code yang diterapkan pada algoritma skema pembagian rahasia model Shamir untuk mengatasi masalah yang lebih umum. Banyak penelitian dilakukan untuk threshold scheme. Diantaranya oleh Jackson dan kawan-kawan [20] yang melakukan penelitian tentang konsffuksi multisecret
threshold scheme yang memenuhi batas bawah informasi yang dimiliki oleh para peserta agar mereka yang berkumpul dengan jumlah kurang dari batasan tertentu betul-
betul tidak bisa mengakses kunci rahasia. Stinson [37] memandangvisual cryptogra-
py sebagai skema pembagian rahasia yang menggunakan sistem penglihatan (visual) manusia untuk melakukan perhitungan-perhitungan, kemudian mengembangkannya
untuk konstruksi threshold scheme. Pada tahun 2005, Stoleru [38] mengembangkan apa yang telah dilakukan oleh Stinson untuk extended visual cryptography scheme.
Skema pembagian rahasia yang menggunakan gambar (image) sebagai kunci raha-
sia maupun share yang dibagikan juga dikembangkan, diantaranya oleh Chang dan
Kieu [12]. Sedangkan pengembangan threshold scheme untuk pemakaian lebih luas diusulkan oleh Jhonson
[21]. Model dasar yang digunakan Jhonson adalah (n,n)
threshold scheme, kemudian diperluas untuk access structure yang lebih umum. Pe-
nelitian tentang threshold scheme yang diasosiakan dengan suatu matriks juga dilakukan oleh Bai dalam [1]. Penyelesaian masalah skema pembagian rahasia dengan pendekatan access structure dalam bentuk hirarki yang diusulkan oleh Chang pada tahun 2004 menjadi landasan bagi penelitian yang dilakukan oleh
Lin dan Lee [25]. Mereka mengadopsi
penggunaan one way hash function untuk mengijinkan share yang diberikan untuk digunakan kembali untuk mencapai sifat-sifat access control yang bersifat hirarki.
Hasil yang diperoleh menunjukkan bahwa skema pembagian rahasia ini lebih efisien dibandingkan dengan skema pembagian rahasia yang diusulkan oleh chang. Penelitian yang dilakukan oleh Krause dan Simon [23] berdasarkan pada ukuran scheme yang disebat contrast, yaitu kejelasan (clarity) dimana suatu pesan men-
jadi terlihat (visible). Parameter ini terletak pada interval [0, 1], dengan nilai kontras 1 berarti "perfect clarity" dan kontras 0 berarti "irwisibility". Ditunjukkan bahwa kemungkinan kontras terbesar C6,n dalam (k,n) skema pembagian rahasia mendekati
4-(x-t). Lebih tepatnya 4-(*-t) {. C*,n q 4-(t-t)rrk l@ _
k)1.
Pada tahun 2007, Beimel dan Franklin [4] mengkonstruksikan skema pemba-
gian rahasia dengan panjang kunci rahasia l-bit dan sharenya ((, + Q-ait, dengan c suatu konstanta yang besarnya tergantung pada access structure yang diberikan.
konstruksikan pula
fficient weakly private scheme untuk threshold
Di-
access structure
dengan sharenya satu bit secret. Pada tahun 2008, Belenkiy [6] menyajikanideal disjunctive multi-level secret
sharing scheme yang sederhana. Disjunctive multi-level secret sharing scheme mem-
bagi participant (user) menjadi beberapa tingkat-tingkat yang berbeda. Setiap level .L berasosiasi dengan
suatl threshold ty dan sekelompokuserbisame-recoverkunci
rahasia hanya jika, untuk suatu -L, terdapat sekurang-kurangnya
t7 user pada level
10
0......L pada kelompok tersebut. Padaproactive secret sharing scheme dilakukanpenyesuaian, yaitu secaraper-
iodik mengupdate share yang didistribusikan. Berdasarkan proactive scheme, Wang dan kawan-kawan [42] pada tahun 2008 mengusulkan completely mobile proactive secret sharing scheme, yaitu skema yang tidak hanya memberikan keleluasaan untuk merubah jumlah peserta n, tetapijuga merub ah threshold
k
secara bebas. Kemudian,
dengan teknik yang mereka kembangkan, diterapkan pada sistem transaksi komersial pada dunia real untuk memenuhi syarat pengiriman berbasis kepercayaan (trust-base
delivery).
1.5. MetodologiPenelitian Penelitian tentang Kunci Rahasia dalam Konstruksi Skema Pembagian Rahasia
ini dilakukan
dengan kombinasi beberapa langkah yang komprehensif. Langkah
pertama meliputi kajian pustaka tentang Konstruksi Skema Pembagian Rahasia secara umum berdasarkan model yang sudah ada. Selanjutnya dilakukan pengamatan pada jenis-jenis matriks apa saja yang mungkin dapat dipakai sebagai kunci rahasia. Langkah berikutnya adalah melakukan analisis apakah konstruksi dengan matriks
yang sudah dipilih tersebut sesuai dengan kriteria idealnya suatu skema pembagian rahasia. Apabila sudah didapat model matriks yang cocok untuk konstruksi skema pembagian rahasia yang umum, selanjutnya dikembangkan untuk skema pembagian rahasia yang mempunyai sifat khusus, seperti hanya Threshold Scheme, Perfect Scheme, Ideal Scheme, Ramp Scheme dan yang lainnya.
