Verschlüsselung: RSA zerstört? – Wohl eher nicht
Ein Paper behauptet, ein neues Verfahren zerstöre das RSA-Krypto-System. Es trägt immerhin den Namen eines renommierten Krypto-Experten.
(Bild: Den Rise/Shutterstock.com)
Der Satz "This destroyes the RSA cryptosystem" sorgte am Dienstag bei manchem Kryptologen für Herzrasen. Immerhin handelt es sich bei dem RSA-Verfahren um einen der zentralen Bausteine des Internets: RSA ermöglicht digitale Signaturen und sicheren Schlüsselaustausch und findet sich quasi überall, wo es um Sicherheit geht: HTTPS, VPNs, SSH und so weiter. Auf dem öffentlichen ePrint-Archiv findet sich nun ein Paper, das dieses Verfahren angeblich zerstört. Es stammt von Claus Peter Schnorr, einem renommierten deutschen Kryptologen der Uni Frankfurt. Auf den ersten Blick wirkt alles echt, der zweite und dritte weckt jedoch Zweifel.
Zum Hintergrund: Das RSA-Verfahren beruht auf dem Phänomen, dass es nahezu unmöglich ist, sehr große Zahlen in Primfaktoren zu zerlegen. Auch beim bisher besten Verfahren dafür, dem Zahlkörpersieb (englisch Number Field Sieve, NFS) steigt der Rechenaufwand exponentiell mit der Größe der Zahlen. Allerdings besteht die Möglichkeit, dass jemand eine clevere Methode findet, das deutlich schneller zu erledigen. Und genau das will Schnorr mit seiner Arbeit zu "Fast Factoring Integers by SVP Algorithms" angeblich geschafft haben. Er spricht von einem nur noch polynomialen Anwachsen der benötigten Rechenzeit, was einen Durchbruch darstellen würde. Ihm würde man so etwas auch durchaus zutrauen und der Inhalt wirkt zunächst seriös.
Erste Zweifel
Der erste Stein des Anstoßes war der offensichtliche Rechtschreibfehler "destroyes" in der Beschreibung auf dem ePrint Archive. Außerdem fand sich die steile Zerstörungs-These zunächst auch nicht im eigentlichen Paper. Das datierte auf den 31.Oktober 2019, war demnach bereits über ein Jahr alt. Eine neuere Version vom 04. März 2020 fand sich auf den Servern der Universität Frankfurt, auch hier ist die Behauptung nicht vorhanden.
Der Tenor der Kommentare ging zunächst in die Richtung, dass wohl jemand eine frühe Version der Arbeit ohne das Wissen von Schnorr hochgeladen habe und damit Stimmung machen wollte. Kryptograf Tim Ruffing forderte bereits, das Paper vom Server zu löschen.
Gegenüber heise online bestätigte Schnorr jedoch, dass es sich um seine Arbeit handele und er lediglich versehentlich die falsche Version hochgeladen habe. Er hat das jetzt korrigiert und eine neue Version hochgeladen, die auch die These der RSA-Zerstörung enthält – jetzt ohne Typo.
Zweiter Anlauf
Doch es mehren sich auch inhaltliche Zweifel, die die neue Version nicht ausräumen kann. Wer sie überfliegt, stellt schnell fest: Die Arbeit ist äußerst anspruchsvoll, selbst für das geübte Auge. Trotzdem haben sich tätige Kryptografen an das Paper gemacht. Die Google-Kryptografin Sophie Schmieg stellte viele mathematische Unstimmigkeiten fest. Abgesehen davon, dass das Paper sich in einem sehr rohen Zustand befindet und noch deutsche Sätze vorhanden sind, fehlt ihr ein schlüssiger Beweis.
Wie es aussieht, hat Schnorr seine Berechnungen lediglich für vergleichsweise kleine Zahlen durchgeführt, Beweise für wirklich große Zahlen fehlen. Auch Matthew Green verwundert es, dass es keinen praktischen Beweis der Praktikabilität des Verfahrens für zumindest näherungsweise typische RSA-Einsatzszenarien gibt. 2019 knackten Wissenschaftler RSA mit 795-Bit-Schlüsseln. Sie nutzten ein optimiertes NFS und benötigten mehr als 900 Prozessorjahre dafür. Das deutlich schneller zu erledigen oder gar einen der leider immer noch nicht völlig ausgemusterten 1024-Bit-Schlüssel zu berechnen, wäre schon ein recht eindrucksvoller Beweis, dass das Ende von RSA tatsächlich gekommen ist. Doch davon ist Schnorrs Paper weit entfernt.
Erster Abgesang
Es bleibt der bisher makellose Ruf des Kryptografie-Experten Schnorr. Er hat immerhin die nach ihm benannte Schnorr-Signatur entwickelt. Doch Kenneth Paterson von der ETH Zürich lässt das nicht gelten. Er deutet auf Sir Michael Atiyah – einen brillanten Mathematiker, den manche auf eine Stufe mit Sir Isaac Newton stellen.
Kurz vor seinem Tod verkündete Atiyah, er habe die berühmte Riemannsche Vermutung bewiesen. Doch die Fachwelt konnte er mit seinem angeblichen Beweis nicht überzeugen. Es stellte sich heraus, dass seine Arbeit fehlerhaft und unvollständig war. Riemanns Vermutung ist nach wie vor unbewiesen – und RSA wohl eher noch nicht zerstört...
Sehr ihr das anders? Diskutiert mit im Expertenforum von heise Security Pro:
Update 4.3.2021 11:10: Die Schnorr-Signatur beruht nicht auf RSA und der Faktorisierung, sondern ähnlich wie DSA auf dem verwandten Problem, den diskreten Logarithmus zu berechnen. Die diesbezügliche Aussage wurde entfernt. (wid)
