Współdzielenie sekretu Shamira: matematyka wielomianów

Schemat Shamir's Secret Sharing (1979) koduje sekret jako punkt przecięcia z osią y (f(0)) losowego wielomianu stopnia (k-1) nad ciałem skończonym. Dowolne k punktów jednoznacznie wyznacza wielomian (interpolacja Lagrange’a); mniej niż k punktów nie ujawnia niczego.

Aby podzielić sekret S z progiem k między n stron: wybierz liczbę pierwszą p > S i n. Wylosuj współczynniki a_1, ..., a_{k-1}. Zdefiniuj f(x) = S + a_1*x + a_2*x^2 + ... + a_{k-1}*x^{k-1} (mod p). Strona i otrzymuje udział (i, f(i)).

Sekret S=7, p=17, k=2 (wielomian liniowy). Wybierz a_1=3. f(x)=7+3x mod 17. Udziały: (1,10), (2,13), (3,16). Dowolne dwa punkty wyznaczają prostą. f(0)=7. Jeden punkt z osobna: nieskończenie wiele możliwych prostych, zero informacji o S.

Mając k punktów (x_1,y_1),...,(x_k,y_k), odtwórz f(0) za pomocą interpolacji Lagrange’a: S = sum_i y_i * prod_{j≠i} (0-x_j)/(x_i-x_j) mod p. Wszystkie działania są modularne. Bez liczb zmiennoprzecinkowych — dokładne odtworzenie w ciele skończonym.

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

Dla k-1 udziałów istnieje dokładnie jeden wielomian stopnia k-1 przechodzący przez te k-1 punktów dla każdej możliwej wartości sekretu S. Zatem znając k-1 udziałów, każda wartość S z [0, p-1] jest jednakowo prawdopodobna — nie zostaje ujawniona żadna informacja.

p musi być większe od sekretu i n. Typowy wybór: p = 2^127-1 (liczba pierwsza Mersenne’a) dla sekretów 128-bitowych. Dzięki temu wszystkie udziały mieszczą się w 128 bitach, a działania arytmetyczne są wydajne. Alternatywnie można użyć p=2^521-1 dla sekretów 512-bitowych.

Podstawowy SSS nie zapewnia integralności udziałów: złośliwy posiadacz udziału może przesłać fałszywy udział, powodując błędną rekonstrukcję sekretu. Feldman VSS (Verifiable Secret Sharing) publikuje zobowiązania g^{a_i} mod p, dzięki czemu można zweryfikować udziały bez ujawniania wielomianu.

Udziały można okresowo odświeżać: wygenerować nowy wielomian z tym samym sekretem S i rozdzielić nowe udziały, dzięki czemu stare udziały tracą ważność. Atakujący, który po odświeżeniu przejmie kontrolę nad jednym z posiadaczy udziałów, uzyska bezużyteczny stary udział. Stosuje się to w systemach zarządzania kluczami o długim cyklu życia.

ssss (wiersz poleceń systemu Linux), python-secret-sharing, hashicorp/vault używa SSS do mechanizmu zapieczętowania, a portfel sprzętowy Trezor używa SSS do tworzenia kopii zapasowej ziarna portfela (SLIP-39). Wszystkie działają w ciałach o dużej charakterystyce pierwszej.

SSS wymaga zaufanego dealera do wygenerowania i rozdzielenia udziałów (dealer zna sekret). Scenariusz bez dealera wymaga DKG (Distributed Key Generation). Rekonstrukcja ujawnia sekret każdemu, kto posiada k udziałów — można tego uniknąć za pomocą MPC lub podpisów progowych.

SSS Shamira koduje sekrety jako wyrazy wolne wielomianów. Interpolacja Lagrange’a odzyskuje sekret z k udziałów. Zapewnia doskonałe bezpieczeństwo w sensie teorii informacji dla mniej niż k udziałów. Dalej: wizualne i addytywne współdzielenie sekretu.