Diffie-Hellman/Geschichte und Bedeutung

Aus Foxwiki

Öffentliche Kryptologie

Ralph Merkle
Whitfield Diffie
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.[1] Unter dem Einfluss dieser Arbeit entwickelten Whitfield Diffie und Martin Hellman im Jahr 1976 den Diffie-Hellman. Sie veröffentlichten die Forschungsarbeit unter dem Titel „New Directions in Cryptography“.[2] Das Verfahren sorgte für einen gewaltigen Schub in der Kryptographie, eine Wissenschaft, die damals noch nicht sehr lange öffentlich betrieben wurde.[3] 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.[4]

Die Bedeutung dieser Entwicklung wird auch mit der kopernikanischen Wende verglichen: „Die Entwicklung der asymmetrischen Kryptografie 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.“[5]

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 sicher, wenn dessen Kryptoanalyse so viel Zeit und Arbeit bedeutet, dass diese in der Praxis nicht ausgeführt werden kann.[6] 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.[7] So ist es beispielsweise eng verwandt mit dem Elgamal-Kryptografieverfahren, 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.[8]

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.[9] 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.[10]

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 RSAs. 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 RSAs.[11]

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.[12] 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.[13][14] 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.[15]

Geheime Kryptologie

Clifford Cocks

Wie erst 1997 bekannt wurde, hatte das britische Government Communications Headquarters (GCHQ) schon in den 1960er Jahren den Auftrag erteilt, zur Vermeidung der hohen Kosten bei der damals üblichen Schlüsselverteilung einen anderen Weg zu finden. James H. Ellis formulierte das Konzept der „nicht-geheimen Kryptografie“. Daraus entwickelte Clifford Cocks ein Verfahren, das er bereits 1973 in einem internen Dokument beschrieb und das dem RSA-Verfahren sehr ähnlich ist. Somit muss aus heutiger Sicht der Dinge festgehalten werden, dass eigentlich Clifford Cocks als erster ein asymmetrisches Kryptoverfahren entwickelte. Diese Errungenschaft wird ihm nicht allgemein anerkannt, da seine Arbeit per definitionem Verschlusssache war und deshalb damals nicht veröffentlicht wurde. Erst 1997 wurde das interne Dokument auf der Website der Communications Electronics Security Group veröffentlicht.

In diesem Zusammenhang wurde auch bekannt, dass Malcolm Williamson, ein weiterer Mitarbeiter des GCHQs, schon 1975 das Schlüsselaustauschverfahren nach Diffie-Hellman entdeckte. Interessant ist dabei, dass die Entdeckung der beiden Verfahren – RSA und DHM – in der öffentlichen und der geheimen Kryptologie in umgekehrter Reihenfolge stattfand.[16]

  1. ↑ Ralph Merkle: Secure Communications over Insecure Channels. In: Communications of the ACM 21, Nr. 4, April 1978, S. 294–299.
  2. ↑ Whitfield Diffie, Martin Hellman: New Directions in Cryptography. In: IEEE Transactions on Information Theory.22, Nr. 6, 1976, S. 644–654.
  3. ↑ Schmeh: Kryptografie. 5. Aufl., 2013, S. 185.
  4. ↑ Martin E. Hellman: An overview of public key cryptography. In: IEEE Communications Magazine 40 (5), 2002, S. 42–49.
  5. ↑ Badach, Hoffmann: Technik der IP-Netze. 3. Aufl., 2015, S. 53.
  6. ↑ Freiermuth u. a.: Einführung in die Kryptologie. 2. Aufl., 2014, S. 200.
  7. ↑ Schmeh: Kryptografie. 5. Aufl., 2013, S. 187.
  8. ↑ 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-Kryptografie (erstellt: 19. Februar 2010, aktualisiert: 29. Mai 2015).
  9. ↑ Beutelspacher: Geheimsprachen. 3. Aufl., 2002, S. 54.
  10. ↑ Schmeh: Kryptografie. 5. Aufl., 2013, S. 204–209.
  11. ↑ Beutelspacher: Geheimsprachen. 3. Aufl., 2002, S. 53.
  12. ↑ Welschenbach: Kryptographie in C und C++. 2. Aufl., 2012.
  13. ↑ Vorlage:Patent
  14. ↑ Vorlage:Patent
  15. ↑ Association for Computing Machinery: Cryptography Pioneers Receive ACM A.M. Turing Award (abgerufen am 1. Mai 2016).
  16. ↑ Borys: Codierung und Kryptologie. 2011, S. 155–156.
Abgerufen von „https://wiki.foxtom.de/index.php?title=Diffie-Hellman/Geschichte_und_Bedeutung&oldid=103991“