Neue Algorithmen und schnellere Rechner beschleunigen Faktorisierung großer Zahlen:

Die Sicherheit von Codes steht auf dem Spiel

02.08.1985

MÜNCHEN - Verschlüsselungsalgorithmen werden aus Gründen der Datensicherheit zunehmend interessanter. Dabei gewinnt die Methode der Faktorisierung großer Zahlen, vor zehn Jahren noch ein relativ unbedeutender Zweig der mathematischen Wissenschaften. große Bedeutung. Peter Lange* berichtet , welche Hindernisse die Mathematiker den Code--Knackern in den Weg legen.

Ist 10e1031--1 eine Primzahl? Natürlich nicht, denn als ganzzahlige Zehnerpotenz muß das Resultat ja eine gerade Zahl sein. Doch wie steht es mit 10e103l- 1? Die Antwort ist leichter, als man auf den ersten Blick glauben möchte. Denn natürlich ist 10e1031- 1 durch drei und durch neun teilbar. Teilt man durch neun, bleibt eine Kette von 1031 Einsern übrig. Ob dies nun eine Primzahl ist, ist nicht mehr durch schnelles Nachdenken zu beantworten. Vielmehr sind hochqualifizierte Mathematiker in einer ganzen Reihe von Forschungsstätten damit beschäftigt, solche und andere Probleme Schritt für Schritt zu knacken. Dabei helfen ihnen schnelle, neue Computer und raffinierte Algorithmen, die Riesenzahlen in ihre Faktoren zu zerlegen - , wenn sie überhaupt welche besitzen. Und man arbeitet auch schon an neuen Computer-Entwicklungen, die speziell für die Aufgabe des Faktorisierens entwickelt werden. Man könnte aber auch sagen: für das schnellere " Knacken " von chiffriertem Text, der mit Hilfe vielstelliger Zahlen verschlüsselt worden ist.

Abseitige Wissenschaft

Noch vor zehn Jahren war die Kunst des Faktoriesierens eine eher abseitige Wissenschaft, erinnert sich einer ihrer Meister, der Mathematiker Hugh. H. Williams von der University of Manitoba in Winnipeg. Doch je mehr Leute sich in letzter Zeit für Verschlüsselungs-Algorithmen interessierten, desto stärker rückten Experten wie er ins Licht wenigstens einer breiteren Fach-Öffentlichkeit. Mehr und mehr Wissenschaftler wandten sich daher dem interessant gewordenen Felde zu, und das hatte wieder zur Folge, berichtet das amerikanische Wissenschaftsmagazin " Science News " ,daß binnen nur weniger Jahre große Fortschritte gemacht wurden: Konnte man seinerzeit höchstens 50stellige " schwer " zu faktorisierende Zahlen " knacken " , so gelingt das heute mit bereits 71 stelligen. Und auch alle Zahlen, die einst auf einer Liste mit den "meistgesuchten Zehn " standen, sind inzwischen in ihre Faktoren zerlegt.

Vielleicht ist manchem noch eine Meldung aus dem letzten Jahr in Erinnerung, wonach es Forschern an den amerikanischen Sandia National Laboratories in Albuquerque, Neu Mexiko, gelungen ist, mit einem Rechenaufwand von 9,5 Stunden auf einer Cray X-MP mit einer allgemein verwendbaren Methode die größte der " schwer " zu knackenden Zahlen zu faktorisieren: nämlich die 71 stellige Zahl 10e71-1.

Heute arbeiten die an jenem Rekordunternehmen Beteiligten an der Verfeinerung einer Faktorisierungstechnik, die als " quadratisches Sieb " (QS) bekannt ist. Vor allem erreichen wollen sie, daß ihr Algorithmus auf einer Cray X-MP möglichst effizient läuft. Dabei geht es ihnen einmal darum, das Programm als solches zu verbessern, und zweitens, es optimal an Multiprozessor-Rechner anzupassen.

Schon heute, so meint Sandia-Forscher Gustavus J. Simmons dazu, sollte es eigentlich möglich sein, bei Einsatz beider Prozessoren einer " Cray X-MP " binnen eines Rechen--Tages 77- bis 78stellige Zahlen des gleichen Schwierigkeitsgrades zu faktorisieren, wie er für 10e71- 1 typisch ist.

Zahlen zerhäckseln

Von Simmons kann man aber auch ein bißchen deutlicher als anderweitig hören, daß es nicht unbedingt das Hauptziel seiner Arbeiten ist, möglichst große Zahlen zu zerhäckseln, sondern daß er und seine Kollegen vor allem herausfinden sollen, wie schwierig es heute wirklich ist, eine gegebene Zahl in ihre Faktoren zu zerlegen. Denn mit Blick auf konkrete Anwendungen im weiten Felde der Kryptographie ist es viel aussageträchtiger, die bekannte 71 stellige Zahl nun - mit modernen Methoden - erneut zu bearbeiten und zu schauen, wie lange sie den Attacken des Computers jetzt widersteht, als nur eine weitere, vielleicht 77 stellige Zahl zu knacken.

Dabei blickt Simmons bereits auf eine ganz neue Klasse von Superrechnern wie die "Cray 2" und deren Gegenstücke aus Japan. Denn diese Maschinen, so meint er, werden sein Programm zehnmal schneller abspulen können. Oder, anders ausgedrückt: Sie sollten innerhalb eines Arbeitstages dann sogar eine 85 stellige " harte Nuß " knacken können.

An der University of Georgia in Athens wartet Jeffrey Smith nicht erst lange, bis die Industrie neue Rechner an der Laderampe abliefert sondern hilft sich selbst. Er baut einen Spezialrechner für einen speziellen Algorithmus mit dem Namen " Continued-fraction " --Methode. Der neu entstandene Rechner selber hört auf den Spitznamen "Georgia-Crakker".

Billiger im Schneckentempo

Dieser EPOC (Extended Precision Operand Computer) soll zwar langsamer arbeiten als eine Cray, aber auch viel billiger sein. Seine Bauteile haben rund 10 000 Dollar gekostet und sein funktioneller Kern faktorisierte schon Zahlen mit bis 56 Stellen.

Während man also die billige EPOC-Maschine wohl bald routinemäßig, wenn auch im "Schneckentempo" an einer Zahl nach der anderen arbeiten lassen wird, wälzt Smith inzwischen schon neue Pläne für einen Rechner, der ganz speziell auf den schon erwähnten QS-Algorithmus (eine Erfindung des in Georgia beheimateten Wissenschaftlers Carl Pomerance) zugeschnitten sein soll. Doch auch Smith hat dabei als Endziel seiner Arbeit gar nicht unbedingt das schnelle Faktorisieren an sich vor Augen, denn er will mit seinen innovativen Rechner-Architekturen eigentlich etwas ganz anderes demonstrieren: nämlich, daß es auch für andere Forscher gar nicht so schwierig sei, " maßgeschneiderte " Prozessoren speziell für ihre höchst eigenen Zwecke zu konfigurieren.

Simple Operationen

Wieder ein anderer Primzahlen--Freak, Marvin C. Wunderlich, benutzt ebenfalls die "Continued-fraction " -Methode, doch er setzt dabei einen " MPP ", also einen " massiv parallelen Prozessor " ein. In Fort Meade, Maryland, wo Wunderlich für die National Security Agency (NSA) arbeitet, tätigt nämlich ein Monster mit 16384 einzelnen Prozessoren seine Rechenvorgänge, die alle zur gleichen Zeit aktiv sind. Sie vollführen, praktisch im Gleichschritt, immense Mengen prinzipiell simpler Operationen.

Wunderlichs Rechner war ursprünglich für die NASA gebaut worden, für die er Bilddaten verarbeiten sollte. Jetzt aber wird bei der NASA versucht, den Faktorisierungs-Algorithmus so zu modifizieren, daß die parallele Architektur der Maschine möglichst gut genutzt wird. Außerdem soll eine Art " Abbruch-Technik " implementiert werden, die verhindert, daß der Rechner unbemerkt in eine Richtung vor sich hinarbeitet, die letztlich zu nichts führen wird.

Überlegenheit schwindet

Der MPP in Fort Meade soll Zahlen mit etwa 60 Stellen noch schneller faktorisieren können als eine Cray, sagt die Theorie, doch oberhalb von 75 Stellen - hier ist natürlich stets von Dezimalstellen die Rede - soll seine Überlegenheit schwinden. Um in diesem Bereich eine Cray einholen zu können, bedürfte es dann wohl schon einer Konfiguration mit gleich achtmal soviel Prozessoren, wie Simmons kommentiert. Und er bemerkt noch, auch Wunderlichs Arbeiten gäben der NSA einen Anhaltspunkt dafür, was man mit einem bestimmten Aufwand an parallelen Prozessoren denn jeweils überhaupt werde leisten können.

Ein weiterer Spezialrechner, und zwar hier einer, der besonders auf große Dezimalzahlen hin ausgelegt ist, entsteht zur Zeit in Baton Rouge, Louisiana, an der dortigen Universität. Er verfügt über 256-Bit-Worte, die sich in bis zu 8-Bit-(32-Bit)-Elemente unterteilen lassen. Man kann also, ist die Maschine einmal fertig, entweder auf einmal zwei 128-Bit-Zahlen miteinander multiplizieren, aber auch zum Beispiel vier 32-Bit-Paare.

Diese Maschine soll in der Lage sein, beim Faktorisieren mit 76 stelligen Dezimalzahlen fertig zu werden, und bei manchen Algorithmen soll dieser Rechner sogar extrem schnell arbeiten, wie seine Konstrukteure hoffen. Zumindest, wenn es gelingt, ihn so zu programmieren, daß diese Algorithmen die speziellen Eigenschaften dieser Hardware effektvoll nutzen können.

Duncan A. Buell, der diese Arbeiten in Baton Rouge vorantreibt, hat speziell einen Algorithmus im Auge, der von Hendrik W. Lenstra jr. von der Universität Amsterdam sowie von Claus P. Schnorr von der Universität Frankfurt entwickelt worden ist. Dabei wird mit Zahlen gearbeitet, die bis auf sehr viele Dezimalstellen völlig akkurat dargestellt werden müssen ; ein Grund übrigens, warum er bisher nicht eben viele Freunde gefunden hat. Doch das könnte sich nun bald ändern, denn Lenstra hat erst kürzlich eine neue, einfachere Version dieses Algorithmus vorgestellt hat. Eine Version, die mit weitaus weniger " Overhead " als die frühere auskommen soll.

Lenstra ist schneller

Wie einfach der neue Algorithmus zu programmieren ist, demonstriert Buell jedem Interessierten anhand eines Programms in der Sprache " C ", das bloß etwa 250 Code-Zeilen umfaßt. Und er erläutert, am besten " funktioniere der neue Algorithm " dann, wenn die in ihre Faktoren zu zerlegende Zahl sich hinterher als eine erweise, die das Produkt von drei oder mehr Primzahlen ist. Oder aber das Produkt nur zweier Primzahlen, von denen die eine aber dann sehr viel kleiner als die andere sein muß.

Hugh C. Williams von der University of Manitoba erläutert zusätzlich, um wieviel schneller der neue Lenstra-Algorithmus tatsächlich eines Tages arbeiten werde, hänge sehr davon ab, wie gut er an den jeweiligen Rechner angepaßt werde. Wobei sich dabei dann ja oft zeige, daß man auf das konkrete Austesten der Laufzeiten nicht verzichten könne; denn da gebe es oft noch Überraschungen im Vergleich zu dem, was die Theorie vorhergesagt hat.

Alte Verfahren

Wenn Lenstras neuer Algorithmus wirklich viel schneller als der bisherige arbeiten sollte - bedeutet das dann nicht eine " Bedrohung " jener Verschlüsselungssysteme, die auf großen Zahlen, die wiederum das Produkt zweier vielstelliger Primzahlen sind, basieren? Und bei denen man sich bisher ja darauf verlassen konnte, es werde einfach unsinnig lange dauern, bis der eventuelle Code-Knacker herausgefunden hat, welche zwei Faktoren denn nun in der Ausgangszahl stecken?

Nun, vorerst hat man ja immer noch die Möglichkeit, die beiden Faktoren in so einem System so zu wählen, daß sie eng beieinander liegen. Und für derartig zusammengesetzte Zahlen arbeitet der Lenstra-Algorithmus ja auch nicht schneller als das QS-Verfahren.

Geheimdienstler in aller Welt können noch eine Zeit lang beruhigt ihre alten Verfahren einsetzen. Es sei denn, irgendwer hat sich insgeheim schon einen noch besseren Algorithmus ausgedacht - und ist so unfair, ihn einfach nicht zu publizieren.

* Peter Lange ist Wissenschaltsjournalist in München.