mini|Vereinbarung eines gemeinsamen geheimen Schlüssels über eine abhörbare Leitung mit dem Diffie-Hellman-Merkle-Schlüsselaustausch
Der Diffie-Hellman-Schlüsselaustausch oder Diffie-Hellman-Merkle-Schlüsselaustausch bzw. -Schlüsselvereinbarung (auch kurz DHM-Schlüsselaustausch oder DHM-ProtokollSo u. a. Yiu Shing Terry Tin u. a.: Provably Secure Mobile Key Exchange: Applying the Canetti-Krawczyk Approach. In: Rei Safavi-Naini, Jennifer Seberry: Information Security and Privacy. 8th Australasian Conference, ACISP 2003, Springer: Berlin, Heidelberg, 2003, S. 166–179.) ist ein Protokoll zur Schlüsselvereinbarung. Es ermöglicht zwei Kommunikationspartnern, über eine öffentliche (abhörbare) Leitung einen gemeinsamen Schlüssel zu vereinbaren, den nur diese kennen und den ein potenzieller Mithörer nicht berechnen kann. Dieser Schlüssel kann anschließend für ein symmetrisches Kryptosystem verwendet werden (beispielsweise Advanced Encryption Standard). Unterschiedliche Varianten des Diffie-Hellman-Merkle-Verfahrens werden heute für die Schlüsselverteilung in den Kommunikations- und Sicherheitsprotokollen des Internets eingesetzt, beispielsweise in den Bereichen des elektronischen Handels. Dieses Prinzip hat damit eine wichtige praktische Bedeutung.
Das Verfahren wurde von Whitfield Diffie und Martin Hellman entwickelt und im Jahr 1976 unter der Bezeichnung ax1x2 veröffentlicht. Es handelt sich um das erste der sogenannten asymmetrischen Kryptoverfahren (auch Public-Key-Kryptoverfahren), das veröffentlicht wurde. Wichtige Vorarbeiten leistete Ralph Merkle mit dem nach ihm benannten Merkles Puzzle. Wie erst 1997 bekannt wurde, entwickelten bereits in den frühen 1970er-Jahren Mitarbeiter des britischen Government Communications Headquarters (GCHQ) als Erste asymmetrische Kryptosysteme. Das GCHQ hat allerdings wegen der Geheimhaltung und wegen des für die Briten aus Sicht der frühen 1970er Jahre fraglichen Nutzens nie ein Patent beantragt.
Der DHM-Schlüsselaustausch zählt zu den Krypto-Systemen auf Basis des diskreten Logarithmus (kurz: DL-Verfahren). Diese basieren darauf, dass die diskrete Exponentialfunktion in gewissen zyklischen Gruppen eine Einwegfunktion ist. So ist in der primen Restklassengruppe die diskrete Exponentialfunktion , prim, auch für große Exponenten effizient berechenbar, deren Umkehrung, der diskrete Logarithmus, jedoch nicht. Es existiert bis heute kein „schneller“ Algorithmus zur Berechnung des Exponenten , bei gegebener Basis , Modul und gewünschtem Ergebnis.
Damit prägten die Forscher mit dem Verfahren auch einen neuen Sicherheitsbegriff in der Kryptographie, der darauf basiert, dass kein effizienter Algorithmus für die Kryptoanalyse existiert: Ein Kommunikationsprotokoll ist sicher, wenn dessen Kryptoanalyse so viel Zeit und Arbeit bedeutet, dass diese in der Praxis nicht ausgeführt werden kann. Das Problem, aus den beiden Nachrichten der Kommunikationspartner den geheimen Schlüssel zu berechnen, wird als Diffie-Hellman-Problem bezeichnet.
Der DHM-Schlüsselaustausch ist allerdings nicht mehr sicher, wenn sich ein Angreifer zwischen die beiden Kommunikationspartner schaltet und Nachrichten verändern kann. Diese Lücke schließen Protokolle wie das Station-to-Station-Protokoll (STS), indem sie zusätzlich digitale Signaturen und Message Authentication Codes verwenden.
Die Implementierung mittels elliptischer Kurven ist als Elliptic Curve Diffie-Hellman (ECDH) bekannt. Dabei werden die beim Originalverfahren eingesetzten Operationen (Multiplikation und Exponentiation) auf dem endlichen Körper ersetzt durch Punktaddition und Skalarmultiplikation auf elliptischen Kurven. Das -fache Addieren eines Punktes zu sich selbst (also die Multiplikation mit dem Skalar ) wird mit bezeichnet und entspricht einer Exponentiation im ursprünglichen Verfahren. Das Prinzip wurde Mitte der 1980er Jahre von Victor S. Miller und Neal Koblitz unabhängig voneinander vorgeschlagen.
Geschichte und Bedeutung Öffentliche Kryptologie mini|hochkant|Ralph Merkle mini|hochkant|Whitfield Diffie mini|hochkant|Martin Hellman
Beim Diffie-Hellman-Merkle-Schlüsselaustausch handelt es sich um das erste der sogenannten asymmetrischen Kryptoverfahren (auch Public-Key-Kryptoverfahren), das veröffentlicht wurde. Es löst das Schlüsseltauschproblem, indem es ermöglicht, geheime Schlüssel über nicht-geheime, also öffentliche Kanäle zu vereinbaren.
Den ersten Schritt zur Entwicklung asymmetrischer Verfahren machte Ralph Merkle 1974 mit dem nach ihm benannten Merkles Puzzle, das aber erst 1978 veröffentlicht wurde.Ralph Merkle: Secure Communications over Insecure Channels. In: Communications of the ACM 21, Nr. 4, April 1978, S. 294–299. Unter dem Einfluss dieser Arbeit entwickelten Whitfield Diffie und Martin Hellman im Jahr 1976 den Diffie-Hellman-Schlüsselaustausch. Sie veröffentlichten die Forschungsarbeit unter dem Titel „New Directions in Cryptography“.Whitfield Diffie, Martin Hellman: New Directions in Cryptography. In: IEEE Transactions on Information Theory 22, Nr. 6, 1976, S. 644–654. Das Verfahren sorgte für einen gewaltigen Schub in der Kryptographie, eine Wissenschaft, die damals noch nicht sehr lange öffentlich betrieben wurde.Schmeh: Kryptografie. 5. Aufl., 2013, S. 185. Ursprünglich nannten die Forscher das Verfahren ax1x2. Martin Hellman schlug 2002 vor, das Verfahren Diffie-Hellman-Merkle-Schlüsselaustausch zu nennen, „wenn schon Namen damit verbunden werden“, in Anerkennung von Ralph Merkles Anteil an der Entwicklung asymmetrischer Verfahren.Martin E. Hellman: An overview of public key cryptography. In: IEEE Communications Magazine 40 (5), 2002, S. 42–49.
Die Bedeutung dieser Entwicklung wird auch mit der kopernikanischen Wende verglichen: „Die Entwicklung der asymmetrischen Verschlüsselung hat für die Kryptographie eine vergleichbare Bedeutung wie die Kopernikanische Wende für die Astronomie und stellt neben der Digitalisierung der Informationen und dem Internet als Kommunikationsplattform ein Fundament des dritten Jahrtausends dar.“Badach, Hoffmann: Technik der IP-Netze. 3. Aufl., 2015, S. 53.
Whitfield Diffie und Martin Hellman prägten mit dem Verfahren auch einen neuen Sicherheitsbegriff in der Kryptographie, der darauf basiert, dass kein effizienter Algorithmus für die Kryptoanalyse existiert: Ein Kommunikationsprotokoll ist rechnerisch sicher (), wenn dessen Kryptoanalyse so viel Zeit und Arbeit bedeutet, dass diese in der Praxis nicht ausgeführt werden kann. Demgegenüber hält ein bedingungslos sicheres Kryptosystem Angriffen unabhängig von der eingesetzten Rechenleistung stand.Freiermuth u. a.: Einführung in die Kryptologie. 2. Aufl., 2014, S. 200. Die Sicherheit des Diffie-Hellman-Merkle-Schlüsselaustauschs beruht entscheidend darauf, dass die diskrete Exponentialfunktion in gewissen zyklischen Gruppen eine Einwegfunktion (englisch one-way function) ist, so insbesondere in der primen Restklassengruppe. Das heißt, dass in dieser die Exponentiation effizient berechenbar ist, für deren Umkehrung, den diskreten Logarithmus, jedoch bis heute kein effizienter Algorithmus bekannt ist.
Das Diffie-Hellman-Merkle-Verfahren ist mittlerweile nur eines von vielen Verfahren, die die diskrete Exponentialfunktion (mit diskretem Logarithmus als Umkehrung) als Einwegfunktion nutzen. Man spricht in diesem Zusammenhang auch von Krypto-Systemen auf Basis des diskreten Logarithmus oder einfach von DL-Verfahren.Schmeh: Kryptografie. 5. Aufl., 2013, S. 187. So ist es beispielsweise eng verwandt mit dem Elgamal-Verschlüsselungsverfahren, das 1985 vom Kryptologen Taher Elgamal entwickelt wurde. Dieses ist im Prinzip nichts anderes als ein DHM-Schlüsselaustausch mit anschließendem Senden einer Nachricht, die mit dem vereinbarten Schlüssel verschlüsselt ist.Taher Elgamal: A public key cryptosystem and a signature scheme based on discrete logarithms. In: IEEE Transactions on Information Theory 31, 1985, S. 469–472. Siehe auch H. W. Lang: Kryptografische Protokolle:ElGamal-Verschlüsselung (erstellt: 19. Februar 2010, aktualisiert: 29. Mai 2015).
Die Forscher führten in der fundamentalen „New Directions“-Arbeit auch das Konzept einer digitalen Signatur ein: Ein Sender berechnet mit Hilfe eines geheimen Signaturschlüssels (dem Private Key) zu einer digitalen Nachricht (d. h. zu beliebigen Daten) einen Wert, der digitale Signatur genannt wird. Dieser Wert ermöglicht es jedem, mit Hilfe des öffentlichen Verifikationsschlüssels (dem Public Key) die nichtabstreitbare Urheberschaft und Integrität der Nachricht zu prüfen.Beutelspacher: Geheimsprachen. 3. Aufl., 2002, S. 54. So entstand als Weiterentwicklung des DHM-Schlüsselaustauschs eine vielfältige Familie an digitalen Signaturen auf Basis des diskreten Logarithmus. Zu den Bekanntesten gehören das Elgamal-Signaturverfahren und der Digital Signature Algorithm.Schmeh: Kryptografie. 5. Aufl., 2013, S. 204–209.
Neben der Einwegfunktion entwickelten Whitfield Diffie und Martin Hellman auch das Konzept der Falltür (englisch trapdoor). Das ist eine „versteckte Abkürzung“ durch eine Zusatzinformation, mit der die ansonsten schwierige Umkehrung einfach gemacht wird. Auf der Basis von Falltürfunktionen lassen sich asymmetrische Verfahren entwickeln, bei denen die Übertragung eines geheimen Schlüssels nicht mehr notwendig ist. Damit leisteten sie auch wichtige Vorarbeiten zur Entwicklung des RSA-Kryptosystems. Ronald L. Rivest, Adi Shamir und Leonard Adleman versuchten eigentlich zu beweisen, dass es ebensolche Falltürfunktionen nicht geben kann. Bei den Beweisversuchen stießen sie jedoch tatsächlich auf eine solche Einwegfunktion mit Falltür. Das führte 1977 zur Entwicklung des berühmtesten Public-Key-Algorithmus, des nach den Initialen seiner Erfinder sogenannten RSA-Kryptosystems.Beutelspacher: Geheimsprachen. 3. Aufl., 2002, S. 53.
Unterschiedliche Varianten des DHM-Verfahrens werden heute für die Schlüsselverteilung in den Kommunikations- und Sicherheitsprotokollen des Internet eingesetzt, wie z. B. IPsec (Internet Protocol Security), IPv6 (Internet Protocol Version 6) und TLS (Transport Layer Security). Diese dienen zur Sicherung bei der Übertragung von Datenpaketen der IP-Protokollschicht bzw. von Daten der Anwendungsebene, beispielsweise in den Bereichen des elektronischen Handels. Dieses Prinzip der Schlüsselverteilung besitzt damit eine wichtige praktische Bedeutung.Welschenbach: Kryptographie in C und C++. 2. Aufl., 2012. Der hier automatisch berechnete Schlüssel wird dann als Schlüssel für ein schnelles symmetrisches Verfahren wie Data Encryption Standard (DES) oder Advanced Encryption Standard (AES) verwendet.
Das Konzept der Public-Key-Kryptographie und einige spezifische Methoden waren bis 1997 durch die U.S. Patente 4.200.770 (Hellman, Diffie, Merkle, 1980) und 4.218.582 (Hellman, Merkle, 1980) geschützt, die der Stanford University gehören. Für die Entwicklung der Public-Key-Kryptographie und der digitalen Signatur erhielten Whitfield Diffie und Martin Hellman im Jahr 2015 den Turing Award verliehen, der als höchste Auszeichnung in der Informatik gilt, vergleichbar dem Nobelpreis oder der Fields-Medaille.Association for Computing Machinery: Cryptography Pioneers Receive ACM A.M. Turing Award (abgerufen am 1. Mai 2016).
Geheime Kryptologie mini|hochkant|Clifford Cocks