Secret Sharing: Die Technologie hinter fragmentiX (Teil 1)

---

Einführung: Was Secret Sharing in der Kryptografie wirklich bedeutet

Im Bereich der Kryptografie gibt es nur wenige Konzepte, deren Bezeichnung so irreführend ist wie Secret Sharing. Auf den ersten Blick könnte man meinen, es handele sich um eine Variante des bekannteren Shared SecretTrotz der ähnlichen Bezeichnung dienen diese beiden Konzepte jedoch ganz unterschiedlichen Zwecken.

Ein Shared Secret ist in der Regel ein einzelner Wert, der mehreren Parteien bekannt ist und zur Herstellung einer sicheren Kommunikation verwendet wird. Im Gegensatz dazu ist Secret Sharing eine Technik, bei der ein Geheimnis in mehrere Teile oder Anteile aufgeteilt wird, sodass nur eine bestimmte Teilmenge dieser Anteile das ursprüngliche Geheimnis rekonstruieren kann. Entscheidend ist, dass kein einzelner Anteil für sich genommen Informationen über das Geheimnis preisgibt.

Im Gegensatz zu Verschlüsselungsverfahren, die zum Sperren und Entsperren von Daten auf Schlüssel angewiesen sind, handelt es sich bei der geheimen Teilung um eine schlüssellose kryptografische Methode, bei der keine einzige vertrauenswürdige Stelle zur Kontrolle eines Schlüssels erforderlich ist. Dies macht sie besonders leistungsfähig in Szenarien, in denen eine zentralisierte Kontrolle ein Risiko darstellt und die Widerstandsfähigkeit gegen Kompromittierung von größter Bedeutung ist.

Das Konzept wurde Ende der 1970er Jahre von Adi Shamir [1] und George Blakley formalisiert. Seitdem hat die Geheimnisteilung weit über die sichere Speicherung hinaus Anwendung gefunden: vom Schutz von nuklearen Startcodes und Kryptowährungs-Wallets bis hin zur Ermöglichung sicherer Mehrparteienberechnungen und schwellenwertbasierter Authentifizierungssysteme.

Bei fragmentiX nutzen wir die Leistungsfähigkeit von Secret Sharing, um sichere, verteilte Cloud-Speichersysteme aufzubauen – damit Ihre Daten auch dann geschützt bleiben, wenn Teile des Systems ausfallen oder kompromittiert werden. In den folgenden Abschnitten werden wir untersuchen, wie Secret Sharing funktioniert, beginnend mit dem klassischen Shamir-Schema im ersten Teil dieses Blogbeitrags, und uns dann im zweiten Teil mit Erweiterungen befassen, die es noch robuster und vielseitiger machen.

Shamirs Secret Sharing: Ein intuitives Beispiel

Stellen Sie sich ein medizinisches Forschungsinstitut vor, das an einer revolutionären medizinischen Behandlung arbeitet. Die Formel ist ein streng gehütetes Geheimnis – nicht nur aus Gründen des geistigen Eigentums, sondern auch, um vorzeitige Lecks oder Missbrauch zu verhindern. Um sie zu schützen, beschließt das Institut, die Formel auf mehrere vertrauenswürdige Forscher in verschiedenen Ländern aufzuteilen.

Aber sie teilen das Dokument nicht einfach in Teile auf. Das wäre riskant, da jeder Teil immer noch Hinweise enthalten könnte. Stattdessen verwenden sie Shamirs Geheimnisteilung, eine Methode, die auf Schwellenwertkryptografie basiert, bei der ein Geheimnis in $n$ Teile aufgeteilt wird und ein vordefinierter Schwellenwert $k$ dieser Teile erforderlich ist, um es wiederherzustellen.

Wichtig ist, dass jede Teilmenge mit weniger als k Anteilen absolut nichts über das ursprüngliche Geheimnis verrät – ein Schutzniveau, das so hoch ist, dass selbst ein Angreifer mit unbegrenzter Rechenleistung aus unzureichenden Anteilen keine Informationen extrahieren kann. Dieses außergewöhnliche Schutzniveau fällt unter die Kategorie der informationstheoretischen Sicherheit (ITS). Es handelt sich um dieselbe Art von Garantie, die auch das One-Time-Pad bietet, das Lehrbuchbeispiel für eine unknackbare Verschlüsselung, die bei korrekter Anwendung ITS erreicht. Während das One-Time-Pad aufgrund seiner strengen Anforderungen selten praktikabel ist, bietet Shamirs Secret Sharing auch unter flexibleren Bedingungen ITS und eignet sich daher für ein breiteres Spektrum realer Anwendungen. Wichtig ist, dass dieses Sicherheitsniveau nicht durch Fortschritte in der Kryptoanalyse oder der Computertechnik, einschließlich Quantencomputern, gefährdet ist.

Eine weitere leistungsstarke Funktion: Es spielt keine Rolle, welche Anteile verfügbar sind. Wenn das Institut 10 Anteile erstellt und den Schwellenwert auf 7 festlegt, können sich 7 dieser 10 Forscher zusammenschließen und die geheime Formel rekonstruieren. Selbst wenn 3 Anteile verloren gehen, bleibt das Geheimnis wiederherstellbar. Dadurch ist Shamirs Schema nicht nur sicher, sondern auch äußerst fehlertolerant.

Diese Flexibilität und Fehlertoleranz machen Shamirs Schema ideal für sichere verteilte Systeme, in denen Datenintegrität und Verfügbarkeit mit strenger Vertraulichkeit einhergehen müssen.

Technische Erklärung: Die Mathematik hinter Shamirs Secret Sharing

Das Herzstück von Shamirs Secret Sharing ist eine wunderbar einfache Idee: Ein Polynom vom Grad $k-1$ wird eindeutig durch $k$ verschiedene Punkte bestimmt. Beispielsweise kann eine Gerade (ein Polynom vom Grad 1) aus zwei beliebigen verschiedenen Punkten rekonstruiert werden, während eine Parabel (Grad 2) drei Punkte erfordert. Dieses Prinzip bildet das Rückgrat des Schemas.

Um ein Geheimnis zu verschlüsseln, betten wir es als konstanten Term eines ansonsten zufällig generierten Polynoms vom Grad $\mathrm{k-1}$ über einem Endlichen Körper. Um eine visuelle Analogie zu verwenden: Stellen Sie sich das Geheimnis als den Punkt vor, an dem der Graph des Polynoms die y-Achse schneidet – also den Wert des Polynoms bei $\mathrm{x=0}$. Anschließend berechnen wir dieses Polynom an $n$ verschiedenen Punkten ungleich Null, um $n$ Anteile zu erzeugen.

Infolgedessen kann jeder $k$ dieser Anteile verwendet werden, um das ursprüngliche Polynom und damit das Geheimnis mithilfe von Interpolationstechniken zu rekonstruieren. Aber weniger als $k$ Anteile geben absolut nichts preis. Dies ist nicht nur eine rechnerische Schwierigkeit, sondern eine mathematische Garantie.

In Abbildung 1 ist das Geheimnis die y-Koordinate des Punktes S, an dem die Parabel die y-Achse schneidet. Vier Punkte auf einer Parabel stellen die vier Aktien dar. (A, B, C, D). Drei beliebige dieser Punkte reichen aus, um das Geheimnis eindeutig zu bestimmen. Zwei Punkte lassen die Parabel – und damit das Geheimnis – unbestimmt. Beachten Sie, dass wir in diesem vereinfachten Beispiel ein Polynom über dem Körper der reellen Zahlen anstelle eines endlichen Körpers visualisieren.

Schritt für Schritt:

1. Definieren des Geheimnisses und der Parameter

• Das Geheimnis sei eine Zahl in einem endlichen Körper (z. B. einem endlichen Körper mit $2^8$ Elementen, die alle möglichen Werte eines Bytes darstellen können).
• Wählen Sie einen Schwellenwert $k$ (Mindestanzahl der Anteile, die zur Rekonstruktion des Geheimnisses erforderlich sind).
• Wählen Sie die Gesamtzahl der Aktien $n$, wobei $n\ge k$.

2. Konstruktion des Polynoms

Um das Geheimnis zu verschlüsseln, konstruieren wir ein zufälliges Polynom $f(x)$ vom Grad $k-1$:

$$f(x)=a_0+a_{1}x+a_2{x}^2+\cdots +a_{k-1}{x}^{k-1}$$

• Der konstante Term $a_0$ ist das Geheimnis.
• Die Koeffizienten $a_1,a_2,...,a_{k-1}$ werden zufällig aus dem endlichen Feld ausgewählt.
• Die Zufälligkeit dieser Koeffizienten ist entscheidend – sie stellt sicher, dass das Polynom unvorhersehbar ist und das Schema informationstheoretische Sicherheit erreicht.

3. Teile generieren

Jeder Anteil $s_i$ ist ein Punkt auf dem Polynom:

$$s_i=(x_i,f(x_i))$$

• Wählen Sie eindeutige Werte ungleich Null $x_1,x_2,...,x_n$ im endlichen Körper.
• Berechne den Wert des Polynoms an jedem Punkt $x_i$ um die entsprechenden Werte zu erhalten $f(x_i)$.

Diese Paare $(x_i,f(x_i))$ werden an die Teilnehmer verteilt. Jeder Anteil sieht für sich genommen wie zufällige Daten aus und verrät nichts über das Geheimnis, solange er nicht mit genügend anderen Anteilen kombiniert wird.

4. Das Geheimnis rekonstruieren

Um das Geheimnis wiederherzustellen $a_0$kann jede Gruppe von $k$ Teilnehmern ihre Anteile verwenden, um das Geheimnis zu rekonstruieren - mithilfe der Lagrange-Interpolation.:

Sicherheitseigenschaften

• Informationstheoretische Sicherheit: Jede Gruppe mit weniger als $k$ Anteilen erfährt nichts über das Geheimnis. Dies ist nicht nur rechnerisch schwierig, sondern mathematisch unmöglich.
• Schwellenwertflexibilität: Sie können $k$ und $n$ beliebig definieren, um ein Gleichgewicht zwischen Sicherheit und Fehlertoleranz herzustellen.
• Resilienz: Es spielt keine Rolle, welche Anteile verloren gehen oder nicht verfügbar sind. Solange $k$ gültige Anteile vorhanden sind, kann das Geheimnis wiederhergestellt werden.

Fazit: Warum Shamirs Secret Sharubg auch heute noch von Bedeutung ist

Shamirs Secret Sharing zeigt, wie Mathematik unsere Sichtweise auf Sicherheit verändern kann: Anstatt Daten hinter einem einzigen Schlüssel zu verschließen, macht es eine einzige vertrauenswürdige Instanz überflüssig und garantiert, dass niemals auch nur Teilinformationen nach außen gelangen können. Diese Grundlage macht es selbst angesichts neuer Bedrohungen leistungsstark und widerstandsfähig.

So leistungsfähig das klassische Schema auch ist, reale Systeme erfordern jedoch mehr. Groß angelegte Speicher bringen Effizienzprobleme mit sich, verteilte Netzwerke bergen das Risiko beschädigter oder bösartiger Freigaben, und langfristige Zuverlässigkeit erfordert Mechanismen, die über die Grundlagen hinausgehen.

In Teil 2 werden wir uns genauer ansehen, wie diese Herausforderungen angegangen werden:

• Wie Computationally Secure Secret Sharing den Speicheraufwand reduziert,
• Wie Robust Secret Sharing beschädigte Shares erkennt und einen hochgradig widerstandsfähigen, selbstheilenden Cloud-Speicher ermöglicht

Bleiben Sie dran – denn die wahre Stärke der geheimen Datenaufteilung liegt nicht nur in ihrer mathematischen Eleganz, sondern auch darin, wie sie sich weiterentwickelt, um den Anforderungen der modernen, verteilten Datensicherheit gerecht zu werden.

Referenzen

[1] Adi Schamir. 1979. Wie man ein Geheimnis teilt. Commun. ACM 22, 11 (Nov. 1979), 612-613. https://doi.org/10.1145/359168.359176

---

Sind Sie bereit, Ihre Daten vor zukünftigen Bedrohungen zu schützen?

➡️ Kontaktieren Sie uns für ein Beratung oder Demo zugeschnitten auf Ihre Infrastruktur.

Erfahren Sie, wie fragmentiX im Detail funktioniert:

➡️ Erkunden Sie unser Lösungen.