• IT-Karriere:
  • Services:

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. KION Group AG, Frankfurt am Main
  2. Tröger & Cie. Aktiengesellschaft, Raum Bremen

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.

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


Anzeige
Spiele-Angebote
  1. (-72%) 16,99€
  2. (-30%) 41,99€
  3. (-20%) 47,99€

Wuestenschiff 05. Dez 2019 / Themenstart

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

Kommentieren


Folgen Sie uns
       


Halo (2001) - Golem retro_

2001 feierte der Master Chief im Klassiker Halo: Kampf um die Zukunft sein Debüt. Wir blicken zurück und merken, wie groß der Einfluss des Spiels wirklich ist.

Halo (2001) - Golem retro_ Video aufrufen
Support-Ende von Windows 7: Für wen Linux eine Alternative zu Windows 10 ist
Support-Ende von Windows 7
Für wen Linux eine Alternative zu Windows 10 ist

Windows 7 erreicht sein Lebensende (End of Life) und wird von Microsoft künftig nicht mehr mit Updates versorgt. Lohnt sich ein Umstieg auf Linux statt auf Windows 10? Wir finden: in den meisten Fällen schon.
Von Martin Loschwitz

  1. Lutris EA verbannt offenbar Linux-Gamer aus Battlefield 5
  2. Linux-Rechner System 76 will eigene Laptops bauen
  3. Grafiktreiber Nvidia will weiter einheitliches Speicher-API für Linux

Sicherheitslücken: Microsoft-Parkhäuser ungeschützt im Internet
Sicherheitslücken
Microsoft-Parkhäuser ungeschützt im Internet

Eigentlich sollte die Parkhaussteuerung nicht aus dem Internet erreichbar sein. Doch auf die Parkhäuser am Microsoft-Hauptsitz in Redmond konnten wir problemlos zugreifen. Nicht das einzige Sicherheitsproblem auf dem Parkhaus-Server.
Von Moritz Tremmel

  1. Datenleck Microsoft-Datenbank mit 250 Millionen Support-Fällen im Netz
  2. Office 365 Microsoft testet Werbebanner in Wordpad für Windows 10
  3. Application Inspector Microsoft legt Werkzeug zur Code-Analyse offen

Kaufberatung (2020): Die richtige CPU und Grafikkarte
Kaufberatung (2020)
Die richtige CPU und Grafikkarte

Grafikkarten und Prozessoren wurden 2019 deutlich besser, denn AMD ist komplett auf 7-nm-Technik umgestiegen. Intel hat zwar 10-nm-Chips marktreif, die Leistung stagniert aber und auch Nvidia verkauft nur 12-nm-Designs. Wir beraten bei Komponenten und geben einen Ausblick.
Von Marc Sauter

  1. SSDs Intel arbeitet an 144-Schicht-Speicher und 5-Bit-Zellen
  2. Schnittstelle PCIe Gen6 verdoppelt erneut Datenrate

    •  /