Stellen Sie sich ein Szenario vor, in dem Sie einen Banktresor sichern müssen. Ohne Schlüssel, der Ihnen am ersten Arbeitstag ausgehändigt wird, gilt es als absolut uneinnehmbar. Ihr Ziel ist es, den Schlüssel sicher aufzubewahren.

Angenommen, Sie beschließen, den Schlüssel immer bei sich zu haben, um bei Bedarf Zugang zum Tresor zu ermöglichen. Sie werden jedoch schnell feststellen, dass eine solche Lösung in der Praxis nicht gut skalierbar ist, da Sie jedes Mal physisch anwesend sein müssen, um den Tresor zu öffnen. Was ist mit dem versprochenen Urlaub? Darüber hinaus ist die Frage noch beängstigender: Was wäre, wenn Sie den einzigen Schlüssel verloren hätten?

Mit dem Gedanken an einen Urlaub beschließen Sie, eine Kopie des Schlüssels anzufertigen und diese einem anderen Mitarbeiter anzuvertrauen. Sie verstehen jedoch, dass dies auch nicht ideal ist. Durch die Verdoppelung der Schlüsselanzahl verdoppelt sich auch die Wahrscheinlichkeit eines Schlüsseldiebstahls.

In Ihrer Verzweiflung zerstören Sie das Duplikat und beschließen, den Originalschlüssel in zwei Hälften zu teilen. Nun denken Sie, dass zwei vertrauenswürdige Personen mit Schlüsselfragmenten physisch anwesend sein müssen, um den Schlüssel abzuholen und den Tresor zu öffnen. Das bedeutet, dass der Dieb zwei Fragmente stehlen muss, was doppelt so schwierig ist wie der Diebstahl eines Schlüssels. Allerdings merkt man schnell, dass dieses Schema nicht viel besser ist als nur ein Schlüssel, denn wenn jemand die Hälfte des Schlüssels verliert, kann der vollständige Schlüssel nicht wiederhergestellt werden.

Das Problem kann mit einer Reihe zusätzlicher Schlüssel und Schlösser gelöst werden, dieser Ansatz wird jedoch schnell erforderlich sein много Schlüssel und Schlösser. Sie entscheiden, dass das ideale Schema darin besteht, den Schlüssel zu teilen, damit die Sicherheit nicht ausschließlich von einer Person abhängig ist. Sie kommen außerdem zu dem Schluss, dass es einen bestimmten Grenzwert für die Anzahl der Fragmente geben muss, damit bei Verlust eines Fragments (oder wenn die Person in den Urlaub fährt) der gesamte Schlüssel funktionsfähig bleibt.

Wie man ein Geheimnis teilt

Diese Art von Schlüsselverwaltungsschema wurde 1979 von Adi Shamir erdacht, als er seine Arbeit veröffentlichte „Wie man ein Geheimnis teilt“. Der Artikel erklärt kurz das sogenannte Schwellenwertschema zur effektiven Aufteilung eines geheimen Werts (z. B. eines kryptografischen Schlüssels). Teile. Dann, wann und nur dann zumindest von Wenn die Teile zusammengebaut sind, können Sie das Geheimnis leicht wiederherstellen .

Aus sicherheitstechnischer Sicht besteht eine wichtige Eigenschaft dieses Schemas darin, dass ein Angreifer absolut nichts lernen sollte, wenn er es nicht zumindest getan hat Teile. Sogar die Anwesenheit Teile sollten keine Auskunft geben. Wir nennen diese Eigenschaft Semantische Sicherheit.

Polynominterpolation

Schwellen-Shamir-Schema rund um das Konzept aufgebaut Polynominterpolation. Wenn Sie mit diesem Konzept nicht vertraut sind, ist es eigentlich ganz einfach. Generell gilt: Wenn Sie jemals Punkte auf einem Diagramm gezeichnet und diese dann mit Linien oder Kurven verbunden haben, haben Sie es bereits verwendet!

Durch zwei Punkte können Sie eine unbegrenzte Anzahl von Polynomen 2. Grades zeichnen. Um das einzige daraus auszuwählen, benötigen Sie einen dritten Punkt. Illustration: Wikipedia

Betrachten Sie ein Polynom mit Grad eins, . 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 deshalb benötigen wir mindestens zwei Punkte. Betrachten Sie als nächstes eine Polynomfunktion vom Grad zwei: . Da es sich um eine quadratische Funktion handelt, sind zum Zeichnen des Diagramms mindestens drei Punkte erforderlich. Wie wäre es mit einem Polynom dritten Grades? Mindestens vier Punkte. Und so weiter und so fort.

Das wirklich Coole an dieser Eigenschaft ist, dass angesichts des Grades der Polynomfunktion und zumindest Punkte können wir zusätzliche Punkte für diese Polynomfunktion ableiten. Wir nennen die Extrapolation dieser zusätzlichen Punkte Polynominterpolation.

Ein Geheimnis machen

Sie haben vielleicht schon herausgefunden, dass hier Shamirs cleverer Plan ins Spiel kommt. Nehmen wir an, unser Geheimnis - Das . Wir können uns umdrehen bis zum Punkt in der Grafik und erstelle eine Polynomfunktion mit einem Grad , was diesen Punkt erfüllt. Erinnere dich daran wird unser Schwellenwert für die erforderlichen Fragmente sein. Wenn wir den Schwellenwert also auf drei Fragmente festlegen, müssen wir eine Polynomfunktion mit einem Grad von zwei wählen.

Unser Polynom wird die Form haben Wo и sind zufällig ausgewählte positive ganze Zahlen. Wir bilden einfach ein Polynom mit einem Grad , wo der freie Koeffizient  - Das ist unser Geheimnis , und jedes der folgenden term ist ein zufällig ausgewählter positiver Koeffizient. Wenn wir zum ursprünglichen Beispiel zurückkehren und davon ausgehen , dann erhalten wir die Funktion .

An diesem Punkt können wir durch Verbinden Fragmente erzeugen eindeutige ganze Zahlen in Wo (weil es unser Geheimnis ist). In diesem Beispiel möchten wir vier Fragmente mit einem Schwellenwert von drei verteilen, also generieren wir zufällig Punkte und senden Sie einen Punkt an jede der vier vertrauenswürdigen Personen, die den Schlüssel behalten. Das sagen wir den Leuten auch , da es sich um öffentliche Informationen handelt und für die Wiederherstellung notwendig ist .

Geheime Wiederherstellung

Wir haben bereits das Konzept der Polynominterpolation diskutiert und wie es dem Schwellenwertschema von Shamir zugrunde liegt. . Wenn drei von vier Treuhändern eine Wiederherstellung wünschen , sie müssen nur interpolieren mit ihren einzigartigen Punkten. Dazu können sie ihre Punkte definieren und berechnen Sie das Lagrange-Interpolationspolynom mit der folgenden Formel. Wenn Ihnen das Programmieren klarer ist als die Mathematik, dann ist Pi im Wesentlichen ein Operator for, was alle Ergebnisse multipliziert, und Sigma ist fordas summiert alles.

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

Da wir das wissen , Erholung geht ganz einfach:

Verwendung unsicherer Ganzzahlarithmetik

Obwohl wir die Grundidee von Shamir erfolgreich angewendet haben , stehen wir vor einem Problem, das wir bisher ignoriert haben. Unsere Polynomfunktion verwendet unsichere Ganzzahlarithmetik. Beachten Sie, dass für jeden zusätzlichen Punkt, den ein Angreifer in unserem Funktionsdiagramm erhält, weniger Möglichkeiten für andere Punkte bestehen. Sie können dies mit eigenen Augen sehen, wenn Sie mithilfe der Ganzzahlarithmetik eine zunehmende Anzahl von Punkten für eine Polynomfunktion zeichnen. Dies ist im Hinblick auf unser erklärtes Sicherheitsziel kontraproduktiv, da der Angreifer erst dann absolut nichts wissen sollte, wenn er es zumindest weiß Fragmente.

Um zu veranschaulichen, wie schwach das Ganzzahl-Arithmetikschema ist, stellen Sie sich ein Szenario vor, in dem der Angreifer zwei Punkte erhalten hat und kennt öffentliche Informationen darüber . Aus diesen Informationen kann er schließen , gleich zwei, und verbinden Sie die bekannten Werte mit der Formel и .

Der Angreifer kann dann finden , Zählen :

Da haben wir definiert Da es sich um zufällig ausgewählte positive ganze Zahlen handelt, ist die Anzahl der möglichen Zahlen begrenzt . Anhand dieser Informationen kann ein Angreifer Rückschlüsse ziehen , weil alles, was größer als 5 ist, ausreicht Negativ. Dies stellt sich als wahr heraus, da wir festgestellt haben

Der Angreifer kann dann die möglichen Werte berechnen ersetzen в :

Mit begrenzten Möglichkeiten für Es wird deutlich, wie einfach es ist, Werte zu erfassen und zu überprüfen . Hier gibt es nur fünf Möglichkeiten.

Lösung des Problems mit unsicherer Ganzzahlarithmetik

Um diese Schwachstelle zu beheben, schlägt Shamir die Verwendung modularer Arithmetik durch Ersetzen vor auf Wo и ist die Menge aller Primzahlen.

Erinnern wir uns kurz daran, wie die modulare Arithmetik funktioniert. Zeigeruhren sind ein bekanntes Konzept. Sie benutzt also eine Uhr . Sobald der Stundenzeiger zwölf überschreitet, kehrt er auf eins zurück. Eine interessante Eigenschaft dieses Systems besteht darin, dass wir allein durch einen Blick auf die Uhr nicht darauf schließen können, wie viele Umdrehungen der Stundenzeiger gemacht hat. Wenn wir jedoch wissen, dass der Stundenzeiger viermal die 12 überschritten hat, können wir mit einer einfachen Formel die Anzahl der verstrichenen Stunden vollständig ermitteln Wo  ist unser Teiler (hier ),  - das ist der Koeffizient (wie oft der Divisor ohne Rest in die ursprüngliche Zahl eingeht, hier). ), und  ist der Rest, der normalerweise einen Aufruf an den Modulo-Operator zurückgibt (hier). ). Wenn wir alle diese Werte kennen, können wir die Gleichung nach lösen , aber wenn wir den Koeffizienten überspringen, können wir den ursprünglichen Wert nie wiederherstellen.

Wir können demonstrieren, wie dies die Sicherheit unserer Schaltung verbessert, indem wir die Schaltung auf unser vorheriges Beispiel anwenden und verwenden . Unsere neue Polynomfunktion , und die neuen Punkte . Jetzt können die Schlüsselverwalter erneut die Polynominterpolation verwenden, um unsere Funktion zu rekonstruieren, nur dass diesmal auf die Additions- und Multiplikationsoperationen eine Modulo-Reduktion folgen muss. (z.B ).

Nehmen wir anhand dieses neuen Beispiels an, dass der Angreifer zwei dieser neuen Punkte gelernt hat: und öffentliche Informationen . Diesmal zeigt der Angreifer basierend auf allen ihm vorliegenden Informationen die folgenden Funktionen an:  ist die Menge aller positiven ganzen Zahlen und stellt den Modulkoeffizienten dar .

Jetzt findet unser Eindringling wieder , berechnend :

Dann versucht er erneut, sich zurückzuziehen ersetzen в :

Diesmal hat er ein ernstes Problem. In der Formel fehlen Werte , и . Da es unendlich viele Kombinationen dieser Variablen gibt, kann er keine zusätzlichen Informationen erhalten.

Sicherheitsüberlegungen

Shamirs geheimer Austauschplan legt nahe Informationssicherheit. Dies bedeutet, dass die Mathematik selbst gegen einen Angreifer mit unbegrenzter Rechenleistung stark ist. Das Schema enthält jedoch immer noch mehrere bekannte Probleme.

Das Shamir-Schema schafft beispielsweise nichts Fragmente, die überprüft werden sollenDas heißt, es steht den Menschen frei, gefälschte Fragmente vorzulegen und die Wiederherstellung des richtigen Geheimnisses zu behindern. Ein feindlicher Fragmentbewahrer mit ausreichend Informationen kann durch Veränderung sogar ein weiteres Fragment erzeugen in Ihrem Ermessen. Dieses Problem wird mit gelöst überprüfbare Schemata zur Weitergabe von Geheimnissen, wie zum Beispiel das Feldman-Schema.

Ein weiteres Problem besteht darin, dass die Länge eines beliebigen Fragments gleich der Länge des entsprechenden Geheimnisses ist, sodass die Länge des Geheimnisses leicht zu bestimmen ist. Dieses Problem wird durch das Triviale gelöst Polsterung geheim durch beliebige Zahlen bis zu einer festen Länge.

Abschließend ist es wichtig zu beachten, dass unsere Sicherheitsbedenken möglicherweise über das System selbst hinausgehen. Bei echten kryptografischen Anwendungen besteht häufig die Gefahr von Seitenkanalangriffen, wenn ein Angreifer versucht, nützliche Informationen aus der Ausführungszeit, dem Caching, Abstürzen usw. der Anwendung zu extrahieren. Wenn dies ein Problem darstellt, sollten Sie die Verwendung von Schutzmaßnahmen während der Entwicklung sorgfältig in Betracht ziehen, z. B. Funktionen und konstante Suchvorgänge, das Speichern von Speicher auf der Festplatte verhindern und eine Reihe anderer Dinge berücksichtigen, die über den Rahmen dieses Artikels hinausgehen.

Demo

Auf Diese Seite Es gibt eine interaktive Demonstration von Shamirs geheimem Austauschprogramm. Die Demonstration erfolgte anhand der Bibliothek ssss-js, das selbst eine JavaScript-Portierung eines beliebten Programms ist ssss. Beachten Sie, dass große Werte berechnet werden , и kann eine Weile dauern.

Source: habr.com