KUNCI RAHASIA DALAM KONSTRUKSI SKEMA PEMBAGIAN RAHASIA

AL. SUTJIJANA, DRS.,M.SC., Prof. Dr. Subanar; Prof. Dr. Soeparna; Prof. Jogiyanto HM, MBA, Ph.D

2015 | Disertasi | S3 Matematika

Skema Pembagian Rahasia (Secret Sharing Scheme) merupakan suatu metode mendistribusikan rahasia kepada sekelompok peserta dengan cara masing-masing peserta diberi suatu bagian dari rahasia sedemikian sehingga hanya sekelompok (subset) tertentu dari para peserta tersebut yang dapat memecahkan rahasia dengan cara menggabungkan semua yang mereka dapatkan. Untuk sebarang skema pembagian rahasia, kunci rahasia K dipilih oleh seseorang yang disebut dealer D. Kemudian dealer memecahkan kunci ini atas beberapa bagian yang disebut share dan membagikannya secara rahasia kepada semua anggota himpunan peserta P. Diasumsikan D tidak berada di P. Pada saat tertentu beberapa peserta yang tergabung dalam suatu himpunan B mengumpulkan masing-masing sharenya. Dalam kasus skema threshold dengan ambang batas t, apabila banyak anggota himpunan B lebih besar atau sama dengan t maka kunci rahasia K dapat terpecahkan oleh sekelompok peserta yang tergabung membentuk himpunan B. Sedangkan jika banyak anggota himpunan B kurang dari t, maka kunci K tidak dapat dipecahkan oleh sekelompok peserta yang tergabung membentuk himpunan B. Dalam skema Shamir, yang dikenal dengan (t,w)- threshold scheme, dealer pada awalnya menentukan lapangan hingga GF(p) dengan p merupakan bilangan prima dan p lebih besar atau sama dengan w+1. Selanjutnya dealer membentuk suku banyak berderajat t-1 dengan koefisien-koefisiennya atas lapangan Z modulo p, f(x) = K+ jumlahan a indeks j kali x pangkat j, untuk nilai j dari 1 sampai dengan j = t - 1 modulo p, dan menetapkan suku konstan K sebagai kunci rahasia yang harus dipecahkan. Kemudian dealer memilih w elemen yang berbeda dan bukan elemen nol dalam Z modulo p, yang dinotasikan dengan x indeks i, dengan i berjalan dari 1 sampai dengan w. Selanjutnya dealer memberikan masing-masing share x indeks i kepada perserta P indeks i dalam P, kemudian menghitung nilai-nilai y indeks i = f(x indeks i). Sehingga setiap peserta P indeks i berkorespondensi dengan (x indeks i,y indeks i). Apabila ada sebanyak t peserta berkumpul dan memberikan sharenya maka akan terdapat t pasangan (x indeks i, y indeks i) yang berbeda dan dapat dipandang sebagai adanya t titik berbeda pada bidang datar R pangkat 2. Dengan interpolasi suku banyak, suku banyak f(x) = K+ jumlahan a indeks j kali x pangkat j, untuk nilai j dari 1 sampai dengan j = t - 1 dapat direkonstruksi kembali dengan diketahuinya t titik yang berbeda tersebut, yang akhirnya kunci rahasia K dapat dipecahkan. Dalam disertasi ini diperkenalkan konsep baru tentang perluasan Skema Pembagian Rahasia yang dikembangkan oleh Shamir. Pengembangan dilakukan dengan cara memperluas lapangan hingga yang semula GF(p) menjadi GF(p pangkat 2) dan bahkan lebih umum lagi yaitu GF(p pangkat n). Begitu pula untuk suku banyak juga diperumum dari yang semula f(x) = K+ jumlahan a indeks j kali x pangkat j, untuk nilai j dari 1 sampai dengan j = t - 1, dalam notasi yang lebih sederhana f(x) = jumlahan a indeks i dikalikan dengan x pangkat i dengan i berjalan dari 0 sampai dengan t-1 , atas GF(p) menjadi f(x) = jumlahan a indeks i dikalikan dengan (x pangkat i dengan x pangkat q i ) dengan i berjalan dari 0 sampai dengan t-1 atas GF(p pangkat n). Beberapa keuntungan dan manfaat yang diperoleh dalam konstruksi ini diantaranya adalah banyaknya peserta yang terlibat menjadi lebih banyak, yang semula sebanyak q peserta menjadi q pangkat 2 dan bahkan q pangkat n. Di samping itu untuk memecahkan kunci rahasia juga jauh lebih sulit dibandingkan dengan menggunakan konstruksi Shamir karena dengan bergabungnya t peserta yang memberikan sharenya mengakibatkan terkonstruksinya t persamaan linear dengan t variabel. Sistem persamaan linear yang terbentuk tersebut mempunyai determinant koefisien yang strukturnya unik dan berpola menyerupai determinant Vandermonde. Permasalahan merekonstruksi suku banyak f(x) di atas menjadi identik dengan permasalahan menunjukan bahwa nilai determinant matriks koefisien sistem persamaan linear yang terbentuk tidak nol. Hal ini yang mendorong peneliti untuk melakukan penelitian lebih dalam pada perhitungan determinant yang terbentuk dari sistem persamaan linear pada skema Shamir yang diperluas atas lapangan hingga GF(p pangkat n). Secara analitik peneliti belum berhasil menunjukkan bahwa nilai determinant tidak nol tetapi dengan simulasi dan pelabelan kembali pada elemen-elemen lapangan hingga bisa ditunjukkan adanya nilai determinant sistem persamaan linear yang terbentuk tidak nol. Dengan demikian konsep skema pembagian rahasia Shamir yang diperluas dapat diterapkan.

Secret Sharing Scheme is a method of distributing a secret or a password to a group of participants in such away that every participant gets a share of the secret such that only qualified subsets of participants can recover the secret by combining their shares. In general secret sharing schemes, a dealer chooses a secret key K, and then secretly distributes the shares of the secret to a set of all participants P. It is assumed that D not in P. Some day in the future, some of participants, incorporated in a set B, combine their shares. In threshold scheme with access level t, if the cardinality of B is greater or equals to t then all of the participants in B can recover the secret K by combining all their shares. However if the cardinality of B is less than t then the participants in B can not get any information about the secret K. In Shamir's secret sharing schemes, called (t,w)-threshold scheme, the dealer determines finite field GF(p) = Z modulo p with p is a prime and p is greater or equals w+1. The dealer chooses a secret polynomial of degree t-1 with coefficients in the field Z mod p, f(x)=K+summation j sub 1} to t - 1 for a sub j times x to the j mod p, and then sets the constant term K as a secret key. The dealer chooses w non zero different elements in Z mod p, denoted by x sub i, where 1 leq i leq w. The dealer distributes each share x sub i to participant P sub i in P, and then calculates the value y sub i=f(x sub i). Each participant P sub i corresponds to (x_i,y_i). When there are t participants combining their share, there will be t different pairs (x_i,y_i) which can be regarded as t different points in the plane R to the 2. Applying Lagrange interpolation the polynomial f(x)=K+ summation j = 1 to j=t-1 times a_j times x to the j can be reconstructed, and the secret key K can be solved. In this dissertation we introduced a new concept of a generalization of Shamir's secret sharing scheme. We generalized finite fields from GF(p) to GF(p to the 2) even more general to GF(p to the n). Likewise the use of polynomials were generalized from f(x)=K+summation fromj = 1 to j=t-1 for a_j times x to the j, in simple notation f(x)=summation from i=0 to i=t-1 for a_i times x to the i, over GF(p) became f(x) = summation from i=0 to i=t-1 for a_i times x to the i+x to the iq over GF(p to the 2) or GF(p to the n). There are some advantages in this construction, among others is more participants get involved, from q become q to the 2 even q to the n participants. Beside that breaking the secret key is more difficult since by joining t participants with their share generate t linear equations of t variables. The system of linear equations formed by the t linear equations has a unique determinant coefficient where its elements structure is like Vandermonde determinant pattern. Reconstructing the above polynomial f(x) can be approached by showing that the determinant value of coefficient matrix of the system of linear equations formed above is not zero. This phenomenon encouraged us to deeply investigate to calculate the value of the determinant formed by the system of linear equations on the generalization of Shamir' scheme over finite field GF(p to then). We have not shown yet analytically that the value of the determinant is not zero, however we were able to show that there exists a determinant formed by system of linear equations which has value is not zero by employing relabeling on the elements of the finite field. From this observation, we convinced that extended Shamir's secret sharing schemes really can be applied.

Kata Kunci : Secret Sharing Scheme, threshold scheme, finite field, Vandermonde determinant.