www.wikidata.de-de.nina.az

Shamir s Secret Sharing ist ein 1979 von Adi Shamir entwickeltes Secret Sharing Verfahren Mit Hilfe eines solchen Verfah

Shamir’s Secret Sharing

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.

Ablauf 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 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 Geheimnisses aber nur konstanten 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.

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

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
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 benotigt wird im Unterschied zum einfachen Secret Sharing bei dem samtliche Instanzen benotigt werden Inhaltsverzeichnis 1 Idee des Verfahrens 2 Ablauf 3 Rekonstruktion mittels der Lagrange Interpolation 4 Shamir s Secret Sharing modulo p 5 Literatur 6 WeblinksIdee des Verfahrens BearbeitenDer Dealer benannt nach dem Kartengeber bei einem Kartenspiel bestimmt eine Zahl t displaystyle t nbsp an Instanzen die das Geheimnis spater wieder rekonstruieren konnen sollen und wahlt daraufhin ein Polynom vom Grad t 1 displaystyle t 1 nbsp und berechnet n n t displaystyle n n geq t nbsp Stutzstellen des Polynoms Diese Stutzstellen Shares verteilt der Dealer an die restlichen beteiligten Instanzen Diese Instanzen konnen daraufhin mit einem Interpolationsverfahren das Polynom rekonstruieren dessen konstanter Term das Geheimnis ist Ablauf BearbeitenDer Dealer wahlt ein Polynom f x s a 1 x a 2 x 2 a t 1 x t 1 displaystyle f x s a 1 cdot x a 2 cdot x 2 dots a t 1 cdot x t 1 nbsp wobei s displaystyle s nbsp das Geheimnis ist und die a i displaystyle a i nbsp zufallig gewahlt werden Nun erzeugt der Dealer n displaystyle n nbsp Wertepaare x i s i f x i displaystyle x i s i f x i nbsp wobei x i 0 displaystyle x i neq 0 nbsp und verteilt diese Wertepaare an die beteiligten Instanzen Die x i displaystyle x i nbsp sind dabei offentlich und die s i displaystyle s i nbsp Shares mussen geheim gehalten werden Nach dem Fundamentalsatz der Algebra benotigt man t displaystyle t nbsp Wertepaare x f x displaystyle x f x nbsp um dieses Polynom eindeutig zu bestimmen Daher konnen bis zu t 1 displaystyle t 1 nbsp Shares kompromittiert werden ohne dass das Geheimnis s displaystyle s nbsp in Gefahr ist bestimmt zu werden Erst wenn t displaystyle t nbsp Shares bekannt sind ist es moglich s displaystyle s nbsp zu bestimmen Das bedeutet aber auch dass zur Bestimmung des Geheimnisses t displaystyle t nbsp Instanzen ihre Shares kombinieren mussen um das Geheimnis zu erhalten Dieses System wird auch als t n Schwellwert Kryptosystem bezeichnet da nur t displaystyle t nbsp der gesamten n displaystyle n nbsp Shares benotigt werden um das Geheimnis zu rekonstruieren Rekonstruktion mittels der Lagrange Interpolation BearbeitenZur effizienten Rekonstruktion des Polynoms kann die Lagrange Interpolation benutzt werden g x s i j i x x j x i x j displaystyle g x sum s i cdot prod j neq i frac x x j x i x j nbsp Da das Geheimnisses aber nur konstanten Term s displaystyle s nbsp ist reicht es g 0 displaystyle g 0 nbsp zu berechnen s g 0 s i j i x j x i x j displaystyle s g 0 sum s i cdot prod j neq i frac x j x i x j nbsp Jeder Teilnehmer berechnet nun w i s i j i x j x i x j displaystyle w i s i cdot prod j neq i frac x j x i x j nbsp und hat dadurch einen additiven Teil des Geheimnisses s w i displaystyle s sum w i nbsp Wichtig ist dass bei dieser Berechnung lediglich diejenigen x i displaystyle x i nbsp und x j displaystyle x j nbsp in die Formel einfliessen die auch wirklich an der Interpolation beteiligt sind Zum Beispiel Sind i 1 6 9 displaystyle i 1 6 9 nbsp beteiligt darf x 4 displaystyle x 4 nbsp nicht benutzt werden Shamir s Secret Sharing modulo p BearbeitenBei der praktischen Nutzung von Shamir s Secret Sharing mit reellen Zahlen konnen Angreifer auch aus weniger als t displaystyle t nbsp Shares Informationen erhalten Daher werden in der Praxis endliche Korper als Zahlenraum verwendet Das Verfahren muss in diesem Fall leicht angepasst werden indem auf die modulare Arithmetik zuruckgegriffen wird Rechnet man im endlichen Korper mit p displaystyle p nbsp Elementen wobei p displaystyle p nbsp prim so muss jede Berechnung modulo p displaystyle p nbsp erfolgen Das Polynom wird nun folgend definiert f x s a 1 x a 2 x 2 a t 1 x t 1 mod p displaystyle f x s a 1 cdot x a 2 cdot x 2 dots a t 1 cdot x t 1 bmod p nbsp wobei 0 a i s lt p displaystyle 0 leq a i s lt p nbsp weiter wird s displaystyle s nbsp folgendermassen berechnet s g 0 i s i j i x j x i x j 1 mod p mod p displaystyle s g 0 sum i left s i cdot prod j neq i x j x i x j 1 bmod p right bmod p nbsp Hierbei ist x i x j 1 displaystyle x i x j 1 nbsp die Inverse im endlichen Korper denmod p displaystyle bmod p nbsp bildet Sie kann mit dem kleinen Satz von Fermat bzw dem Satz von Euler berechnet werden da p eine Primzahl ist x i x j 1 x i x j p 2 mod p displaystyle x i x j 1 x i x j p 2 bmod p nbsp und ist eine naturliche Zahl Eine effiziente Berechnung dieses Ausdrucks bietet beispielsweise die Right to left binary method Literatur BearbeitenAdi Shamir How to share a secret PDF 194 kB In Communications of the ACM 22 1979 S 612 613 Weblinks BearbeitenShamir s Secret Sharing in der Crypto Software Bibliothek Shamir s Secret Sharing Scheme ssss eine GNU GPL Implementierung sharedsecret Implementierung in Go s4 Online Shamir s Secret Sharing Tool das im Browser betrieben werden kann Abgerufen von https de wikipedia org w index php title Shamir s Secret Sharing amp oldid 234079797