Mit Beispielen erläuterte Verschlüsselungsalgorithmen

Kryptographie ist im Grunde die Wissenschaft der Verwendung von Codes und Chiffren zum Schutz von Nachrichten.

Bei der Verschlüsselung werden Nachrichten verschlüsselt, damit nur der beabsichtigte Empfänger die Bedeutung der Nachricht verstehen kann. Es handelt sich um eine Zwei-Wege-Funktion (Sie müssen in der Lage sein, das Verwürfeln der Nachricht rückgängig zu machen). Dies dient zum Schutz von Daten während der Übertragung.

Wenn Sie einen allgemeinen Hintergrund zum Unterschied zwischen symmetrischen und asymmetrischen Algorithmen und einen allgemeinen Überblick über die Verschlüsselung suchen, beginnen Sie hier. Dieser Artikel behandelt hauptsächlich zwei der am häufigsten verwendeten Verschlüsselungsalgorithmen.

Als allgemeine Übersicht gab es bei der ersten Erstellung ein großes Problem mit symmetrischen Algorithmen - sie funktionierten nur dann effektiv, wenn beide Parteien das gemeinsame Geheimnis bereits kannten. Wenn dies nicht der Fall war, war es äußerst schwierig, einen Schlüssel sicher auszutauschen, ohne dass ein Dritter ihn fallen ließ.

Und wenn ein Dritter den Schlüssel erhielt, war es für ihn sehr einfach, die Verschlüsselung zu brechen und den Zweck der sicheren Kommunikation zu vereiteln.

Diffie-Hellman löste dieses Problem, indem es Fremden ermöglichte, Informationen über öffentliche Kanäle auszutauschen, die zur Bildung eines gemeinsamen Schlüssels verwendet werden können. Ein gemeinsam genutzter Schlüssel ist schwer zu knacken, selbst wenn die gesamte Kommunikation überwacht wird.

Wie funktioniert Diffie-Hellman?

Diffie-Hellman ist ein sogenanntes Schlüsselaustauschprotokoll. Dies ist die Hauptanwendung für Diffie-Hellman, obwohl sie auch für die Verschlüsselung verwendet werden kann (normalerweise nicht, da es effizienter ist, DH zum Austausch von Schlüsseln zu verwenden und dann zur Datenübertragung auf eine (erheblich schnellere) symmetrische Verschlüsselung umzuschalten ).

Dies funktioniert folgendermaßen:

Grundsätzlich gibt es zwei Parteien, Alice und Bob, die sich auf eine Startfarbe einigen (willkürlich, muss aber jedes Mal anders sein). Sie haben auch eine geheime Farbe, die sie für sich behalten. Diese Farbe wird dann mit der gemeinsamen Farbe gemischt, was zu zwei verschiedenen Farben führt. Sie geben diese Farbe dann an die andere Partei weiter, die sie mit ihrer geheimen Farbe mischt, was zu derselben geheimen Endfarbe führt.

Dies beruht auf der Idee, dass es relativ einfach ist, zwei Farben miteinander zu mischen, aber es ist sehr schwierig, sie zu trennen, um die geheime Farbe zu finden. In der Praxis geschieht dies mit Mathematik.

Zum Beispiel:

  1. Bob und Alice einigen sich auf zwei Zahlen, eine große Primzahl, p = 29 und die Basis g = 5
  2. Jetzt wählt Bob eine Geheimzahl, x (x = 4), und führt Folgendes aus: X = g ^ x% p (in diesem Fall gibt% den Rest an. Zum Beispiel ist 3% 2 3/2, wobei der Rest 1 ist) . X = 5 ^ 4% 29 = 625% 29 = 16
  3. Alice wählt auch eine Geheimzahl, y (y = 8), und macht Folgendes: Y = g ^ y% p. Y = 5 ^ 8% 29 = 390.625% 29 = 24
  4. Bob schickt X an Alice und Alice schickt Y an Bob.
  5. Dann macht Bob Folgendes: K = Y ^ x% p, K = 24 ^ 4% 29 = 331.776% 29 = 16
  6. Alice macht dann folgendes: K = X ^ y% p, K = 16 ^ 8% 29 = 4,294,967,296% 29 = 16

Das Tolle (* möglicherweise magische *) daran ist, dass sowohl Bob als auch Alice die gleiche Nummer K haben und diese nun verwenden können, um heimlich zu sprechen, weil sonst niemand K. kennt.

Die Sicherheit dieses Protokolls basiert auf einigen Dingen:

  1. (Fakt) Es ist relativ einfach, Primzahlen zu generieren, selbst große Primzahlen (wie p).
  2. (Fakt) Modulare Potenzierung ist einfach. Mit anderen Worten, es ist relativ einfach, X = g ^ x% p zu berechnen.
  3. (Annahme basierend auf der aktuellen Rechenleistung und Mathematik) Die modulare Wurzelextraktion ohne die Primfaktoren ist sehr schwierig. Im Wesentlichen ist es sehr schwierig, K zu finden, ohne x und y zu kennen, selbst wenn Sie im Verkehr herumgeschnüffelt haben und p, g, X und Y sehen können.

Unter der Annahme, dass dies korrekt implementiert wurde, ist es relativ einfach, die zum Erstellen des Schlüssels erforderlichen Berechnungen durchzuführen, aber es ist äußerst schwierig und zeitaufwendig, die erforderlichen Berechnungen durchzuführen, um zu versuchen, den Schlüssel durch brutales Erzwingen zu brechen.

Selbst wenn ein Angreifer diesen Schlüssel kompromittieren könnte, ermöglicht Diffie-Hellman ein perfektes Vorwärtsgeheimnis.

Was ist perfektes Vorwärtsgeheimnis?

Dies ist die Idee, dass, wenn Sie die Verschlüsselung knacken, mit der der Server jetzt kommuniziert, dies nicht bedeutet, dass alle Kommunikationen, die der Server jemals ausgeführt hat, gelesen werden können.

Mit anderen Worten, Sie können nur die Kommunikation sehen, die gerade verwendet wird (dh mit diesem geheimen Schlüssel). Da jeder Kommunikationssatz einen anderen geheimen Schlüssel hat, müssten Sie alle separat knacken.

Dies ist möglich, wenn jede Sitzung für jede Sitzung einen anderen, kurzlebigen Schlüssel hat. Da Diffie-Hellman für jede Sitzung immer neue Zufallswerte verwendet (und daher für jede Sitzung neue Schlüssel generiert), wird es als Ephemeral Diffie Hellman (EDH oder DHE) bezeichnet. Viele Cipher Suites verwenden dies, um ein perfektes Vorwärtsgeheimnis zu erreichen.

Da Sie mit Diffie-Hellman Schlüsselmaterial im Klartext austauschen können, ohne sich Gedanken über die Gefährdung des gemeinsamen Geheimnisses machen zu müssen, und die Mathematik für einen Angreifer zu kompliziert ist, um Gewalt anzuwenden, kann der Angreifer den Sitzungsschlüssel nicht ableiten (und selbst wenn dies möglich ist) Unterschiedliche, kurzlebige Schlüssel für jede Sitzung bedeuten, dass sie nur an dieser Sitzung herumschnüffeln konnten (keine in der Vergangenheit oder Zukunft).

Die Weiterleitungsgeheimnis wird bei jedem Diffie-Hellman-Schlüsselaustausch aktiviert, aber nur der kurzlebige Schlüsselaustausch (ein anderer Schlüssel für jede Sitzung) bietet perfekte Vorwärtsgeheimnis.

Hier ist ein Beitrag von Scott Helme, der ausführlicher darüber spricht und erklärt, wie Sie dies auf Ihren Servern aktivieren können.

Was sind die Einschränkungen von Diffie-Hellman?

Die größte Einschränkung von DH ist, dass die Identität nicht überprüft wird. Mit anderen Worten, jeder kann behaupten, Alice oder Bob zu sein, und es gibt keinen eingebauten Mechanismus, um zu überprüfen, ob seine Aussage wahr ist.

Wenn die Implementierung nicht auf sichere Weise durchgeführt wird, kann der Algorithmus außerdem mit ausreichend dedizierten Ressourcen geknackt werden (unwahrscheinlich, aber für akademische Teams oder nationalstaatliche Akteure möglich).

Dies kann beispielsweise der Fall sein, wenn der Zufallszahlengenerator nicht über eine ausreichende Entropie verfügt, um die gewünschte Stärke zu unterstützen. Mit anderen Worten, da computergenerierte Zahlen niemals wirklich zufällig sind, ist der Grad der künstlichen Injektion von Unsicherheit für die Stärke von Bedeutung Ihrer Implementierung.

Darüber hinaus wurde 2015 ein Angriff demonstriert, der zeigte, dass die Gesamtsicherheit von Diffie-Hellman geringer war als erwartet, wenn von vielen Servern zu Beginn des Schlüsselaustauschs dieselben Primzahlen verwendet wurden.

Im Wesentlichen könnte ein Angreifer den Angriff gegen diese Primzahl einfach vorberechnen, wodurch es einfacher wird, Sitzungen für jeden Server zu kompromittieren, der diese Primzahl verwendet hat.

Dies geschah, weil Millionen von Servern dieselben Primzahlen für den Schlüsselaustausch verwendeten. Die Vorberechnung dieser Art von Angriffen erfordert immer noch Ressourcen auf akademischer oder nationaler Ebene und wird wahrscheinlich nicht die überwiegende Mehrheit der Menschen betreffen.

Glücklicherweise gibt es für diejenigen, die sich um nationalstaatliche Angreifer sorgen müssen, einen anderen Weg, um den DH-Schlüsselaustausch mithilfe der elliptischen Kurvenkryptographie (ECDHE) zu erreichen. Dies fällt nicht in den Geltungsbereich dieses Artikels. Wenn Sie jedoch mehr über die Mathematik hinter diesem Austausch erfahren möchten, lesen Sie diesen Artikel.

Weitere Informationen zu den Schwächen von DH finden Sie in diesem Whitepaper und auf dieser Website.

RSA

RSA ist nach den Erstellern benannt - Rivest, Shamir, Adleman - und dient dazu, öffentliche und private Schlüssel zu generieren.

Technisch gesehen gibt es zwei RSA-Algorithmen (einen für digitale Signaturen und einen für asymmetrische Verschlüsselung). Dieser Artikel behandelt den asymmetrischen Verschlüsselungsalgorithmus.

Dies ermöglicht den Schlüsselaustausch: Sie weisen jeder Partei zuerst die öffentlichen / privaten Schlüssel der Transaktion zu, generieren dann einen symmetrischen Schlüssel und schließlich verwenden Sie die öffentlichen / privaten Schlüsselpaare, um den gemeinsam genutzten symmetrischen Schlüssel sicher zu kommunizieren.

Da die asymmetrische Verschlüsselung im Allgemeinen langsamer als die symmetrische Verschlüsselung ist und sich auch nicht skalieren lässt, ist die Verwendung der asymmetrischen Verschlüsselung zum sicheren Austausch symmetrischer Schlüssel weit verbreitet.

Wie funktioniert es?

  1. Wählen Sie 2 sehr große Primzahlen (mindestens 512 Bit oder jeweils 155 Dezimalstellen), x und y (diese Zahlen müssen geheim und zufällig ausgewählt sein).
  2. Finden Sie das Produkt, dh z = x * y
  3. Wählen Sie eine ungerade öffentliche Ganzzahl e zwischen 3 und n - 1 aus, und es gibt keine gemeinsamen Faktoren (außer 1) mit (x-1) (y-1) (daher ist sie relativ prim zu x - 1 und y - 1 ).
  4. Finden Sie das am wenigsten verbreitete Vielfache von x - 1 und y - 1 und nennen Sie es L.
  5. Berechnen Sie den privaten Exponenten d aus x, y und e. de = 1% L. d ist die Umkehrung von e% L (Sie wissen, dass eine Umkehrung existiert, weil e für z - 1 und y - 1 relativ prim ist). Dieses System funktioniert, weil p = (p ^ e) ^ d% z.
  6. Geben Sie (z, e) als öffentlichen Schlüssel und (z, d) als privaten Schlüssel aus.

Wenn Bob nun eine Nachricht an Alice senden möchte, generiert er den Chiffretext (C) aus dem Klartext (P) mit folgender Formel:

C = P ^ e% z

Um diese Nachricht zu entschlüsseln, berechnet Alice Folgendes:

P = C ^ d% z

Die Beziehung zwischen d und e stellt sicher, dass Verschlüsselungs- und Entschlüsselungsfunktionen umgekehrt sind. Dies bedeutet, dass die Entschlüsselungsfunktion die ursprüngliche Nachricht erfolgreich wiederherstellen kann und dass es ziemlich schwierig ist, die ursprüngliche Nachricht ohne den privaten Schlüssel (z, d) (oder die Primfaktoren x und y) wiederherzustellen.

Dies bedeutet auch, dass Sie z und e öffentlich machen können, ohne die Sicherheit des Systems zu beeinträchtigen, und so die Kommunikation mit anderen Personen vereinfachen können, mit denen Sie noch keinen gemeinsamen geheimen Schlüssel haben.

Sie können die Operationen auch in umgekehrter Reihenfolge verwenden, um eine digitale Signatur der Nachricht zu erhalten. Zunächst verwenden Sie die Entschlüsselungsoperation für den Klartext. Zum Beispiel ist s = SIGNATUR (p) = p ^ d% z.

Anschließend kann der Empfänger die digitale Signatur überprüfen, indem er die Verschlüsselungsfunktion anwendet und das Ergebnis mit der Nachricht vergleicht. Zum Beispiel ist m = VERIFY (s) = S ^ e% z.

In diesem Fall ist der Klartext häufig ein Hash der Nachricht. Dies bedeutet, dass Sie die Nachricht (unabhängig von der Länge) mit nur einer Potenzierung signieren können.

Die Sicherheit des Systems basiert auf einigen Dingen:

  1. (Fakt) Es ist relativ einfach, Primzahlen zu generieren, selbst große Primzahlen (wie x und y).
  2. (Fakt) Multiplikation ist einfach. Es ist sehr leicht zu finden, z.
  3. (Annahme basierend auf der aktuellen Mathematik) Faktorisierung ist schwierig. Bei z ist es relativ schwierig, x und y wiederherzustellen. Es ist machbar, aber es dauert eine Weile und es ist teuer.

    Einer Schätzung zufolge würde die Wiederherstellung der Primfaktoren einer 1024-Bit-Zahl auf einem Computer, der 10 Millionen US-Dollar kostet, ein Jahr dauern. Eine Verdoppelung der Größe würde den Arbeitsaufwand exponentiell erhöhen (mehrere Milliarden Mal mehr Arbeit).

    Mit fortschreitender Technologie werden diese Kosten (und der erforderliche Arbeitsaufwand) sinken, aber zu diesem Zeitpunkt ist diese ordnungsgemäß implementierte Art der Verschlüsselung eine unwahrscheinliche Kompromissquelle.

    Im Allgemeinen sind Nationalstaaten die einzigen Hacker mit dieser Art von Geld und Engagement für ein einzelnes Ziel. Wenn es einen einfacheren Weg gibt, ein System zu kompromittieren (siehe unten), ist dies wahrscheinlich eine bessere Option.

4. (Fakt) Modulare Exponentiation ist einfach. Mit anderen Worten, es ist relativ einfach, c = p ^ e% z zu berechnen.

5. (Fakt) Die modulare Wurzelextraktion - Umkehrung des obigen Prozesses - ist einfach, wenn Sie die Primfaktoren haben (wenn Sie z, c, e und die Primfaktoren x und y haben, ist es einfach, p so zu finden, dass c = p ^ e% z).

6. (Annahme basierend auf der aktuellen Rechenleistung und Mathematik) Die modulare Wurzelextraktion ohne die Primfaktoren ist sehr schwierig (wenn Sie z, c, e, aber nicht x und y haben, ist es relativ schwierig, p so zu finden, dass c = p ^ e% z, insbesondere wenn a ausreichend groß ist).

Möchten Sie mehr über die Mathematik von viel klügeren Leuten erfahren? Lesen Sie diesen Artikel.

Großartig, was ist besser?

Dies hängt von Ihrem Anwendungsfall ab. Es gibt einige Unterschiede zwischen den beiden Algorithmen - erstens das perfekte Vorwärtsgeheimnis (PFS), über das wir zuvor im Zusammenhang mit Diffie-Hellman gesprochen haben. Während technisch Sie könnte kurzlebig RSA - Schlüsselpaare generieren, und Perfect Forward Secrecy mit RSA bieten, ist der Rechenaufwand höher viel als für Diffie-Hellman - was bedeutet , dass Diffie-Hellman eine bessere Wahl für SSL / TLS - Implementierungen ist , wo Sie Perfect Forward Secrecy wollen .  

Zwar gibt es einige Leistungsunterschiede zwischen den beiden Algorithmen (in Bezug auf die vom Server geforderte Arbeit), doch sind die Leistungsunterschiede im Allgemeinen nicht groß genug, um bei der Auswahl eines Algorithmus einen Unterschied zu machen.

Stattdessen hängt die Hauptüberlegung bei der Bestimmung, welche besser ist, davon ab, welche für Ihren Anwendungsfall besser unterstützt wird (z. B. bei der Implementierung von SSL möchten Sie Diffie Hellman aufgrund der perfekten Geheimhaltung der Weiterleitung) oder welche populärer oder akzeptierter ist als Standard in der Branche.

Während Diffie-Hellman beispielsweise von der US-Regierung genehmigt und von einer institutionellen Einrichtung unterstützt wurde, wurde der Standard nicht veröffentlicht - während RSA (standardisiert von einer privaten Organisation) einen kostenlosen Standard bereitstellte, was bedeutet, dass RSA bei privaten Organisationen sehr beliebt wurde.

Wenn Sie mehr lesen möchten, finden Sie hier einen großen Thread zu den Unterschieden.

Möchten Sie lernen, wie Hacker kryptografische Angriffe verwenden? Probieren Sie diese Herausforderungen von Cryptopals aus.

Je mehr ich über Kryptographie lerne, desto mehr denke ich, dass Alice und Bob sich wahrscheinlich nur persönlich unterhalten sollten.

- Paul Reinheimer (@preinheimer), 13. März 2017