Shamir'in Gizli Paylaşımı: Polinom Matematiği

Shamir'in Gizli Paylaşımı (1979), gizli bilgiyi sonlu bir cisim üzerindeki rastgele, (k-1) dereceli bir polinomun y eksenini kestiği nokta (f(0)) olarak kodlar. Herhangi k nokta polinomu tekil olarak belirler (Lagrange enterpolasyonu); k'dan az nokta hiçbir bilgi vermez.

Gizli S bilgisini n taraf arasında k eşikli paylaşmak için: S ve n'den büyük bir asal p seçin. Rastgele a_1, ..., a_{k-1} katsayılarını seçin. f(x) = S + a_1*x + a_2*x^2 + ... + a_{k-1}*x^{k-1} (mod p) tanımını yapın. i. taraf (i, f(i)) payını alır.

Gizli S=7, p=17, k=2 (doğrusal polinom). a_1=3 seçin. f(x)=7+3x mod 17. Paylar: (1,10), (2,13), (3,16). Herhangi iki nokta doğruyu belirler. f(0)=7. Tek bir nokta: sonsuz sayıda olası doğru, S hakkında sıfır bilgi.

k adet (x_1,y_1),...,(x_k,y_k) noktası verildiğinde, Lagrange kullanarak f(0) değerini yeniden oluşturun: S = sum_i y_i * prod_{j≠i} (0-x_j)/(x_i-x_j) mod p. Tüm aritmetik işlemler modülerdir. Kayan nokta yoktur; sonlu cisim üzerinde kesin yeniden oluşturma yapılır.

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

k-1 pay için, her olası gizli değer S için bu k-1 noktadan geçen, derecesi k-1 olan tam olarak bir polinom vardır. Bu nedenle k-1 payı bilmek, [0, p-1] aralığındaki her S değerinin eşit olasılıklı olması demektir; hiçbir bilgi açığa çıkmaz.

p, gizli değerden ve n'den büyük olmalıdır. Yaygın bir seçim, 128 bitlik gizli değerler için p = 2^127-1 (Mersenne asalı) kullanmaktır. Bu, tüm payların 128 bite sığmasını ve aritmetiğin verimli olmasını sağlar. Alternatif olarak 512 bitlik gizli değerler için p=2^521-1 kullanılabilir.

Temel SSS'de pay bütünlüğü yoktur: kötü niyetli bir pay sahibi yanlış bir pay sunarak gizli değerin yanlış yeniden oluşturulmasına neden olabilir. Feldman VSS (Doğrulanabilir Gizli Paylaşım), g^{a_i} mod p taahhütlerini yayımlar; böylece polinom açığa çıkarılmadan paylar doğrulanabilir.

Paylar düzenli aralıklarla yenilenebilir: aynı gizli değer S ile yeni bir polinom üretilir ve yeni paylar dağıtılır; eski paylar geçersiz olur. Yenilemeden sonra bir pay sahibini ele geçiren saldırgan, işe yaramaz eski bir pay elde eder. Bu yöntem uzun ömürlü anahtar yönetimi sistemlerinde kullanılır.

ssss (Linux komut satırı), python-secret-sharing ve hashicorp/vault, mühür mekanizmaları için SSS kullanır; Trezor donanım cüzdanı ise cüzdan tohumu yedeği için SSS kullanır (SLIP-39). Bunların tümü büyük asal cisimler üzerinde çalışır.

SSS, payları üretip dağıtmak için güvenilir bir dağıtıcı gerektirir (dağıtıcı gizli değeri bilir). Dağıtıcının olmadığı senaryolarda DKG (Dağıtık Anahtar Üretimi) gerekir. Yeniden oluşturma, k payı elinde bulunduran kişiye gizli değeri açığa çıkarır; bu sorun MPC/eşik imzalarıyla ortadan kaldırılır.

Shamir'in SSS'si gizli değerleri polinomların y-kesişimleri olarak kodlar. Lagrange enterpolasyonu gizli değeri k paydan geri kazandırır. k'dan az pay için kusursuz bilgi-kuramsal güvenlik sağlar. Sıradaki konu: görsel ve toplamsal gizli paylaşım.