FÜR DIE ERFINDUNG DER AUF ELLIPTISCHEN KURVEN BASIERENDEN KRYPTOGRAPHIE

Zahlentheorie, Elliptische Kurven und Kryptographie
y2 + xy = x3 + 1

 

Eine physische Unterschrift auf einem Vertrag gibt eine bescheidene, aber rechtsverbindliche Garantie, dass der Unterzeichner die Vereinbarung genehmigt hat. Solche Unterschriften spielen seit langem eine wichtige Rolle in der Gesellschaft, aber sie haben mehrere Nachteile: Sie sind leicht zu fälschen, sie gewährleisten nicht, dass das Dokument nach der Unterzeichnung nicht verändert wurde und sie sind umständlich auf viele Dokumente anzuwenden. Eine natürliche Frage ist, ob die digitale Technologie diese Mängel überwinden kann, d.h. ob digitale Signaturen die Authentizität und Informationsintegrität auf effiziente Weise gewährleisten können. Effizienz ist besonders wichtig für die heutigen Internet-Webbrowser, die zusammengenommen täglich Milliarden von Klicks übermitteln. Kunden, die online einkaufen, wollen zum Beispiel wissen, dass die Webseiten, die sie sehen, authentisch sind, und Banken wollen wissen, dass die Transaktionen, die sie durchführen, von legitimen Parteien autorisiert sind.

 

Digitale Signaturen basieren auf einem Zweig der Mathematik, der sonst nur begrenzt Anwendung fand: Der Zahlentheorie. Ein klassisches zahlentheoretische Problem ist z. B. die scheinbar seltsame Frage: gibt es positive ganzzahlige Lösungen für an+bn=cn für jede ganze Zahl n größer als zwei? Die Antwort auf diese Frage ist in der Tat Fermats letzter Satz von 1637, dessen Beweis 358 Jahre später elliptische Kurven betraf.

 

Die Zahlentheorie wurde 1976 mit der Erfindung der Public-Key-Kryptographie durch Diffie und Hellman für die Datensicherheit wichtig. Diese beiden Forscher schlugen einen neuen Algorithmus zum Austausch geheimer Schlüssel vor, der digitale Signaturen liefern kann und dessen Sicherheit auf der Schwierigkeit beruht diskrete Logarithmen über eine Menge namens „multiplikative Gruppe eines endlichen Feldes“ durchzuführen (der Leser, der mit der Bedeutung einer „multiplikativen Gruppe“ nicht vertraut ist, kann sich einfach vorstellen positive ganze Zahlen modulo eine Primzahl wie 127 zu multiplizieren). Eine wichtige Schwäche dieser Gruppe besteht jedoch darin, dass es konkurrierende Algorithmen gibt, die Logarithmen leichter umkehren können als durch die Suche mit roher Kraft. Diese Schwäche bedeutet z. B. dass digitale Signaturen für ein vernünftiges Maß an Sicherheit große Schlüssel mit über 3000 Bit benötigen. Die beträchtliche Schlüssellänge führt zu langsamer Verarbeitung, kostspieliger Speicherung und hohem Energieverbrauch.

 

Die Gewinner des Eduard-Rhein-Technologiepreises 2020 sind Neal Koblitz und Victor Miller für die Erfindung der auf elliptischen Kurven basierenden Kryptographie. Ihre Kernidee von 1985 war es, die „multiplikative Gruppe eines endlichen Feldes“ durch die „Gruppe von Punkten auf einer elliptischen Kurve über einem endlichen Feld“ zu ersetzen. Diese Idee wird für die meisten Leser obskur klingen, aber sie ist praktisch wichtig, weil Probleme wie die Berechnung diskreter Logarithmen in der zweiten Gruppe wesentlich schwieriger zu sein scheinen als in der ersten. Dies wiederum bedeutet, dass die auf elliptischen Kurven basierenden Kryptographie nur 283-Bit-Schlüssel benötigt, um das gleiche Sicherheitsniveau wie die 3000-Bit-Schlüssel früherer Methoden zu erreichen. Darüber hinaus ermöglicht die zehnfache Reduzierung der Schlüssellänge, dass kryptographische Geräte mit höherer Geschwindigkeit, kleinerem Speicher und geringerem Energiebedarf arbeiten.

 

Im Jahr 2013 empfahl das U.S. National Institute of Standards and Technology (NIST) die auf elliptischen Kurven basierende Kryptographie für den Schlüsselaustausch durch einen Algorithmus namens „Elliptic Curve Diffie Hellman“ (ECDH) und für digitale Signaturen durch einen Algorithmus namens „Elliptic Curve Digital Signature Algorithm“ (ECDSA). Darüber hinaus erlaubte die U.S. National Security Agency die Verwendung dieser Algorithmen zum Schutz von bis zu streng geheimen Informationen mit 384-Bit-Schlüsseln. Heute werden elliptische Kurven von Anwendungen wie Bitcoin, TLS (Transport Layer Security)-basiertem Web-Browsing und vielen anderen verwendet.

 

Neal Koblitz erhielt 1969 einen Bachelor of Arts von der Harvard University und 1974 einen Doktortitel von der Princeton University. Seit 1979 ist er an der University of Washington tätig. Kurz bevor er die Kryptographie mit elliptischen Kurven erfand, veröffentlichte er 1984 das Lehrbuch „Introduction to Elliptic Curves and Modular Forms“ mit, in seinen Worten, bodenständigen Beispielen, die das Material lesbar und interessant machen sollen. Er hat mehrere Anerkennungen für seine Arbeit erhalten, darunter 2009 zusammen mit Victor Miller einen RSA Excellence in Mathematics Award.

 

Victor Miller wurde in Brooklyn, New York, geboren und lernte als Studienanfänger im Jahr 1964 elliptische Kurven kennen, als diese Objekte, in seinen Worten, ein interessantes, aber undurchschaubares Stück Mathematik waren. Von 1964-75 studierte er Mathematik an der Columbia University und in Harvard. Er arbeitete ab 1973 an der University of Massachusetts, ab 1978 bei IBM in Yorktown Heights und ab 1993 in dem Center for Communications Research (CCR) des Institute for Defense Analyses in Princeton, New Jersey.

 

Durch ihre Erfindung der auf elliptischen Kurven basierenden Kryptographie haben Neal Koblitz und Victor Miller einen nachhaltigen Einfluss auf die digitale Technologie gehabt, der mit Sicherheit mit der Zeit wachsen wird. Ihre Anwendung grundlegender Mathematik auf ein Problem von großer technischer und gesellschaftlicher Relevanz hat eine sichere und effiziente Kommunikation über das Internet ermöglicht.

 

(Die Polynomgleichung im Titel stellt die Koblitz-Kurve K-283 dar, wie in Abschnitt D.1.3 der NIST-Publikation FIPS PUB 186-4 vom Juli 2013 beschrieben.)