Acht Mikrocomputer auf der Suche nach Primzahlen:

Kleincomputer knacken Codes kostengünstig

05.09.1986

Hacker mit vergleichsweise schmalem Geldbeutel können jetzt an das Knacken schwieriger Geheimcodes gehen. Parallel operierende Kleinrechner haben In den USA gute Erfolge bei der Ermittlung von Primzahlen verzeichnet - einem Basisgebiet der Kryptografie.

Wahrscheinlich seit es überhaupt Computer gibt, haben Mathematiker aus aller Welt in den betriebsschwachen Stunden jener Maschinen nichts Besseres zu tun, als ihre "Rechenknechte" eifrig nach immer noch größeren, bislang unbekannten Primzahlen suchen zu lassen. Diese Beschäftigung ist allerdings nur scheinbar zweckfrei-spielerisch. Denn sie kann unter Umständen ernste Konsequenzen für die Sicherheit geheimzuhaltender, verschlüsselter Informationen nach sich ziehen.

Ernste Konsequenzen für die Sicherheit

Im allgemeinen benutzt man zum Ermitteln neuer Primzahlen Supercomputer; zum Beispiel eine "Cray" oder auch eine Maschine von Control Data. Doch jetzt wird aus den USA berichtet, daß auch eine Gruppe parallel operierender Kleinrechner recht Ordentliches leistet, läßt man sie wie bei der Suche nach Primzahlen große Zahlen in deren Faktoren zerlegen. Und eben dies ist eine Neuheit, die vielen Datensicherungsexperten zu denken geben dürfte.

Was ist geschehen? Der Mathematiker Robert D. Silverman von der Firma Mitre in Bedford, Massachusetts/USA, hat die 81stellige Dezimalzahl (2 (269)+1) mit Hilfe von acht "Sun"-Mikrocomputern in ihre einzelnen Faktoren zerlegt, wobei jede dieser Maschinen an die 150 Stunden aktiv war; übrigens nur "nebenbei", also vor allem in den Nachtstunden und an Wochenenden. Und damit hat Silverman immerhin einen Rekord gebrochen; denn die nun "faktorisierte" Zahl ist, so wird berichtet, die bisher größte "schwer zu bearbeitende" Zahl, die je mit Hilfe eines allgemeinen Faktorisierungs-Algorithmus in ihre Komponenten zerlegt werden konnte.

Neue Ideen mit neuen Algorithmen

Der Schlüssel zu diesem Fortschritt liegt nicht allein darin, daß moderne Mikrorechner inzwischen schon erstaunlich leistungsfähig sind, sondern auch im Bereich Software beziehungsweise Mathematik. Denn in den vergangenen Jahren wurden beim Ersinnen immer neuer Faktorisierungs-Algorithmen immer neue Ideen entwickelt - und so konnte Silverman denn auch eine besondere Variante eines neuen Algorithmus einsetzen, dessen Kern der Kalifornier Peter Montgomery von der Systems Development Corp. in Santa Monica erdacht hat. Es handelt sich dabei um eine Abwandlung des sogenannten "quadratischen Siebs", wobei das Gesamtproblem hier aber in einige voneinander unabhängige, auf mehreren Rechnern parallel bearbeitbare Teilstücke zerlegt wird.

Schnelle Ergebnisse auf billiger Hardware

Es steht zwar außer Frage, daß ein Supercomputer das gleiche Faktorisierungsproblem erheblich schneller als erst nach rund 150 Stunden bewältigt hätte, doch auf der anderen Seite macht Silvermanns Arbeit nun eines ganz klar: Man kann auch mit billiger Hardware rasch zu Ergebnissen kommen. Und dies wiederum bedeutet: Auch Leute mit vergleichsweise schmalem Geldbeutel haben ab jetzt eine "faire" Chance, unfaire Attacken auf Geheimcodes zu unternehmen. Und zwar auf solche, deren Sicherheit bisher darauf basierte, daß es astronomisch lange dauert, ehe man eine große Zahl faktorisiert hatte.

Doch nicht nur Unsicherheit können Mathematiker mit ihrem Suchen nach Primzahlen in die Welt der EDV tragen; umgekehrt können ihre Versuche, die Grenzen der bekannten Primzahl-Regionen immer weiter hinauszuschieben, auch wieder ein Stück Sicherheit bescheren. Sicherheit insofern, als eine erfolgreich abgeschlossene Primzahlensuche gleich auch ein Indiz dafür ist, daß der betreffende Rechner wirklich korrekt arbeitet. Was ja nicht ganz so selbstverständlich ist, wie bunte Hochglanzprospekte es gern suggerieren.

So hat die Firma Chevron Geosciences Co. in Houston unlängst einmal genau wissen wollen, ob ihr "Cray-X-MP" wirklich so korrekt rechnet, wie er eigentlich sollte. Und deshalb ließ man ihn so lange Zahlen verdauen, bis er am Ende die bislang größte überhaupt bekannte Primzahl ausspuckte; ein Monster von immerhin 65 050 Stellen.

Der Zehn-Millionen-Dollar-Gigant der texanischen Geowissenschaftler hatte mit der Ermittlung der Riesenzahl viel Arbeit, denn er mußte dazu 1,5 Billionen Einzelkalkulationen vollführen (1,5 mal 10 12). Damit war er aber nicht gleich auf Tage lahmgelegt, sondern allenfalls eine gemütliche Mittagspause lang, denn schon nach rund drei Stunden stand das Ergebnis fest.

Dieses Ergebnis ist nicht etwa eine gewöhnliche Primzahl, sondern eine sogenannte "Mersenne-Primzahl". Dabei handelt es sich um Primzahlen die sich alle in der Form (2 n-1) darstellen lassen. Und bei denen n gleichfalls eine Primzahl ist.

Ein "kleines" Beispiel für so eine Mersenne-Primzahl ist 127; denn hier ist der Exponent n gleich sieben. Bei der neugefundenen Zahl indes, es ist übrigens die dreißigste Mersenne-Primzahl, die die Welt heute kennt, hat der Exponent den Wert 216 091.

Bloß eine Primzahl zu finden, reicht natürlich nicht; es muß ein unabhängiges Team mit einem anderen Computer hinterher auch verifizieren, daß die gefundene Zahl in der Tat "prim" ist.

Neue Entdeckung nach neun Tagen

Dieser vergnüglichen Arbeit unterzog sich Stephen K. McGrogan von der Firma Elxsi in San Jose, Kalifornien. Mit einem eigenen Primzahlen-Prüfprogramm und einem Rechner seiner Firma versehen, war McGrogan rund neun Tage beschäftigt, ehe er die neue Entdeckung bestätigen konnte.

Wie spannend für Zahlen-Freaks dieses ewige Suchen nach immer noch größeren - und bisher vielleicht noch nicht entdeckten, weniger großen - Primzahlen zu sein scheint, zeigt McGrogans Bemerkung, er suche systematisch nach Mersenne-Primzahlen, die kleiner als die jetzt gefundene größte ihrer Art sind. Dazu entwickelt auch er einen Algorithmus, der das Testen von präsumptiven Primzahlen beschleunigen soll.

An der Neuentdeckung aus Houston ist noch bemerkenswert, daß sie sozusagen durch Zufall gemacht worden ist. Denn der - auf der Cray eingesetzte - Algorithmus zum Finden von Mersenne-Primzahlen ist so beschaffen, daß er nur dann einen "Treffer" erzielt, wenn die "Startzahl" zufällig eine ist, die zum Erfolg führt.

Das Programm zum Finden der Riesen-Primzahl stammt von David Slowinski von der Firma Cray. Auch ihn scheint die vordergründig nutzlose Suche nach immer größeren Primzahlen so sehr in ihren Bann geschlagen zu haben, daß er seine Software in der Freizeit immer noch weiter verbessert. Zur Zeit setzt er die "Version vier" ein - und die ist schon glatt dreißigmal schneller als die erste. Doch noch flotter soll die Rechnerei ablaufen, kann Slowinski nur erst einen der neuen "Cray-2"-Rechner einsetzen; an einem Programm speziell für diese Maschine arbeitet er jedenfalls schon.

* Peter Lange ist Fachjournalist in München