Verschlüsselung
Wie kann man Daten so codieren, dass nur Eingeweihte die repräsentierte Information verstehen können, nicht aber Aussenstehende?
SymmetrischeVerschlüsselung.pptx
Vigenère knacken
Manchmal möchte man Informationen nur mit bestimmten Personen teilen, beispielsweise soll nur ein Mitschüler den Text auf einem Zettelchen verstehen, nicht aber der Lehrer, der das Zettelchen vielleicht abfängt. Seit langem gibt es daher die Idee, eine Nachricht so zu verschlüsseln, dass nur der intendierte Empfänger sie entziffern kann. Im Kontext von Digitaltechnologien ist das Verschlüsseln von Inhalten sehr wichtig, denn nur wenn Passwörter u.ä. verschlüsselt übertragen werden, ist die Vertraulichkeit dieser kritischen Information gewährleistet. Neben Textnachrichten lassen sich auch andere Arten von (digitalisierten) Information verschlüsseln: Sprachnachrichten, Filme oder der Quellcode von Programmen.
Eine Klartext-Nachricht in eine verschlüsselte Form zu übersetzen (und später wieder zu entschlüsseln) ist eine typische Aufgabe für eine Codierung:
Codierung
Um sehr einfache Informationen zu codieren (z.B. den Wahrheitsgehalt einer logischen Aussage) braucht es ggf. nur ein Bit. Für komplexere Informationen (z.B. die genaue Angabe einer Farbe) werden mehrere Bit kombiniert. Mehrere Bit bzw. eine Bit-Sequenz repräsentieren also einen Sachverhalt (einen Zustand, eine Information) mithilfe eines zugrundeliegenden Systems – der Codierung. Um von den Daten auf die repräsentierten Informationen schliessen zu können, muss man die Art der Codierung kennen.
Wenn man es sehr genau nimmt, ist die obenstehende Beschreibung übrigens nicht ganz korrekt. Das liegt daran, dass es «Information» in reiner Form nicht gibt. Eigentlich übersetzt eine Codierung also nur Information von einer Repräsentationsform (korrekter: Zeichensystem) in eine andere, bspw. Licht bestimmter Wellenlängen in binäre Zahlen und wieder zurück (Sensor einer Kamera → Grafikdatei → Bildschirm).
Codierungen gelten immer für eine gewisse Menge an Informationen, also z.B. alle Buchstaben, eine bestimmte Anzahl verschiedener Farben, o.ä.
Analogie
4; IV; 100; llll; vier; four sind verschiedene (nicht digitale) Codierungen für denselben Sachverhalt – und im gewählten System liesse sich auch jeder andere Zahlenwert ausdrücken.
Der Zweck der Verschlüsselung von Nachrichten im Internet ist natürlich der Schutz der enthaltenen Information vor unbefugtem Zugriff, genauer: Vertraulichkeit, Integrität, Authentizität und Verbindlichkeit.
Welche Bedeutung haben diese Anforderungen an kryptographische Verfahren?
- Vertraulichkeit: Es soll sichergestellt sein, dass wirklich nur der die Nachricht lesen kann für den diese auch bestimmt ist.
- Integrität: Der Empfänger soll feststellen können, ob die Nachricht nach ihrer Erzeugung verändert wurde.
- Authentizität: Der Verfasser einer Nachricht soll identifizierbar sein, bzw. der Empfänger soll nachprüfen können, wer der Verfasser ist.
- Verbindlichkeit: Der Verfasser soll nicht abstreiten können, dass er der Verfasser der Nachricht ist.
Um diese Ziele möglichst gut zu erfüllen, werden sogenannte kryptographische Verfahren eingesetzt, bei denen man zwischen den symmetrischen und den asymmetrischen Verschlüsselungsverfahren unterscheidet.
1. Symmetrische Verschlüsselungsverfahren
Symmetrische Verschlüsselung
Unter dem Begriff Symmetrische Verschlüsselung fasst man alle Kryptosysteme zusammen, bei welchen zur Ver- und Entschlüsselung derselbe Schlüssel verwendet wird.
Der Sender verschlüsselt also die Nachricht mit dem gemeinsamen Schlüssel. Der Geheimtext wird anschliessend übermittelt und der Empfänger dekodiert diesen mit demselben Schlüssel. Das bedeutet auch, dass dieser Schlüssel ebenfalls übermittelt, aber unbedingt geheim bleiben muss. Darin liegt auch ein Hauptproblem: Sender und Empfänger müssen sich auf einen gemeinsamen Schlüssel einigen, ohne dass ein Dritter auf den Schlüssel zugreifen kann.
Analogie
Alice und Bob möchten geheime Nachrichten austauschen. Alice kauft also eine Kiste mit Schloss, nun kann sie eine geheime Nachricht in die Kiste legen, die Kiste abschliessen und an Bob schicken. Damit Bob die Nachricht lesen kann, muss er entweder von vornherein eine Kopie des Schlüssels haben, oder der Schlüssel muss ebenfalls an ihn geschickt werden – nur so kann er die Kiste öffnen.
Symmetrische Verschlüsselungsverfahren haben eine lange Tradition, angefangen von den monoalphabetischen Verfahren römischer Feldherren bis hin zu zunehmend komplexeren polyalphabetischen Codierungen, deren Höhe- wie auch Endpunkt man in der Enigma-Maschine sehen kann, die im Zweiten Weltkrieg von Deutschland zur Verschlüsselung militärischer Kommunikation eingesetzt wurde.
Geschichtlicher Rückblick
- 600 v. Chr. benutzen hebräische Gelehrte einfache Zeichenaustauschalgorithmen.
- 405 v. Chr.: Eine verschlüsselte Botschaft auf der Innenseite eines Gürtels wird lesbar, wenn man den Gürtel um einen Holzstab wickelt.
- 50 v. Chr. entwickelt der römische Feldherr Julius Cäsar das heute als Caesar-Verschlüsselung bekannte Verfahren.
- Im 16. Jahrhundert entwickelt Blaise de Vigenère die nach ihm benannte polyalphabetische Verschlüsselungstechnik. Sie wurde für unknackbar gehalten, bis Charles Babbage 1854 eben doch einen Weg zur Entzifferung fand.
- Ende des 19. Jahrhunderts werden durch die Einführung des Telegrafen neue Überlegungen in der Kryptographie angeregt. Durch das relativ einfache Abhören von Telegrafen wächst auch das Bedürfnis nach einer verschlüsselten Übertragung.
- Während des 2. Weltkriegs gilt die Enigma zunächst als absolut sichere Chiffriermaschine, wird jedoch von polnischen und englischen Kryptoanalytikern (insb. Alan Turing) geknackt – unter Zuhilfenahme eines eigens dafür entwickelten Vorläufers moderner Computer.
Einen Endpunkt erfuhren symmetrische Verschlüsselungsverfahren, nachdem der Enigma-Code geknackt wurde; spätestens mit dem Aufkommen von Computern in jener Zeit wurde die Angreifbarkeit aller symmetrischen Verfahren offensichtlich:
Nicht nur müssen sich Sender und Empfänger auf einen gemeinsamen Schlüssel einigen (der keinesfalls in die Hände eines Lauschers gelangen darf), symmetrische Verschlüsselungsverfahren sind darüber hinaus auch anfällig für statistische Methoden, mit denen eine verschlüsselte Nachricht ggf. auch ohne Kenntnis des Schlüssels in Klartext zurückübersetzt werden kann.
Häufigkeitsanalyse
Die Häufigkeitsanalyse ist eine der Methoden, die statistische Eigenschaften von verschlüsselten Texten ausnutzen, um Rückschlüsse auf die unverschlüsselte Nachricht zu ziehen.
In jeder Sprache kommen die einzelnen Buchstaben in einem ausreichend langen Text in einer für die Sprache charakteristischen Häufigkeit vor. Im Deutschen ist der am häufigsten vorkommende Buchstabe das E (etwa 17%), gefolgt von N (ca. 10%), I und R (je ca. 8%). Ersetzt man also in einer verschlüsselten Nachricht das am häufigsten vorkommende Zeichen mit E, und die nächsthäufigsten mit N, I und R, dann hat man gute Chance, schon ca. die Hälfte des Textes übersetzt zu haben.
Häufigkeitsverteilung der Buchstaben im Deutschen
Natürlich gibt es noch weitere ähnliche Ansätze:
- Der erste Buchstabe in drei-Zeichen-Worten ist wahrscheinlich ein D (der, die, das, den,…).
- Ein Zeichen, das fast nur in Begleitung eines bestimmten anderen Zeichens vorkommt, ist ziemlich sicher ein C (gefolgt von H).
- Ein Zeichen, das nur in Begleitung eines bestimmten anderen Zeichens vorkommt, ist sehr sicher ein Q (gefolgt von U).
- Das E ist am Wortende sehr häufig gefolgt von N (üblichster Plural), innerhalb von Wörtern oft in Kombination mit I (ei, ie).
- Nur wenige Buchstaben können doppelt vorkommen, im Deutschen verdoppelt man zumeist N, M oder T.
- Vokale und Konsonanten können zumeist aufgrund ihrer Verteilung in Wörtern voneinander unterschieden werden.
2. Asymmetrische Verschlüsselungsverfahren
Erst in den 1970er-Jahren wurde ein Verfahren erfunden, das selbst mit modernsten Computern nicht zu knacken ist – obwohl jeder nachlesen kann, wie das Verfahren funktioniert. Mit dem Konzept der Asymmetrischen Verschlüsselungsverfahren (Public-Key-Verfahren) wurde das Problem des «geheimen» Schlüsselaustausches gelöst – das ist nämlich bei diesem Verfahren gar nicht nötig – und auch die statistischen Methoden funktionieren nicht, weil nicht zeichenweise übersetzt wird.
Asymmetrische Verschlüsselung
Bei einer Asymmetrischen Verschlüsselung gibt es zwei verschiedene, aber zusammengehörige Schlüssel:
- Der public key kann nur für die Verschlüsselung verwendet werden, deswegen muss er auch nicht geheim sein
- Der private key wird für die Entschlüsselung verwendet, er bleibt geheim, muss aber nie an den Kommunikationspartner geschickt werden
Grob gesagt geht der Ablauf so: Wer verschlüsselte Nachrichten empfangen will, rechnet sich ein Schlüsselpaar aus – einen öffentlichen (Public Key) und einen privaten (Privat Key). Den Public Key kann er nun an einem öffentlich zugänglichen Ort (z.B. Server) hinterlegen oder auf Anfrage herausgeben. Der Sender benutzt diesen Public Key, um mithilfe einer einfachen Rechnung eine Bitsequenz (=Klartext) in eine verschlüsselte Sequenz zu übersetzen – dann kann er diese Geheimnachricht an den Empfänger schicken. Zum Entschlüsseln muss jetzt die einfache Rechnung von oben rückgängig gemacht werden – das geht aber nur mit Kenntnis des zugehörigen Privat Key. Diesen kennt natürlich der Urheber des Schlüsselpaars, sonst aber niemand, denn der Privat Key musste ja nie an irgendwen übermittelt werden.
Analogie
Bob möchte, dass man ihm geheime Nachrichten schicken kann. Er kauft ein Vorhängeschloss (Public Key) und hinterlegt dieses Schloss an einem öffentlichen Ort. Alice legt ihre Nachricht in eine Kiste, verschliesst diese mit dem öffentlichen Schloss von Bob, und schickt die verschlossene Kiste an Bob. Nur Bob kann diese Kiste öffnen, denn nur er hat den entsprechenden Schlüssel (Private Key).
Varianten der Asymmetrischen Verschlüsselung (z.B. RSA, PGP) sind heutzutage der Standard für jegliche Art von digitaler Kryptografie, sei das die sichere Passwortübertragung, die Ende-zu-Ende Verschlüsselung von E-Mails oder WhatsApp-Nachrichten oder auch die Verschlüsselung einer bestimmten Datei, oder gleich der ganzen Festplatte.
Sinn macht ein solches Verfahren natürlich nur, wenn es unmöglich ist, von Public Key (oder der Geheimnachricht selbst) auf den Private Key zu schliessen. Um dies zu gewährleisten, macht man sich eine Kombination von zwei Einwegfunktionen (üblicherweise Primfaktoren und Modulo-Rechnung) zunutze.
Einwegfunktion
Unter einer Einwegfunktion versteht man in der Informatik eine mathematische Funktion, die ressourcensparend zu berechnen, aber sehr schwer umzukehren ist.
Das «sehr schwer» im obigen Satz bedeutet genau dasselbe wie in der folgenden Aussage: «Ein gutes Passwort ist nicht unmöglich zu erraten, aber sehr schwer.» Das Problem besteht in beiden Fällen nicht darin, dass der Lösungsweg (=Algorithmus) unbekannt ist, sondern darin, dass das Finden/Berechnen der Lösung schlicht zu lange braucht. Wie lange genau, hängt von der Rechengeschwindigkeit ab – das ist aber wenig relevant, weil weder Millionen noch Milliarden von Jahren als angemessene Zeit für das Erraten eines Passworts oder für das Knacken einer Verschlüsselung gelten können.
Analogie
Analog zu einer mathematischen Einwegfunktion können wir uns auch ein Kuchenrezept vorstellen. Es ist nahezu unmöglich vom Kuchen zurück auf alle einzelnen Zutaten und deren exakte Mengen zu schliessen.
Trotz aufwendiger Analysen wurde es bislang nicht geschafft, bekannte Produkte wie Coca Cola oder auch die Big Mac Sauce zu kopieren.
Aufgabe
Sie können mithilfe des RSA Interactive die für Asymmetrische Verschlüsselung nötigen Berechnungen nachvollziehen. Das zugehörige Arbeitsblatt AB_RSA_Interactive.pdf erklärt den Ablauf zum Austausch einer so verschlüsselten Nachricht mit einem Partner.
Aufgabe
Nach heutigem Wissen können die üblichen asymmetrischen Verschlüsselungsverfahren als sicher gelten – vorausgesetzt, der Schlüssel ist ausreichend lang (ein Rechenbeispiel). Und das, obwohl allgemein bekannt ist, wie man Sie knacken könnte: Durch die – ausreichend schnelle – Zerlegung einer grossen Zahl (>600 Stellen) in ihre zwei Primfaktoren (aus denen sich der private Schlüssel ableiten lässt).
Details zur Sicherheit asymmetrischer Verschlüsselung (in Zukunft)
Es ist nicht klar, ob die heutigen kryptologischen Standards auch in Zukunft noch sicher sein werden. Einfach nur mit schnelleren Computern wird die Primfaktorisierung mit den bisher bekannten Algorithmen auch in Zukunft nicht in nützlicher Zeit zu machen sein, aber zukünftige Möglichkeiten könnten asymmetrische Schlüssel vielleicht doch entschlüsseln.
- Es könnte ein schnellerer Algorithmus erfunden werden. Das ist zwar sehr unwahrscheinlich, aber genau genommen ist nicht bewiesen, dass es nicht geht.
- Quantencomputer arbeiten ganz anders als herkömmliche CPUs. Zumindest in der Theorie wurde bereits gezeigt, dass ein Quantencomputer die Primfaktorisierung sehr schnell lösen kann. Ob und wann es einen wirklich funktionierenden Quantencomputer (mit ausreichend vielen Q-Bits) geben wird, ist unklar – aber in Punkto Sicherheit wäre dessen Umsetzung ein echtes Problem.
- Geheimdienste arbeiten an der Schwächung kryptologischer Standards. Konkret weiss man das von der NSA: Diese Behörde hat erwiesenermassen auf verschiedenen Wegen versucht, auf die Hersteller von Computerchips Einfluss zu nehmen. Ein Ziel war die Manipulation der Chips, die hinter der Generierung von Zufallszahlen stecken. So ergeben sich gewisse Muster in den eben nicht ganz zufällig gewählten Primfaktoren, auf denen ein Schlüsselpaar basiert. Wer das Muster kennt, hat einen Vorteil beim Erraten der Primfaktoren und schafft es so evtl. doch in nützlicher Zeit.
Allerdings muss man nicht unbedingt der Urheber der Manipulation sein, um das Muster zu kennen – dieses lässt sich auch aus einer Analyse von manipulierten Zufallsgeneratoren ableiten. Wie auch andere digitale Hintertüren, die sich die NSA schafft oder offen hält, kann also auch diese von anderen Akteuren benutzt werden.