Abo
  • IT-Karriere:

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. Wirtschaftsrat der CDU e.V., Berlin
  2. Institut Franco-Allemand de Recherches Saint-Louis, Weil am Rhein

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.

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.



Anzeige
Top-Angebote
  1. (u. a. Lenovo Legion Y530-15ICH für 699€ + Versand - Bestpreis!)
  2. (aktuell u. a. Sennheiser Momentum 2 Wireless für 199€ statt 229€ im Vergleich)
  3. 39€ + Versand (Bestpreis!)
  4. (aktuell u. a. Intel Core i5-9600K boxed für 229€ + Versand statt 247,90€ + Versand im...

Anonymer Nutzer 19. Mai 2014

Spiel satz und Sieg :) Ich hab kein blassen was ihr so Quatscht :D

Mingfu 18. Mai 2014

Denkbar wäre das durchaus, wenn auch in etwas anderer Form. So könnten z. B. Fehler im...


Folgen Sie uns
       


Workers Resources Soviet Republic - Test

Wem Aufbaustrategiespiele wie Anno oder Sim City zu einfach sind, sollte Workers & Resources: Soviet Republic ausprobieren. Das Spiel ist Wirtschaftssimulation und Verkehrsmanager in einem.

Workers Resources Soviet Republic - Test Video aufrufen
Zulassung autonomer Autos: Der Mensch fährt besser als gedacht
Zulassung autonomer Autos
Der Mensch fährt besser als gedacht

Mehrere Jahre haben Wissenschaftler und Autokonzerne an Testverfahren für einen Autobahnpiloten geforscht. Die Ergebnisse sprechen für den umfangreichen Einsatz von Simulation. Und gegen den schnellen Einsatz der Technik.
Von Friedhelm Greis

  1. Autonomes Fahren US-Post testet Überlandfahrten ohne Fahrer
  2. Mercedes-Sicherheitsstudie Wenn das Warndreieck autonom aus dem Auto fährt
  3. Einride T-Pod Autonomer Lkw fährt in Schweden Waren aus

Kontist, N26, Holvi: Neue Banking-Apps machen gute Angebote für Freelancer
Kontist, N26, Holvi
Neue Banking-Apps machen gute Angebote für Freelancer

Ein mobiles und dazu noch kostenloses Geschäftskonto für Freiberufler versprechen Startups wie Kontist, N26 oder Holvi. Doch sind die Newcomer eine Alternative zu den Freelancer-Konten der großen Filialbanken? Ja, sind sie - mit einer kleinen Einschränkung.
Von Björn König


    LTE-V2X vs. WLAN 802.11p: Wer hat Recht im Streit ums Auto-WLAN?
    LTE-V2X vs. WLAN 802.11p
    Wer hat Recht im Streit ums Auto-WLAN?

    Trotz langjähriger Verhandlungen haben die EU-Mitgliedstaaten die Pläne für ein vernetztes Fahren auf EU-Ebene vorläufig gestoppt. Golem.de hat nachgefragt, ob LTE-V2X bei direkter Kommunikation wirklich besser und billiger als WLAN sei.
    Eine Analyse von Friedhelm Greis

    1. Vernetztes Fahren Lobbyschlacht um WLAN und 5G in Europa
    2. Gefahrenwarnungen EU setzt bei vernetztem Fahren weiter auf WLAN

      •  /