Vor wenigen Jahren gab es in der Bundesrepublik erhebliche Probleme bei der Durchführung einer Volkszählung. Die erste Fassung des Gesetzes mußte auf höchstrichterliche Anweisung überarbeitet, werden. Auch danach wehrten sich noch einige Bürger dagegen. Erstaunlicherweise wird trotz der offensichtlich vorhandenen Sensibilität für den Schutz der persönlichen Daten weitgehend kritiklos hingenommen, daß Daten über unsere Person und unser Vermögen möglicherweise unzureichend geschätzt in öffentlichen Netzen Übertragen werden.
In letzter Zeit ist immer mehr die Rede davon, daß in wichtigen Institutionen der Wirtschaft und Bereichen des täglichen Lebens, vor allem im Geld- und Telefonverkehr, Informationen durch kryptographische Verfahren geschätzt werden sollen, bei denen "Public-Key"-Kryptosysteme zum Einsatz kommen. Sehr stark wird in diesem Zusammenhang das RSA-Verfahren propagiert (siehe Kasten). Es wurde im Jahre 1978 in einer gemeinsamen Arbeit der israelischen und amerikanischen Autoren Rivest, Shamir und Adleman [RSA78] vorgeschlagen.
Zum Zeitpunkt der Entdeckung des Verfahrens wurde geschätzt, daß zur Faktorisierung (Zerlegung in Primzahlen) einer 200-stelligen Zahl etwa 100 Millionen Jahre (eine Zahl mit 8 Nullen) notwendig sind, wobei man von der damaligen Geschwindigkeit der Rechner (etwa 106 Operationen pro Sekunde) und der Effizienz der damals bekannten Verfahren ausging. Rechnet man dies beispielsweise auf eine 138stellige Zahl um, so ergeben sich, ganz grob geschätzt, noch 5000 Jahre Rechenaufwand zum Knacken dieses Problems. Die Berechnung beruht auf folgenden "Überlegungen: Die Anzahl der Rechenschritte für die Faktorisierung einer n-stelligen Zahl ist ungefähr 10Radikal(ninn). Kann man in der Sekunde 106 Rechenschritte ausführen, so ergeben sich für die Dauer in Jahren Tn jeweils die folgenden Werte: T200=108 und T138= 5000. Die Angaben sind dem Buch [Denn83] "Denning D.R.E.: Cryptography and Data Security, Addison-Wesley, 1983" -entnommen.
Durch wesentliche Verbesserungen der Faktorisierungsalgorithmen und durch die inzwischen stark gestiegenen Rechnerleistungen gelang es Ende des Jahres 1989, eine 138 stellige Zahl innerhalb weniger Wochen zu faktorisieren. Mit extrem schnellen Rechnern dauerte die Primfaktoren-Zerlegung 100 stelliger Zahlen nur noch etwa 9 Stunden.
Diese Entwicklung ist schon seit längerem abzusehen. Einer der Beteiligten an den erwähnten Faktorisierungsversuchen, Prof. Riesel, befand deshalb schon vor einigen Jahren, daß der RSA-Algorithmus nicht dafür geeignet sei, als Grundlage kryptographischer Verfahren in der Praxis in größerem Rahmen eingesetzt zu werden. In seinem Buch 99Prime "Numbers and Computer Methods for Factorization" [Ries85] schreibt er in seiner zusammenfassenden Würdigung des RSA-Algorithmus sinngemäß: Es ist nicht möglich, die Wahrscheinlichkeit zu schätzen, mit der jemand in naher Zukunft eine Faktorisierungsmethode erfinden wird (oder vielleicht sogar schon erfunden hat), um eine Zahl N mit einem Aufwand zu faktorisieren, der zum Beispiel wie die Funktion C0(ln N)k wächst mit einer Konstanten co und einer natürlichen Zahl k. Angesichts der Fortschritte, die in den letzten Jahren auf diesem Gebiet gemacht wurden, ist diese Befürchtung sicher nicht unberechtigt.
Die Tatsache, daß nunmehr im kommerziellen Bereich der RSA-Algorithmus als Grundlage kryptographischer Verfahren verwendet werden soll, um Informationen und materielle Werte vor unberechtigten Zugriffen zu schützen, ist angesichts der Fortschritte bei der Rechengeschwindigkeit und der Verbesserung der Faktorisierungsalgorithmen äußerst bedenklich. Da man auf die Annehmlichkeiten, die man sich durch den Einsatzentsprechender Techniken erhofft, nicht verzichten will, stellt sich die Frage nach einem Ausweg aus dieser Situation.
Möglichkeit 1.: Man könnte, wie verschiedentlich auch schon vorgeschlagen, beim Einsatz des RSA-Algorithmus Zahlen verwenden, zu deren Darstellung man auf einem Rechner 512 Bits benötigt und die sich als Produkt zweier, nicht allgemein bekannter Primzahlen schreiben lassen. Bezeichnet die Zeit, die man braucht, um eine Zahl zu faktorisieren, die Produkt zweier Primzahlen ist und mit m Bits dargestellt werden kann, so ergibt sich
t512 = 3 * T138
Man beachte dabei, daß bei Tn n die Anzahl der Stellen bedeutet und bei tm m die Anzahl der Bits. Zur Faktorisierung einer Zahl, für deren Darstellung im Dualsystem 512 Stellen benötigt werden, braucht man also etwa drei Mal so lange wie für eine Zahl mit 138 Dezimalziffern.
Der Berechnung liegt jetzt die Komplexitätsabschätzung
tm=exp(1.5Radikal3[m * (ln m)2]
zu Grunde, die sich als Folge der in den letzten Jahren bekannt gewordenen effizienteren Faktorisierungsalgorithmen zu bestätigen scheint [BVA90]. Manche Vorschläge gehen dahin, 200-stellige Dezimalzahlen zu verwenden, zu deren Darstellung man zirka 640 Bits benötigt, oder gar Zahlen mit 1024 Bits. Dies ergibt
t640=50 * T138
t1024=1100 * T138
Die dadurch bedingten längeren Schlüssel haben natürlich negative Auswirkungen auf die Geschwindigkeit, mit der Nachrichten chiffriert beziehungsweise dechiffriert werden können. Angesichts der stets wachsenden Verarbeitungsgeschwindigkeit sollte dieses Argument jedoch nur sehr gering gewichtet werden.
Möglichkeit 2: Ein anderer Ausweg besteht darin, sich neuer kryptographischer Verfahren zu bedienen, die wesentlich schwerer zu brechen sind. In den letzten Jahren wurden beispielsweise Möglichkeiten gefunden, Erkenntnisse aus der Theorie der elliptischen Kurven (einem Spezialgebiet der reinen Mathematik, der algebraischen Zahlentheorie) in der Kryptographie einzusetzen. Im Kasten "Kryptographie mit elliptischen Kurven, wird erläutert, wie mit Hilfe daraus abgeleiteter Techniken der Benutzer A eine Nachricht m an B schickt. Dabei soll nur B die Nachricht empfangen können und es soll sichergestellt sein, daß diese Nachricht nur von A stammen kann. Genaueres findet man in [Kobl87].
Die vom RSA-Verfahren her bekannten kryptographischen Algorithmen lassen sich auf elliptische Kurven übertragen [Kob185] und dank neuerer Forschungsergebnisse in effizienter Weise auch auf Chips [BeGo89] realisieren. Prototypen, die ansprechende Leistungsmerkmale aufweisen, wurden an der University of Waterloo in Kanada und am Europäischen Institut für Systemsicherheit (E.I.S.S.) der Universität Karlsruhe entwickelt.
Bei in etwa gleichem Aufwand für das Ver- und Entschlüssen der übertragenen Nachrichten ist der für das Brechen dieses Verfahrens nötige Aufwand, nach dem augenblicklichen Wissensstand, noch um 14 Zehnerpotenzen höher als bei der Variante des RSA-Algorithmus, bei der eine Zahl n verwendet wird, zu deren Darstellung auf einem Rechner man 512 Bits benötigt. Im Vergleich mit dem RSA-Algorithmus mit 640 Bits beziehungsweise 1024 Bits schneidet das vorgeschlagene Verfahren ebenfalls noch sehr gut ab. Es zu knacken erfordert einen um zehn Zehnerpotenzen höheren Aufwand. Will man eine ähnliche Sicherheit erreichen wie mit dem RSA-Algorithmus bei Verwendung einer 138stelligen Zahl (512 Bits), so ist der Aufwand für das Ver- und Entschlüsseln wesentlich geringer. Hinzu kommt, daß die Schlüsselverwaltung bei Einsatz des obigen Protokolls wegfällt: jeder Teilnehmer kann seinen Schlüssel selber wählen und beliebig oft verändern. Also müssen auch keine Schlüssel von einer zentralen Stelle verteilt werden.
Einen Nachteil jedoch hat die Verwendung elliptischer Kurven: Die Nachricht wird dreimal, zwischen A und B hin und her geschickt, während bei Verwendung des RSA-Algorithmus ein einmaliges Senden genügt. Da jedoch noch keine Ansätze erkennbar sind, die eine deutliche Effizienzsteigerung bei Versuchen, es zu brechen, erwarten lassen, besitzt dieses Verfahren hinsichtlich der Sicherheit Vorzüge gegenüber allen sonst bekannten.
Technische Lösung legt in Reichweite
Obwohl man nicht garantieren kann, daß nicht doch innerhalb der nächsten zehn bis zwanzig Jahre Erkenntnisse in der Zahlentheorie die Grenzen der Leistungsfähigkeit der vorgeschlagenen Verfahren deutlich werden lassen, erscheinen Methoden die auf der Theorie elliptischer Kurven basieren, als ein vernünftiger Ausweg, der weiter verfolgt werden sollte. Die technische Lösung der anstehenden Probleme liegt in Reichweite, nachdem die wissenschaftlichen Grundlagen geklärt sind.
Die Ausschließlichkeit mit der zur Zeit noch auf das RSA-Verfahren gesetzt wird, das bald an die Grenzen seiner Leistungsfähigkeit stößt, ist unverständlich. Sein Einsatz in großem Rahmen hat nur Sinn, wenn man mit einiger Sicherheit garantieren kann, daß es noch zehn bis zwanzig Jahre seinen Zweck erfüllt. Sonst sind die Investitionen für die Einführung nicht zu rechtfertigen.
Kryptographie mit dem RSA-Algorithmus
Der RSA-Algorithmus beruht auf dem Rechnen im Restklassenring Zn. Dabei ist n eine Zahl, die sich als Produkt zweier Primzahlen p und q schreiben läßt: n = p * q.
Das Verschlüsseln einer Nachricht m, die als Element von Zn, dargestellt wird, erfolgt durch Potenzieren von m mit einer Zahl e, die zu n teinerfremd ist. Die verschlüsselte Nachricht me wird entschlüsselt, in dem sie nochmals mit einer Zahl d potenziert wird, die das zu e inverse Element in der Gruppe Z*n der Einheiten von Zn, ist. Da e teilerfremd zu n ist, existiert d und es gilt ed = de = 1 in Z. Man erhält damit (me)d =med = m.
Jeder Benutzer hat einen öffentlichen und einen geheimen Schlüssel, die ihm von einer zentralen Schlüsselverteilungsstelle zugeteilt werden. Der "geheime" Schlüssel ist nur dem jeweiligen Benutzer und möglicherweise der Schlüsselverteilungsstelle bekannt. Will der Benutzer A dem Benutzer B eine geheime Nachricht m senden, so verschlüsselt er m mit dem öffentlichen Schlüssel EB von B. Dies ergibt EB(m). B und nur B kann die verschlüsselte Nachricht EB(m) entschlüsseln, indem er seinen geheimen Schlüssel DB darauf anwendet: DB(EB(m)) = m.
Will der Benutzer A, dem Benutzer B eine Nachricht schicken, die nur von ihm stammen kann und die nur B entschlüsseln kann, so enkryptiert A die Nachricht m zuerst mit seinem geheimen Schlüssel DA und dann mit dem öffentlichen EB von B. A schickt EB(DA(m)) an B. B wendet darauf zuerst seinen geheimen Schlüssel DB und dann den öffentlichen EA von A an und erhält EA (DB(EB(DA(m) = EA(DA(m)=m.
Diese Art des Nachrichtenaustauschs wird erwähnt, weil sie im zweiten Kasten mit Hilfe eines anderen Verfahrens dargestellt wird, das jedoch keine zentrale Schlüsselverteilungsstelle kennt.
Beim RSA-Algorithmus sind außer dem öffentlichen Schlüssel eines jeden Benutzers die Zahl n und das Verfahren zur Ver- beziehungsweise Entschlüsselung allgemein bekannt. Die Sicherheit des Verfahrens hängt alleine von der Schwierigkeit ab, die Primfaktoren p und q zu ermitteln, wenn nur ihr Produkt n bekannt ist.
Kryptographie mit elliptischen Kurven
Man betrachtet die Menge G der Lösungen der Gleichung
y2 + y = x3
über einem endlichen Körper F der Charakteristik 2, das heißt 2*k = 0 für jedes Element keF. Ist n eine ungerade natürliche Zahl, so bildet die Menge G eine abelsche Gruppe mit N = 2n + 1 Elementen, die "elliptische Kurve" der obigen Gleichung.
( Mathematische Symbole)
Bekannt istN sowie die Abbildung, die m in ein Element Pm der elliptischen Kurve abbildet. Diese Abbildung sowie ihre Umkehrabbildung müssen einfach zu berechnen sein. Beispiele findet man in der oben erwähnten Literaturstelle. A wählt eine beliebige natürliche Zahl a<N, die zu N teilerfremd ist, und sendet P(...) an B. B wählt eine natürliche Zahl b > N, die ebenfalls zu N teilerfremd ist, und schickt P(...) an A. A berechnet daraus P(...)= P(...) und schickt dies wieder an B. Dabei ist a-1 beziehungsweise b-1 das Inverse von a beziehungsweise b im Restklassenring ZN. B ermittelt daraus P(...)= P(...) .Damit ist die Nachricht m bei B angekommen. Der Datenfluß ist in der eingeblockten. Formel dargestellt.
B kann den Schlüssel a von A nicht ermitteln, denn dazu müßte B den Logarithmus in der elliptische Kurve G berechnen, das heißt die Gleichung P(...) = Q lösen können, falls eine solche Lösung überhaupt existiert. Das gleiche gilt für A. Dieses Problem hat die Komplexität e0,5 dp, wobei dp die Anzahl der Stellen des größten Primteilers p von N ist. Nach dem aktuellen Stand der Forschung ist es bei geeigneter Wahl von n und damit von N = 2n + 1 mit den heute zur Verfügung stehenden Hilfsmitteln nicht lösbar. Verwendet man eine elliptische Kurve mit N = 2251 + 1 Elementen, so werden zur Ermittlung des diskreten Logarithmus etwa 1035 Rechenschritte benötigt, da der größte Primteiler 70 Dezimalstellen aufweist. Um eine ähnliche Sicherheit zu erreichen wie mit dem RSA-Algorithmus bei Verwendung einer 138stelligen Zahl (512 Bits) genügt eine elliptische Kurve mit N = 2 179+ 1 Elementen. N hat dann etwa 60 Dezimalstellen.
*Dr. Winfried Gleißner, Informatiker und Diplom-Mathematiker, beschäftigt sich privat mit Problemen der Kryptographie.
Winfried Gleißner