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 ,
Früher hat man versucht, Zahlensiebe mit mechanischen Geräten zu berechnen, heute verwendet man Computercluster.
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.

Stellenmarkt
  1. Head of Engineering (m/w/d)
    Hays AG, Niedersachsen
  2. Mitarbeiter (m/w/d) IT Support / Service Desk
    Camfil APC GmbH, Tuttlingen, Reinfeld
Detailsuche

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.

Golem Karrierewelt
  1. First Response auf Security Incidents: Ein-Tages-Workshop
    14.11.2022, Virtuell
  2. Microsoft Azure Administration: virtueller Zwei-Tage-Workshop
    22./23.08.2022, virtuell
Weitere IT-Trainings

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.

Bitte aktivieren Sie Javascript.
Oder nutzen Sie das Golem-pur-Angebot
und lesen Golem.de
  • ohne Werbung
  • mit ausgeschaltetem Javascript
  • mit RSS-Volltext-Feed


Wuestenschiff 05. Dez 2019

RSA ist trotzdem tot es gibt moderne besser Verfahren, wechselt eure Schlüssel. Zum...



Aktuell auf der Startseite von Golem.de
Optibike
E-Bike mit 480 km Reichweite kostet 17.000 Euro

Das E-Bike Optibike R22 Everest setzt mit seinen zwei Akkus auf Reichweite.

Optibike: E-Bike mit 480 km Reichweite kostet 17.000 Euro
Artikel
  1. Krypto-Kriminalität: Behörden fahnden nach Onecoin-Betrügerin
    Krypto-Kriminalität
    Behörden fahnden nach Onecoin-Betrügerin

    Deutsche und internationale Behörden suchen nach den Hintermännern und -frauen von Onecoin. Der Schaden durch Betrug mit der vermeintlichen Kryptowährung geht in die Milliarden.

  2. Hassrede: Bayern will soziale Netzwerke bestrafen
    Hassrede
    Bayern will soziale Netzwerke bestrafen

    Der bayrische Justizminister fordert, bei der Verbreitung von Hassrede auch die Betreiber von sozialen Medien stärker zur Verantwortung zu ziehen.

  3. Prehistoric Planet: Danke, Apple, für so grandiose Dinosaurier!
    Prehistoric Planet
    Danke, Apple, für so grandiose Dinosaurier!

    Musik von Hans Zimmer, dazu David Attenborough als Sprecher: Apples Prehistoric Planet hat einen Kindheitstraum zum Leben erweckt.
    Ein IMHO von Marc Sauter

Du willst dich mit Golem.de beruflich verändern oder weiterbilden?
Zum Stellenmarkt
Zur Akademie
Zum Coaching
  • Schnäppchen, Rabatte und Top-Angebote
    Die besten Deals des Tages
    Daily Deals • Samsung 870 QVO 1 TB 79€ • Prime Video: Filme leihen für 0,99€ • Alternate (u. a. Recaro Rae Essential 429€) • Gigabyte RTX 3080 12 GB ab 1.024€ • Mindstar (u. a. AMD Ryzen 5 5600 179€, Palit RTX 3070 GamingPro 669€) • SanDisk Ultra microSDXC 256 GB ab 14,99€ • Sackboy 19,99€ [Werbung]
    •  /