Kryptographie – die Public-Key-Chiffrierung

Alle kryptographischen Verfahren, die wir bisher behandelt haben, waren so aufgebaut, dass sowohl Sender als auch Empfänger den gleichen Schlüssel benutzten, um zu chiffrieren bzw. zu dechiffrieren. Diese Kryptosysteme werden als symmetrisch bezeichnet. Damit bekommen wir jedoch in der heutigen Zeit ein gewaltiges Problem. Wie kommuniziere ich -geheim- mit jemandem, den ich gar nicht kenne und mit dem ich noch nie in Kontakt stand? Wie kann ich jemandem, mit dem ich in Kontakt treten möchte und den ich kenne, auf öffentlichen Kommunikationskanälen einen geheimen Schlüssel zusenden, um ein herkömmliches und schnelles Verschlüsselungsverfahren in Anspruch zu nehmen? Das Problem ist auch ein mathematisches! Wenn zwei Personen miteinander kommunizieren und sich einer symmetrischen Verschlüsselung bedienen wollen, dann brauchen diese beiden einen gemeinsamen und geheimen Schlüssel. Angenommen n Personen stehen in Kontakt miteinander, und jeder möchte mit jedem geheim kommunizieren. Die Anzahl der Schlüssel lässt sich ganz einfach berechnen:
Das sind bei nur n=100 Leuten (und was ist das im Internet) bereits S₁₀₀=4950 Schlüssel. Die Zahl der Schlüssel entwickelt sich quadratisch; wie wir oben gesehen haben, ist S_n eine quadratische Funktion von n. Jedes Mal, wenn ein neuer Teilnehmer dazukommt, werden n neue Schlüssel benötigt, denn:
Damit sind die Grenzen der klassischen Kryptographie erreicht. Es musste ein neues Schlüsselmanagement gefunden werden. Eine dieser neuen Methoden zur Schlüsselerzeugung (den Diffie-Hellman-Algorithmus) vergleicht Albrecht Beutelspacher mit der Kunst, öffentlich ein geheimes Süppchen zu kochen. Die beiden Köche A und B wollen eine gemeinsame geheime Suppe kochen, die nur sie beide kochen können, obwohl jeder zugucken kann. Das funktioniert im Prinzip so:

1. Beide Köche haben eine Art Ursuppe - wenigstens einen Topf Wasser mit gleichviel Wasser drin.
2. Beide Köche haben Gewürze g_A und g_B, die sehr geheim sind. Beide würzen nun jeweils ihren Topf und merken sich, wie viel Gewürz in den Topf kommt.
3. Nun werden die Töpfe mit den halbfertigen Suppen ausgetauscht. Koch A schickt seinen an Koch B und umgekehrt.
4. Sobald die Töpfe angekommen sind, fügen wieder beide ihr geheimes Gewürz in den entsprechenden Mengen hinzu. Sie haben nun genau dieselbe Suppe gekocht.

Dass beide die gleiche Suppe haben, scheint klar zu sein. Aber kann ein Unbefugter diese nachkochen? Nein! Zwar kann ein Angreifer beide Töpfe abfangen, aber er kann die Gewürze nicht isolieren. Die Umsetzung dieses Protokolls mit seinen Eigenschaften auf Zahlen ist der Beginn der modernen asymmetrischen Kryptographie, welche die beiden folgenden zusammenfassenden Nachteile der klassischen Kryptographie umgeht:

• Wer verschlüsseln kann, der kann auch entschlüsseln.
• Je zwei Partner müssen einen gemeinsamen Schlüssel austauschen.

Asymmetrische Kryptographie bedeutet also, dass der Empfänger die Nachricht mit einem anderen Schlüssel wieder entschlüsselt und nicht den gleichen nutzt, den der Sender verwendet hat.
Wie funktioniert das? Die Lösung liegt in sogenannten Einwegfunktionen. Das sind Funktionen, die sich zwar in eine Richtung gut und einfach durchführen lassen, deren Ausführung in umgekehrter Richtung mit großen Schwierigkeiten verbunden ist. (Denken Sie an die Suppe, diese zu versalzen, ist ganz einfach, aber das Salz aus der Suppe zu trennen, ist ziemlich kompliziert! Oder versuchen Sie einmal, eine ausgedrückte Zahnpastatube wieder aufzufüllen!) Ein einfaches mathematisches Beispiel wäre das Lösen eines Gleichungssystems. Relativ einfach, aber die Rekonstruktion aus den Lösungen vorzunehmen, ist ein Problem.
Eines der bekanntesten asymmetrischen Kryptosysteme wurde von Ronald Rivest, Adi Shamir und Leonard Adleman entwickelt, weshalb es auch mit den Anfangsbuchstaben ihrer Nachnamen als RSA-Algorithmus bezeichnet wurde. RSA ist ein sogenanntes Public-Key-Verfahren. Dies bedeutet, dass ein öffentlicher Schlüssel herausgegeben wird, mit dem alle Absender ihre Nachrichten verschlüsseln. Dieser Schlüssel kann z. B. in der Datenbank einer Zertifizierungsstelle für jeden zugänglich gespeichert sein. Der Empfänger dieser Nachrichten besitzt einen eigenen zweiten, den privaten Schlüssel. Er ist ein absolutes Geheimnis des Empfängers und kann sogar als Identitätsnachweis dienen. Nur mit diesem Schlüssel ist es möglich, die Nachricht zu entschlüsseln. So kann zwar jeder eine Nachricht verschlüsseln, aber nur der Besitzer des privaten Schlüssels kann sie wieder dechiffrieren. Damit wächst die Zahl der nötigen Schlüssel lediglich linear mit der Zahl der Teilnehmer.