Shamir’s Secret Sharing

Verfahren zur Aufteilung von Geheimnissen

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

Der „Dealer“ (benannt nach dem Kartengeber bei einem Kartenspiel) bestimmt eine Zahl   an Instanzen, die das Geheimnis später wieder rekonstruieren können sollen, und wählt daraufhin ein Polynom vom Grad   und berechnet   Stützstellen des Polynoms. Diese Stützstellen („Shares“) verteilt der Dealer an die restlichen beteiligten Instanzen. Diese Instanzen können daraufhin mit einem Interpolationsverfahren das Polynom rekonstruieren, dessen konstanter Term das Geheimnis ist.

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.

 
Polynome zweiten Grades durch zwei Punkte können die y-Achse an jedem Punkt schneiden.

Nach dem Fundamentalsatz der Algebra benötigt man   Wertepaare  , um dieses Polynom eindeutig zu bestimmen. Daher können bis zu   Shares kompromittiert werden, ohne dass das Geheimnis   in Gefahr ist, bestimmt zu werden. Erst wenn   Shares bekannt sind, ist es möglich,   zu bestimmen. Das bedeutet aber auch, dass zur Bestimmung des Geheimnisses   Instanzen ihre Shares kombinieren müssen, um das Geheimnis zu erhalten.

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

Rekonstruktion mittels der Lagrange-Interpolation

Bearbeiten

Zur effizienten Rekonstruktion des Polynoms kann die Lagrange-Interpolation benutzt werden.

 

Da das Geheimnis aber nur der konstante Term   ist, reicht es,   zu berechnen

 

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. Zum Beispiel: Sind   beteiligt, darf   nicht benutzt werden.

Shamir’s Secret Sharing modulo p

Bearbeiten

Bei der praktischen Nutzung von Shamir’s Secret Sharing mit reellen Zahlen können Angreifer auch aus weniger als   Shares Informationen erhalten. Daher werden in der Praxis endliche Körper als Zahlenraum verwendet. 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 (wobei   prim), so muss jede Berechnung modulo   erfolgen.[1]

Das Polynom wird nun folgend definiert.

 

wobei

 

weiter wird   folgendermaßen berechnet

 

Hierbei ist  die Inverse im endlichen Körper, den  bildet. Sie kann mit dem kleinen Satz von Fermat bzw. dem Satz von Euler berechnet werden, da p eine Primzahl ist:   und ist eine natürliche Zahl. Eine effiziente Berechnung dieses Ausdrucks bietet beispielsweise die „Right-to-left binary method“.

Literatur

Bearbeiten
Bearbeiten

Einzelnachweise

Bearbeiten
  1. Manon Bischoff: Die fabelhafte Welt der Mathematik: Kryptografie löst das Vertrauensdilemma. In: Spektrum der Wissenschaft. Abgerufen am 2. Dezember 2023.