Skema Pembagian Data Rahasia dari Shamir (Bagian 2)

Selain menggunakan metode eliminasi Gauss untuk menemukan solusi polinom interpolasi, metode lain yang dipakai untuk membentuk polinom secara langsung adalah dengan menggunakan metode interpolasi. Jika anda pernah mengambil kuliah metode numerik, anda tentu pernah mempelajari metode-metode meninterpolasi sejumlah titik data dengan polinom.

Salah satu metode interpolasi polinom adalah Polinom Lagrange. Misalkan diberikan t buah titik yaitu (x1, y1), (x2, y2), …, (xt, yt). Polinom Lagrange, dalam modulo p, yang melalui t titik adalah polinom derajat t– 1:

                                        p(x)  = y1L1(x1) + y2L2(x2) + … + ytLt(xt) (mod p),

yang dalam hal ini:

Polinom Lagrange ini harus dirahasiakan supaya pihak lawan tidak bisa menghitung secret M. Untuk memperoleh secret M caranya mudah, yaitu bila diketahui polinom p(x) maka hitung p(x) pada x = 0.

Misalkan partisipan 2, 3, dan 7 menggunakan interpolasi Lagrange, mereka mengumpulkan semua share mereka:
(x1, y1) = (2, 1045116192326)
(x2, y2) = (3, 154400023692)
(x3, y3) = (7, 973441680328)

Mereka kemudian membentuk polinom Lagrange derajat dua:p(x) = y1L1(x1) + y2L2(x2) + y3L3(x3) (mod p), dan diperoleh hasilnya sebagai berikut:

p(x) =  20705602144728/5 – 1986192751427x + (1095476582793/5)x2 (mod p)

Karena polinom  dihitung dalam modulus p dan dengan mengingat 740740734080  dikali 5 kongruen dengan 1 (mod p), maka 1/5 dapat diganti dengan 740740734080, sehingga kita memperoleh polinom tanpa modulo p:

p(x) = 190503180520 + 482943028839x +120674920705602144728x2

Untuk memproleh M, hitung p(0), dan diperoleh p(0) = 190503180520 = M, yaitu secret semula.

 

Referensi

1. Trappe, W., Washington, L. (2006): Introduction to Cryptography with Coding Theory, Prentice Hall.

Tinggalkan komentar

Filed under Secret sharing

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s