Ohje... telepolis übt sich in Kryptografie

Meistens les ich ja telepolis ganz gerne. Nur gelegentlich kommt völliger Bullshit dabei heraus. So schwadroniert heute ein Artikel, dass asymmetrische Kryptografie bald obsolet werden könnte.

Kleine Einführung für nicht-Mathematiker: Bei fast allen sicheren Online-Verbindungen wie ssl, ssh o.ä., sowie bei eMail-Verschlüsselung mit PGP/GnuPG und in vielen weiteren Fällen wird sogenannte asymmetrische Kryptografie (auch Public Key-Verfahren genannt) eingesetzt. Das bekannteste und am weitesten verbreitete Verfahren ist RSA, die meisten anderen Verfahren (El Gamal, DSA) basieren auf ähnlichen mathematischen Problemen.

Die Sicherheit von RSA beruht darauf, dass es zwar einfach ist, zwei große Primzahlen miteinander zu multiplizieren, umgekehrt jedoch schwierig, eine Zahl in ihre Primfaktoren zu zerlegen. Hat man also beispielsweise zwei große Primzahlen a und b, so ist es einfach a*b=c zu berechnen. Umgekehrt ist es jedoch nur mit hohem Rechenaufwand möglich, von c auf a und b zu schließen.

2001 haben drei Inder den AKS-Test entwickelt, mit dem man in polynomialer Rechenzeit (einfach gesprochen heißt das: auch bei großen Zahlen noch schnell) herausfinden kann, ob eine große Zahl eine Primzahl ist oder nicht. Für die Sicherheit von RSA ist dies jedoch völlig unbedeutend. Im Gegenteil: Um RSA nutzen zu können, benötigt man schnelle Primzahltests bei der Schlüsselgenerierung. Es ist mathematisch gesehen ein völlig anderes Problem, eine Zahl zu faktorisieren oder sie auf ihre Primzahleigenschaft zu testen.

Nun ist das schon einige Jahre her und war auch damals nicht wirklich überraschend. Das einzige, was passiert ist: Der bekannte AKS-Test wurde in einer mathematischen Zeitschrift veröffentlicht. Genaugenommen ist also garnichts passiert.

Übrigens gibt es bereits seit den 70er-Jahren den sogenannten Miller-Rabin-Test, von dem man ebenfalls vermutet, dass er in polynomialer Zeit Primzahlen erkennen kann. Dafür fehlt bislang jedoch der Beweis. Überraschen konnte das Ergebnis der drei Inder daher aber auch 2001 nicht wirklich.

Korrekt ist im übrigen, dass es rein theoretisch möglich wäre, dass ein bisher unbekannter Algorithmus zur schnellen Faktorisierung existiert. Nur hat ihn bisher noch niemand gefunden (und da sich mit diesem Problem Mathematiker schon ziemlich lange rumschlagen, ist damit auch nicht in absehbarer Zeit zu rechnen).

Daneben strotzt der Artikel nur so von inhaltlichen Fehlern. So wird behauptet, die Faktorisierung von Zahlen sei nur in exponentieller Rechenzeit möglich. Mit modernen Verfahren, etwa dem Zahlkörpersieb, ist dies deutlich schneller möglich, nur eben immer noch zu langsam, um RSA mit ausreichend großer Schlüssellänge (>=2048 bit) in annehmbarer Zeit zu brechen.

Kleiner Tipp an telepolis: Wenn ihr das nächste Mal etwas über Kryptografie schreibt, sucht doch erstmal jemand, der zumindest mal eine Anfängervorlesung dazu besucht hat. Dann würdet ihr vielleicht nicht so einen Unfug schreiben.

Quellen:
Vorlesungsskript über den AKS-Algorithmus (war selber in der Vorlesung)
Miller-Rabin-Test bei Wikipedia
AKS-Test bei Wikipedia