Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


23. Kryptologie



Kryptosysteme mit öffentlichen Schlüsseln

Bei kommerziellen Anwendungen, wie etwa beim elektronischen Kapitaltransfer und bei der (echten) Computerpost, ist das Problem der Schlüsselverteilung sogar noch komplizierter als bei den traditionellen Anwendungen der Kryptographie. Die Aussicht, jeden Bürger mit langen, oft zu ändernden Schlüsseln versorgen zu müssen, wobei gleichzeitig sowohl die Sicherheit als auch die Rentabilität zu gewährleisten sind, erschwert sicher die Entwicklung solcher Systeme. In jüngster Zeit wurden jedoch Verfahren entwickelt, die das Problem der Schlüsselverteilung vollständig zu beseitigen versprechen. Solche Systeme, die Kryptosysteme mit öffentlichen Schlüsseln oder auch Public-Key-Systeme genannt werden, dürften wahrscheinlich in naher Zukunft eine weite Verbreitung finden. Eines der herausragendsten dieser Systeme beruht auf einigen der von uns betrachteten arithmetischen Algorithmen, weshalb wir uns seine Arbeitsweise genauer ansehen wollen.

Die Idee der Kryptosysteme mit öffentlichen Schlüsseln besteht in der Verwendung eines »Telefonbuchs« mit Schlüsseln für die Verschlüsselung. Jedermanns Schlüssel für die Verschlüsselung (mit P bezeichnet) ist öffentlich bekannt; der Schlüssel einer Person könnte zum Beispiel neben ihrer Nummer im Telefonbuch angegeben sein. Jedermann besitzt außerdem einen geheimen Schlüssel, der für die Entschlüsselung benutzt wird; dieser geheime Schlüssel (mit S bezeichnet) ist niemandem sonst bekannt. Um eine Botschaft M zu übermitteln, sucht der Absender den öffentlichen Schlüssel des Empfängers heraus, benutzt ihn, um die Botschaft zu verschlüsseln, und übermittelt dann die Botschaft. Wir wollen die verschlüsselte Botschaft (Chiffretext) mit C = P(M) bezeichnen. Der Empfänger verwendet seinen privaten Schlüssel für das Entschlüsseln der Botschaft. Damit dieses System funktioniert, müssen zumindest die folgenden Bedingungen erfüllt sein:

  1. S(P(M)) = M für jede Botschaft M.
  2. Alle Paare (S, P) sind verschieden.
  3. Die Ableitung von S aus P ist ebenso schwer wie das Entschlüsseln von M ohne Kenntnis des Schlüssels S.
  4. Sowohl S als auch P lassen sich leicht berechnen.

Die erste Bedingung ist eine grundlegende kryptographische Eigenschaft, die nächsten beiden gewährleisten die Sicherheit und die vierte die praktische Anwendbarkeit des Systems.

Dieses allgemeine Schema wurde 1976 von W. Diffie und M. Hellman angegeben, doch sie verfügten über keine Methode, die allen diesen Bedingungen genügt hätte. Eine derartige Methode wurde bald danach von R. Rivest, A. Shamir, L. Adleman entdeckt. Ihr Schema, das als RSA-Kryptosystem mit öffentlichen Schlüsseln bekannt geworden ist, beruht auf arithmetischen Algorithmen, die auf sehr große ganze Zahlen angewandt werden. Der Schlüssel P für die Verschlüsselung ist das Paar ganzer Zahlen (N, p), und der Schlüssel für die Entschlüsselung ist das Paar ganzer Zahlen (N, s), wobei s geheimgehalten wird. Hierfür sollen sehr große Zahlen verwendet werden (typisch wäre etwa, daß N aus 200 Ziffern besteht und p und s aus 100 Ziffern). Die Verfahren der Verschlüsselung und Entschlüsselung sind dann einfach: Zuerst wird die Botschaft in Zahlen zerlegt, die kleiner als N sind (zum Beispiel indem von der binären Zeichenfolge, die der Kodierung der Zeichen der Botschaft entspricht, jedesmal lg N Bits betrachtet werden). Danach werden diese Zahlen unabhängig voneinander zu einer Potenz modulo N erhoben: Um eine Botschaft (bzw. einen Teil einer Botschaft) M zu verschlüsseln, berechne man C = P(M) = Mp mod N, und um einen Chiffretext C zu entschlüsseln, berechne man M = S(C) = Cs mod N. In Kapitel 36 untersuchen wir, wie diese Berechnung erfolgen kann; wiewohl das Rechnen mit aus 200 Ziffern bestehenden Zahlen beschwerlich sein kann, bedeutet die Tatsache, daß wir nur den nach der Division durch N verbleibenden Rest benötigen, daß die Zahlen nicht zu groß werden, auch wenn Mp und Cs selbst außerordentlich große Zahlen sind.

Eigenschaft 23.1 Im RSA-Kryptosystem kann eine Botschaft in linearer Zeit verschlüsselt werden.

Für lange Botschaften kann die Länge der Schlüssel-Zahlen als konstant angesehen werden; dies ist ein Implementationsdetail. Weiterhin erfolgt das Erheben einer Zahl in eine Potenz in konstanter Zeit, da die Zahlen eine »konstante« Länge nicht überschreiten dürfen. Diese Argumentation kaschiert natürlich viele bei der Implementation auftretende Probleme, die mit dem Rechnen mit langen Zahlen zusammenhängen; die Kosten dieser Operationen erschweren natürlich die Verbreitung dieses Verfahrens. w.z.b.w.

Die obige Bedingung (iv) ist demzufolge erfüllt, und die Einhaltung von Bedingung (ii) kann leicht erreicht werden. Wir müssen noch gewährleisten, daß die Kryptovariablen N, p und s so gewählt werden können, daß sie den Bedingungen (i) und (iii) genügen. Um das nachzuweisen, wäre eine Darlegung von Problemen aus der Zahlentheorie notwendig, die über den Rahmen dieses Buches hinausgehen würde; wir können jedoch die Grundidee skizzieren. Zuerst ist es erforderlich, drei große (ungefähr 100 Ziffern besitzende) »zufällige« Primzahlen zu erzeugen; die größte ist dann s, und die beiden anderen wollen wir x und y nennen. Dann wird N als das Produkt von x und y gewählt, und p wird so gewählt, daß ps mod (x - 1)(y - 1) = 1 gilt. Man kann beweisen, daß für derartige N, p und s für alle Botschaften M Mps mod N = M gilt.

Zum Beispiel könnte bei Benutzung unserer Standard-Kodierung die Botschaft ATTACK AT DAWN der aus 28 Ziffern zusammengesetzten Zahl

0120200103110001200004012314

entsprechen, da A der erste Buchstabe (01) im Alphabet ist, T der zwanzigste Buchstabe (20) usw. Damit nun der Umfang des Beispiels klein bleibt, beginnen wir mit einigen zweistelligen Primzahlen (anstatt mit 100-stelligen, wie es gefordert wird): Wir wählen x = 47, y = 79 und s = 97. Diese Werte führen zu N = 3713 (dem Produkt von x und y) und p = 37 (der einzigen ganzen Zahl, die den Rest 1 liefert, wenn sie mit 97 multipliziert und dann durch 3588 dividiert wird). Um nun die Botschaft zu verschlüsseln, zerlegen wir sie in vier Ziffern lange Teilstücke und erheben diese in die p-te Potenz (modulo N). Dies liefert die verschlüsselte Version

1404293235360001328422802235.

Das heißt, es ist 012037 == 1404,200137 == 2932,031137 == 3536 (mod 3713) usw. Der Prozeß der Entschlüsselung ist der gleiche, nur daß s anstelle von p verwendet wird. Somit erhalten wir wieder die ursprüngliche Botschaft, da 140497 == 0120,293297 == 2001 (mod 3713) usw. gilt.

Der wesentliche Teil der erforderlichen Berechnungen entfällt auf die Verschlüsselung der Botschaft, wie in der obigen Eigenschaft 23.1 erörtert wurde. Doch es gibt überhaupt kein Kryptosystem, wenn es nicht möglich ist, die Schlüsselvariablen zu berechnen. Obwohl hierzu sowohl hochentwickelte Hilfsmittel aus der Zahlentheorie als auch relativ ausgeklügelte Programme für die Behandlung großer Zahlen benötigt werden, ist die für die Berechnung der Schlüssel notwendige Zeit meist kleiner als das Quadrat ihrer Länge (und nicht proportional zu ihrer Größe, was unannehmbar wäre).

Eigenschaft 23.2 Die Schlüssel für das RSA-Kryptosystem können ohne übermäßigen Berechnungsaufwand erzeugt werden.

Auch hierfür werden gewisse auf der Zahlentheorie beruhende Methoden benötigt, deren Darlegung über den Rahmen dieses Buches hinausgehen würde; es erweist sich, daß jede große Primzahl erzeugt werden kann, indem zuerst eine große Zufallszahl erzeugt wird und dann an dieser Stelle beginnend die folgenden Zahlen testet, bis eine Primzahl gefunden wird. Mit Hilfe einer einfachen Methode kann für eine beliebige Zahl eine Berechnung ausgeführt werden, mit der mit einer Wahrscheinlichkeit von 50% »bewiesen« werden kann, daß die zu prüfende Zahl keine Primzahl ist. (Eine Zahl, die keine Primzahl ist, übersteht 20 Anwendungen dieses Tests in weniger als einem von einer Million Fällen, 30 Anwendungen in weniger als einem von einer Milliarde Fällen.) Der letzte Schritt ist die Berechnung von p; es zeigt sich, daß eine Variante des Euklidischen Algorithmus (siehe Kapitel 2) genau das ist, was gebraucht wird. w.z.b.w.

Wir erinnern daran, daß der Schlüssel für die Entschlüsselung s (und die Faktoren x und y von N) geheimgehalten werden müssen und daß der Erfolg der Methode davon abhängt, daß der Kryptoanalytiker nicht in der Lage ist, bei gegebenen N und p den Wert von s zu finden. Nun ist es zwar für unser kleines Beispiel einfach festzustellen, daß 3713 = 47 * 79 ist, doch wenn N eine Zahl mit 200 Stellen ist, gibt es kaum Hoffnung, ihre Faktoren zu finden. Das heißt, daß es schwer zu sein scheint, ausgehend von der Kenntnis von p (und N) s zu berechnen, doch noch niemand konnte beweisen, daß dies so ist. Offenbar erfordert die Bestimmung von s aus p die Kenntnis von x und y, und offenbar ist es erforderlich, N in Faktoren zu zerlegen, um x und y zu berechnen. Die Zerlegung von N in Faktoren gilt jedoch als sehr kompliziert: Die besten bekannten Algorithmen für die Zerlegung in Faktoren würden beim gegenwärtigen Stand der Technik Millionen von Jahren benötigen, um eine 200-stellige Zahl in Faktoren zu zerlegen.

Eine günstige Eigenschaft des RSA-Systems besteht darin, daß die komplizierten Berechnungen, die N, p und s betreffen, für jeden Anwender, der sich an dem System beteiligt, nur einmal ausgeführt werden müssen, während die wesentlich häufigeren Operationen der Ver- und Entschlüsselung nur das Zerlegen der Botschaft und die Anwendung der einfachen Prozedur des Potenzierens erfordern. Diese rechnerische Einfachheit macht in der Kombination mit all den Zweckmäßigkeitsmerkmalen, die Kryptosysteme mit öffentlichen Schlüsseln aufweisen, dieses System für sichere Kommunikationen sehr attraktiv, besonders für Computersysteme und Netzwerke.

Die RSA-Methode besitzt ihre Nachteile: Die Prozedur des Potenzierens ist im Vergleich zu kryptographischen Standards ziemlich aufwendig, und - was schlimmer ist - es kann nicht ausgeschlossen werden, daß es doch möglich ist, unter Benutzung dieser Methode verschlüsselte Botschaften zu knacken. Dies gilt für viele Kryptosysteme: Ein kryptographisches Verfahren muß ernsthaften kryptoanalytischen Angriffen standhalten, bevor es ohne Bedenken benutzt werden kann.

Für die Implementation von Kryptosystemen mit öffentlichen Schlüsseln wurden einige weitere Methoden vorgeschlagen. Einige der interessantesten davon hängen mit einer wichtigen Klasse von Problemen zusammen, die im allgemeinen als sehr schwierig gelten (obwohl dies nicht mit Sicherheit bekannt ist) und die wir in Kapitel 45 erörtern werden. Diese Kryptosysteme haben die interessante Eigenschaft, daß ein erfolgreicher Angriff Einblicke vermitteln könnte, wie bestimmte bekannte, schwierige, ungelöste Probleme gelöst werden könnten (wie im Falle der Zerlegung in Faktoren bei der RSA-Methode). Diese Verbindung zwischen der Kryptologie und grundlegenden Forschungsgegenständen der Informatik hat zusammen mit den potentiellen Möglichkeiten einer breiten Anwendung der Kryptographie mit öffentlichen Schlüsseln bewirkt, daß auf diesem Gebiet gegenwärtig aktive Forschungsarbeit geleistet wird.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]