Public-Key-Verschlüsselungsverfahren

Ein Public-Key-Verschlüsselungsverfahren ist ein asymmetrisches Verschlüsselungsverfahren, also ein kryptographisches Verfahren, um mit einem öffentlichen Schlüssel einen Klartext in einen Geheimtext umzuwandeln, aus dem der Klartext mit einem geheimen Schlüssel wieder gewonnen werden kann.

Der geheime Schlüssel muss geheim gehalten werden und 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 an den Besitzer des geheimen Schlüssels senden will. Dabei muss sichergestellt sein, dass der öffentliche Schlüssel auch wirklich dem Empfänger zugeordnet ist.

Geschichte

Bis in die 1970er Jahre gab es nur symmetrische Kryptosysteme, bei denen Sender und Empfänger den gleichen Schlüssel besitzen müssen. Dabei stellt sich das Problem des Schlüsselaustauschs und der Schlüsselverwaltung.

Das erste Public-Key-Verschlüsselungsverfahren war das von Ralph Merkle und Martin Hellman entwickelte Merkle-Hellman-Kryptosystem.^[1] Das MH-Verfahren wurde 1983 von Adi Shamir gebrochen.^[2]

Das heute noch verwendete RSA-Verfahren wurde 1977 von Ronald L. Rivest, Adi Shamir und Leonard Adleman am MIT entwickelt.^[3]

Formale Definition

Eine Zufallszahl wird verwendet, um ein Schlüsselpaar zu erzeugen.

Jeder kann den öffentlichen Schlüssel zum Verschlüsseln verwenden. Nur der Besitzer des privaten Schlüssels kann entschlüsseln.

Formal besteht ein Public-Key-Verschlüsselungsverfahren aus drei Algorithmen:

• Der Schlüsselerzeugungsalgorithmus erzeugt zu einem gegebenen Sicherheitsparameter ein Schlüsselpaar, das aus einem öffentlichen und dem dazugehörigen geheimen Schlüssel besteht.
• Der Verschlüsselungsalgorithmus erzeugt aus einem Klartext unter Verwendung des öffentlichen Schlüssels einen Geheimtext. Es kann zu einem Klartext mehrere Geheimtexte geben, in diesem Fall ist der Algorithmus probabilistisch.
• Der Entschlüsselungsalgorithmus berechnet zu einem Geheimtext unter Verwendung des geheimen Schlüssels den passenden Klartext.

Es wird nun gefordert, dass jede Nachricht, die mit einem öffentlichen Schlüssel verschlüsselt wurde, mit dem zugehörigen geheimen Schlüssel wieder aus dem Chiffrat gewonnen werden kann.

Sicherheit

Von einem Verschlüsselungsverfahren wird mindestens gefordert, dass ohne den geheimen Schlüssel kein Geheimtext entschlüsselt werden kann. Diese Anforderung ist aber oft zu schwach, denn damit wird nicht verhindert, dass ein Angreifer Informationen über Teile der Nachricht aus dem Chiffrat gewinnen kann. Aus diesem Grund ist der etablierte Sicherheitsbegriff Ciphertext Indistinguishability unter verschiedenen Angriffsstärken. Bei dieser Definition darf der Angreifer aus einem Chiffrat überhaupt keine Informationen über den Klartext extrahieren können, außer der Länge des Klartextes, die nicht geheim gehalten werden kann.

Literatur

• Jonathan Katz und Yehuda Lindell: Introduction to Modern Cryptography. CRC Press, 2007, ISBN 1-58488-551-3.
• Alfred J. Menezes; P. C. van Oorschot; Scott A. Vanstone: Handbook of Applied Cryptography. 1997, ISBN 0-8493-8523-7 (http://www.cacr.math.uwaterloo.ca/hac/).

Einzelnachweise

1. ↑ Ralph Merkle and Martin Hellman: Hiding information and signatures in trapdoor knapsacks. In: Information Theory, IEEE Transactions on. 24, Nr. 5, 1978, S. 525–530 (http://ieeexplore.ieee.org/search/freesrchabstract.jsp?tp=&arnumber=1055927).
2. ↑ Adi Shamir: A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem. In: Proceedings of CRYPTO. 1982, S. 279–288 (http://dsns.csie.nctu.edu.tw/research/crypto/HTML/PDF/C82/279.PDF).
3. ↑ Ronald L. Rivest, Adi Shamir, and Leonard Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. (http://people.csail.mit.edu/rivest/Rsapaper.pdf).