Cryptography Reference
In-Depth Information
RSA und Quantencomputer
In Abschnitt 7.3.3 haben Sie erfahren, was ein Quantencomputer ist. Das Tolle
an diesen Geräten ist, dass sie nicht an die klassische Physik gebunden sind und
daher Rechenoperationen durchführen können, die für einen herkömmlichen
Computer unmöglich sind. Der Nachteil an Quantencomputern besteht darin,
dass man noch weit davon entfernt ist, praxistaugliche Exemplare bauen zu kön-
nen. Möglicherweise wird es nie Quantencomputer geben, die mehr als ein paar
einzelne Bits verarbeiten.
Sollten irgendwann doch brauchbare Quantencomputer verfügbar sein, dann
dürfte das Knacken von Verschlüsselungen die wichtigste Anwendung werden.
Ein Beispiel ist die in Abschnitt 7.3.3 beschriebene vollständige Schlüsselsuche
bei symmetrischen Verfahren mit dem Grover-Algorithmus - sie kommt dem
Halbieren der Schlüssellänge gleich. Noch deutlich wirkungsvoller ist ein Quan-
tencomputer, wenn es um das Faktorisieren geht. Mit dem sogenannten Shor-
Algorithmus kann ein Quantencomputer ein Primzahlprodukt in vergleichsweise
kurzer Laufzeit in seine Faktoren zerlegen [Shor]. Das bedeutet: Sollte es einmal
größere Quantencomputer geben, dann ist das RSA-Verfahren erledigt. Die Ver-
fahren auf Basis des diskreten Logarithmus wären ebenfalls hinfällig, da sich der
diskrete Logarithmus auf das Faktorisierungsproblem zurückführen lässt. Auch
Verfahren auf Basis elliptischer Kurven würden in einem solchen Fall ihre Wir-
kung verlieren. Schlaflose Nächte sind bisher jedoch nicht angebracht, denn noch
sind Quantencomputer eher Science Fiction als Realität.
TWINKLE und TWIRL
Das bisher kurioseste Kapitel in der Geschichte der RSA-Kryptoanalyse schlug
ausgerechnet RSA-Miterfinder Adi Shamir auf. 1999 präsentierte er bei der Euro-
crypt-Konferenz in Prag die Idee zu einer Maschine, die zu einem Primzahlpro-
dukt die beiden zugehörigen Primzahlen berechnen konnte [Sham99, Luck99].
Das Besondere daran war, dass es sich dabei um keinen Computer, sondern um
einen optisch-elektronischen Apparat handelte. Shamir gab seiner Maschine den
Namen
TWINKLE
(The Weizmann Institute Key Locating Engine). Shamir
schätzte, dass eine TWINKLE-Maschine für etwa 5.000 US-Dollar pro Stück rea-
lisierbar wäre und bei Faktorisierungsvorgängen 100 bis 1.000 PCs ersetzen
könnte. Bisher hat zwar noch niemand ein solches Gerät gebaut (jedenfalls ist
nichts bekannt geworden), doch Experten gehen davon aus, dass es möglich wäre.
2003 stellte Shamir zusammen mit einem Kollegen einen TWINKLE-Nach-
folger vor, den er
TWIRL
(The Weizmann Institute Relation Locator) nannte
[ShaTro]. Auch TWIRL ist bisher eine fiktive Maschine geblieben. Shamir geht
davon aus, dass sich damit ein 1.024-Bit-RSA-Schlüssel innerhalb eines Jahres
faktorisieren ließe - bei Kosten von einigen Millionen Euro. Dies erscheint zwar
immer noch reichlich viel, ist aber für Geheimdienste und Militärorganisationen
