Skema Pembagian Data Rahasia dari Shamir (Bagian 1)

Ada segerombolan perompak kapal yang beranggotakan 6 orang. Mereka sepakat  untuk menyimpan uang hasil rampasan mereka di bank. Untuk itu mereka perlu membuka rekening baru di sebuah bank. Pihak bank akan memberikan PIN kartu ATM kepada para perompak tadi. Masalah muncul karena keenam perompak kapal itu tidak saling percaya satu sama lain.  Mereka tidak mau salah seorang dari mereka berkhianat lalu menarik uang dengan PIN tersebut tanpa sepengetahuan yang lain. Oleh karena itu, para perompak meminta anda sebagai orang yang adil untuk menyelesaikan masalah mereka. Anda meminta pihak bank untuk membagi PIN menjadi enam bagian (share), tetapi untuk merangkainya menjadi PIN yang utuh dibutuhkan paling sedikit  tiga buah share dari  tiga orang perompak. Bagaimana bank dapat melakukan pembagian ini?

Persoalan di atas ditemukan jawabannya oleh Adi Shamir dari MIT di dalam makalahnya yang berjudul How to Share a Secret. Makalah tersebut dimuat di dalam majalah Communication of the ACM 22 (11):  612-613 pada tahun 1979. Secret  adalah istilah untuk data atau informasi rahasia seperti kunci kriptografi, password, PIN,  dan sebagainya. Secret sharing adalah metode membagi a secret menjadi sejumlah bagian (share), masing-masing bagian diberikan kepada sejumlah partisipan (orang atau pihak yang memperoleh share). Setiap bagian adalah unik satu sama lain dan untuk merekonstruksi secret semula diperlukan beberapa (atau semua) bagian.

Misalnya jika anda memiliki kunci enkripsi “1234abcd” dan membaginya kepada beberapa orang yang dipercaya, bagaimana cara membagi kunci ini kepada orang-orang tersebut menjadi setiap bagian? Cara yang sederhana adalah memotong-motong kunci tersebut, misalnya “12”, “34”, “ab”, dan “cd” dan memberikan setiap bagian kepada setiap orang. Namun, metode ini tidak dapat digunakan jika hanya beberapa share saja yang diperlukan untuk merekonstruksi kunci  semula. Diperlukan semua share dari semua orang untuk merekonstruksi kunci semula.  Lagipula, jika jumlah parstisipan banyak sedangkan ukuran secret relatif pendek, metode pembagian sederhana seperti itu tidak dapat diterapkan.  Bagaimana anda membagi PIN “1234” kepada 20 orang?

Pada tahun 1979 Adi Shamir, di dalam makalah yang saya sebutkan di atas, mengemukakan skema pembagian secret yang dinamakan skema ambang Shamir (Shamir threshold scheme). Skema pembagian tersebut berbunyi:

Misalkan t dan w adalah bilangan bulat positif dengan t <= w. Skema ambang (t, w) adalah metode pembagian secret M kepada w partisipan sedemikian sehingga sembarang himpunan bagian yang terdiri dari t partisipan dapat merekonstruksi M, tetapi jika kurang dari t maka M tidak dapat direkonstruksi.

Untuk dapat menggunakan skema ambang Shamir tersebut maka secret harus direpresentasikan dengan integer M. Misalnya secret  ‘ABCD’  dinyatakan sebagai M = 102030405 dengan mengkodekan A = 01, B = 02, C = 03, dan seterusnya. Orang yang melakukan pembagian secret dinamakan dealer. Dealer haruslah orang yang dipercaya oleh semua parstisipan.

Secara teknis, pembagian secret M menjadi sejumlah share menggunakan konsep interpolasi polinom yang dikenal di dalam metode numerik. Di dalam teori interpolasi, untuk membentuk persamaan linier y = a0 + a1x diperlukan  2 buah titik yaitu (x1, y1) dan (x2, y2). Selanjutnya, untuk membentuk persamaan kuadratik y = a0 + a1x + a2x2 diperlukan 3 buah titik, untuk membentuk persamaan kubik diperlukan empat titik, dan seterusnya.  Secara umum untuk membentuk polinomial y = a0 + a1x + a2x2 + … + anxn diperlukan n + 1 titik.

Titik-titik tersebut disulihkan ke dalam persamaan polinom y, selanjutnya kita memperoleh sistem persamaan linier dan menyelesaikannya dengan metode eliminasi Gauss untuk memperoleh koefisien-koefisien polinom. Misalkan untuk menginterpolasi dua buah titik dengan sebuah garis lurus y = a0 + a1x, maka dua buah titik yaitu (x0, yo) dan (x1, y1) disulihkan ke dalam persamaan garis menjadi:

y1 = a0 + a1x1
y2 = a0 + a1x2

Lihat ilustrasinya pada Gambar 1 di bawah ini.

Gambar 1. Interpolasi linier

Selanjutnya sistem persamaan linier diselesaikan dengan metode eliminasi untuk menentukan a0 dan a1. Semakin banyak jumlah titiknya maka sistem persamaan linier menjadi besar, namun metode eliminasi Gauss dapat diterapkan untuk mencari solusi sistem tersebut.

Skema (t, w) yang ditemukan oleh Adi Shamir dapat dituliskan algoritmanya sebagai berikut (Trapper, 2006):

1. Pilih bilangan prima p, yang harus lebih besar dari semua kemungkinan nilai pesan M dan juga lebih besar dari jumlah w partisipan. Semua komputasi dihasilkan dalam modulus p.

2. Pilih secara acak t – 1 buah bilangan bulat dalam modulus p, misalkan s1, s2, …, st– 1, dan nyatakan polinomial:

        s(x) =  M + s1x + s2x2 + … + st – 1 xt -1 (mod p)

sedemikian sehingga s(0) =  M (mod p). Sebagai catatan, p tidak perlu rahasia, tetapi polinom s(x) harus dirahasiakan.

3. Untuk w partisipan, kita pilih integer berbeda, x1, x2, …, xw (mod p),dan setiap orang memperoleh share (xi, yi) yang dalam hal ini yi = s(xi) (mod p). Untuk memudahkan perhitungan, misalkan untuk w orang kita memilih x1 = 1, x2 = 2, …, xw = w.

4. Misalkan t orang partisipan akan merekonstruksi M, dengan share masing-masing (x1, y1), (x2, y2) …, (xt, yt). Sulihkan setiap (xk, yk) ke dalam polinomial   s(x) = M + s1x + s2x2 + … + st – 1 xt – 1 (mod p).  Ini berarti:

5. Jika dimisalkan M = s0 maka kita dapat menulis ulang sistem persamaan ke dalam bentuk matriks:

Selesaikan sistem persamaan linier di atas dengan metode eliminasi Gauss untukmemperoleh s0 = M.

Untuk mengilustrasikan skema di atas, ambil contoh sebagai berikut. Misalkan ada w = 8 partisipan akan membagi secret M = 190503180520 dan mereka sepakat bahwa  diperlukan t = 3 partisipan untuk melakukan rekonstruksi M.  Misalkan dipilih bilangan prima p = 190503180520. Selanjutnya pilih 3 – 1 = 2 buah bilangan acak,  sebut s1 = 482943028839 dan s2 = 1206749628665, untuk membentuk polinom  s(x) =  M + s1x + s2x2 (mod p), yaitu

                s(x) = 190503180520 + 482943028839x + 1206749628665x2 (mod 1234567890133 )

Setiap partisipan memperoleh (x, s(x)). Misakan x1 = 1, x2 = 2, …, x8 = 8, maka, setiap orang memperoleh share:

(1, 645627947891)
(2, 1045116192326)
(3, 154400023692)
(4, 442615222255)
(5, 675193897882)
(6, 852136050573)
(7, 973441680328)
(8, 1039110787147)

Untuk merekonstruksi kembali secret M dibutuhkan paling sedikit 3 partisipan. Misalkan partisipan 2, 3, dan 7 ingin merekonstruksi M. Mereka perlu memecahkan sistem persamaan linier:

Dengan metode eliminasi Gauss sistem persamaan linier tersebut dapat dipecahkan dan solusinya adalah  (M, s1, s2) = (190503180520, 482943028839, 1206749628665). Dengan kata lain secret M = 190503180520 dapat diperoleh kembali.

Apa yang terjadi jika 2 orang partisipan mencoba merekonstruksi M? Nilai M tidak dapat ditemukan karena  mustahil dua buah buah titik dapat membentuk polinom kuadratik  s(x) =  M + s1x + s2x2 (mod p). Misalkan mereka mencoba menggunakan titik ketiga yaitu (0, c) dengan c adalah sembarang secret, maka polinom unik yang melalui ketiga titik tersebut tetap tidak berhasil menemukan nilai M.

Apa yang terjadi jika > 3 orang partisipan mencoba merekonsruksi M? Sistem persamaan linier yang terbetuk memiliki lebih dari 3 persamaan dengan tiga peubah yang tidak diketahui, pada kondisi seperti ini sistem persamaan linier tetap dapat dipecahkan dan polinom interpolasi tetap bisa ditemukan! Dengan kata lain, minimal dibutuhkan 3 partisipan untuk bisa merekonstruksi M dengan skema (3, 8) tersebut.

Referensi

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

1 Komentar

Filed under Secret sharing

One response to “Skema Pembagian Data Rahasia dari Shamir (Bagian 1)

  1. rosma

    mas atau mba yang pinter,,
    slam kenal ya
    saya mau nanya cara menginterpolasi data triwulanan jadi data sebulanan gmn,,saya sudah pusing,,huhuhuhu

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