Asymmetrische Verschlüsselung

Inhalt:

• Das "Kreuz" mit der Symmetrie
• Die Idee zur Lösung
• Mäßig elegante Lösung des Problems der Schlüsselübergabe
• Elegante Lösung des Problems der Schlüsselübergabe
• Das RSA-Verfahren

---

Das "Kreuz" mit der Symmetrie

Denken wir noch einmal zurück an das symmetrische Verschlüsselungsverfahren. Dieses war so aufgebaut, dass zwei Personen, die miteinander kommunizieren möchten, einen gemeinsamen geheimen Schlüssel zum Chiffrieren wie auch zum Dechiffrieren verwenden. Das ist im Prinzip vergleichbar mit der Zahlenkombination eines Fahrradschlosses. Nur wer diese kennt, kann losfahren. Oder um wieder mit Alice und Bob zu sprechen: der Text der Nachricht ist "eingeschlossen", nur Alice und Bob haben den richtigen Schlüssel für das Schloss.

Der Erfolg eines symmetrischen Verfahrens hängt also maßgeblich von der Geheimhaltung des Schlüssels ab. Sind bloß zwei Personen - Alice und Bob - am Austausch von Nachrichten beteiligt, ist die sichere Schlüsselübergabe vielleicht noch zu bewerkstelligen (obwohl auch das problemtisch sein kann, wenn wir annehmen, dass Alice in Europa und Bob in Australien lebt), sind jedoch viele Personen am Kommunikationsprozess beteiligt, ergeben sich gewisse Probleme.
Denken wir etwa an eine Mailingliste mit vielen Mitgliedern, dann stellt sich die Frage, wie der eine und einzige Schlüssel an alle Personen ohne beträchtlichem Aufwand verteilt werden kann? Oder, stellen wir uns eine Situation vor, in der n (n sei eine hohe Zahl) Personen miteinander in Kontakt stehen (z. B. über Email), und jede möchte mit jeder geheim kommunizieren. Wie viele Schlüssel S_n werden benötigt?

Das sind bei nur n=100 Personen bereits S₁₀₀=4950 Schlüssel. Für eine sichere Email-Kommunikation im Internet scheint dies keine praktikable Lösung. Man benötigt zunächst sehr viele Schlüssel, die in Folge auch sicher verteilt werden müssen.

Die Problematik der Schlüsselverteilung hat den KryptographInnen schon immer einiges an Kopfzerbrechen verursacht. Während des 2. Weltkrieges etwa stellte die Übergabe von umfangreichen Schlüsselbüchern an U-Boote, die häufig lange Zeit im Einsatz waren, ein logistisches Problem dar. Wie sicher die Verschlüsselung auch gewesen sein mag, die Übergabe der Schlüssel war ein großer Unsicherheitsfaktor. In der Nachkriegszeit widmeten sich die KryptographInnen vorrangig dem Problem der Schlüsselübergabe, da die Schlüsselverwaltung vielen Staaten Unsummen an Geld kostete. Damals dachte man auch, dass Verschlüsselung einzig und allein Staaten vorbehalten sein kann und sich ein Unternehmen niemals die Verwaltung der Schlüssel wird leisten können.

Die Idee zur Lösung

Das ganze Problem der Schlüsselverteilung ist eine klassische Paradoxie. Wenn ein Mensch einem anderen eine geheime Nachricht am Telefon übermitteln will, muss er sie verschlüsseln. Dazu braucht er einen Schlüssel, der selbst wiederum ein Geheimnis ist, und so ergibt sich das Problem, diesen geheimen Schlüssel dem Empfänger zu übermitteln, damit die geheime Botschaft gesendet werden kann. Kurz, wenn zwei Menschen sich ein Geheimnis (eine verschlüsselte Botschaft) mitteilen wollen, müssen sie sich zuvor bereits ein Geheimnis (den Schlüssel) mitgeteilt haben.
Simon Singh, Geheime Botschaften, 1999

Mitte der 70er Jahre des vergangenen Jahrhunderts entwickelte eine Gruppe von Wissenschaftlern ein Verfahren, welches das Problem mit der Schlüsselverteilung löste. Aus heutiger Sicht ist dies sicherlich die herausragendste Leistung auf dem Gebiet der Kryptographie seit der Erfindung der monoalphabetischen Verschlüsselung (vor ca. 2000 Jahren).

Stellen wir uns folgende bekannnte Situation vor: Alice will Bob eine geheime Nachricht schicken. Sie steckt ihre Nachricht in eine kleine Kiste und verschließt diese mit einem Vorhängeschloss, zu dem nur sie den Schlüssel besitzt. Daraufhin schickt sie die Kiste an Bob, der sie auf Grund des fehlenden Schlüssels natürlich nicht öffnen kann. Bob jedoch verschließt die Kiste mit einem zweiten Vorhängeschloss, zum dem nur er den Schlüssel besitzt und schickt die Kiste zurück an Alice. Alice entfernt nun ihr Vorhängeschloss und schickt die nach wie vor mit Bobs Schloss versperrte Kiste wieder an Bob. Dieser kann die Kiste nun aufsperren und Alices Nachricht lesen.
Auf diesem Weg wurde also eine geheime Nachricht ausgetauscht, ohne dass zuvor ein Schlüsseltausch erforderlich gewesen wäre.

Erzählen wir dieselbe kleine Geschichte unter der Perspektive der Verschlüsselung:
Alice verschlüsselt die Nachricht mit ihrem Schlüssel und sendet sie an Bob. Dieser verschlüsselt die Nachricht nun mit seinem Schlüssel und schickt sie zurück an Alice, welche ihre eigene Verschlüsselung entfernt und die Nachricht wieder an Bob zurück sendet. Bob entschlüsselt die Nachricht und kann sie nicht lesen! :-(

Warum nicht? Das Problem liegt in der Reihenfolge von Ver- und Entschlüsselung. Die letzte Verschlüsselung muss die erste sein, die wieder gelöst wird. Bob nimmt die letzte Verschlüsselung vor, jedoch ist es Alice, die als erste ihre Verschlüsselung löst.

Übung:
Versuche an Hand einer monoalphabetischen Verschlüsselung die Bedeutung der richtigen Reihenfolge der Ver- und Entschlüsselung zu prüfen. Nehmen wir an, Alice hat ihren eigenen Schlüssel und Bob ebenfalls seinen eigenen. Alice verschlüsselt als erste, dann verschlüsselt Bob. Beobachte, was passiert wenn Alice zuerst entschlüsselt und dann erst Bob. Prüfe, ob Du mit der richtigen Reihenfolge wieder den ursprünglichen Klartext erhältst.

• Klartext: ASTERIX
• Alices Schlüssel:

  

• Bobs Schlüssel:

  

Reihenfolge I:

• Von Alice verschlüsselt
• Von Bob verschlüsselt
• Von Alice entschlüsselt
• Von Bob entschlüsselt

Reihenfolge II:

• Von Alice verschlüsselt
• Von Bob verschlüsselt
• Von Bob entschlüsselt
• Von Alice entschlüsselt

Du kannst Papier und Bleistift verwenden!

Obwohl wir nun gesehen haben, dass sich die kleine Geschichte mit den Vorhängeschlössern nicht in die Welt der Kryptographie transferieren läßt, so hat dieses Gedankenexperiment doch die Wissenschaftler in den 70er Jahren ermutigt, sich weiterhin dem Problem der Schlüsselverteilung zu widmen. Es waren insbesondere Whitfield Diffie, Martin Hellman und Ralph Merkle in den USA, die mit aller Kraft nach Alternativen zum mühseligen und unsicheren Transport von Schlüsseln über weite Entfernungen suchten. Sie interessierten sich zunehmend für "nicht-umkehrbare" mathematische Funktionen, mit deren Hilfe der Klartext verschlüsselt wird, es jedoch auf Grund der "nicht-Umkehrbarkeit" nicht möglich ist, den verschlüsselten Text wieder zu entschlüsseln. Bei diesem Vorgehen wird der Klartext zunächst in eine Zahl umgewandelt (vgl. ASCII Tabellen), die dann als Eingabe in die "nicht-umkehrbare" Funktion dient. Wir wollen die "nicht-umkehrbaren" Funktionen als Einwegfunktionen bezeichnen. Auf Grund der "nicht-Symmetrie" der Einwegfunktionen nennt man dieses Verschlüsselungsverfahren asymmetrisches Verschlüsselungsverfahren .

Mäßig elegante Lösung des Problems der Schlüsselübergabe

Den oben genannten Wissenschaftlern gelang schließlich der Beweis, dass Alice und Bob einen Schlüssel vereinbaren können, ohne sich treffen zu müssen. Das Konzept beruht auf einer Einwegfunktion der Form Y ^x(modP). Zunächst vereinbaren die beiden Werte für Y und P, die nicht geheim sind (Eve kann ruhig mithören!). Zum Beispiel sei Y=7 und P=11, die Einwegfunktion lautet daher: 7 ^x(mod11). Nun kann die Schlüsselübergabe beginnen!

Überlegen wir nun, wie sich die Sachlage für Eve verhält:
Sie kennt die Einwegfunktion 7 ^x(mod11) und sie kennt die Ergebnisse A=2 und B=4. Um den Schlüssel herauszufinden, kann Eve nun zweierlei tun:

• sie geht vor wie Bob und verwandelt A an Hand von b in den Schlüssel, oder
• sie geht vor wie Alice und verwandelt B mittels a in den Schlüssel.

Beides ist nicht möglich, da sie weder den Wert von a noch von b kennt. Sie könnte noch versuchen, von A auf a zu schließen, da sich A daraus ergibt, dass a in eine Funktion eingesetzt wird. Eve kennt ja sogar die Funktion, aber - und das ist Pech für Eve - handelt es sich um eine Einwegfunktion, die es zwar leicht macht, a in A umzuwandeln, aber sehr schwer, aus A auf a zu schließen.

Wie wir sehen, sind Diffie, Hellman und Merkle ein schönes Stück weiter auf dem Weg zur sicheren Schlüsselübergabe gekommen, doch das Verfahren bleibt noch ziemlich unbequem. Angenommen Alice und Bob leben auf verschiedenen Kontinenten. Zum Erstellen eines Schlüssels müssen sie aber Informationen austauschen: Alice teilt ihr Ergebnis A=2 Bob mit und Bob teilt sein Ergebnis B=4 Alice mit. Der Austausch dieser Information kann sich etwa durch einen Zeitunterschied verzögern und macht das Verfahren umständlich. Es bleibt die Frage offen, wer wann ein effizienteres und praktikables Verfahren für den Schlüsselaustausch finden würde.

Elegante Lösung des Problems der Schlüsselübergabe

oder wieviel Öffentlichkeit verträgt die Kryptographie?

Wir betrachten nun ein einfaches Verfahren für die Verschlüsselung von Nachrichten. Als Hilfsmittel benötigst Du ein dickes Telefonbuch, zum Beispiel dasjenige der Stadt Wien (oder Linz oder Berlin). Es ist - hoffentlich - alphabetisch nach Familiennamen geordnet. Wie können wir damit den Klartext ASTERIX verschlüsseln?

• Du suchst dir zunächst einen Eintrag, der mit A beginnt. Zum Beispiel S. Albert. Die Telefonnummer mag lauten: 912 73 11.
• Anschließend wählst Du einen beliebigen Eintrag unter all jenen, die mit S beginnen. Die Telefonnummer von E. Sieber zum Beispiel mag 163 12 69 sein.
• In dieser Art verfährst Du mit den verbleibenden Buchstaben des Klatextes T, E, R I und X.

Fertig! Die verschlüsselte Nachricht ist: 9127311-1631269-8648249-7732261-5668217-3556917-3215469.

Übung I: Wir nehmen an, Du verwendest zur Entschlüsselung eine Spezialausgabe des Telefonbuchs, in der die Nummern in aufsteigender Reihenfolge gelistet sind. Wie entschlüsselst Du mit der Spezialausgabe die Botschaft 9127311-1631269-8648249-7732261-5668217-3556917-3215469?

Übung II: Leider besitzt Du keine Spezialausgabe des Telefonbuchs. Überlege, ob Du die Nachricht mit dem üblichen Telefobuch entschlüsseln kannst?

Übung III: Niemand außer Du selbst besitzt die Spezialausgabe des Telefonbuchs. Musst Du unter diesen Umständen die Verschlüsselungsmethode geheim halten? Anders gefragt: Kann zum Beispiel unsere alte Bekannte Eve etwas mit der Botschaft 9127311-1631269-8648249-7732261-5668217-3556917-3215469 anfangen, wenn sie weiss, wie der ursprüngliche Text verschlüsselt wurde?

Es sollte uns nun klar sein, dass das Verschlüsselungsverfahren öffentlich bekannt sein darf. Die Spezialausgabe des Telefonbuchs muss hingegen auf jeden Fall geheim bleiben. Wie wir bereits wissen, ist die Verschlüsselung auch ohne Austausch des Schlüssels möglich, indem ein Verfahren angewendet wird, das in der einen Richtung ganz leicht umzusetzen ist, in der entgegen gesetzten aber sehr schwer.
Denken wir noch einmal an unser Beispiel mit dem Telefonbuch: Das Suchen einer Nummer nach dem Namen funktioniert wunderbar, wer es umgekehrt versuchen will, wird bald die Flinte ins Korn werfen.

Fassen wir nun die bisher wichtigsten Punkte der asymmetrischen Verschlüsselung zusammen:

• Das Verschlüsselungsverfahren selbst muss nicht geheim bleiben. Es kann zum Beispiel in der Zeitung öffentlich bekannt geben werden. Aus diesem Grund wird das asymmetrische Verschlüsselungsverfahren auch als public-key Verfahren bezeichnet.
• Das Verschlüsseln einer Botschaft ist nicht schwierig. Alle können eine Nachricht verschlüsseln.
• Die Entschlüsselung ist im Grunde genommen auch einfach. Allerdings benötigt man dafür ein weiteres Hilfsmittel bzw. eine zusätzliche Information. Nur so kann die Nachricht in vernünftiger Zeit entschlüsselt werden.
• Das Hilfsmittel bzw. die Information muss unbedingt geheim bleiben, sonst kann das ganze System nicht funktionieren.

Beim asymmetrischen oder public-key Verfahren besitzt - im Gegensatz zum symmetrischen Verfahren - jede/r KommunikationspartnerIn ein Schlüsselpaar. Beide Schlüsel erfüllen eine ganz bestimmte Aufgabe. Der öffentliche Schlüssel (public key) wird für das Chiffrieren eingesetzt, der geheime private Schlüssel (private key) fürs Dechiffrieren. Alle Personen, die Alice eine verschlüsselte Nachricht senden wollen, verwenden Alices public key zur Verschlüsselung. Alice kann die chiffrierte Nachricht mit ihrem private key (der völlig geheim ist und den nur sie selbst kennt) entschlüsseln.

In unserem Beispiel mit dem Telefonbuch kann jede beliebige Person eine Botschaft mit Hilfe des allgemein zur Verfügung stehenden regulären Telefonbuchs verschlüsseln. Also stellt das Telefonbuch den öffentlichen Schlüssel dar.
Wo befindet sich in unserem System der private Schlüssel? Sehr richtig! Der private Schlüssel ist die Spezialausgabe des Telefonbuchs.

Wenn wir nun wieder an Alice und Bob denken, sieht die Situation wie folgt aus: Alice möchte Bob eine geheime Nachricht schicken. Zur Verschlüsselung der Nachricht verwendet sie Bobs öffentlichen Schlüssel. Dieser kann zum Beispiel in einer Datenbank abgelegt und für alle zugänglich sein. Bob alleine ist im Besitz seines privaten Schlüssels, mit dem er die chiffrierte Nachricht wieder in Klartext umwandelt.

Das RSA-Verfahren

Aufbauend auf den Vorarbeiten (insbesondere dem Konzept der Einwegfunktion) von Diffie und Hellman und Merkle entwickelten Ron Rivest, Adi Shamir und Leonard Adelman im Jahr 1977 ein Verschlüsselungsverfahren, das man heute nach den Anfangsbuchstaben ihrer Nachnamen RSA nennt.

Die Sicherheit dieses Verfahrens beruht letztendlich darauf, dass die Bestimmung der Faktoren großer Primzahlen schwierig und aufwändig ist.

Die genaue Funktionsweise von RSA erfährst Du in den beiden Realisierungen:

• als Flash-Film
• mit einem CAS (DERIVE)

Übung:
Mit Hilfe der RSA-Maschine kannst Du Begriffe nach diesem Verfahren verschlüsseln. Das zu Grunde liegende JavaScript verwendet für n=187 und e=7; Du kannst dich bemühen den Schlüssel zu knacken, indem Du versuchst, p und q herauszufinden.