Stellen Sie sich das Szenario vor, in dem die Sicherheit des Banktresors gewährleistet werden muss. Es gilt als absolut uneinnehmbar ohne Schlüssel, den Sie am ersten Arbeitstag erhalten. Ihr Ziel ist es, den Schlüssel sicher zu speichern.

Angenommen, Sie möchten den Schlüssel immer bei sich haben und bei Bedarf Zugriff auf das Geschäft gewähren. Sie werden jedoch schnell feststellen, dass eine solche Lösung in der Praxis nicht normal skaliert werden kann, da Sie jedes Mal Ihre physische Präsenz benötigen, um das Repository zu öffnen. Was ist mit den Ferien, die Ihnen versprochen wurden? Darüber hinaus ist die Frage noch beängstigender: Was ist, wenn Sie einen einzelnen Schlüssel verloren haben?

Mit dem Gedanken an Urlaub haben Sie beschlossen, eine Kopie des Schlüssels zu erstellen und ihn einem anderen Mitarbeiter anzuvertrauen. Sie verstehen jedoch, dass dies auch nicht ideal ist. Durch die Verdoppelung der Anzahl der Schlüssel haben Sie auch die Möglichkeiten des Schlüsseldiebstahls verdoppelt.

Verzweifelt zerstören Sie das Duplikat und beschließen, den Originalschlüssel in zwei Hälften zu teilen. Sie denken, zwei vertrauenswürdige Personen mit Schlüsselfragmenten müssen physisch anwesend sein, um den Schlüssel zu sammeln und den Laden zu öffnen. Dies bedeutet, dass der Dieb zwei Fragmente stehlen muss, was doppelt so schwierig ist wie das Stehlen eines Schlüssels. Sie werden jedoch bald feststellen, dass dieses Schema nicht viel besser ist als nur ein Schlüssel, denn wenn jemand den halben Schlüssel 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. Bei diesem Ansatz benötigen Sie jedoch schnell viele Schlüssel und Schlösser. Sie entscheiden, dass Sie in einem idealen Schema den Schlüssel teilen müssen, damit die Sicherheit nicht nur von einer Person abhängt. Sie kommen auch zu dem Schluss, dass es einen bestimmten Schwellenwert für die Anzahl der Fragmente geben muss, damit der gesamte Schlüssel funktionsfähig bleibt, wenn ein Fragment verloren geht (oder wenn eine Person in den Urlaub fährt).

Wie man ein Geheimnis teilt

Diese Art von Schlüsselverwaltungsschema wurde 1979 von Adi Shamir gedacht, als er seine Arbeit How to Share a Secret veröffentlichte . Der Artikel erklärt kurz das sogenannte $$$(k, n)$Schwellenwertschema zum effektiven Teilen eines geheimen Werts (z. B. eines kryptografischen Schlüssels) in $$$n$Teile. Dann, wann und nur wann zumindest $$$k$von $$$n$Teile zusammengebaut, können Sie das Geheimnis leicht wiederherstellen $$$S$.

Unter dem Gesichtspunkt der Sicherheit ist eine wichtige Eigenschaft dieses Schemas, dass der Angreifer absolut nichts wissen sollte, wenn er dies zumindest nicht hat $$$k$Teile. Auch Verfügbarkeit $$$k - 1$Teile sollten keine Informationen geben. Wir nennen diese Eigenschaft semantische Sicherheit .

Polynominterpolation

Shamir-Schwellenwertschema $$$(k, n)$gebaut um das Konzept der Polynominterpolation . Wenn Sie mit diesem Konzept nicht vertraut sind, ist es eigentlich ganz einfach. Wenn Sie jemals Punkte auf einem Diagramm gezeichnet und diese dann mit Linien oder Kurven verbunden haben, haben Sie sie im Allgemeinen bereits verwendet!


Eine unbegrenzte Anzahl von Polynomen des Grades 2 kann durch zwei Punkte gezogen werden. Um den einzigen auszuwählen, benötigen Sie einen dritten Punkt. Abbildung: Wikipedia

Betrachten Sie ein Polynom mit Grad eins, $$$f (x) = x + 2$. 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 werden mindestens zwei Punkte benötigt. Als nächstes betrachten wir eine Polynomfunktion mit Grad zwei, $$$f (x) = x ^ 2 + 2x + 1$. Dies ist eine quadratische Funktion, daher sind mindestens drei Punkte erforderlich, um ein Diagramm zu erstellen. 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 zumindest $$$Grad + 1$Punkte können wir zusätzliche Punkte für diese Polynomfunktion ableiten. Die Extrapolation dieser zusätzlichen Punkte wird als Polynominterpolation bezeichnet .

Ein Geheimnis machen

Möglicherweise haben Sie bereits erkannt, dass Shamirs intelligentes Schema hier ins Spiel kommt. Nehmen wir unser Geheimnis an $$$S$- Das $$$42$. Wir können uns wenden $$$S$zu einem Punkt auf dem Diagramm $$$(0,42)$und kommen mit einer Polynomfunktion mit Grad $$$k-1$was diesen Punkt erfüllt. Erinnern Sie sich daran $$$k$wird unser Schwellenwert für die erforderlichen Fragmente sein. Wenn wir also den Schwellenwert auf drei Fragmente setzen, müssen wir eine Polynomfunktion mit Grad zwei wählen.

Unser Polynom wird die Form annehmen $$$f (x) = a_0 + a_1x + a_2x ^ 2 + a_3x ^ 3 + ... + a_ {k-1} x ^ {k-1}$wo $$$a_0 = S$und $$$a_1, ..., a_ {k-1}$- zufällig ausgewählte positive ganze Zahlen. Wir bauen gerade ein Polynom mit einem Abschluss $$$k-1$wo ist der freie Koeffizient $$$a_0$Ist unser Geheimnis $$$S$und jede der folgenden $$$k-1$Mitglieder haben einen zufällig ausgewählten positiven Koeffizienten. Wenn Sie zum ursprünglichen Beispiel zurückkehren und dies annehmen $$$S = 42, k = 3, a_1, ..., a_ {k-1} = [3,5]$dann bekommen wir die Funktion $$$f (x) = 42 + 3x + 5x ^ 2$.

In diesem Stadium können wir durch Verbinden Fragmente erzeugen $$$n$eindeutige ganze Zahlen in $$$f (x) = 42 + 3x + 5x ^ 2$wo $$$x \ neq 0$(weil dies unser Geheimnis ist). In diesem Beispiel möchten wir vier Fragmente mit einem Schwellenwert von drei verteilen, sodass wir zufällig Punkte generieren $$$(18, 1716), (27, 3768), (31, 4940), (35, 6272)$und senden Sie einen Punkt an jede der vier vertrauenswürdigen Personen, Schlüsselbewahrer. Das sagen wir auch den Leuten $$$k = 3$, da es als öffentliche Information betrachtet wird und für die Wiederherstellung notwendig ist $$$S$.

Geheime Genesung

Wir haben bereits das Konzept der Polynominterpolation und die Tatsache diskutiert, dass es dem Shamir-Schwellenwertschema zugrunde liegt $$$(k, n)$. Wenn drei der vier Proxys wiederhergestellt werden möchten $$$S$Sie müssen nur interpolieren $$$f (0)$mit seinen eigenen einzigartigen Punkten. Dazu können sie ihre Punkte bestimmen $$$(x_1, y_1), ..., (x_k, y_k) = (18, 1716), (27, 3768), (31, 4940)$und berechnen Sie das Lagrange-Interpolationspolynom unter Verwendung der folgenden Formel. Wenn Programmieren für Sie verständlicher ist als Mathematik, dann ist pi im Wesentlichen eine for Anweisung, die alle Ergebnisse multipliziert, und sigma ist eine for Anweisung, die alles addiert.

$$

$$P (x) = \ sum_ {j = 1} ^ {k} p_j (x)$$

$$

$$P_j (x) = y_j \ prod _ {\ scriptstyle m = 1 \ atop \ scriptstyle m \ neq j} ^ {k} \ frac {x-x_m} {x_j-x_m}$$

Bei $$$k = 3$Wir können dies wie folgt lösen und unsere ursprüngliche Polynomfunktion zurückgeben:

$$

$$\ begin {align} P (x) & = {y_1} \ left ({x-x_2 \ über x_1-x_2} \ cdot {x-x_3 \ über x_1-x_3} \ right) + {y_2} \ left ( {x-x_1 \ über x_2-x_1} \ cdot {x - \ _ 3 \ über x_2-x_3} \ rechts) + {y_3} \ links ({x-x_1 \ über x_3-x_1} \ cdot {x-x_2 \ über x_3-x_2} \ rechts) \\ P (x) & = {1716} \ links ({x-27 \ über 18-27} \ cdot {x-31 \ über 18-31} \ rechts) + {3768 } \ left ({x-18 \ over 27-18} \ cdot {x-31 \ over 27-31} \ right) + {4940} \ left ({x-18 \ over 31-18} \ cdot {x -27 \ über 31-27} \ rechts) \\ P (x) & = 42 + 3x + 5x ^ 2 \ end {align}$$

Weil wir das wissen $$$S = P (0)$Erholung $$$S$einfach durchgeführt:

$$

$$\ begin {align} P (0) & = 42 + 3 (0) + 5 (0) ^ 2 \\ P (0) & = 42 \ end {align}$$

Verwenden unsicherer Ganzzahlarithmetik

Obwohl wir die Grundidee von Shamir erfolgreich angewendet haben $$$(k, n)$Wir haben immer noch ein Problem, das wir bisher ignoriert haben. Unsere Polynomfunktion verwendet unsichere Ganzzahlarithmetik. Beachten Sie, dass für jeden zusätzlichen Punkt, den der Angreifer im Diagramm unserer Funktion erhält, weniger Optionen für andere Punkte vorhanden sind. Sie können es mit eigenen Augen sehen, wenn Sie ein Diagramm mit einer Erhöhung der Anzahl von Punkten für eine Polynomfunktion unter Verwendung von Ganzzahlarithmetik erstellen. Dies ist für unser erklärtes Sicherheitsziel kontraproduktiv, da der Angreifer absolut nichts lernen muss, bis er es zumindest getan hat $$$k$Fragmente.

Stellen Sie sich ein Szenario vor, in dem ein Angreifer zwei Punkte erhalten hat, um zu demonstrieren, wie schwach das Schema mit Ganzzahlarithmetik ist $$$(18, 1716), (27.3768)$und kennt öffentliche Informationen, die $$$k = 3$. Aus diesen Informationen kann er ableiten $$$f (x)$gleich zwei und verbinden Sie die bekannten Werte in der Formel $$$x$und $$$f (x)$.

$$

$$\ begin {align} f (x) & = a_0 + a_1x + a_2x ^ 2 + a_3x ^ 3 + ... + a_ {k-1} x ^ {k-1} \\ f (x) & = S + a_1x + a_2x ^ 2 \\ f (18) \ äquiv. 1716 & = S + a_118 + a_218 ^ 2 \\ f (27) \ äquiv. 3768 & = S + a_127 + a_227 ^ 2 \ end {align}$$

Dann kann der Angreifer finden $$$a_1$Zählen $$$f (27) - f (18)$::

$$

$$\ begin {align} 3768 - 1716 & = (S - S) + (27a_1 - 18a_1) + (729a_2 - 324a_2) \\ 2052 & = 9a_1 + 405a_2 \\ 9a_1 & = 2052 - 405a_2 \\ a_1 & = \ frac {2052 - 405a_2} {9} \\ a_1 & = 228 - 45a_2 \ end {align}$$

Da haben wir uns identifiziert $$$a_1, ..., a_ {k-1}$Als zufällig ausgewählte positive ganze Zahlen ist eine begrenzte Anzahl möglich $$$a_2$. Anhand dieser Informationen kann ein Angreifer schließen $$$a_2 \ in [1,2,3,4,5]$, da alles, was mehr als 5 ist, ausreicht $$$a_1$negativ. Dies stellt sich als wahr heraus, wie wir festgestellt haben $$$a_2 = 5$

Dann kann der Angreifer die möglichen Werte berechnen $$$S$ersetzen $$$a_1$in $$$f (18)$::

$$

$$\ begin {align} 1716 & = S + a_118 + a_218 ^ 2 \\ 1716 & = S + 18 \ left (228 - 45a_2 \ right) + a_218 ^ 2 \\ 1716 - S & = 18 \ left (228 - 45a_2 \ rechts) + a_218 ^ 2 \\ -S & = 18 \ links (228 - 45a_2 \ rechts) + a_218 ^ 2 - 1716 \\ -S & = 4104 - 810a_2 + a_218 ^ 2 - 1716 \\ S & = -4104 + 810a_2 - a_218 ^ 2 + 1716 \\ S & = 810a_2 - 324a_2 -2388 \\ S & = 486a_2 - 2388 \ end {align}$$

Mit einer begrenzten Auswahl an Optionen für $$$a_2$Es wird deutlich, wie einfach es ist, die Werte auszuwählen und zu überprüfen $$$S$. Es gibt nur fünf Optionen.

Lösen des Problems mit unsicherer Ganzzahlarithmetik

Um diese Sicherheitsanfälligkeit zu beseitigen, schlägt Shamir vor, modulare Arithmetik zu verwenden und zu ersetzen $$$f (x)$auf $$$f (x) \ mod p$wo $$$p \ in \ mathbb {P}: p> S, p> n$und $$$\ mathbb {P}$- die Menge aller Primzahlen.

Erinnern Sie sich schnell daran, wie modulare Arithmetik funktioniert. Eine Uhr mit Pfeilen ist bereits ein bekanntes Konzept. Sie benutzt Uhren, die sind $$$\ mod 12$. Sobald der Stundenzeiger um zwölf vergeht, kehrt er zu eins zurück. Eine interessante Eigenschaft dieses Systems ist, dass wir durch einfaches Betrachten der Uhr nicht ableiten können, wie viele Umdrehungen der Stundenzeiger gemacht hat. Wenn wir jedoch wissen, dass der Stundenzeiger zwölfmal viermal vergangen ist, können wir die Anzahl der verstrichenen Stunden mithilfe einer einfachen Formel vollständig bestimmen $$$a = mq + r$wo $$$m$Ist unser Teiler (hier $$$m = 12$), $$$q$Ist der Koeffizient (wie oft der Divisor ohne Rest zur ursprünglichen Zahl geht, hier $$$q = 4$) und $$$r$Ist der Rest, der normalerweise das Anrufmodul des Bedieners zurückgibt (hier $$$r = 1,5$) Wenn wir alle diese Werte kennen, können wir die Gleichung für lösen $$$a = 49,5$Wenn wir jedoch den Koeffizienten überspringen, können wir den ursprünglichen Wert niemals wiederherstellen.

Sie können zeigen, wie dies die Sicherheit unserer Schaltung verbessert, indem Sie die Schaltung auf unser vorheriges Beispiel anwenden und verwenden $$$p = 73$. Unsere neue Polynomfunktion $$$f ’(x) = 42 + 3x + 5x ^ 2 \ mod 73$und neue Punkte $$$(18, 37), (27, 45), (31, 49), (35, 67)$. Jetzt können die Schlüsselhalter wieder die Polynominterpolation verwenden, um unsere Funktion wiederherzustellen. Nur dieses Mal müssen die Additions- und Multiplikationsoperationen von einer Modulo-Reduktion begleitet sein $$$p$(zB $$$48 + 93 \ mod 73 = 68$)

Angenommen, der Angreifer hat anhand dieses neuen Beispiels zwei dieser neuen Punkte erkannt. $$$(18, 37), (27, 45)$und öffentliche Informationen $$$k = 3, p = 73$. Dieses Mal zeigt der Angreifer basierend auf allen Informationen, über die er verfügt, die folgenden Funktionen an, wobei $$$\ mathbb {N}$Ist die Menge aller positiven ganzen Zahlen und $$$q_x$repräsentiert den Koeffizienten des Moduls $$$f ’(x)$.

$$

$$\ begin {align} f '(x) & = S + a_1x + a_2x ^ 2 \ mod 73 \\ f' (x) & = S + a_1x + a_2x ^ 2 - 73q_x: q_x \ in \ mathbb {N} \\ f '(18) \ equiv 37 & = S + a_118 + a_218 ^ 2 - 73q_ {18} \\ f' (27) \ equiv 45 & = S + a_127 + a_227 ^ 2 - 73q_ {27} \ end {ausgerichtet}$$

Jetzt findet unser Angreifer wieder $$$a_1$durch Computer $$$f ’(27) - f’ (18)$::

$$

$$\ begin {align} 45 - 37 & = (S - S) + (27a_1 - 18a_1) + (729a_2 - 324a_2) + (-73q_ {27} - (-73q_ {18})) \\ 8 & = 9a_1 + 405a_2 + 73 (q_ {18} - q_ {27}) \\ -9a_1 & = -8 + 405a_2 + 73 (q_ {18} - q_ {27}) \\ 9a_1 & = 8 - 405a_2 - 73 (q_ {18} - q_ {27}) \\ a_1 & = \ frac {8 - 405a_2 - 73 (q_ {18} - q_ {27})} {9} \\ a_1 & = \ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27}) \ end {align}$$

Dann versucht er erneut, sich zurückzuziehen $$$S$ersetzen $$$a_1$in $$$f ’(18)$::

$$

$$\ begin {align} 37 & = S + 18 \ left (\ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27}) \ right) + a_218 ^ 2 - 73q_ {18} \\ -S & = 18 \ left (\ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27}) \ right) + a_218 ^ 2 - 73q_ {18} - 37 \\ S & = -18 \ left (\ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27} ) \ right) - 324a_2 + 73q_ {18} + 37 \\ S & = 486a_2 + 21 + 219q_ {18} - 146q_ {27} \ end {align}$$

Diesmal hat er ein ernstes Problem. Die Formel enthält keine Werte $$$a_2$, $$$q_ {18}$und $$$q_ {27}$. Da es unendlich viele Kombinationen dieser Variablen gibt, können keine zusätzlichen Informationen empfangen werden.

Sicherheitsüberlegungen

Shamirs geheimes Austauschschema bietet Sicherheit in Bezug auf die Informationstheorie . Dies bedeutet, dass die Mathematik selbst gegen einen Angreifer mit unbegrenzter Rechenleistung resistent ist. Die Schaltung enthält jedoch noch einige bekannte Probleme.

Zum Beispiel erzeugt Shamirs Schema keine Testfragmente, dh Menschen können gefälschte Fragmente frei präsentieren und die Wiederherstellung des richtigen Geheimnisses stören. Ein feindlicher Fragmenthalter mit genügend Informationen kann durch Ändern sogar ein anderes Fragment erzeugen $$$S$nach eigenem Ermessen. Dieses Problem wird durch die Verwendung verifizierter geheimer Freigabeschemata wie des Feldman-Schemas gelöst.

Ein weiteres Problem besteht darin, dass die Länge eines Fragments gleich der Länge des entsprechenden Geheimnisses ist, so dass die Länge des Geheimnisses leicht zu bestimmen ist. Dieses Problem wird gelöst, indem das Geheimnis trivial mit beliebigen Zahlen bis zu einer festen Länge gefüllt wird.

Schließlich ist zu beachten, dass unsere Sicherheitsbedenken möglicherweise über den Rahmen des Systems selbst hinausgehen. Bei realen kryptografischen Anwendungen besteht häufig die Gefahr von Angriffen auf Kanäle von Drittanbietern, wenn ein Angreifer versucht, nützliche Informationen aus der Laufzeit der Anwendung, dem Caching, Abstürzen usw. zu extrahieren. Wenn dies ein Problem darstellt, sollten Sie die Verwendung von Sicherheitsvorkehrungen während der Entwicklung, z. B. Funktionen und Suche mit konstanter Laufzeit, sorgfältig prüfen, die Speicherung von Speicher auf der Festplatte verhindern und eine Reihe anderer Dinge berücksichtigen, die den Rahmen dieses Artikels sprengen.

Demo

Diese Seite enthält eine interaktive Demo von Shamirs geheimem Freigabeschema. Die Demonstration wurde auf der Grundlage der ssss-js- Bibliothek durchgeführt, die an sich der JavaScript-Port des beliebten ssss- Programms ist. Beachten Sie, dass Sie große Werte berechnen $$$k$, $$$n$und $$$S$kann einige Zeit dauern.