Harte Nüsse - Verschlüsselungsverfahren und ihre Anwendungen

Asymmetrische Verfahren

Inhaltsverzeichnis

Ein grundsätzliches Problem der verschlüsselten Kommunikation besteht im Austausch des Schlüssels: Da dieser geheim bleiben muss, sollte er nicht im Klartext über einen unsicheren Kanal wie das Internet versendet werden. Die erste praktikable Lösung für den Schlüsseltransfer publizierten Diffie und Hellman 1976. Sie beruht auf dem Problem, diskrete Logarithmen zu ermitteln: Die Berechnung des üblichen Logarithmus, also des Exponenten x aus bekannten Größen a und ax, gehört zum Schulstoff. Anders verhält es sich, wenn man nur mit ganzen Zahlen arbeitet und die Reste bei Teilung durch eine Primzahl p betrachtet. Es ist für große p (typischerweise 1024 oder 2048 Bit lang) im Allgemeinen nicht möglich, aus dem Teilungsrest ax mod p bei bekannter Basis a die Größe x zu ermitteln. Zumindest hat man in den letzten Jahrzehnten trotz größter Anstrengungen keine praktikable Methode gefunden. Nach Diffie und Hellman vereinbaren die Kommunikationspartner (in der Kryptographie traditionell Alice und Bob genannt) zwei gemeinsame Zahlen a und p, und jeder wählt für sich zufällige (geheime) Exponenten x und y. Schickt Alice an Bob

X = ax mod p

und Bob an Alice

Y = ay mod p

können beide ein gemeinsames Geheimnis errechnen, ohne dass es über das Netz übertragen werden muss, nämlich

axy mod p

Dieses Geheimnis kann jetzt als Schlüssel in einem symmetrischen Verfahren genutzt werden.

Der Diffie-Hellman-Schlüsseltausch ist beispielsweise Grundlage für das Protokoll der Secure Shell (SSH2, OpenSSH) und ebenso für IPSec. Weil es jedoch eine Interaktion beider Parteien voraussetzt, kann es beispielsweise nicht bei der Mail-Verschlüsselung eingesetzt werden.

Dazu dienen asymmetrische oder auch Public-Key-Verfahren, bei denen es zwei Schlüssel gibt: einen öffentlichen, der nur zum Chiffrieren dient, und einen geheimen (privaten) - ausschließlich mit ihm kann man wieder dechiffrieren. Jeder kann also chiffrieren, doch nur der Besitzer des privaten Schlüssels kann den Geheimtext wieder entschlüsseln. Damit braucht kein geheimer Schlüssel mehr transportiert zu werden. Die bekanntesten solchen Public-Key-Verfahren sind ElGamal und vor allem RSA.

Der wichtigste asymmetrische Algorithmus RSA beruht darauf, dass es mathematisch extrem schwierig ist, große Zahlen zu faktorisieren, also etwa aus dem Produkt pq zweier sehr großer Primzahlen die beiden Faktoren p und q zu ermitteln. Zur Anwendung wählt man zufällig zwei Primzahlen p und q, von denen nur das Produkt pq bekannt gegeben wird, und konstruiert zwei spezielle Exponenten, einen „öffentlichen“ d und einen „privaten“ e. Bei der Chiffrierung einer Zahl (Nachricht) m berechnet man

c = md mod pq ,

und e ist so gewählt, dass

de = 1 mod (p-1)(q-1) und

m = ce mod pq

gilt. Dabei lässt sich e nicht aus d berechnen, ohne die Primzahlen p und q zu kennen. Ließen sich diese aus pq bestimmen, dann wäre der diskrete Algorithmus und damit RSA geknackt.

Eine Übersicht symmetrischer und asymmetrischer Krypto-Verfahren finden sie in der Tabelle Verschlüsselungs-Algorithmen.