Quelltext der Seite 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 [[Secret-Sharing#Einfaches Secret-Sharing|einfachen Secret-Sharing]], bei dem sämtliche Instanzen benötigt werden).

== Idee des Verfahrens ==
Der „Dealer“ (benannt nach dem Kartengeber bei einem [[Kartenspiel]]) bestimmt eine Zahl <math>t</math> an Instanzen, die das Geheimnis später wieder rekonstruieren können sollen, und wählt daraufhin ein [[Polynom]] vom Grad <math>t-1</math> und berechnet <math>n, n \geq t</math> Stützstellen des Polynoms. Diese Stützstellen („Shares“) verteilt der Dealer an die restlichen beteiligten Instanzen. Diese Instanzen können daraufhin mit einem [[Interpolation (Mathematik)|Interpolationsverfahren]] das Polynom rekonstruieren, dessen konstanter Term das Geheimnis ist.

== Ablauf ==
Der Dealer wählt ein Polynom
:<math>f(x) = s + a_1\cdot x + a_2 \cdot x^2 + \dots + a_{t-1} \cdot x^{t-1}</math>

wobei <math>s</math> das Geheimnis ist und die <math>a_i</math> zufällig gewählt werden. Nun erzeugt der Dealer <math>n</math> Wertepaare <math>(x_i,s_i=f(x_i))</math>, wobei <math>x_i \neq 0</math> und verteilt diese Wertepaare an die beteiligten Instanzen. Die <math>x_i</math> sind dabei öffentlich und die <math>s_i</math> („Shares“) müssen geheim gehalten werden.
[[Datei:3 polynomials of degree 2 through 2 points.svg|mini|Polynome zweiten Grades durch zwei Punkte können die y-Achse an jedem Punkt schneiden.]]
Nach dem [[Fundamentalsatz der Algebra]] benötigt man <math>t</math> Wertepaare <math>(x,f(x))</math>, um dieses Polynom eindeutig zu bestimmen. Daher können bis zu <math>t-1</math> Shares kompromittiert werden, ohne dass das Geheimnis <math>s</math> in Gefahr ist, bestimmt zu werden. Erst wenn <math>t</math> Shares bekannt sind, ist es möglich, <math>s</math> zu bestimmen. Das bedeutet aber auch, dass zur Bestimmung des Geheimnisses <math>t</math> Instanzen ihre Shares kombinieren müssen, um das Geheimnis zu erhalten.

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

== Rekonstruktion mittels der Lagrange-Interpolation ==
Zur effizienten Rekonstruktion des Polynoms kann die [[Lagrange-Interpolation]] benutzt werden.
:<math>g(x)=\sum s_i \cdot \prod_{j \neq i} \frac{x-x_j}{x_i-x_j}</math>
Da das Geheimnis aber nur der konstante Term <math>s</math> ist, reicht es, <math>g(0)</math> zu berechnen
:<math>s=g(0)=\sum s_i \cdot \prod_{j \neq i} \frac{-x_j}{x_i-x_j}</math>

Jeder Teilnehmer berechnet nun
:<math>w_i=s_i \cdot \prod_{j \neq i} \frac{-x_j}{x_i-x_j}</math>
und hat dadurch einen additiven Teil des Geheimnisses <math>s=\sum w_i</math>.

Wichtig ist, dass bei dieser Berechnung lediglich diejenigen <math>x_i</math> und <math>x_j</math> in die Formel einfließen, die auch wirklich an der Interpolation beteiligt sind. Zum Beispiel: Sind <math>i=\{1,6,9\}</math> beteiligt, darf <math>x_4</math> nicht benutzt werden.

== Shamir’s Secret Sharing modulo p ==
Bei der praktischen Nutzung von Shamir’s Secret Sharing mit [[Reelle Zahl|reellen Zahlen]] können Angreifer auch aus weniger als ''<math>t</math>'' Shares Informationen erhalten. Daher werden in der Praxis [[Endlicher Körper|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 <math>p</math> Elementen (wobei <math>p</math> [[Primzahl|prim]]), so muss jede Berechnung [[Kongruenz (Zahlentheorie)|modulo]] <math>p</math> erfolgen.<ref>{{Internetquelle |autor=Manon Bischoff |url=https://www.spektrum.de/kolumne/wie-shamirs-secret-sharing-das-teilen-von-geheimnissen-revolutioniert/2197885 |titel=Die fabelhafte Welt der Mathematik: Kryptografie löst das Vertrauensdilemma |werk=[[Spektrum der Wissenschaft]] |sprache=de |abruf=2023-12-02}}</ref>

Das Polynom wird nun folgend definiert.

:<math>f(x) = s + a_1\cdot x + a_2 \cdot x^2 + \dots + a_{t-1} \cdot x^{t-1} \bmod p</math>
wobei
:<math>0 \leq a_i,s < p</math>

weiter wird <math>s</math> folgendermaßen berechnet
:<math>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 </math>
Hierbei ist <math>(x_i-x_j)^{-1}</math>die Inverse im endlichen Körper, den<math>\bmod p </math> bildet. Sie kann mit dem [[Kleiner fermatscher Satz|kleinen Satz von Fermat]] bzw. dem [[Satz von Euler]] berechnet werden, da p eine Primzahl ist: <math>(x_i-x_j)^{-1} = (x_i-x_j)^{p-2} \bmod p</math> und ist eine [[natürliche Zahl]]. Eine effiziente Berechnung dieses Ausdrucks bietet beispielsweise die „Right-to-left binary method“.

== Literatur ==
* Adi Shamir: ''[https://dl.acm.org/doi/pdf/10.1145/359168.359176 How to share a secret.]'' (PDF; 194&nbsp;kB) In: ''[[Communications of the ACM]].'' 22, 1979, S. 612–613.

== Weblinks ==
* [https://www.cryptopp.com/docs/ref/class_secret_sharing.html Shamir's Secret Sharing] in der [[Crypto++]]-Software-Bibliothek
* [http://point-at-infinity.org/ssss/ Shamir's Secret Sharing Scheme (ssss)] – eine [[GNU General Public License|GNU GPL]] Implementierung
* [https://github.com/posener/sharedsecret sharedsecret] – Implementierung in [[Go (Programmiersprache)|Go]]
* [https://simon-frey.com/s4/ s4] - Online Shamir's Secret Sharing Tool das im Browser betrieben werden kann

== Einzelnachweise ==
<references />

[[Kategorie:Kryptologisches Verfahren]]