Shamir’s Secret Sharing

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Shamir’s Secret Sharing ist ein 1979 von Adi Shamir entwickeltes Secret-Sharing-Verfahren. Mit Hilfe eines solchen Verfahrens kann man ein Geheimnis so auf mehrere „Instanzen“ (Mitwisser) aufteilen, dass zur Rekonstruktion des Geheimnisses nur eine gewisse Teilmenge dieser Instanzen benötigt wird (im Unterschied zum einfachen Secret-Sharing, bei dem sämtliche Instanzen benötigt werden).

Idee des Verfahrens[Bearbeiten | Quelltext bearbeiten]

Der „Dealer“ (benannt nach dem Kartengeber bei einem Kartenspiel) wählt ein Polynom vom Grad und berechnet 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[Bearbeiten | Quelltext bearbeiten]

Der Dealer wählt ein Polynom

wobei das Geheimnis ist und die zufällig gewählt werden. Nun erzeugt der Dealer Wertepaare , wobei und verteilt diese Wertepaare an die beteiligten Instanzen. Die sind dabei öffentlich und die („Shares“) müssen geheim gehalten werden.

Nach dem Fundamentalsatz der Algebra benötigt man Wertepaare um dieses Polynom eindeutig zu bestimmen. Daher können bis zu Teilgeheimnisse kompromittiert werden, ohne dass das Geheimnis in Gefahr ist, bestimmt zu werden. Erst wenn Shares bekannt sind, ist es möglich zu bestimmen. Dies bedeutet aber auch, dass zur Bestimmung des Geheimnisses 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 der gesamten Shares benötigt werden, um das Geheimnis zu rekonstruieren.

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

Rekonstruktion mittels der Lagrange-Interpolation[Bearbeiten | Quelltext bearbeiten]

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

Da wir aber nur am konstanten Term interessiert sind, reicht es, wenn wir betrachten

Jeder Teilnehmer berechnet nun

und hat dadurch einen additiven Teil des Geheimnisses .

Wichtig ist, dass bei dieser Berechnung lediglich diejenigen und in die Formel einfließen, die auch wirklich an der Interpolation beteiligt sind. Sind beteiligt, darf nicht benutzt werden.

Shamir’s Secret Sharing modulo p[Bearbeiten | Quelltext bearbeiten]

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 Elementen ( prim), so muss jede Berechnung modulo erfolgen.

Das Polynom wird nun folgend definiert.

wobei

weiter wird folgendermaßen berechnet

Die Berechnung für läuft analog.

Literatur[Bearbeiten | Quelltext bearbeiten]