Asymmetrisches Kryptosystem

Was ist ein asymmetrisches Kryptosystem?

Ein asymmetrisches Kryptosystem (auch Public-Key-Kryptosystem) ist ein kryptographisches Verfahren, bei dem die kommunizierenden Parteien im Gegensatz zu einem symmetrischen Kryptosystem keinen gemeinsamen geheimen Schlüssel benötigen. Jeder Benutzer erzeugt sein eigenes Schlüsselpaar: einen geheimen privaten Schlüssel und einen nicht geheimen öffentlichen Schlüssel. Mit dem öffentlichen Schlüssel kann jeder Daten für den Besitzer des privaten Schlüssels verschlüsseln, dessen digitale Signaturen prüfen oder ihn authentifizieren. Mit dem privaten Schlüssel kann der Besitzer verschlüsselte Daten entschlüsseln, Signaturen erzeugen oder sich authentifizieren. Es dient u. a. der Public-Key-Authentifizierung und digitalen Signaturen.

Prinzip: Schlüsselpaar und Falltürfunktionen

Der private Schlüssel muss geheim gehalten werden; es muss praktisch unmöglich sein, ihn aus dem öffentlichen Schlüssel zu berechnen. Der öffentliche Schlüssel muss jedem zugänglich sein, der eine verschlüsselte Nachricht senden will – dabei muss aber sichergestellt sein, dass er wirklich dem Empfänger zugeordnet ist. Grundlage sind Falltürfunktionen: Funktionen, die leicht zu berechnen, aber ohne ein Geheimnis (die „Falltür“) praktisch unmöglich zu invertieren sind. Der öffentliche Schlüssel beschreibt die Funktion, der private Schlüssel ist die Falltür. Der große Vorteil: Asymmetrische Verfahren vermindern das Schlüsselverteilungsproblem. Bei symmetrischen Verfahren muss der Schlüssel über einen abhörsicheren und manipulationsgeschützten Kanal ausgetauscht werden; bei asymmetrischen muss der Kanal nicht abhörsicher sein, da der öffentliche Schlüssel nicht geheim ist. Wichtig ist nur die eindeutige Zuordnung des öffentlichen Schlüssels zum privaten Schlüsselinhaber, z. B. durch ein digitales Zertifikat einer vertrauenswürdigen Zertifizierungsstelle oder alternativ durch ein Vertrauensnetz (Web of Trust) mit gegenseitigem Zertifizieren ohne zentrale Stelle.

Sicherheit

Die Sicherheit beruht darauf, dass die zugrunde liegenden Einwegfunktionen praktisch unumkehrbar sind, sonst könnte man aus dem öffentlichen den privaten Schlüssel berechnen. Diese Sicherheit beruht derzeit auf unbewiesenen Annahmen, insbesondere der Annahme, dass P ungleich NP ist; die Nicht-Umkehrbarkeit der Falltürfunktionen ist nicht bewiesen, wird aber stark vermutet. Die informationstheoretische Sicherheit des symmetrischen One-Time-Pad kann mit asymmetrischen Verfahren nicht erreicht werden, weil ein entsprechend mächtiger Angreifer immer das zugrunde liegende mathematische Problem lösen kann.

Praktische Aspekte

Vorteil: Das Geheimnis bleibt klein, da jeder nur seinen eigenen privaten Schlüssel geheim halten muss – bei symmetrischen Kryptosystemen müsste jeder Benutzer alle Schlüssel geheim halten, was mit wachsender Benutzerzahl aufwendiger wird. Nachteil: Asymmetrische Algorithmen arbeiten im Vergleich zu symmetrischen sehr langsam. Praxislösungen: Bei hybriden Verfahren wird nur ein symmetrischer Schlüssel asymmetrisch verschlüsselt, während die eigentliche Nachricht mit diesem symmetrischen Schlüssel verschlüsselt wird. Bei digitalen Signaturen wird statt der ganzen Nachricht meist nur deren Hashwert signiert.

Geschichte

Bis in die 1970er Jahre gab es nur symmetrische Kryptosysteme mit dem Problem des Schlüsselaustauschs und der Schlüsselverwaltung. 1974 entwickelte Ralph Merkle Merkles Puzzle (veröffentlicht erst 1978). Das erste Public-Key-Verschlüsselungsverfahren war das Merkle-Hellman-Kryptosystem (Merkle und Hellman), das 1983 von Adi Shamir gebrochen wurde. 1975 veröffentlichten Whitfield Diffie und Martin Hellman eine Idee zur asymmetrischen Verschlüsselung; 1976 entwickelten sie den Diffie-Hellman-Schlüsselaustausch. 1977 entwickelten Ronald L. Rivest, Adi Shamir und Leonard M. Adleman am MIT das RSA-Verfahren – nach heutiger Terminologie eine Falltürpermutation, die für Verschlüsselung und Signaturen eingesetzt werden kann. Unabhängig davon entwickelten Anfang der 1970er Jahre James H. Ellis, Clifford Cocks und Malcolm Williamson am britischen GCHQ ähnliche Verfahren (dem Diffie-Hellman-Schlüsselaustausch und RSA ähnlich), die aber geheim blieben und nicht publiziert oder patentiert wurden. Weitere Kryptosysteme: Merkle-Hellman (1978), McEliece (1978), Rabin (1979), Chor-Rivest (1984), Elgamal (1985) und Elliptic Curve Cryptography (1985).

Formale Definition und Anwendungen

Formal besteht ein Public-Key-Verschlüsselungsverfahren aus drei Algorithmen: dem Schlüsselerzeugungsalgorithmus, der zu einem Sicherheitsparameter ein Schlüsselpaar (öffentlicher und geheimer Schlüssel) erzeugt; dem Verschlüsselungsalgorithmus, der mit dem öffentlichen Schlüssel aus einem Klartext einen Geheimtext erzeugt (probabilistisch, wenn es zu einem Klartext mehrere Geheimtexte geben kann); und dem Entschlüsselungsalgorithmus, der mit dem geheimen Schlüssel aus dem Geheimtext den passenden Klartext berechnet. Gefordert wird, dass jede mit dem öffentlichen Schlüssel verschlüsselte Nachricht mit dem zugehörigen geheimen Schlüssel wieder aus dem Chiffrat gewonnen werden kann. Anwendungen: E-Mail-Verkehr (OpenPGP, S/MIME) und kryptografische Protokolle wie SSH oder SSL/TLS, letzteres z. B. als https für die sichere Kommunikation zwischen Web-Browser und Server. Digitale Signaturen werden u. a. für sichere Geschäfte im Internet genutzt: Aus der Nachricht wird ein Hashwert gebildet und mit dem privaten Schlüssel signiert; Nachricht und Signatur werden geschickt, die Signatur muss nicht verschlüsselt sein, da Signierung Integrität und Authentizität schafft, nicht Vertraulichkeit. Der Empfänger prüft die Signatur mit dem öffentlichen Schlüssel; bei erfolgreicher Verifizierung stammt die Nachricht vom Besitzer des privaten Schlüssels und wurde nicht manipuliert. Meist ist dazu eine Public-Key-Infrastruktur nötig, die die Gültigkeit der Schlüssel durch Zertifikate bestätigt.