Verschlüsselung FOR DUMMIES

Bei der Übertragung von Daten spielen die garantierte Vertraulichkeit (Confidentiality), Unversehrtheit (Integrity) und Authentizität (Authenticity) eine wichtige Rolle.

1. Vertraulichkeit

Um bei einer Datenübertragung über ein nicht vertrauenswürdiges Medium wie das Internet die Vertraulichkeit zu garantieren, müssen die Daten verschlüsselt übertragen werden.

1.1 Symmetrische Verschlüsselung

Bei symmetrischen Verschlüsselungen erfolgt die Entschlüsselung durch den gleichen Schlüssel und mit ähnlich viel Aufwand wie die Verschlüsselung, das Verfahren muss nicht mathematisch sein.
Ohne Kenntnis des Schlüssels ist das Entschlüsseln bei geeigneten Verfahren unmöglich, d. h. diese Verschlüsselung kann sehr sicher sein, das Problem ist der sichere Schlüsselaustausch.

1.1.1 Buch-Verschlüsselung

Sowohl Sender als auch Empfänger haben (mindestens) ein gleiches Buch (gleiche Ausgabe etc.). Man verschlüsselt ein Zeichen, indem man das Auftreten dieses Zeichens in diesem Buch sucht und dann durch Seitenzahl, Zeilennummer und Stelle in dieser Zeile kodiert.

Geheime Nachricht: 135
Geheimes Verfahren: Die Bibel, Ausgabe xyz.
Man sucht ein Auftreten der Ziffer 1, notiert sich diese Seite, die Zeile und die Stelle in dieser Zeile: Seite₁-Zeile₁-Stelle₁ und geht dann für 3 bzw. 5 analog vor und übermittelt dann
Seite₁-Zeile₁-Stelle₁: Seite₂-Zeile₂-Stelle₂: Seite₃-Zeile₃-Stelle₃
Der Empfänger nimmt seine Bibelausgabe, schlägt Seite₁ auf, sucht in Zeile₁ die Stelle₁ und notiert sich die gefundene „1“ usw.
Wenn man das Verfahren nicht kennt bzw. nicht weiss, welches Buch zum Einsatz kommt, ist der Code i. Allg. unmöglich zu knacken, wenn man nicht immer wieder die gleichen Seiten nimmt und durch eine Häufigkeitsanalyse etc. doch Attacken möglich sind.

1.1.2 Modifikation der Caesar-Verschlüsselung

Geheime Nachricht: 135
Öffentliches Verfahren: Addition
Geheimer Schlüssel: 899
Übertragene Zahl: 135 + 899 = 1034
Entschlüsselung: 1034 - 899 = 135.

Selbst wenn man das Verfahren (Addition) kennt, kann man ohne den Schlüssel (899) 1034 nicht zu 135 „entschlüsseln“ (man beachte oben den Hinweis auf Häufigkeitsanalysen etc.), kennt man jedoch den Schlüssel, ist das Entschlüsseln sehr einfach, da die inverse Funktion zur Addition - die Subtraktion - einfach umzusetzen ist.

ROT13 ist eine bekannte Variante, in der die Buchstaben A, B, C, … durch N, O, P, … ersetzt werden.

1.2 Asymmetrische Verschlüsselung

Voraussetzung: Man findet eine Funktion, deren Inverse deutlich mehr Aufwand verlangt oder die gar nicht eindeutig lösbar ist, es gibt aber geheimes „Zusatzwissen“, durch das das Problem (schneller) lösbar wird.

Wenn beim asymmetrischen Verfahren ein Teil des Geheimnisses geteilt werden kann, spricht man von Public-Key-Verschlüsselungsverfahren.

1.2.1 Physische „Verschlüsselung“

Ich verteile Sparschweine, zu deren Schloss nur ich den Schlüssel habe.
Wenn mir jemand die Nachricht „135“ senden möchte, nimmt er eines dieser Sparschweine, steckt einen Zettel mit „135“ hinein und schickt es mir per Post. Ich öffne mit meinem Schlüssel das Sparschwein und kann den Zettel lesen.

1.2.2 Mathematische Verschlüsselung

1.2.2.a Faktorisierung/Division

Geheime Nachricht: 135
Öffentliches Verfahren: Multiplikation mit größtem Faktor
Öffentlicher Schlüssel: 899
Übertragene Zahl: 135 * 31 = 4185
Entschlüsselung: 4185 / Max-Faktor(899).

Die Faktorisierung von 899 dauert (durch Probieren) ziemlich lange, wenn man den geheimen Schlüssel (29) aber kennt, lässt sich der 2. Faktor sehr schnell aus dem öffentlichen Schlüssel berechnen: 899 / 29 = 31 und daraus die geheime Nachricht: 4185 / 31 = 135.

Ein etwas komplexeres Beispiel:

1.2.2.b Potenzierung/Wurzelziehen

Geheime Nachricht: 135
Öffentliches Verfahren: Potenz
Öffentlicher Schlüssel: 899
Übertragene Zahl: 135⁸⁹⁹ = x (~ 1,5 * 10^1.900)
Entschlüsselung: ⁸⁹⁹√x

Diese Entschlüsselung würde sehr viel Zeit in Anspruch nehmen, allerdings gilt (was geheim gehalten wird): 899 = 29 * 31. Und damit gilt ⁸⁹⁹√x = ²⁹√³¹√x.

Wenn man davon ausgeht, dass 2 „kleine“ Wurzeln deutlich schneller zu ziehen sind als eine „große“, kann jemand, der weiss, dass 899 das Produkt von 29 und 31 ist (geheimer Schlüssel; Primfaktorenzerlegung sehr großer Zahlen ist sehr aufwendig), das Problem im Vergleich relativ schnell lösen.

Diese Beispiele sind jetzt rein fiktiv, da die zu übermittelnden Zahlen bei entsprechend großen Primzahlen dann unglaublich groß würden und es nicht mehr möglich wäre, damit zu rechnen.
Tatsächlich zum Einsatz kommt aber u. a. ein sehr ähnliches Verfahren, wobei aber mit der Modulo-Funktion gearbeitet wird, wodurch die Werte, mit denen gearbeitet wird, viel kleiner bleiben (RSA-Verfahren).

Problem

Wenn es für das Hauptproblem (im Beispiel 1.2.1 das Öffnen des Sparschweins, in Beispiel 1.2.2.b die Lösung von ^y√x) eine neue, schnellere Lösungsmethode (z. B. durch schnellere Technologie) oder Seitenkanalangriffe gibt (z. B. das Sparschwein zu zerschlagen und gar nicht zu versuchen das Schloss zu knacken), kann jeder, der diese neue Methode kennt bzw. Zugriff auf diese Technologie hat, die geheime Botschaft schnell entschlüsseln.
Auch wenn es eine neue schnelle Methode für das „Nebenproblem“ (in Beispiel 1.2.1 die Produktion eines passenden Schlüssels, in den Beispielen 1.2.2.a und b die Primfaktorenzerlegung durch einen neuen Algorithmus oder viel leistungsfähigere Computer) gibt, kann ein Angreifer die verschlüsselte Zahl eventuell ähnlich schnell entschlüsseln wie der Besitzer des Wissens, in welche 2 Primzahlen sich der öffentliche Schlüssel faktorisieren lässt.

Die Sicherheit der Methoden in den Beispielen 1.2.2.a und b hängt also auch von der Leistungsfähigkeit von Computern (Stichwort Quantencomputer) und vom Stand des (mathematischen) Wissens ab!

1.3 Hybride Verschlüsselung

Diese kombiniert die beiden Methoden und verwendet die asymmetrische (langsame) Verschlüsselung zum Austausch eines symmetrischen Schlüssels. Danach kommt eine (schnelle) symmetrische Verschlüsselung zum Einsatz, was wichtig ist, wenn sehr viele Daten sicher und schnell übertragen werden sollen.
Ein Beispiel eines häufig eingesetzten hybriden Verfahrens ist SSL bzw. TLS, das z. B. im Web (https) zum Einsatz kommt.

Problem

Wenn die Entschlüsselung nicht zeitkritisch ist und man den Datenverkehr aufzeichnet, kann man mit genug Zeit und Aufwand die asymmetrische Verschlüsselung knacken und mit dem dann erhaltenen symmetrischen Schlüssel die gesamte Kommunikation dechiffrieren. Aber auch dafür gibt es bereits Lösungen, bei denen der Schlüssel für die symmetrische Verschlüsselung nicht übertragen wird (PFS).

2. Integrität

Das asymmetrische Verfahren kann auch verwendet werden um eine Nachricht zu signieren (d. h. seine Unversehrtheit zu garantieren):
Dazu wird aus der Nachricht ein „Fingerabdruck“ (kollissionsfreier Hash-Wert) erstellt, dieser wird dann mit dem privaten geheimen Schlüssel verschlüsselt (eigentlich ja entschlüsselt) und zusammen mit der Nachricht übertragen. Zur Verfizierung entschlüsselt (eigentlich verschlüsselt) der Empfänger dann die Signatur mit dem öffentlichen Schlüssel des Absenders und vergleicht das Ergebnis mit dem selbst errechneten Fingerabdruck der Nachricht. Wenn das Ergebnis übereinstimmt, wurde die Nachricht nicht verändert.

Wenn wir uns am fiktiven Beispiel 1.2.2.b orientieren, würden wir zuerst den zu übertragenden Text nach einem definierten Verfahren (z. B. SHA-256) in einen Fingerabdruck umwandeln. Um beim Beispiel zu bleiben:
Der SHA-256-Fingerabdruck für „135“ ist die Hexadezimalzahl 13671077b66a29874a2578b5240319092ef2a1043228e433e9b006b5e53e7513. Dezimal ist das ca. 10³⁵. Der private Schlüssel des Absenders sei 17 * 37 = 629. Wir ziehen daher die 37. und dann die 17. Wurzel (= geheimer Schlüssel) und bekommen als Signatur ca. ¹⁸√10. Wir übermitteln dann diese Signatur zusammen mit dem Originaltext (135).
Der Empfänger nimmt diese Signatur und wendet den öffentlichen Schlüssel an (potenziert die Signatur also mit 629), das Ergebnis ist ca. (¹⁸√10)⁶²⁹ = 10^629/18 ~ 10³⁵.
Wenn der Empfänger nun selbst den Fingerabdruck der Nachricht erstellt und mit diesem Wert vergleicht, sieht er, ob die Nachricht verändert wurde oder nicht.

Problem

Beim Verfahren zur Erzeugung des Fingerabdrucks darf es nicht möglich sein die Ausgangsdatei so zu verändern, dass derselbe Fingerabdruck (eine „Kollission“) entsteht - daher kommt auch das lange verwendete Verfahren SHA-1 nicht mehr zum Einsatz.

3. Vertraulichkeit und Integrität

Wenn man nun die Vertraulichkeit mit der Integrität kombinieren möchte, signiert man die Nachricht mit dem eigenen privaten Schlüsel und verschlüsselt dann das Ergebnis mit dem öffentlichen Schlüssel des Empängers. Der Empfänger entschlüsselt die Nachricht dann mit seinem privaten Schlüssel und überprüft die Datei dann, indem er die Signatur mit dem öffentlichen Schlüssel des Absenders entschlüsselt. Ein moderner E-Mail-Client macht das ganz automatisch und quasi unsichtbar, er zeigt nur an, ob die E-Mail gültig signiert und ob sie verschlüsselt ist.

Beispiel für 1.2.2.b:
Öffentlicher Schlüssel des Absenders: 629.
Öffentlicher Schlüssel des Empfängers: 899.

Absender (geheim: 629 = 17 * 37):
Verschlüsselt die Nachricht: 135⁸⁹⁹ ~ 1,5 * 10¹⁹⁰⁰
Berechnet die Signatur: SHA-256(135) ~ 10³⁵.
Entschlüsselt die Signatur: ¹⁷√³⁷√10³⁵ ~ ¹⁸√10

Empfänger (geheim: 899 = 29 * 31):
Entschlüsselt die Nachricht: ²⁹√³¹√1,5 * 10¹⁹⁰⁰ = 135
Verschlüsselt die (entschlüsselt übermittelte) Signatur: (¹⁸√10)⁶²⁹ ~ 10³⁵.
Berechnet die Signatur der entschlüsselten Nachricht: SHA-256(135) ~ 10³⁵
und vergleicht die beiden Werte.

4. Authentizität

Kann man den öffentlichen Schlüssel in einem (vertrauenswürdigen) Verzeichnisdienst einer Person zuordnen oder ist der Schlüssel selbst durch einen vertrauenswürdigen Dienst (Certificate Authorityi) signiert, ist auch die Authentizität der Nachricht gesichert.

5. Literatur

Auch für Laien interessant: Geheime Botschaften von Simon Singh.
Cryptography For Dummies von Chey Cobb.

6. Rechenbeispiel

Das Verfahren sei das aus Beispiel 1.2.2.b, aber mit noch händisch berechenbaren Zahlen:
Mein öffentlicher Schlüssel sei 6, Ihr geheimer Schlüssel sei 10 = 2 * 5.
Die geheime Nachricht sei 7 und der Fingerabdruck dieser Nachricht sei e6a9.

Wie schaut dann die verschlüsselte Nachricht aus und wie die Signatur, wenn Sie mir diese Nachricht verschlüsselt und signiert schicken wollen?

Verschlüsselte Nachricht: Signatur: