Shamir Secret Sharing: Polynommathematik

Shamir's Secret Sharing (1979) codiert das Geheimnis als y-Achsenabschnitt (f(0)) eines zufälligen Polynoms vom Grad (k-1) über einem endlichen Körper. Beliebige k Punkte bestimmen das Polynom eindeutig (Lagrange-Interpolation); weniger als k Punkte verraten nichts.

Um das Geheimnis S mit dem Schwellenwert k auf n Parteien aufzuteilen: Wählen Sie eine Primzahl p > S und n. Wählen Sie zufällige Koeffizienten a_1, ..., a_{k-1}. Definieren Sie f(x) = S + a_1*x + a_2*x^2 + ... + a_{k-1}*x^{k-1} (mod p). Partei i erhält den Anteil (i, f(i)).

Geheimnis S=7, p=17, k=2 (lineares Polynom). Wählen Sie a_1=3. f(x)=7+3x mod 17. Anteile: (1,10), (2,13), (3,16). Zwei beliebige Punkte bestimmen die Gerade. f(0)=7. Ein einzelner Punkt: unendlich viele mögliche Geraden, keinerlei Information über S.

Gegeben k Punkte (x_1,y_1),...,(x_k,y_k), rekonstruieren Sie f(0) mit Lagrange: S = sum_i y_i * prod_{j≠i} (0-x_j)/(x_i-x_j) mod p. Alle Berechnungen erfolgen modular. Keine Gleitkommaarithmetik — exakte Rekonstruktion über dem endlichen Körper.

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

Für k-1 Shares gibt es für jeden möglichen Geheimniswert S genau ein Polynom vom Grad k-1, das durch diese k-1 Punkte verläuft. Wenn Sie k-1 Shares kennen, ist daher jeder Wert von S in [0, p-1] gleich wahrscheinlich — es werden keinerlei Informationen preisgegeben.

p muss größer als das Geheimnis und n sein. Eine gängige Wahl ist p = 2^127-1 (Mersenne-Primzahl) für 128-Bit-Geheimnisse. Dadurch passen alle Shares in 128 Bit und die Arithmetik ist effizient. Alternativ können Sie p=2^521-1 für 512-Bit-Geheimnisse verwenden.

Das einfache SSS bietet keine Integritätsschutz für Shares: Ein böswilliger Teilnehmer kann einen falschen Share übermitteln und dadurch eine falsche Rekonstruktion des Geheimnisses verursachen. Feldman VSS (Verifiable Secret Sharing) veröffentlicht Commitments g^{a_i} mod p, sodass Shares überprüft werden können, ohne das Polynom offenzulegen.

Shares können regelmäßig aufgefrischt werden: Erzeugen Sie ein neues Polynom mit demselben Geheimnis S und verteilen Sie neue Shares. Die alten Shares werden dadurch ungültig. Ein Angreifer, der nach der Auffrischung den Share eines Teilnehmers kompromittiert, erhält nur einen nutzlosen alten Share. Dieses Verfahren wird in langlebigen Schlüsselverwaltungssystemen eingesetzt.

ssss (Linux-Kommandozeile), python-secret-sharing, hashicorp/vault verwendet SSS für seinen Seal-Mechanismus, und die Trezor-Hardware-Wallet verwendet SSS für die Sicherung des Wallet-Seeds (SLIP-39). Alle arbeiten über großen Primkörpern.

SSS erfordert einen vertrauenswürdigen Dealer, der Shares erzeugt und verteilt (der Dealer kennt das Geheimnis). Ein Szenario ohne Dealer erfordert DKG (Distributed Key Generation). Bei der Rekonstruktion wird das Geheimnis allen offengelegt, die k Shares besitzen — durch MPC/Schwellenwertsignaturen lässt sich dieses Problem vermeiden.

Beim (3,5)-Secret-Sharing nach Shamir: Wie viele Shares werden mindestens benötigt, um das Geheimnis zu rekonstruieren?

Shamirs SSS kodiert Geheimnisse als y-Achsenabschnitte von Polynomen. Die Lagrange-Interpolation rekonstruiert das Geheimnis aus k Shares. Für weniger als k Shares besteht perfekte informationstheoretische Sicherheit. Als Nächstes folgen visuelles und additives Secret Sharing.