Betrachten wir das Szenario, in dem die Sicherheit eines Bankspeichers gewährleistet werden muss. Er gilt als absolut unzugänglich ohne den Schlüssel, den Sie am ersten Arbeitstag erhalten. Ihr Ziel ist es, den Schlüssel zuverlässig zu schützen.

Angenommen, Sie haben beschlossen, den Schlüssel stets bei sich zu behalten und den Zugang zum Speicher nach Bedarf zu gewähren. Sie werden jedoch schnell feststellen, dass diese Lösung in der Praxis nicht skalierbar ist, da Ihr physisches Erscheinen für das Öffnen des Speichers erforderlich ist. Was ist mit den Urlauben, die Ihnen versprochen wurden? Darüber hinaus gibt es eine noch beunruhigendere Frage: Was wenn Sie den einzigen Schlüssel verlieren?

Mit dem Gedanken an den Urlaub haben Sie beschlossen, eine Kopie des Schlüssels anzufertigen und diese einem anderen Mitarbeiter anzuvertrauen. Sie erkennen jedoch, dass dies auch nicht ideal ist. Indem Sie die Anzahl der Schlüssel verdoppeln, haben Sie auch die Möglichkeiten zum Diebstahl des Schlüssels verdoppelt.

Verzweifelt entscheiden Sie sich, die Kopie zu löschen und den ursprünglichen Schlüssel in zwei Teile zu teilen. Jetzt denken Sie, dass zwei vertraute Personen mit den Schlüsselfragmente physisch anwesend sein müssen, um den Schlüssel zusammenzusetzen und das Lager zu öffnen. Das bedeutet, dass ein Dieb zwei Fragmente stehlen muss, was es doppelt so schwierig macht, wie einen Schlüssel zu stehlen. Doch bald realisieren Sie, dass dieses Schema kaum besser ist als ein einzelner Schlüssel, denn wenn jemand die Hälfte des Schlüssels verliert, kann der vollständige Schlüssel nicht mehr wiederhergestellt werden.

Das Problem könnte mit einer Reihe zusätzlicher Schlüssel und Schlösser gelöst werden, aber mit diesem Ansatz benötigt man schnell eine Menge von Schlüsseln und Schlössern. Sie kommen zu dem Schluss, dass es in einem idealen Schema notwendig ist, den Schlüssel zu teilen, damit die Sicherheit nicht vollständig von einer einzelnen Person abhängt. Außerdem stellen Sie fest, dass es eine bestimmte Schwelle an Fragmenten geben muss, damit der gesamte Schlüssel funktionsfähig bleibt, selbst wenn ein Fragment verloren geht (oder wenn jemand im Urlaub ist).

Wie man ein Geheimnis teilt

Über diese Art von Schlüsselmanagement-Schema dachte Adi Shamir im Jahr 1979 nach, als er seine Arbeit veröffentlichte „Wie man ein Geheimnis teilt“. In diesem Artikel wird kurz erklärt, was eine Schwellen-Schemata für eine effektive Aufteilung eines geheimen Wertes (zum Beispiel eines kryptografischen Schlüssels) in Teile. Nur wenn mindestens von Teilen gesammelt sind, kann das Geheimnis einfach wiederhergestellt werden. .

Aus Sicht der Sicherheit ist eine wichtige Eigenschaft dieses Schemas, dass ein Angreifer absolut nichts erfahren sollte, wenn er nicht mindestens Teile hat. Selbst der Besitz von Teilen sollte keine Informationen geben. Wir nennen diese Eigenschaft semantische Sicherheit..

Polynominterpolation

Das Shamir'sche Schwellen-Schema basiert auf dem Konzept der Polynominterpolation.Wenn Sie mit diesem Konzept nicht vertraut sind, ist es eigentlich ziemlich einfach. Wenn Sie jemals Punkte auf einem Diagramm gezeichnet und dann mit Linien oder Kurven verbunden haben, haben Sie es bereits verwendet!

Durch zwei Punkte kann eine unbegrenzte Anzahl von Polynomen zweiten Grades durchgeführt werden. Um eines aus ihnen auszuwählen, benötigt man einen dritten Punkt. Illustration: Wikipedia

Betrachten wir ein Polynom ersten Grades, . Wenn Sie diese Funktion auf dem Graphen darstellen möchten, wie viele Punkte benötigen Sie? Nun, wir wissen, dass es sich um eine lineare Funktion handelt, die eine Linie bildet, und daher mindestens zwei Punkte benötigt werden. Betrachten wir als Nächstes eine polynomialen Funktion zweiten Grades, . Das ist eine quadratische Funktion, daher sind für die Erstellung des Graphen mindestens drei Punkte erforderlich. Und was ist mit einem Polynom dritten Grades? Mindestens vier Punkte. Und so weiter und so fort.

Das wirklich Tolle an dieser Eigenschaft ist, dass wir, wenn wir den Grad des polynomialen Funktion und mindestens Punkte berücksichtigen, zusätzliche Punkte für diese polynomiale Funktion ableiten können. Die Extrapolation dieser zusätzlichen Punkte nennen wir polynomiale Interpolation..

Das Geheimnis erstellen

Vielleicht haben Sie bereits verstanden, dass hier das clevere Shamir-Schema ins Spiel kommt. Angenommen, unser Geheimnis — ist . Wir können es in einen Punkt auf dem Graphen verwandeln und eine polynomialen Funktion vom Grad erstellen, die diesen Punkt erfüllt. Erinnern wir uns daran, dass wird unser Schwellenwert für die erforderlichen Fragmente sein. Wenn wir also den Schwellenwert auf drei Fragmente setzen, müssen wir eine polynomiale Funktion mit dem Grad zwei wählen.

Unser Polynom wird die Form haben , wobei und — zufällig ausgewählte positive ganze Zahlen sind. Wir bauen lediglich ein Polynom mit dem Grad , wobei der freie Koeffizient  — unser Geheimnis ist , und jeder der nachfolgenden Glieder einen zufällig ausgewählten positiven Koeffizienten hat. Wenn wir zum ursprünglichen Beispiel zurückkehren und annehmen, dass , dann erhalten wir die Funktion .

An diesem Punkt können wir Fragmente generieren, indem wir einzigartige ganze Zahlen in , wobei einfügen (denn das ist unser Geheimnis). In diesem Beispiel möchten wir vier Fragmente mit einem Schwellenwert von drei verteilen, also generieren wir zufällig Punkte und senden jeweils einen Punkt an jede der vier vertrauenswürdigen Personen, die Schlüsselverwalter sind. Wir teilen den Leuten auch mit, dass , da dies als öffentliche Information angesehen wird und für die Wiederherstellung notwendig ist. .

Wiederherstellung des Geheimnisses

Wir haben bereits das Konzept der polynomialen Interpolation und dessen Grundlagen für das Schlüsselschema von Shamir diskutiert. . Wenn drei von vier vertrauenswürdigen Personen eine Wiederherstellung wünschen, , müssen sie nur interpolieren mit ihren einzigartigen Punkten. Dazu können sie ihre Punkte bestimmen und das Lagrange-Interpolationspolynom mit der folgenden Formel berechnen. Wenn Ihnen Programmierung klarer ist als Mathematik, dann ist Pi im Grunde ein Operator, für, der alle Ergebnisse multipliziert, und Sigma ist der für, der alles summiert.

Mit können wir es auf folgende Weise lösen und unsere ursprüngliche polynomialen Funktion zurückgeben:

Da wir wissen, dass , erfolgt die Wiederherstellung einfach: Verwendung unsicherer ganzzahliger Arithmetik

Obwohl wir die Grundidee von Shamir erfolgreich angewendet haben.

Obwohl wir die grundlegende Idee von Shamir erfolgreich angewendet haben , wir haben ein Problem, das wir bis jetzt ignoriert haben. Unsere polynomielle Funktion verwendet unsichere ganzzahlige Arithmetik. Beachten Sie, dass für jeden zusätzlichen Punkt, den ein Angreifer auf dem Graphen unserer Funktion erhält, weniger Möglichkeiten für andere Punkte verbleiben. Sie können dies selbst sehen, wenn Sie den Graphen mit zunehmender Anzahl von Punkten für die polynomielle Funktion unter Verwendung ganzzahliger Arithmetik erstellen. Das ist kontraproduktiv für unser erklärtes Sicherheitsziel, da der Angreifer absolut nichts erfahren sollte, solange er nicht mindestens Teilstücke.

Um zu demonstrieren, wie schwach das System mit ganzzahliger Arithmetik ist, betrachten wir ein Szenario, in dem ein Angreifer zwei Punkte erhalten hat und öffentliche Informationen kennt, die . Aus diesen Informationen kann er ableiten , das gleich zwei ist, und die bekannten Werte in die Formel einsetzen und .

Dann kann der Angreifer finden, indem er :

berechnet. Da wir als zufällig gewählte positive ganze Zahlen definiert haben, gibt es eine begrenzte Anzahl möglicher Mit diesen Informationen kann ein Angreifer , da alles über 5 es negativ macht. Dies stellt sich als wahr heraus, da wir festgestellt haben,

Der Angreifer kann dann mögliche Werte berechnen, , indem er in :

Mit einer begrenzten Auswahl an Optionen für wird klar, wie einfach es ist, Werte zu erraten und zu überprüfen. Hier gibt es insgesamt fünf Optionen.

Das Problem mit unsicherer ganzzahliger Arithmetik lösen.

Um diese Schwachstelle zu beheben, schlägt Shamir vor, modulare Arithmetik zu verwenden, indem er findet man , wobei und – die Menge aller Primzahlen.

Lassen Sie uns kurz erinnern, wie modulare Arithmetik funktioniert. Uhren mit Zeigern sind ein bereits bekanntes Konzept. Sie nutzen Uhren, die . Sobald der Stundenzeiger die zwölf passiert, kehrt er auf eins zurück. Eine interessante Eigenschaft dieses Systems ist, dass wir nur, indem wir auf die Uhr schauen, nicht ableiten können, wie viele Umdrehungen der Stundenzeiger gemacht hat. Wenn wir jedoch wissen, dass der Stundenzeiger viermal die 12 überschritten hat, können wir die vergangene Stundenanzahl durch eine einfache Formel vollständig bestimmen, , wobei  – das ist unser Divisor (hier ),  — das ist der Koeffizient (wie oft der Divisor ohne Rest in die Ausgangszahl passt, hier ), und  — das ist der Rest, den der Modulo-Operator normalerweise zurückgibt (hier ). Das Wissen um all diese Werte ermöglicht es uns, die Gleichung für zu lösen, aber wenn wir den Koeffizienten übersehen, können wir den ursprünglichen Wert niemals wiederherstellen.

Wir können demonstrieren, wie dies die Sicherheit unseres Schemas verbessert, indem wir das Schema auf unser vorheriges Beispiel anwenden und dabei verwenden. Unsere neue polynomiale Funktion , und die neuen Punkte . Jetzt können die Schlüsselhalter die polynomialen Interpolationen erneut verwenden, um unsere Funktion wiederherzustellen, nur müssen die Addition und Multiplikation diesmal mit einer Modulo-Reduktion begleitet werden (z. B. ).

Angenommen, der Angreifer hat zwei dieser neuen Punkte erfahren, , und die öffentliche Information . Diesmal leitet der Angreifer auf der Grundlage aller verfügbaren Informationen folgende Funktionen ab, wobei  — die Menge aller positiven ganzen Zahlen ist, und den Modulo-Koeffizienten darstellt. .

Jetzt findet unser Angreifer erneut , indem er :

berechnet. Dann versucht er erneut, abzuleiten , indem er in :

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

Sicherheitsüberlegungen

Das Shamir'sche Geheimnistrennungsverfahren bietet Sicherheit aus der Perspektive der Informationstheorie. Das bedeutet, dass die Mathematik sogar gegen einen Angreifer mit unbegrenzter Rechenleistung robust ist. Allerdings weist das Verfahren nach wie vor einige bekannte Probleme auf.

Zum Beispiel generiert das Shamir-Verfahren keine überprüfbaren Fragmente, das heißt, Menschen können gefälschte Fragmente präsentieren und die Wiederherstellung des korrekten Secrets stören. Ein feindlicher Fragmentwächter mit genügend Informationen kann sogar ein anderes Fragment erzeugen, indem er nach eigenem Ermessen ändert. Dieses Problem wird durch überprüfbare Geheimnistrennungsverfahren, wie das Feldman-Verfahren, gelöst.

Ein weiteres Problem besteht darin, dass die Länge jedes Fragments der Länge des entsprechenden Secrets entspricht, sodass die Länge des Secrets leicht zu bestimmen ist. Dieses Problem wird durch eine triviale Padrierung gelöst. Geheimnisse mit beliebigen Zahlen bis zu einer festen Länge.

Es ist wichtig zu beachten, dass unsere Bedenken hinsichtlich der Sicherheit über das Schema hinausgehen können. Bei realen kryptografischen Anwendungen besteht häufig die Gefahr von Seitenkanalangriffen, bei denen ein Angreifer versucht, nützliche Informationen aus der Laufzeit des Programms, Caching, Abstürzen usw. zu extrahieren. Wenn dies besorgniserregend ist, sollten während der Entwicklung Schutzmaßnahmen wie Funktionen und die Suche mit konstanter Laufzeit in Betracht gezogen werden, um das Speichern von Informationen auf der Festplatte zu verhindern und eine Reihe anderer Aspekte zu berücksichtigen, die über diesen Artikel hinausgehen.

Demo

Auf auf dieser Seite gibt es eine interaktive Demonstration des Schemas zur Geheimnistrennung von Shamir. Die Demonstration basiert auf der Bibliothek ssss-js, die selbst ein JavaScript-Port des beliebten Programms ist ssss.Bitte beachten Sie, dass die Berechnung großer Werte , und eine gewisse Zeit in Anspruch nehmen kann.

Quelle: habr.com