Pembagian Rahasia Shamir: Matematika Polinomial

Pembagian Rahasia Shamir (1979) mengodekan rahasia sebagai titik potong-y (f(0)) dari polinom acak berderajat-(k-1) di atas medan hingga. Setiap k titik menentukan polinom secara unik (interpolasi Lagrange); kurang dari k titik tidak mengungkapkan apa pun.

Untuk membagi rahasia S dengan ambang batas k di antara n pihak: pilih bilangan prima p > S dan n. Pilih koefisien acak a_1, ..., a_{k-1}. Definisikan f(x) = S + a_1*x + a_2*x^2 + ... + a_{k-1}*x^{k-1} (mod p). Pihak i menerima bagian (i, f(i)).

Rahasia S=7, p=17, k=2 (polinom linear). Pilih a_1=3. f(x)=7+3x mod 17. Bagian: (1,10), (2,13), (3,16). Setiap dua titik menentukan garis tersebut. f(0)=7. Satu titik saja: terdapat tak terhingga banyak garis yang mungkin, sehingga tidak ada informasi tentang S.

Diberikan k titik (x_1,y_1),...,(x_k,y_k), rekonstruksi f(0) menggunakan Lagrange: S = sum_i y_i * prod_{j≠i} (0-x_j)/(x_i-x_j) mod p. Semua aritmetika bersifat modular. Tidak ada bilangan titik mengambang — rekonstruksi dilakukan secara eksak di atas medan hingga.

from functools import reduce def lagrange(shares, p): xs = [s[0] for s in shares] ys = [s[1] for s in shares] result = 0 for i, (xi, yi) in enumerate(shares): num = reduce(lambda a,b: a*b%p, [(-xj)%p for j,xj in enumerate(xs) if j!=i], 1) den = reduce(lambda a,b: a*b%p, [(xi-xj)%p for j,xj in enumerate(xs) if j!=i], 1) result = (result + yi * num * pow(den, p-2, p)) % p return result

Untuk k-1 bagian, terdapat tepat satu polinom berderajat k-1 yang melalui k-1 titik tersebut untuk setiap kemungkinan nilai rahasia S. Jadi, dengan mengetahui k-1 bagian, setiap nilai S dalam [0, p-1] sama-sama mungkin—tidak ada informasi yang terungkap.

p harus lebih besar daripada rahasia dan n. Pilihan umum: p = 2^127-1 (bilangan prima Mersenne) untuk rahasia 128 bit. Ini memastikan semua bagian dapat dimuat dalam 128 bit dan aritmetikanya efisien. Alternatifnya, gunakan p=2^521-1 untuk rahasia 512 bit.

SSS dasar tidak menjamin integritas bagian: pemegang bagian yang berniat jahat dapat mengirimkan bagian palsu sehingga menyebabkan rekonstruksi rahasia yang salah. Feldman VSS (Pembagian Rahasia yang Dapat Diverifikasi) memublikasikan komitmen g^{a_i} mod p, sehingga bagian dapat diverifikasi tanpa mengungkapkan polinom.

Bagian dapat diperbarui secara berkala: buat polinom baru dengan rahasia S yang sama, bagikan ulang bagian baru, dan bagian lama menjadi tidak valid. Penyerang yang menyusupi seorang pemegang bagian setelah pembaruan hanya memperoleh bagian lama yang tidak berguna. Teknik ini digunakan dalam sistem pengelolaan kunci berumur panjang.

ssss (baris perintah Linux), python-secret-sharing, hashicorp/vault menggunakan SSS untuk mekanisme penyegelannya, dan dompet perangkat keras Trezor menggunakan SSS untuk pencadangan benih dompet (SLIP-39). Semuanya beroperasi pada medan prima besar.

SSS memerlukan pihak tepercaya untuk membuat dan membagikan bagian (pihak tersebut mengetahui rahasia). Skenario tanpa pihak pembagi memerlukan DKG (Pembuatan Kunci Terdistribusi). Rekonstruksi mengungkapkan rahasia kepada siapa pun yang memegang k bagian—hal ini dihilangkan oleh tanda tangan ambang batas berbasis MPC.

SSS Shamir menyandikan rahasia sebagai titik potong polinom dengan sumbu-y. Interpolasi Lagrange memulihkan rahasia dari k bagian. Keamanan sempurna berdasarkan teori informasi untuk jumlah bagian kurang dari k. Berikutnya: pembagian rahasia visual dan aditif.