Die Entdeckung der Public-Key-Kryptographie

Ehre, wem Ehre gebührt

Der folgende Beitrag ist vor 2021 erschienen. Unsere Redaktion hat seither ein neues Leitbild und redaktionelle Standards. Weitere Informationen finden Sie hier.

Kurz vor Weihnachten erklärte eine bis dahin wenig bekannte britische Regierungsbehörde, daß sie bereits Jahre vor ihrer Veröffentlichung die Public-Key-Kryptographie entdeckt hat. Die überraschende Enthüllung wirft Licht auf die charakteristische Form, in der die Geheimwissenschaft Kryptographie betrieben wird.

In den aufgeregten Meldungen zum Jahreswechsel über die längst bekannten Abhörmaßnahmen des US-Geheimdienstes National Security Agency (NSA) (siehe u.a. www.heise.de/newsticker und cŽt, Ausgabe 2/98, S.51) in Europa ging eine unscheinbare Nachricht aus derselben Szene fast völlig unter: Auf einer schmucklosen Textseite präsentierte die britische Regierungsbehörde Communications-Electronics Security Group (CESG) Mitte Dezember bescheiden einen Bericht ihres pensionierten Mitarbeiters James H. Ellis.

Der Inhalt des Papiers ist eine wissenschaftsgeschichtliche Sensation: Ellis erzählt darin, wie er 1970 die Public-Key-Kryptographie (PKC) entdeckte. Diese heutzutage praktisch allen wichtigen Verschlüsselungstechniken zugrundeliegende Theorie war bisher den Mathematikern Whitfield Diffie, Martin Hellman und Ralph Merkle zugeschrieben worden, die sie 1976 veröffentlichten. Auch der wichtigste Algorithmus der PKC, mit dem Ron Rivest, Adi Shamir, und Leonard Adleman 1977 an die Öffentlichkeit traten, und der heute unter dem Kürzel RSA selbst einfachen PGP-Nutzern schon ein Begriff ist, wurde laut Ellis von der britischen Krypto-Agentur Jahre vorher entwickelt.

Ellis schrieb den Bericht nach Aussagen der CESG bereits 1987. Seine Veröffentlichung hat er nicht mehr erlebt: Er starb am 25. November 1997.

Die Public-Key-Kryptographie, die mit Paaren von öffentlichen und geheimen Schlüsseln arbeitet, hat die uralte Wissenschaft der Verschlüsselung in den letzten 20 Jahren vollkommen umgewälzt. Durch sie wurde es möglich, daß auch Partner, die nie zuvor in Kontakt miteinander waren, sicher kommunizieren können. Sie gilt deshalb als die Schlüsseltechnologie für den Schutz der Privatsphäre und für den Handel im Zeitalter der digitalen Kommunikation.

In der Zeit vor Entdeckung der PKC diente ein und derselbe Schlüssel sowohl zum Kodieren einer Nachricht als auch zum umgekehrten Vorgang ihrer Wiederherstellung. Sender und Empfänger der Nachricht mußten über identische Kopien dieses Schlüssels verfügen. Der Austausch der geheimen Schlüssels ist der naheliegende Schwachpunkt dieser Form der Kryptographie: Wem es gelingt, den Schlüssel abzufangen, der kann auch die mit ihm verschlüsselten Nachrichten lesen.

In kleinen Gruppen mit festen Strukturen kann dieses Verfahren funktionieren, doch je größer die Zahl der potentiellen Sender und Empfänger ist, desto schwieriger wird die Schlüsselverwaltung. Die enorme Menge benötigter Schlüssel, berichtet der CESG-Agent Ellis in seinem Bericht, habe den Streitkräften in den 60er Jahren einiges Kopfzerbrechen verursacht. Doch lange Zeit schien es, als gebe es dazu keine Alternative:

"Es war für jeden offensichtlich, mich eingeschlossen, daß ohne geheimen Schlüssel keine geheime Kommunikation möglich war... Es gab keine Veranlassung, nach etwas so eindeutig Unmöglichem Ausschau zu halten."

Ellis führt den Grundgedanken hinter PKC auf eine Arbeit des legendären AT&T-Forschungslabors Bell Laboratories von 1944 zurück, das die Verschlüsselung von Telefongesprächen durch die Überlagerung von Schwingungen vorschlug. Damit sei der Samen gelegt worden: "Der relevante Punkt ist, daß der Empfänger kein besonderes Wissen benötigt, um sicher sprechen zu können... Der Angreifer kann alles über das System wissen...", er kann die Nachricht trotzdem nicht verstehen.

Mit anderen Worten: Wie oft in der Geschichte der Wissenschaft bestand die Schwierigkeit nicht darin, die Antwort zu finden, sondern die Frage zu formulieren, nämlich, in Ellis' Worten:

"Können wir eine sicher verschlüsselte Nachricht erstellen, die der vorgesehene Empfänger lesen kann, ohne daß zuvor ein geheimer Austausch des Schlüssels stattfinden muß? Diese Frage fiel mir eines Nachts im Bett ein, und der Beweis der theoretischen Möglichkeit war eine Sache weniger Minuten. Wir hatten einen Existenzsatz."

Die PKC -- die Ellis "Non-Secret Encryption" nannte -- war geboren.
Ellis publizierte seinen nächtlichen Geistesblitz 1970 in dem internen Zirkular der CESG. Einen praktikablen Algorithmus für seine Anwendung zu finden, sei "angesichts seiner schwachen Zahlentheorie" anderen vorbehalten gewesen. Clifford Cocks, ein Kollege von Ellis, veröffentlichte die erste Implementation ebenfalls CESG-intern 1973: Cocks fand, wie Ellis darlegt, einen Spezialfall des RSA-Algorithmus. Und Malcolm Williamson, ein weiterer CESG-Agent, fand das später als Diffie-Hellman-Algorithmus bekannt gewordene Verfahren ebenfalls lange bevor es 1976 öffentlich vorgestellt wurde.

Der Onlineausgabe der New York Times, CyberTimes, sagte Malcolm Williamson nach der Veröffentlichung von Ellis Bericht, er habe sich zwar geärgert, als andere diese Lösung entdeckten, die er nur im kleinen Kreis vorstellen durfte, aber das sei eben der Preis gewesen:

"Ich habe für die britische Regierung gearbeitet und das ist nun mal eine der Einschränkungen, wenn man für die Regierung arbeitet."

Der als Vater der PKC berühmte Martin Hellman zeigte sich gegenüber CyberTimes nach zwanzig Jahren verständnisvoll: "Es muß wirklich schwer für sie gewesen sein mitanzusehen, wie andere Leute die Anerkennung erfahren." Hellman weist allerdings auch darauf hin, daß die Mathematiker des britischen Dienstes dafür auf Material zurückgreifen konnten, das ihm nie zur Verfügung stand:

Diffie, Merkle und ich haben in einem völligen Vakuum gearbeitet. Wenn wir die gesamte geheime Literatur der vorangegangenen 30 Jahre zur Verfügung gehabt hätten, wäre das ein echter Vorteil gewesen.

Martin Hellman

Keine Veröffentlichung bedeutet für die britischen Krypto-Forscher nicht nur kein Ruhm, sondern auch keine Ansprüche auf das Patent. Das sieht nicht nur Jim Bidzos so, der Geschäftsführer der Firma RSA Data Security, die das US-Patent auf den RSA-Algorithmus und zahlreiche weitere kryptographische Algorithmen innehat. Die CESG erklärte, sie habe die Patentierung seinerzeit prüfen lassen, doch die Patentierung mathematischer Formeln sei nach britischem Recht nicht möglich gewesen. Tatsächlich war das RSA-Patent das erste seiner Art überhaupt.

Die überraschende Veröffentlichung der CESG hat nun auch ältere Gerüchte wieder hochkochen lassen, wonach ihr berüchtigtes US-Pendant, die NSA, schon Mitte der 60er Jahre die PKC entwickelt habe. Diese Gerüchte gehen zurück auf eine Behauptung des früheren NSA-Chefs Robert Inman, der dafür allerdings keine Beweise vorlegte. Zwei Wissenschaftler am Forschungslabor von AT&T verweisen auf inzwischen freigegebene Dokumente der US-Regierung, in denen es um Verfahren zur Genehmigung des Starts von Atomraketen geht, und die ihrer Ansicht nach den Anstoß für eine solche Entwicklung bei der NSA gegeben haben könnten.

Und natürlich fragt man sich unwillkürlich: Wenn sie das schon vorher wußten ohne es zu verraten -- was wissen sie dann jetzt?

Warum die Geheimdienste meinen, solche Erkenntnisse zurückhalten zu müssen, dafür gibt Ellis in seinem Papier selbst die Begründung:

Der volle Wert der Kryptographie wird entfaltet, indem man die Information minimiert, die dem potentiellen Gegner zur Verfügung steht.

James H.Ellis

Das ist das nicht nur von den Cypherpunks angegriffene Prinzip "Security by Obscurity", Sicherheit durch Geheimhaltung. Ellis räumt ein, daß es die Kryptographie zu einer "völlig unüblichen Wissenschaft" macht.

Wenn es Hoffnungen dafür gibt, daß dieses Denken der Nachrichtendienste auf dem Rückzug ist -- auf dem freilich Position um Position mit Zähnen und Klauen verteidigt wird --, dann weil der Kalte Krieg vorbei und der globale Kapitalismus ausgebrochen ist. Denn die von Ellis stellvertretend geäußerte Haltung macht ja in Wirklichkeit nur für den Sinn, der den Gegner daran hindern will, seine Daten effektiv zu verschlüsseln. Kryptographische Erkenntnisse zurückzuhalten liegt vor allem im Interesse des Lauschers.

Das Hauptinteresse der Wirtschaft hingegen ist es, ihre Kommunikation zu schützen. Sicher hat mancher nichts dagegen einzuwenden, gelegentlich von den Aktivitäten eines Konkurrenten zur rechten Zeit zu erfahren, aber die Bedrohung der Firmenkommunikation durch schwache Kryptographie ist doch ungleich größer und riskanter als der Gewinn, den die eigene Spionage versprechen könnte. Das Paradigma der nicht-staatlichen Kryptographie entspricht eher dem öffentlichen Beta-Test: Wenn Verfahren bekanntgegeben werden, dann fallen Fehler schneller auf und können korrigiert werden.

Auch die CESG nennt als Grund für ihre neue Offenheit die zunehmende Sichtbarkeit, die die Agentur erlangt hat, seit sie 1994 für die Sicherung der Kommunikation aller britischen Regierungsstellen verantwortlich wurde. Der letzte Anstoß kam aber wohl durch das Streben der Labour-Regierung Tony Blairs, mit öffentlichen Informationen freigiebiger umzugehen. Auf eine solche Politik wird man im Fall der NSA und erst recht im Fall der westdeutschen Dienste wohl noch etwas länger warten müssen.

Boris Gröndahl schreibt Texte und entwirft Konzepte für Neue Medien und lebt in Berlin.