Schlüsselknacker aus Leuchtdioden

Trends & News | News

Einen deutlichen Fortschritt in der Faktorisierung verheißt TWINKLE, ein optoelektronisches Gerät, das der Kryptologe Adi Shamir konzipiert hat (http://jya.com/twinkle.htm). Die Schwierigkeit, große Zahlen in ihre Primfaktoren zu zerlegen, macht die Sicherheit des verbreiteten RSA-Public-Key-Verschlüsselungsverfahrens aus, das unter anderem in Web-Browsern (bei SSL-Verbindungen) und in der Krypto-Software Pretty Good Privacy (PGP) arbeitet.

TWINKLE (The Weizman INstitute Key Locating Engine) soll einen der besten Faktorisierungsalgorithmen um den Faktor 100 bis 1000 schneller abarbeiten können als normale Computer. Die bislang größte in einem öffentlichen Wettbewerb faktorisierte Zahl hat 140 Dezimalstellen, was einer Länge von 465 Bit entspricht. Dazu hatten Anfang des Jahres zunächst rund 200 Computer etwa vier Wochen lang parallel gearbeitet, um ein komplexes Gleichungssystem aufzustellen. Für die Lösung dieser 4,7 Millionen Gleichungen benötigte ein Cray-Supercomputer dann nochmals rund 100 CPU-Stunden.

Shamirs optischer Prozessor beschleunigt den ersten Schritt drastisch - zumindest in der Theorie, denn gebaut hat ihn noch niemand. Zum Aufstellen der Gleichungen ist zwar die Addition von etlichen Summanden notwendig, deren Ergebnis benötigt man aber nur näherungsweise. TWINKLE addiert im Prinzip Hunderttausende Werte in einem Taktzyklus: Jeder mögliche Summand ist durch eine Leuchtdiode (LED) von spezifischer Helligkeit vertreten - die jeweilige Gesamtlichtausbeute entspricht mit hinreichender Genauigkeit der Summe der `aktiven´ Werte.

In einer TWINKLE-Einheit werden hunderttausend LEDs im 10-Gigahertz-Gleichtakt optisch getriggert.

Handelsübliche Gallium-Arsenid-LEDs und -Photoempfänger, wie sie etwa für Glasfasernetze benutzt werden, erlauben Taktraten von 10 Gigahertz. Um alle LEDs in dieser immensen Geschwindigkeit synchron anzusteuern, sieht der TWINKLE-Entwurf einen optischen Taktgeber vor (siehe Bild). Nach Abschluß der Prototyp-Entwicklung dürfte eine TWINKLE-Einheit voraussichtlich für etwa 5000 US-Dollar zu bauen sein. Schon sieben solche Einheiten würden einer Abschätzung von Robert D. Silverman zufolge die Gleichungen für die 465-Bit-Rekord-Faktorisierung bereits in sechs Tagen finden (www.rsa.com/rsalabs/html/twinkle.html). Mit einer entsprechend größeren Anzahl könne man in akzeptabler Rechenzeit sogar 512-Bit-Zahlen faktorisieren - das entspricht der maximalen Verschlüsselungsstärke der Export-Versionen von US-Software.

Dennoch bedeutet TWINKLE nicht das Ende für RSA oder andere skalierbare Verfahren, die auf die Faktorisierung bauen: Einen 1024-Bit-Schlüssel zu brechen, dauert laut Silvermans Schätzungen auch mit 45 000 TWINKLEs eine halbe Million Jahre, nur um die Gleichungen aufzustellen, für deren Lösung man dann noch unvorstellbare Mengen an Arbeits- und Massenspeicher sowie Rechenzeit benötigen würde - da könnte man auch gleich per Anhalter durch die Galaxis reisen. (nl)

Anzeige