[Datenschleuder] [53]    RSA nicht mehr sicher?

RSA nicht mehr sicher? Fast unbemerkt von der Öffentlichkeit ist ein gewaltiger Durchbruch auf dem Gebiet der Faktorisierung gelungen. Erstmals wurde ein Verfahren entwickelt, mit dem eine Zahl mit nur polynominellem Aufwand in ihre Primfaktoren zerlegt werden kann. Die Grundidee ist dabei die Verwendung von Computern, deren Gatter auf Atomgröße reduziert werden. Dieses als ‹Quantum Computing– bezeichnete Verfahren benutzt die Wellenfunktion des Computers (der aus einem ‹Haufen Atome– besteht) zur Berechnung und macht dabei von der Tatasache Gebrauch, daß, solange man den Prozeß nicht beobachtet, alle Quantenzustände gleichzeitig ablaufen und damit die Berechnung für alle Quantenzustände gleichzeitig durchgeführt wird. Dadurch wird eine Parallelität erreicht, die exponentiell mit der Anzahl der beteiligten Teilchen wächst. Sämtliche NP-Probleme lassen sich damit mit einer polynominellen Anzahl von Teilchen in polynomineller Zeit lösen. Ein Verfahren zur Faktorisierung von großen Zahlen mit Hilfe von Quantum Computing wurde von P.W. Shor entwickelt (http://vesta.physics.ucla.edu/~smolin). Da alle derzeit als sicher geltenden Public-Key-Verfahren auf der Komplexität des Faktorisierungspro-blems bzw. auf dem äquivalenten Problem des diskreten Logarithmus basieren, muß man sich die Frage stellen, wie lange man noch Public-Key-Kryptographie als sicher betrachten kann. Doch vorerst besteht kein Grund zur Sorge: technisch ist das Verfahren von Shor auf absehbare Zeit nicht beherschbar. Trotzdem sollte man sich jedoch bereits jetzt über Kryptographie mit Hilfe von Quanteneffekten Gedanken machen Quelle: Science, Vol. 270, October 13, 1995, pp. 255-261, ‹Quantum Computation–, David P. DiVincenzo

[Datenschleuder] [53]    RSA nicht mehr sicher?