Shamirs geheimes Teilungssystem

Ursprünglicher Autor: Eric Rafaloff
  • Übersetzung
Berücksichtigen Sie das Szenario, in dem es notwendig ist, die Sicherheit des Tresors zu gewährleisten. Ohne Schlüssel, den Sie am ersten Arbeitstag erhalten haben, gilt dies als völlig unzugänglich. Ihr Ziel ist es, den Schlüssel sicher zu speichern.

Angenommen, Sie entscheiden sich dafür, den Schlüssel immer bei sich zu haben, und geben bei Bedarf Zugriff auf das Repository. Sie werden jedoch schnell verstehen, dass eine solche Lösung in der Praxis normalerweise nicht skalierbar ist, da jedes Mal, wenn Sie Ihr Geschäft eröffnen, Ihre physische Präsenz erfordert. Was ist mit den Ferien, die Ihnen versprochen wurden? Darüber hinaus ist die Frage noch erschreckender: Was wäre, wenn Sie den einzigen Schlüssel verloren hätten?

Mit dem Gedanken an den Urlaub haben Sie sich entschieden, eine Kopie des Schlüssels anzufertigen und ihn einem anderen Mitarbeiter anzuvertrauen. Sie verstehen jedoch, dass dies auch nicht ideal ist. Durch das Verdoppeln der Schlüsselanzahl verdoppeln Sie außerdem die Möglichkeit eines Schlüsseldiebstahls.

Verzweifelt zerstören Sie das Duplikat und entscheiden, den Quellschlüssel in zwei Hälften zu teilen. Nun glauben Sie, dass zwei vertrauenswürdige Personen mit Schlüsselfragmenten physisch anwesend sein müssen, um den Schlüssel zu sammeln und den Tresor zu öffnen. Dies bedeutet, dass ein Dieb zwei Fragmente stehlen muss, was doppelt so schwer ist, einen Schlüssel zu stehlen. Sie stellen jedoch schnell fest, dass dieses Schema nicht viel besser ist als nur ein Schlüssel, denn wenn jemand den halben Schlüssel verliert, kann der volle Schlüssel nicht wiederhergestellt werden.

Das Problem kann mit einer Reihe zusätzlicher Schlüssel und Schlösser gelöst werden. Bei diesem Ansatz sind jedoch viele Schlüssel und Schlösser schnell erforderlich . Sie entscheiden, dass Sie im Idealfall den Schlüssel teilen müssen, damit die Sicherheit nicht ausschließlich von einer Person abhängt. Sie schlussfolgern auch, dass es eine bestimmte Schwelle für die Anzahl der Fragmente geben muss, damit bei Verlust eines Fragments (oder wenn eine Person in Urlaub geht) der gesamte Schlüssel funktionsfähig bleibt.

So teilen Sie ein Geheimnis


Adi Shamir dachte 1979 an diese Art von Schlüsselverwaltungssystem, als er seine Arbeit "How to share a secret" veröffentlichte . Der Artikel erklärt kurz das sogenannte Schwellenwertschema, um effektiv einen geheimen Wert (z. B. einen kryptographischen Schlüssel) gemeinsam zu nutzen Teile. Dann wann und nur wann von der Teile montiert sind, können Sie das Geheimnis leicht wiederfinden .

Aus Sicherheitsgründen ist ein wichtiges Merkmal dieses Schemas, dass ein Angreifer nicht absolut nichts lernen sollte, wenn er dies nicht einmal getan hatTeile. Sogar mitTeile sollten keine Informationen geben. Wir nennen diese Eigenschaft semantische Sicherheit .

Polynominterpolation


Shamir-Schwellenwertschema um das Konzept der Polynominterpolation herum aufgebaut . Wenn Sie mit diesem Konzept nicht vertraut sind, ist es eigentlich ganz einfach. Wenn Sie schon einmal Punkte in eine Grafik gezeichnet und diese dann mit Linien oder Kurven verbunden haben, haben Sie sie bereits verwendet!


Eine unbegrenzte Anzahl von Polynomen mit Grad 2 kann durch zwei Punkte gezogen werden. Um einen von ihnen zu wählen, ist ein dritter Punkt erforderlich. Abbildung: Wikipedia

Betrachten Sie ein Polynom mit dem ersten Grad.. Wenn Sie diese Funktion in einem Diagramm darstellen möchten, wie viele Punkte benötigen Sie? Nun, wir wissen, dass dies eine lineare Funktion ist, die eine Linie bildet und daher mindestens zwei Punkte benötigt. Als nächstes betrachten wir eine Polynomfunktion mit Grad zwei,. Dies ist eine quadratische Funktion, daher sind mindestens drei Punkte zum Plotten erforderlich. Was ist mit einem Polynom mit Grad drei? Mindestens vier Punkte. Und so weiter und so fort.

Das wirklich Coole an dieser Eigenschaft ist, dass angesichts des Grades der Polynomfunktion und zumindestPunkte können wir zusätzliche Punkte für diese Polynomfunktion schließen. Die Extrapolation dieser zusätzlichen Punkte wird Polynominterpolation genannt .

Ein Geheimnis machen


Vielleicht haben Sie bereits verstanden, dass Shamirs intelligentes Schema hier zum Tragen kommt. Angenommen, unser Geheimnis - Das . Wir können uns wenden auf die Karte zeigen und mit einer Polynomfunktion mit Grad kommen was diesen Punkt erfüllt. Daran erinnern, dasswird unsere Schwelle für die erforderlichen Fragmente sein. Wenn wir also die Schwelle auf drei Fragmente setzen, müssen wir eine Polynomfunktion mit Grad zwei wählen.

Unser Polynom wird die Form habenwo und - zufällig ausgewählte positive ganze Zahlen. Wir bauen einfach ein Polynom mit Gradwo freies Verhältnis  - das ist unser Geheimnis und jedes der folgenden Mitglieder haben einen zufällig gewählten positiven Koeffizienten. Gehen Sie zum ursprünglichen Beispiel zurück und nehmen Sie das anDann bekommen wir die Funktion .

In dieser Phase können wir Fragmente erzeugen, indem wir verbinden einzigartige ganze Zahlen in wo (weil es unser Geheimnis ist). In diesem Beispiel möchten wir vier Fragmente mit einem Schwellenwert von drei verteilen. Daher generieren wir zufällig Punkteund senden Sie einen Punkt an jeden der vier Vertrauenspersonen, die Schlüsselhalter. Wir informieren die Leute auch darüberda es als öffentliche Information betrachtet wird und für die Wiederherstellung erforderlich ist .

Geheimnis der Genesung


Wir haben bereits das Konzept der Polynominterpolation und die Tatsache besprochen, dass es dem Shamir-Schwellenwertschema zugrunde liegt. . Wenn drei der vier Proxys wiederhergestellt werden möchtenSie müssen nur interpolieren mit seinen eigenen einzigartigen Punkten. Dafür können sie ihre Punkte definieren.und berechnen Sie das Lagrange-Interpolationspolynom unter Verwendung der folgenden Formel. Wenn die Programmierung für Sie klarer ist als für die Mathematik, dann ist pi im Wesentlichen ein Operator for, der alle Ergebnisse multipliziert, und Sigma ist das, forwas summiert.



Mit Wir können dies wie folgt lösen und unsere ursprüngliche Polynomfunktion zurückgeben:


Wie wir das wissen Erholung einfach durchgeführt:


Verwendung von unsicherer Ganzzahlarithmetik


Obwohl wir die Grundidee von Shamir erfolgreich angewendet haben Wir haben immer noch ein Problem, das wir bisher ignoriert haben. Unsere Polynom-Funktion verwendet eine unsichere Ganzzahlarithmetik. Beachten Sie, dass für jeden zusätzlichen Punkt, den ein Angreifer im Diagramm unserer Funktion erhält, weniger Möglichkeiten für andere Punkte bestehen. Sie können es mit eigenen Augen sehen, wenn Sie einen Graphen erstellen, bei dem die Anzahl der Punkte für eine Polynomfunktion mithilfe von Ganzzahlarithmetik erhöht wird. Dies ist kontraproduktiv für unser angegebenes Sicherheitsziel, da der Angreifer bis zum Schluss absolut nichts wissen sollteFragmente.

Um zu zeigen, wie schwach die Schaltung mit Ganzzahlarithmetik ist, sollten Sie ein Szenario betrachten, in dem ein Angreifer zwei Punkte erhalten hat und kennt die Informationen der Öffentlichkeit . Aus dieser Information kann er ableitengleich zwei und verbinden Sie die bekannten Werte mit der Formel und .


Dann kann der Angreifer finden durch Zählen :


Da haben wir definiert Wie zufällig ausgewählte positive ganze Zahlen gibt es eine begrenzte Anzahl möglicher Werte . Mit dieser Information kann der Angreifer anzeigenweil etwas mehr als 5 ausreichen wird negativ. Dies stellt sich als wahr heraus, da wir identifiziert haben

Der Angreifer kann dann die möglichen Werte berechnen. durch Ersetzen in der :


Mit einer begrenzten Anzahl von Optionen für Es wird deutlich, wie einfach es ist, die Werte zu finden und zu überprüfen . Es gibt nur fünf Optionen.

Lösung des Problems der unsicheren Ganzzahlarithmetik


Um diese Sicherheitsanfälligkeit zu beseitigen, schlägt Shamir vor, die modulare Arithmetik zu ersetzen auf wo und - die Menge aller Primzahlen.

Erinnern Sie sich schnell, wie die modulare Arithmetik funktioniert. Eine Pfeiluhr ist ein bekanntes Konzept. Sie benutzt Uhren, die sind. Sobald der Stundenzeiger zwölf ist, kehrt er zu eins zurück. Ein interessantes Merkmal dieses Systems ist, dass wir durch bloßes Betrachten der Uhr nicht ableiten können, wie viele Umdrehungen der Stundenzeiger gemacht hat. Wenn wir jedoch wissen, dass der Stundenzeiger viermal vergangen ist, können wir die Anzahl der verstrichenen Stunden mithilfe einer einfachen Formel vollständig bestimmenwo  - das ist unser Teiler (hier )  - ist der Koeffizient (wie oft der Teiler ohne Rest in die ursprüngliche Zahl geht, hier) ) und  - Dies ist der Rest, der normalerweise den modularen Bedieneraufruf zurückgibt (hier ). Wenn wir all diese Werte kennen, können wir die Gleichung für lösenAber wenn wir den Koeffizienten verfehlen, können wir den ursprünglichen Wert niemals wiederherstellen.

Sie können demonstrieren, wie dies die Sicherheit unserer Schaltung verbessert, indem Sie die Schaltung auf unser vorheriges Beispiel anwenden und verwenden. Unsere neue Polynomfunktionund neue Punkte . Jetzt können die Schlüsselhalter erneut die Polynominterpolation verwenden, um unsere Funktion wiederherzustellen. Diesmal müssen jedoch die Additions- und Multiplikationsoperationen von einem Reduktionsmodul begleitet werden (zB ).

Nehmen Sie an diesem neuen Beispiel an, dass der Angreifer zwei dieser neuen Punkte gelernt hat:und öffentliche Informationen . Diesmal zeigt der Angreifer auf der Grundlage aller Informationen die folgenden Funktionen an, wo - eine Menge aller positiven ganzen Zahlen und repräsentiert den Modulkoeffizienten .


Nun findet unser Angreifer wieder durch berechnen :


Dann versucht er erneut, sich zurückzuziehen durch Ersetzen in der :


Dieses Mal hat er ein ernstes Problem. Die Formel enthält keine Werte.. und . Da es unendlich viele Kombinationen dieser Variablen gibt, kann er keine zusätzlichen Informationen erhalten.

Sicherheitsüberlegungen


Shamirs geheimes Sharing-System bietet Sicherheit in Bezug auf Informationstheorie . Das bedeutet, dass die Mathematik auch gegen Angreifer mit unbegrenzter Rechenleistung beständig ist. Das Schema enthält jedoch immer noch einige bekannte Probleme.

Zum Beispiel erzeugt das Shamir-Schema keine überprüfbaren Fragmente , das heißt, Menschen können gefälschte Fragmente frei präsentieren und die Wiederherstellung des richtigen Geheimnisses behindern. Ein feindlicher Fragmenthalter mit ausreichenden Informationen kann durch Ändern sogar ein anderes Fragment erzeugennach eigenem Ermessen. Dieses Problem wird mit Hilfe überprüfbarer geheimer Verteilungsprogramme wie dem Feldman-Schema gelöst .

Ein anderes Problem besteht darin, dass die Länge eines Fragments der Länge des entsprechenden Geheimnisses entspricht, sodass die Länge des Geheimnisses leicht zu bestimmen ist. Dieses Problem wird durch die unbedeutende Packung des Geheimnisses mit beliebigen Zahlen bis zu einer festen Länge gelöst .

Schließlich ist es wichtig anzumerken, dass unsere Sicherheitsbedenken über das System selbst hinausgehen können. Bei kryptografischen Anwendungen in der realen Welt drohen häufig Angriffe über Kanäle von Drittanbietern, wenn ein Angreifer versucht, nützliche Informationen aus der Anwendungsausführungszeit, Caching, Ausfällen usw. zu extrahieren. Wenn dies ein Problem ist, sollten Sie die Verwendung von Schutzmaßnahmen, z. B. Funktionen und Suche mit konstanter Ausführungszeit, sorgfältig prüfen, den Speicherplatz auf der Festplatte verhindern und eine Reihe anderer Dinge in Betracht ziehen, die den Rahmen dieses Artikels sprengen würden.

Demo


Auf dieser Seite finden Sie eine interaktive Demonstration des Shamir-Geheimschemas. Die Demonstration wird auf der Grundlage der Bibliothek gemacht ssss-js , die an sich eine JavaScript-Port des beliebten Programms ist ssss . Beachten Sie, dass große Werte berechnet werden. und kann einige Zeit dauern.

Jetzt auch beliebt: