RSA-240: Faktorisierungserfolg gefährdet RSA nicht

Forscher haben auf einem Rechencluster eine 795 Bit große Zahl faktorisiert. Das RSA-Verschlüsselungs- und Signaturverfahren basiert darauf, dass Faktorisierung schwierig ist. Für die praktische Sicherheit von RSA mit modernen Schlüssellängen hat dieser Durchbruch heute aber wenig Bedeutung.

Artikel veröffentlicht am 4. Dezember 2019, 16:57 Uhr, Hanno Böck

Früher hat man versucht, Zahlensiebe mit mechanischen Geräten zu berechnen, heute verwendet man Computercluster. (Bild: Marcin Wichary, Wikimedia Commons/CC-BY 2.0)

Einem Forscherteam ist es gelungen, die sogenannte RSA-240-Zahl zu faktorisieren. Diese Zahl ist 795 Bit lang und Teil der Faktorisierungs-Challenge, die 1991 vom Unternehmen RSA Security ausgerufen wurde. Moderne RSA-Implementierungen verwenden meist mindestens 2.048 Bit Schlüssellänge, sie sind durch diesen Durchbruch nicht gefährdet.

Der RSA-Algorithmus, der zum Verschlüsseln und Signieren von Daten verwendet wird und zu den am häufigsten verwendeten kryptographischen Algorithmen gehört, basiert darauf, dass es für einen Angreifer schwierig ist, große Zahlen zu faktorisieren. Ein öffentlicher RSA-Schlüssel enthält eine große, zusammengesetzte Zahl, die mit dem Buchstaben N bezeichnet wird und das Produkt aus zwei Primzahlen mit Namen p und q ist. Wenn ein Angreifer in der Lage wäre, N in seine Bestandteile p und q zu zerlegen, könnte er den passenden privaten Schlüssel berechnen.

Faktorisierungs-Wettbewerb 1991 ausgerufen

Die Firma RSA Security hatte 1991 solche zusammengesetzten Zahlen in verschiedenen Größen veröffentlicht und Forscher dazu aufgefordert, diese zu faktorisieren. Offiziell wurde dieser Wettbewerb 2007 eingestellt, aber weiterhin gibt es Versuche und Erfolge beim Lösen. Zuletzt gelang es 2009 einem Forscherteam, eine 768 Bit große Zahl zu faktorisieren.

Die Forscher hinter dem aktuellen Durchbruch haben gleichzeitig auch einen diskreten Logarithmus in ähnlicher Größe berechnet. Dieses mathematische Problem ist für das Diffie-Hellman-Schlüsselaustauschverfahren wichtig. Die Faktorisierung und der diskrete Logarithmus sind ähnliche Probleme und werden mit ähnlichen Algorithmen gelöst. In beiden Fällen nutzten die Forscher das sogenannte Zahlkörpersieb.

Laut der Ankündigung gelang die Berechnung nicht nur, weil die Hardware schneller geworden ist, sondern auch, weil es diverse Verbesserungen am Algorithmus und an der Software gab. Dadurch konnte die Berechnung um das Dreifache beschleunigt werden. Der Code der von den Forschern verwendeten Software Cado-NFS steht unter der LGPL und ist somit freie Software.

2003 bereits Warnung vor 1.024-Bit-Schlüsseln

Für die Sicherheit von RSA und anderen Verschlüsselungsverfahren hat der Durchbruch wenig Bedeutung. Dass kurze RSA-Schlüssel problematisch sind ist schon lange bekannt. Bereits 2003 warnten RSA-Erfinder Adi Shamir und sein Kollege Eran Tromer, dass RSA-Schlüssel mit 1.024 Bit problematisch sind und stellten ein hypothetisches Design für einen teuren Spezialrechner namens TWIRL vor, der solche Schlüssel knacken könnte. Seitdem gelten Schlüssel mit 1.024 Bit als problematisch und es ist denkbar, dass finanzstarke Angreifer in der Lage sind, diese zu knacken.

Die Warnungen von Shamir und Tromer wurden ernstgenommen: RSA mit 1.024 Bit oder noch kürzeren Schlüsseln findet man in modernen Anwendungen normalerweise nicht mehr. TLS-Zertifikate haben heutzutage beispielsweise eine Mindest-Schlüsselgröße von 2.048 Bit.

RSA mit ausreichend großen Schlüsseln wird mit hoher Wahrscheinlichkeit nicht mit Algorithmen wie dem Zahlkörpersieb gebrochen werden. Problematisch bei RSA sind vor allem Implementierungsfehler oder Protokollschwächen wie beispielsweise die ROBOT-Sicherheitslücke.

Wirklich brechen könnte man moderne RSA-Implementierungen nur mit leistungsfähigen Quantencomputern, die es bislang nicht gibt. Um sich davor zu schützen, muss man auf komplett neue kryptographische Verfahren umsteigen - daran wird bereits gearbeitet.