Kryptographie: Schnellerer Algorithmus für das diskrete Logarithmusproblem

Auf der Eurocrypt-Konferenz ist ein schnellerer Algorithmus für eine spezielle Variante des diskreten Logarithmusproblems vorgestellt worden. Dieses Problem ist die Grundlage zahlreicher kryptographischer Verfahren, doch eine direkte Bedrohung für real eingesetzte Algorithmen gibt es zur Zeit nicht.

Artikel veröffentlicht am , Hanno Böck
Verschlüsselungsverfahren sind von dem neuen Algorithmus vermutlich nicht betroffen.
Verschlüsselungsverfahren sind von dem neuen Algorithmus vermutlich nicht betroffen. (Bild: Wikimedia Commons)

Ein französisches Forscherteam um den Kryptographen Antoine Joux hat auf der Eurocrypt-Konferenz in Kopenhagen einen verbesserten Algorithmus zur Lösung einer bestimmten Variante des sogenannten diskreten Logarithmusproblems vorgestellt. Eine Pressemitteilung des französischen nationalen Zentrums für wissenschaftliche Forschung (CNRS) spricht davon, dass der Algorithmus kryptographische Algorithmen gefährden könnte, doch es ist sehr fraglich, ob eine solche Warnung tatsächlich angebracht ist.

Stellenmarkt
  1. Softwareentwickler - Java (m/w/d)
    Brockhaus AG, Lünen
  2. Systems Engineer (m/w/d) - Microsoft SQL Server
    OEDIV KG, Bielefeld
Detailsuche

Das diskrete Logarithmusproblem ist die Grundlage zahlreicher Verschlüsselungs- und Signaturverfahren. Das ElGamal-Verfahren, der Signaturstandard DSA und der Diffie-Hellman-Schlüsselaustausch basieren alle darauf, dass es schwierig ist, das diskrete Logarithmusproblem zu lösen. Ein schneller Algorithmus zur Lösung dieses mathematischen Problems würde also die Sicherheit zahlreicher Verfahren gefährden. Doch die Resultate des französischen Forscherteams betreffen nur eine sehr spezielle Variante des diskreten Logarithmusproblems.

"Der Algorithmus ist mathematisch sehr interessant", sagte uns dazu die Kryptographin Tanja Lange von der Universität Eindhofen. "Aber auf gängige kryptographische Verfahren, die im Internet eingesetzt werden, lassen sich diese Resultate nicht übertragen."

Das diskrete Logarithmusproblem wird in einer mathematischen Struktur berechnet, die man als endliche Körper bezeichnet. Die jetzt offiziell veröffentlichten Resultate betreffen aber nur sogenannte endliche Körper mit kleiner Charakteristik. Verfahren wie der Diffie-Hellman-Schlüsselaustausch oder der DSA-Signaturalgorithmus nutzen allerdings endliche Körper mit großer Charakteristik.

Golem Akademie
  1. Linux-Systeme absichern und härten
    8.-10. November 2021, online
  2. Penetration Testing Fundamentals
    23.-24. September 2021, online
  3. Microsoft 365 Security Workshop
    27.-29. Oktober 2021, Online
Weitere IT-Trainings

Eine Bedrohung für die Sicherheit im Netz sind die Resultate also im Moment nicht. Trotzdem ist natürlich nicht auszuschließen, dass in Zukunft verbesserte Angriffe die Sicherheit dieser Algorithmen in Zweifel ziehen. Möglicherweise gibt es eine Variation dieses neuen Algorithmus, die sich auch auf generische endliche Körper anwenden lässt.

Falls sich das diskrete Logarithmusproblem schnell lösen ließe, würde dies unter Umständen auch die Sicherheit des weit verbreiteten RSA-Verfahrens bedrohen. RSA basiert zwar auf dem mathematisch etwas anders gelagerten Faktorisierungsproblem. In der Vergangenheit war es jedoch meistens so, dass Fortschritte bei Algorithmen zur Lösung des diskreten Logarithmusproblems später auch zu schnelleren Algorithmen für das Faktorisierungsproblem führten.

Wirklich neu sind die Resultate nicht: Eine Vorabversion des Papers wurde bereits im vergangenen Jahr veröffentlicht. In einem Vortrag auf der Blackhat-Konferenz warnten infolgedessen einige Forscher vor einer bevorstehenden Cryptopocalypse. Andere Fachleute sahen die Resultate jedoch deutlich gelassener.

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


Aktuell auf der Startseite von Golem.de
Mobiles Betriebssystem
iOS 15 mit Focus, OCR und schickem Facetime

Apple hat iOS 15 für iPhones und den iPod Touch vorgestellt. Radikale Neuerungen sind nicht dabei, dafür aber einige interessante Funktionen.

Mobiles Betriebssystem: iOS 15 mit Focus, OCR und schickem Facetime
Artikel
  1. Windows 11: Geplante Obsoleszenz ist schlecht, Microsoft!
    Windows 11
    Geplante Obsoleszenz ist schlecht, Microsoft!

    Kunden ärgern sich darüber, dass ihre vier Jahre alten Prozessoren bereits kein Windows 11 mehr unterstützen. Zu Recht.
    Ein IMHO von Oliver Nickel

  2. Apple Watch: watchOS 8 mit Achtsamkeits-Funktion und Porträt-Zifferblatt
    Apple Watch
    watchOS 8 mit Achtsamkeits-Funktion und Porträt-Zifferblatt

    Apple hat für die Apple Watch mit watchOS 8 ein neues Betriebssystem vorgestellt, das neue Zugriffs-, Konnektivitäts- und Achtsamkeitsfunktionen auf die Smartwatch bringt.

  3. Diablo 2 Resurrected: Entwickler äußern sich zu Blizzard-Boykott
    Diablo 2 Resurrected
    Entwickler äußern sich zu Blizzard-Boykott

    Für viele Spieler wäre Diablo 2 Resurrected ein Pflichtkauf. Blizzard soll aber nicht unterstützt werden. Das sagen Entwickler zum Dilemma.

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 • MM-Prospekt (u. a. Asus Gaming-Notebook 17" RTX 3050 1.099€) • PCGH-PC mit Ryzen 5 3600 & RTX 3060 999€ • Samsung 970 Evo Plus 1TB 99€ • Saturn Hits 2021 (u. a. Philips 55" OLED 120Hz 1.849€) • Corsair RGB 16GB Kit 3600MHz 87,90€ • Dualsense Schwarz + Deathloop 99,99€ [Werbung]
    •  /