Verwickelte Codesysteme auf Basis extrem großer Schlüsselzahlen sind heute auch nicht mehr das, was sie mal waren: Denn seit eine emsige Industrie immer schnellere Computer entwickelt, wächst von Tag zu Tag die Gefahr, andere könnten den schönen, eigenen Code knacken. Wie erst jetzt wieder für alle Welt sichtbar wurde, als amerikanische Forscher sich hundertstellige Zahlen zur Bearbeitung vornahmen.
Hundertstellige Zahlen - diese sind, so sollte man sich immer vor Augen führen, nicht bloß einfach "um ein paar Nuller längere" als beispielsweise jene 71stelligen, die noch vor vier Jahren den Rekord der eben noch zerlegbaren Zahlen markierten. Sondern sie sind, grob gesagt, milliarden-milliarden-milliardenfach größer als jene und verhalten sich also zur 71stelligen Zahl wie etwa ein Gebirge zu einem Sandkorn.
Das Zerlegen sehr großer Zahlen in einzelne Faktoren ist eine Aufgabe deren Schwierigkeitsgrad im Einzelfall natürlich primär von eben diesen Faktoren abhängt. Denn daß etwa (10E100 + 2) als gerade Zahl Faktoren besitzt, ist sowieso trivial; und auch, daß in (10 E100 + 5) zumindest der Faktor 5 steckt, weiß praktisch jeder. Oder auch, daß (10E 100 - wegen der Quersumme 9 - durch 3 teilbar sein muß.
Ganz anders aber sieht es bei den wirklich harten Nüssen aus, nämlich bei Zahlen-Jumbos, die ihrerseits das Produkt von bloß zwei - annähernd gleich großen - Primzahlen sind Wie etwa jetzt die frisch zerlegte Zahl in der Größenordnung vor 10E 99, die sich als Produkt zweier Primzahlen mit 41 beziehungsweise 60 Stellen entpuppte.
Um dieser Monsterzahl auf ihre internen Faktoren zu kommen, mußten Rechner in den USA, den Niederlanden und Australien in konzentriertem Einsatz 26 Tage lang- kalkulieren und ihre Resultate bündeln. Doch damit haben sie nun etwas erreicht, was nach Meinung maßgeblicher Fachleute "eigentlich" erst hätte in ein paar Jahren möglich sein dürfen. Und von dem man in Kreisen von Datensicherheitsexperten und insbesondere von Kryptologen noch vor zehn Jahren meinte, es werde noch sehr, sehr lange dauern, ehe Schlüsselzahlen dieser Größenordnung in Gefahr geraten würden, zerlegt und mit hin quasi "entlarvt" zu werden.
Rechner spielen transkontinentales Puzzle
Wie schwer das Problem ist, hundertstellige Zahlen auch dann in ihre Faktoren zu zerlegen, wenn es von jenen sowie bloß zwei von jeweils mehr als 40 Stellen gibt, erläutern amerikanische Wissenschaftler mit der eingängigen Aussage, selbst die schnellsten der heutigen Rechner würden dafür im Soloeinsatz länger brauchen, als der Kosmos überhaupt existiert; also viele Milliarden Jahre. Jedenfalls dann, wenn sie, nach Art der Schulmathematik, schrittweise immer größere Primzahlen als mögliche Faktoren erproben und jedesmal prüfen, ob beim Dividieren der Ausgangszahl durch 3, 5, 7, 11 und so weiter vielleicht irgendwann mal kein Rest bleibt.
Beim Bearbeiten des 100-Stellen-Monsters durch Rechner aus drei Kontinenten wurde dieser Elementarmethode, ihrer Langsamkeit wegen, ein Verfahren vorgezogen, das Carl Pomerance von der Universität Georgia in Athens 1981 vorgestellt hat. Es trägt den Namen "quadratisches Siebb" und erinnert von dieser Benennung her an das bekannte Sieb des Eratosthenes", das übrigens auch gern als Meßlatte zur Bewertung der reinen CPU-Geschwindigkeit eines gegebenen Computers benutzt wird.
Hinter Pomerances quadratischem Sieb steckt im Kern die Idee, statt nach Faktoren der angezielten Zahl selber lieber nach Faktoren einer sorgsam ausgewählten Anzahl erheblich kleinerer Zahlen zu suchen. Und auf diesem Weg Hinweise zu gewinnen, aus denen sich nach Art eines Puzzles letztlich die gesuchte Information über die eigentlich interessierende Zahl zusammensetzen läßt. Wobei dem skizzierten 26-Tage und 100-Stellen-Projekt zugute kam, daß eine bestimmte algorithmische Form der Pomerance-Methode gut auf mehrere, separat arbeitende Rechner verteilt werden konnte. Und zwar auf Rechner durchaus unterschiedlicher Machart und Leistungsklasse: vom Supercomputer bis hinab zur schnellen Mehrprozessor-Arbeitsstation.
Diese insgesamt rund ein Dutzend Rechner wurden so programmiert, daß sie ihren jeweiligen Teil des Gesamtproblems automatisch immer dann weiterbearbeiteten, wenn sie gerade unproduktiv herumstanden; denn dadurch haben die Wissenschaftler verhindert, daß das Faktorisierungsprojekt der Universität Chicago sowie eines kalifornischen Computer-Forschungszentrums mit teuren Rechenzeitgebühren belastet wurde. Und man hat außerdem Verbindungen über ein Electronic-Mail-System geschaltet, die die Teilresultate aus aller Welt schließlich in Kalifornien zusammenführten.
Wie aber sah nun die Rekordzahl aus, deren Faktorenzerlegung jetzt erstmals gelungen ist? - Es handelt sich um jenen hundertstelligen Rest, der bleibt, dividiert man 11E 104 + 1 erst durch die Zahl 17 und dann durch 6 304 673 und nochmals durch 2.
Zwar leuchtet nicht unmittelbar ein, daß dieser Rest gerade 100 Stellen haben soll, doch mit Hilfe eines halbwegs brauchbaren Taschenrechners mit Zahlendarstellung bis hinauf zu etwa (9,9x 10E 99) und mit den Funktionen (ln x) und (eE x} läßt sich dies dennoch recht genau verifizieren. Auch ohne daß man dabei mit raffinierten Tricks aus Pomerances mathematischem Werkzeugkasten operieren müßte.
Nachdem der aktuelle Rekord erreicht war, nahmen Arjen K. Lenstra von der Universität Chicago und sein Kollege Mark S. Manasse vom Computer-Forschungszentrum in Palo Alto als nächsten Kandidaten eine 102stellige Zahl ins Visier; eine Zahl, von der sie meinten, sie sollte sich binnen etwa eines Monats zerlegen lassen.
Will man indes noch höher hinaus und vielleicht gar Zahlen mit 120 Stellen bearbeiten - wobei die ja dann wieder rund milliarden-milliardenmal so groß wären, wie die eben faktorisierte -, so müßte man dazu, meint Manasse, vermutlich schon mehrere Tausend Rechner einsetzen. Oder aber, wie Pomerance denkt, vielleicht "ganz einfach" eine Million herkömmlicher PC-Kleinrechner, die dann aber sogar schon mit 145stelligen Monstern relativ schnell fertig werden sollten.
Die Experten waren schnell beraten
Pomerance selber allerdings arbeitet in einer etwas anderen Richtung, denn er baut, wie man hört, derzeit eine speziell auf die Faktorenzerlegung großer Zahlen zugeschnittene, aber eher bescheidene Maschine: Sie soll nämlich bloß an die 50 000 Mark kosten - und dennoch mit 100stelligen Zahlen fertig werden. Während wieder ein anderer Forscher gebannt auf die Bildschirme von 100 PCs starrt und hofft, mit ihrer Hilfe Zahlen von immerhin auch schon 95 Stellen knacken zu können.
Und blickt man noch ein wenig weiter in die Zukunft, so kann man mit Pomerance bereits Spezialrechner erblicken, die, für dann aber entsprechend viel Geld, sogar Zahlen von 200 Dezimalstellen zerlegen sollen.
Doch egal, wie immens groß jene Zahlen dann auch immer sein mögen - allein schon die Tatsache, daß Wissenschaftler in aller Öffentlichkeit die Frage der Bearbeitung diskutieren, zeigt eines mit aller Deutlichkeit: wie weit die Kunst der Zahlenzerlegung in den letzten paar Jahren schon gediehen ist. Und wie schlecht doch jene Experten beraten waren, die sich erst vor zehn Jahren noch völlig sicher waren: Zum Schutz einer extrem sensiblen Nuklearanlage der US-Regierung müßten schon Codes genügen, die auf "nur" 103stelligen Zahlen basieren. Während man heute doch weiß: So einen 103er-Ziffernwurm dürften Manasse und Lenstra binnen kürzester Zeit zerlegt haben.