Shamir’s Secret Sharing

Shamir's Secret Sharing ist ein 1979 von Adi Shamir entwickeltes Secret-Sharing-Verfahren. Mit Hilfe eines solchen Verfahrens ist es möglich, ein Geheimnis auf mehrere „Instanzen“ (Mitwisser) aufzuteilen, wobei eine gewisse Untermenge dieser Instanzen erforderlich ist, um das Geheimnis zu rekonstruieren.

Idee des Verfahrens

Der „Dealer“ (benannt nach dem Kartengeber bei einem Kartenspiel) wählt ein Polynom vom Grad t − 1 und berechnet $n, n \geq t$ Stützstellen des Polynoms. Diese Stützstellen („Shares“) verteilt der Dealer an die restlichen beteiligten Instanzen. Diese können daraufhin mit einem Interpolationsverfahren das Polynom rekonstruieren, dessen konstanter Term das Geheimnis ist.

Ablauf

Der Dealer wählt ein Polynom

$f(x) = s + a_1\cdot x + a_2 \cdot x^2 + \dots + a_{t-1} \cdot x^{t-1}$

wobei s das Geheimnis ist und die a_i zufällig gewählt werden. Nun erzeugt der Dealer n Wertepaare (x_i,s_i = f(x_i)), wobei $x_i \neq 0$ und verteilt diese Wertepaare an die beteiligten Instanzen. Die x_i sind dabei öffentlich und die s_i („Shares“) müssen geheim gehalten werden.

Nach dem Fundamentalsatz der Algebra benötigt man t Wertepaare (x,f(x)) um dieses Polynom eindeutig zu bestimmen. Daher können bis zu t − 1 Teilgeheimnisse kompromittiert werden, ohne dass das Geheimnis s in Gefahr ist, bestimmt zu werden. Erst wenn t Shares bekannt sind, ist es möglich s zu bestimmen. Dies bedeutet aber auch, dass zur Bestimmung des Geheimnisses t Instanzen ihre Shares kombinieren müssen, um an das Geheimnis zu kommen.

Dieses System wird auch als (t,n)-Schwellwert-Schema (sprich: t aus n Schwellwert-Schema) bezeichnet, da nur t der gesamten n Shares benötigt werden, um das Geheimnis zu rekonstruieren.

Zur Rekonstruktion von s kann eine optimierte Lagrange-Interpolation benutzt werden:

Rekonstruktion mittels der Lagrange-Interpolation

Zur Rekonstruktion des Polynoms kann man die Lagrange-Interpolation benutzen.

$g(x)=\sum s_i \cdot \prod_{i \neq j} \frac{x-x_j}{x_i-x_j}$

Da wir aber nur am konstanten Term s interessiert sind, reicht es, wenn wir g(0) betrachten

$s=g(0)=\sum s_i \cdot \prod_{i \neq j} \frac{-x_j}{x_i-x_j}$

Jeder Teilnehmer berechnet nun

$w_i=s_i \cdot \prod_{i \neq j} \frac{-x_j}{x_i-x_j}$

und hat dadurch einen additiven Teil des Geheimnisses $s=\sum w_i$.

Wichtig ist, dass bei dieser Berechnung lediglich diejenigen x_i und x_j in die Formel einfließen, die auch wirklich an der Interpolation beteiligt sind. Sind i = {1,6,9} beteiligt, darf x₄ nicht benutzt werden.

Shamir's Secret Sharing modulo p

In der Kryptographie ist es nicht praktikabel, mit reellen Zahlen zu rechnen. Man beschränkt sich deshalb auf endliche Körper. Das Verfahren muss in diesem Fall leicht angepasst werden, indem auf die modulare Arithmetik zurückgegriffen wird. Rechnet man im endlichen Körper mit p Elementen (p prim), so muss jede Berechnung modulo p erfolgen.

Das Polynom wird nun folgend definiert.

$f(x) = s + a_1\cdot x + a_2 \cdot x^2 + \dots + a_{t-1} \cdot x^{t-1} \mod p$

wobei

$0 \leq a_i,s < p$

weiters wird s folgendermaßen berechnet

$s=g(0)=\sum_i s_i \cdot \prod_{i \neq j} (x_j)(x_j-x_i)^{-1} \mod p$

Die Berechnung für w_i läuft analog.

Literatur

• Adi Shamir: How to share a secret. In: Communications of the ACM 22, 1979, S. 612–613