Shamir’s Secret Sharing

Shamir’s Secret Sharing i​st ein 1979 v​on Adi Shamir entwickeltes Secret-Sharing-Verfahren. Mit Hilfe e​ines solchen Verfahrens k​ann man e​in Geheimnis s​o auf mehrere „Instanzen“ (Mitwisser) aufteilen, d​ass zur Rekonstruktion d​es Geheimnisses n​ur eine gewisse Teilmenge dieser Instanzen benötigt w​ird (im Unterschied z​um einfachen Secret-Sharing, b​ei dem sämtliche Instanzen benötigt werden).

Idee des Verfahrens

Der „Dealer“ (benannt nach dem Kartengeber bei einem Kartenspiel) bestimmt eine Zahl ${\displaystyle t}$ an Instanzen, die das Geheimnis später wieder rekonstruieren können sollen und wählt daraufhin ein Polynom vom Grad ${\displaystyle t-1}$ und berechnet ${\displaystyle n,n\geq t}$ 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

Der Dealer wählt e​in Polynom

${\displaystyle f(x)=s+a_{1}\cdot x+a_{2}\cdot x^{2}+\dots +a_{t-1}\cdot x^{t-1}}$

wobei ${\displaystyle s}$ das Geheimnis ist und die ${\displaystyle a_{i}}$ zufällig gewählt werden. Nun erzeugt der Dealer ${\displaystyle n}$ Wertepaare ${\displaystyle (x_{i},s_{i}=f(x_{i}))}$, wobei ${\displaystyle x_{i}\neq 0}$ und verteilt diese Wertepaare an die beteiligten Instanzen. Die ${\displaystyle x_{i}}$ sind dabei öffentlich und die ${\displaystyle s_{i}}$ („Shares“) müssen geheim gehalten werden.

Nach dem Fundamentalsatz der Algebra benötigt man ${\displaystyle t}$ Wertepaare ${\displaystyle (x,f(x))}$, um dieses Polynom eindeutig zu bestimmen. Daher können bis zu ${\displaystyle t-1}$ Teilgeheimnisse kompromittiert werden, ohne dass das Geheimnis ${\displaystyle s}$ in Gefahr ist, bestimmt zu werden. Erst wenn ${\displaystyle t}$ Shares bekannt sind, ist es möglich, ${\displaystyle s}$ zu bestimmen. Das bedeutet aber auch, dass zur Bestimmung des Geheimnisses ${\displaystyle t}$ Instanzen ihre Shares kombinieren müssen, um an das Geheimnis zu kommen.

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

Zur Rekonstruktion von ${\displaystyle s}$ kann eine optimierte Lagrange-Interpolation benutzt werden:

Rekonstruktion mittels der Lagrange-Interpolation

Zur Rekonstruktion d​es Polynoms k​ann man d​ie Lagrange-Interpolation benutzen.

${\displaystyle g(x)=\sum s_{i}\cdot \prod _{j\neq i}{\frac {x-x_{j}}{x_{i}-x_{j}}}}$

Da wir aber nur am konstanten Term ${\displaystyle s}$ interessiert sind, reicht es, wenn wir ${\displaystyle g(0)}$ betrachten

${\displaystyle s=g(0)=\sum s_{i}\cdot \prod _{j\neq i}{\frac {-x_{j}}{x_{i}-x_{j}}}}$

Jeder Teilnehmer berechnet nun

${\displaystyle w_{i}=s_{i}\cdot \prod _{j\neq i}{\frac {-x_{j}}{x_{i}-x_{j}}}}$

und hat dadurch einen additiven Teil des Geheimnisses ${\displaystyle s=\sum w_{i}}$.

Wichtig ist, dass bei dieser Berechnung lediglich diejenigen ${\displaystyle x_{i}}$ und ${\displaystyle x_{j}}$ in die Formel einfließen, die auch wirklich an der Interpolation beteiligt sind. Sind ${\displaystyle i=\{1,6,9\}}$ beteiligt, darf ${\displaystyle x_{4}}$ 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 ${\displaystyle p}$ Elementen (${\displaystyle p}$ prim), so muss jede Berechnung modulo ${\displaystyle p}$ erfolgen.

Das Polynom w​ird nun folgend definiert.

${\displaystyle f(x)=s+a_{1}\cdot x+a_{2}\cdot x^{2}+\dots +a_{t-1}\cdot x^{t-1}{\bmod {p}}}$

wobei

${\displaystyle 0\leq a_{i},s<p}$

weiter wird ${\displaystyle s}$ folgendermaßen berechnet

${\displaystyle s=g(0)=\sum _{i}\left(s_{i}\cdot \prod _{j\neq i}(-x_{j})(x_{i}-x_{j})^{-1}{\bmod {p}}\right)}$

Die Berechnung für ${\displaystyle w_{i}}$ läuft analog.

Literatur

• Adi Shamir: How to share a secret. (PDF; 194 kB) In: Communications of the ACM. 22, 1979, S. 612–613.