Shamir’s Secret Sharing


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.

Inhaltsverzeichnis

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 ai zufällig gewählt werden. Nun erzeugt der Dealer n Wertepaare (xi,si = f(xi)), wobei x_i \neq 0 und verteilt diese Wertepaare an die beteiligten Instanzen. Die xi sind dabei öffentlich und die si („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 xi und xj in die Formel einfließen, die auch wirklich an der Interpolation beteiligt sind. Sind i = {1,6,9} beteiligt, darf x4 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 wi läuft analog.

Literatur


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Shamir's Secret Sharing — is an algorithm in cryptography. It is a form of secret sharing, where a secret is divided into parts, giving each participant its own unique part, where some of the parts or all of them are needed in order to reconstruct the secret.Counting on… …   Wikipedia

  • 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 …   Deutsch Wikipedia

  • Secret sharing — refers to any method for distributing a secret amongst a group of participants, each of which is allocated a share of the secret. The secret can only be reconstructed when the shares are combined together; individual shares are of no use on their …   Wikipedia

  • Secret Sharing — Unter Geheimnisteilung (geteiltes Geheimnis) oder Secret Sharing versteht man eine Technik, ein Geheimnis (meist eine Zahl) unter einer gewissen Anzahl von so genannten Spielern aufzuteilen. Keine der Personen kann ohne die anderen das Geheimnis… …   Deutsch Wikipedia

  • Shamirs 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… …   Deutsch Wikipedia

  • Verifiable secret sharing — In cryptography, a secret sharing scheme is verifiable if auxiliary information is included that allows players to verify their shares as consistent. More formally, verifiable secret sharing ensures that even if the dealer is malicious there is a …   Wikipedia

  • Homomorphic secret sharing — In cryptography, homomorphic secret sharing is a form of secret sharing algorithm involving homomorphism.In abstract algebra, a homomorphism is a structure preserving map between two algebraic structures (such as groups, rings, or vector spaces) …   Wikipedia

  • Shamir — ist der Familienname folgender Personen: Adi Shamir (* 1952), israelischer Kryptologieexperte Efraim Shamir, israelischer Gitarrist und Sänger und Teilnehmer am Eurovision Song Contest 1974, siehe Kaveret#Mitglieder Moshe Shamir (1921–2004),… …   Deutsch Wikipedia

  • Shamir, Yitzhak — orig. Yitzhak Jazernicki born Oct. 15, 1915, Ruzinoy, Pol., Russian Empire Polish born Israeli statesman. He immigrated in 1935 to Palestine, where he helped found the Israel Freedom Fighters, later known as the Stern Gang. Twice arrested by… …   Universalium

  • Partage de clé secrète de Shamir — Le partage de clé secrète de Shamir (Shamir s Secret Sharing) est un algorithme de cryptographie. C est une forme de partage de secret, où un secret est divisé en parties, donnant à chaque participant sa propre clé partagée, où certaines des… …   Wikipédia en Français


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.