ASymmetrische Verschlüsselung
🎯 Um was geht es?
Symmetrisch können Informationen sicher verschlüsselt werden. Aber wie kommen beide Seiten zum Schlüssel? Wie kann ein nicht-verschlüsselter Schlüssel sicher ausgetauscht werden?
Asymmetrische Kryptosysteme nutzen zwei Schlüssel. Einen öffentlichen Schlüssel zum Verschlüsseln, den jeder kennen darf, und einen privaten, geheimen Schlüssel mit dem entschlüsselt werden kann.
Jeder Teilnehmer erzeugt sein eigenes Schlüsselpaar (privater und öffentlicher Schlüssel).
Schlüsselaustauschproblem
Wenn man miteinander kommunizieren möchte, dann muss man irgendwie einen Schlüssel sinnvoll austauschen können - und zwar ohne, dass eine Drittperson mit diesen Schlüsseln etwas anfangen kann. Doch wie geht das ?
Auftrag
Man hat zwei Schlüssel zur Verfügung. Alice und Bob kennen jedoch nur ihren eigenen Schlüssel.
Wie könnte man den Inhalt der Truhe nun sicher übertragen?
Inhalt sinnvoll übertragen - Variante 1
Variante 1
Alice verschlüsselt die Truhe (hier ein Brief) mit ihrem Schlüssel.
Bob verschlüsselt die empfangene Nachricht mit seinem Schlüssel.
Alice entschlüsselt wiederum die empfangene Nachricht von Bob mit ihrem Schlüssel und nun wir zuletzt die von Bob verschlüsselte Nachricht wieder an Bob zurückgeschickt. So kann er ganz einfach die Nachricht entschlüsseln und den Brief lesen.
Was ist jedoch ein Problem bei diesem Verfahren? Wie weiss Alice, dass es sich um Bobs Verschlüsselung handelt? Jemand könnte ja unterwegs das Schloss austauschen....
Inhalt sinnvoll übertragen - Variante 2 & 3
Variante 2
Bob könnte Alice das eigene Schloss senden, mit dem Alice anschliessend die Truhe verschliesst.
Problem: Wie weiss Alice, dass es sich um Bobs Schloss handelt?
Variante 3
Alice erhält von einer vertrauenswürdigen dritten Stelle das Schloss, mit welcheem Alice anschliessend die Truhe verschliesst.
Diffie-Hellman-Schlüsselaustausch
Das Diffie-Hellman-Protokoll ermöglicht, dass zwei Kommunikationspartner über eine öffentliche, abhörbare Leitung einen gemeinsamen geheimen Schlüssel in Form einer Zahl vereinbaren können, den nur diese kennen und ein potenzieller Lauscher nicht berechnen kann.
Doch wie geht das?
Bevor es darum geht, wie der Diffie-Hellman-Schlüsselaustausch mit Zahlen funktioniert, überlegen wir uns eine Analogie mit Farben.
Alice und Bob wählen je eine geheime Farbe aus. Dass sie diese Farbe gewählt haben, teilen sie mit niemandem (Alice sagt es auch nicht Bob und umgekehrt!)
Weiter wählen sie jedoch noch zusätzlich eine öffentliche Farbe. Diese Farbe kennt jede:r.
Alice und Bob mischen jeweils ihre zwei Farben (Alice rot und gelb, Bob gelb und blau) und schicken ihr Gemisch dem/der jeweilig anderen.
Wiederum mischen sie nun dieses erhaltene Gemisch mit ihrer jeweilig geheimen Farben und kommen nun auf die gemeinsame Farbe braun.
Diese Farbe ist für niemanden anderen sichtbar/niemand kann aufgrund der Übertragung des grünen/orangen Farbgemisches auf die gemeinsame geheime Farbe braun kommen.
Das Diffie-Hellman-Protokoll läuft sehr ähnlich ab wie die Farbanalogie. Und zwar folgend: Die Idee ist, dass Alice und Bob jeweils eine geheime Primzahl a und b wählen.
Öffentlich wählen Alice und Bob eine grosse Primzahl p und eine natürliche Zahl g, welche kleiner als p sein muss. p und g darf jede:r kennen!
Alice und Bob erzeugen eine geheime Zahl a und b aus der Menge {1, ..., p-1}. a und b sind geheim und werden nicht übertragen!
Alice berechnet ihren öffentlichen Schlüssel A = g^a mod p und schickt A Bob und Bob berechnet seinen öffentlichen Schlüssel B = g^b mod p und schickt B and Alice.
Alice erhält von Bob seinen öffentlichen Schlüssel B und berechnet mit ihrem privaten Schlüssel a die Zahl K = B^a mod p. Bob berechnet mit dem öffentlichen Schlüssel A mit seinem privaten Schlüssel b die Zahl K = A^b mode p.
Alice und Bob haben denselben Schlüssel K berechnet. Das ist nun der gemeinsame Schlüssel, welchen man z.B. in einem symmetrischen Verschlüsselungsverfahren nutzen könnte.
Wichtig ist, dass die Primzahl p gross genug ist! Weil dann ist es für Eve sehr aufwändig, um alle Zahlen zwischen 1 und p-1 auszuprobieren, um auf die geheimen Schlüssel von Alice und Bob zu kommen.
Modulo Berechnung
Modulo-Rechnungen sind nichts anderes als Division mit Rest.
Du kannst dir die Uhr als Analogie vorstellen. Die Uhr hat 12 Zahlen. Wenn ich jedoch über die 12 hinausgehe, z.B. auf 15 Uhr, dann ist das eigentlich dasselbe wie 3 Uhr Nachmittags.
D.h. ich berechne: 15:12 = 1 Rest 3. Das kann man auch aufschreiben als: 15 mod 12 = 3.
Weitere Beispiele:
7 mod 3 = 1, weil 7 : 3 = 2 Rest 1.
8 mod 2 = 0, weil 8 : 2 = 4 Rest 0.
Auftrag
Berechne den gemeinsamen Schlüssel K für Alice und Bob, wenn p = 13, g = 2, a = 5 und b = 8 ist.
Zusatz (schwierig): Wieso ist der berechnete Schlüssel K derselbe für Alice und Bob?
Lösung
A = g^a mod p = 2^5mod 13 = 6. B = g^b mod p = 2^8 mod 13 = 9. K_1 = B^a mod p = 9^5 mod 13 = 3. K_2 = A^b mod p = 6^8 mod 13 = 3
K_1 = K_2 = 3.
Asymmetrische Verschlüsselung
Jede Person besitzt ein eigenes Schlüsselpaar
Geheimer Schlüssel lässt sich aus dem öffentlichen Schlüssel nicht in sinnvoller Zeit berechnen.
Alice verschlüsselt mit dem öffentlichen Schlüssel von Bob die Nachricht.
Bob kann die verschlüsselte Nachricht von Alice mit seinem geheimen Schlüssel entschlüsseln.
Asymmetrisch, weil nicht mehr derselbe Schlüssel für die Ver- und Entschlüsselung genutzt wird.
Auftrag
Zeichne auf, wie die Verschlüsselung funktioniert, wenn ein Dokument an verschiedene Leute versendet wird.
Gibt es Nachteile?
RSA - Asymmetrische Verschlüsselung
Der Schlüssel bei der RSA-Verschlüsselung besteht aus zwei Teilen, einem öffentlichen Teil, der jedem bekannt sein kann, sowie einem privaten Teil, der nur einer Person bekannt ist. Der öffentliche Teil des Schlüssels reicht nicht aus, um eine verschlüsselte Nachricht wieder zu entschlüsseln. Jedoch ist die Entschlüsselung mit Hilfe des privaten Teils des Schlüssels einfach möglich.
Um das RSA-System jedoch zu verstehen, muss man noch eine weitere mathematische Grundlage verstehen.
Wir brauchen um im RSA-Verfahren zu entschlüsseln, das multiplikative Inverse modulo einer Zahl m.
Wie berechnet man das?
Beispiel 1
a = 7, m = 3. Was ist das multiplikative Inverse von 7 modulo 3, also b = 7^(-1) mod 3?
D.h. wir suchen die ganze Zahl b < 3, für die gilt: 1 = 7 * b mod 3.
für b = 1 erhalten wir direkt 7 mod 3 = 1, d.h. b = 1 ist das Inverse!
Beispiel 2
a = 7, m = 4. Was ist das multiplikative Inverse von 7 modulo 4, also b = 7^(-1) mod 4?
Wir suchen die ganze Zahl b < 4, für die gilt: 1 = 7 * b mod 4
7 * 1 mod 4 = 3
7 * 2 mod 4 = 2
7 * 3 mod 4 = 1
d.h. b = 3 ist das Inverse!
Protokoll
Auftrag
Gehe das RSA-Protokoll Schritt für Schritt durch mit den Werten p = 3, q = 11, a = 7, x = 6.
Verfahren kombinieren
In kryptographischen Verfahren, die heutzutage eingesetzt werden, ist das Ziel, die Vorteile beider Verfahren zu nutzen und die Nachteile zu eliminieren. Daher werden zur Verschlüsselung von Daten beide Verfahren eingesetzt.
Das Asymmetrische Verfahren ist viel langsamer als das symmetrische Verfahren, deshalb werden zur Verschlüsselung der Daten symmetrische Verfahren eingesetzt. Der symmetrsiche SChlüssel kann vom Computer gewählt werden, das hat zwei Vorteile:
Der Schlüssel ist zufällig und gleichverteilt im gesamten Schlüsselraum
Er kann für jede Nachricht neu gewählt werden. Somit erhält jede Nachricht einen eigenen Schlüssel. Man spricht daher von einem Sitzungsschlüssel (session key) für die symmetrische Verschlüsselung.
Jedoch werden asymmetrische Verfahren eingesetzt zur Verschlüsselung des symmetrischen Schlüssels.
Asymmetrische Verfahren sind nicht besser als symmetrische!
Symmetrische Verfahren sind nicht unsicher, einzig die Erstellung des Schlüssels und der Schlüsselaustausch sind ein Problem!