Kryptographie IX

Wie man verschlossene Kisten hin und her schickt.

Bis in die 70er Jahre galt das Problem der Schlüsselübertragung als der Schwachpunkt der Kryptographie. Es gab zwar seit langem Verschlüsselungs-Verfahren, die de facto 100%-ige Sicherheit bieten. Aber nur, solange der Schlüssel geheim bleibt. Der Schlüssel mußte zunächst übertragen werden; ein Problem, daß lange als unvermeidbar galt und ohne dessen Lösung 1976 durch Diffie und Hellman die heutige Internet-Kommunikation viel aufwendiger wäre.

Bis ins 19. Jahrhundert in Gebrauch war die Vigenere-Verschlüsselung: man benutzt einen vorher vereinbarten Text, um andere Texte zu verschlüsseln. Der vereinbarte Text gibt an, um wieviele Stellen im Alphabet die Buchstaben im zu verschlüsselnden Text verschoben werden.
Also, wenn man zum Beispiel als Schlüssel BAU festgelegt hat, dann wird im zu verschlüsselnden Text der 1. Buchstabe um 2, der 2. Buchstabe um 1 und der 3. Buchstabe um 21 verschoben (weil BAU der 2., 1. und 21. Buchstabe im Alphabet ist), danach der 4. Buchstabe wieder um 2 verschoben usw.
Zum Beispiel:

Die vereinbarten Texte müssen natürlich lang genug sein (also nicht nur 3 Buchstaben wie eben), um ein Entziffern durch Häufigkeitsanalyse unmöglich zu machen. Beliebt waren z.B. Kapitel aus der Bibel oder anderen populären Büchern. Wenn der Text in etwa genau so lang ist wie der zu verschlüsselnde Text, dann ist das Verfahren so gut wie 100% sicher, d.h. jemand, der den verschlüsselten Text abfängt, wird ihn nicht entschlüsseln können. Aber eben nur, wenn er den Schlüssel nicht kennt. Und dieser Schlüssel muß zunächst einmal sicher übertragen werden. Womit man im Grunde nichts gewonnen hat.

Im Prinzip gibt es eine Möglichkeit, Nachrichten sicher zu übertragen ohne vorher den Schlüssel übertragen zu müssen:

Ein gerne genutzter Vergleich: Alice will Bob eine verschlossene Kiste (mit einer Nachricht) schicken, ohne den Schlüssel zu schicken. Sie macht folgendes: sie sichert die Kiste mit einem Vorhängeschloß (und behält den Schlüssel) und schickt Bob die verschlossene Kiste. Bob kann die Kiste natürlich nicht öffnen, aber er sichert die Kiste mit einem zweiten Vorhängeschloß (und behält ebenfalls den Schlüssel) und schickt die doppelt gesicherte Kiste an Alice zurück. Alice öffnet ihr Schloß mit ihrem Schlüssel und schickt die (immer noch mit Bob’s Vorhängeschloß gesicherte) Kiste an Bob. Bob kann die Kiste jetzt mit seinem eigenen Schlüssel öffnen. Während des gesamten Vorgangs ist die Kiste nie unverschlossen unterwegs gewesen.

Quelle

Im Prinzip könnte man so Daten sicher übertragen. Nur ist es natürlich viel zu umständlich, alles zweimal hin- und herzuschicken.

Lange hielt man das Problem der Schlüsselübertragung für ein unvermeidbares Problem bei der Datenübertragung. Mitte der 70er Jahre wurden dann (eigentlich relativ einfache) asymmetrische Verschlüsselungsmethoden entwickelt, die dieses Problem umgehen. Im Nachhinein ist es natürlich paradox, daß diese Methoden gerade rechtzeitig entdeckt wurden, um dann ab den 80er Jahren die sichere Datenübertragung per Internet zu ermöglichen. Ohne die mathematischen Entdeckungen, die Diffie-Hellman 1976 und Rivest-Shaneson-Adleman Rivest-Shamir-Adleman 1977 machten, würde der Datenaustausch im Internet heute wesentlich zeitaufwendiger sein.

In Teil 7 hatten wir beschrieben, wie man das Rechnen mit Restklassen (mathematisch ausgedrückt: das Rechnen im Körper F_p^*) für den Schlüsselaustausch nach Diffie-Hellman benutzen kann.
Wie in Teil 6 gesagt, funktioniert der Diffie-Hellman-Schlüsselaustausch auch mit anderen abelschen Gruppen; vorausgesetzt, das Logarithmieren ist aufwendiger als das Potenzieren. (Entschlüsseln soll aufwendiger sein als Verschlüsseln.)

Es gibt zur Zeit in der Praxis zwei Typen von abelschen Gruppen, die für den Schlüsselaustausch verwendet werden. Zum einen, wie in Teil 7 beschrieben, die Restklassenkörper F_p^*, und zum anderen elliptische Kurven.

Um elliptische Kurven wird es in den nächsten beiden Folgen gehen. Heute nur so viel: elliptische Kurven sind Lösungsmengen einer Gleichung der Form y²=x³+ax+b mit fest gewählten Zahlen a,b (aus technischen Gründen erlaubt man nur a,b mit 4a³+27b²=0). Zwei Beispiele:

Zu dieser Kurve nimmt man noch einen gedachten Punkt im Unendlichen hinzu.
Und auf dieser Kurve definiert man eine abelsche Gruppe wie folgt:
– Nullelement ist der Punkt im Unendlichen
– Inverses Element zu (x,y) ist (x,-y), d.h. der an der x-Achse gespiegelte Punkt (wenn (x,y) auf der Kurve liegt, ist natürlich auch (x,-y) auf der Kurve)
– wenn drei Punkte wie im Bild links auf einer Gerade liegen, dann ist P+Q+R=0 (und wenn eine Gerade wie im Bild Mitte Tangente an P ist, dann ist 2Q+P=0).
Mit anderen Worten P+Q ist gerade -R, d.h. der an der x-Achse gespiegelte dritte Schnittpunkt der Gerade mit der Kurve. (Diese Definition setzt natürlich implizit voraus, daß es genau drei Schnittpunkte bzw. im Tangenten-Fall genau zwei Schnittpunkte gibt. Das folgt aber aus dem Satz von Bezout.)

Mit dieser Verknüpfung wird die Elliptische Kurve eine abelsche Gruppe (der Beweis des Assoziativgesetzes ist eine sehr aufwendige Rechnung, auf die ich lieber verzichte), die man für den Diffie-Hellman-Schlüsselaustausch verwenden kann. Mehr zu elliptischen Kurven und ihrer Rolle in Mathematik und Kryptographie in der nächstan Folge.

Teil 1, Teil 2,Teil 3, Teil 4, Teil 5, Teil 6, Teil 7, Teil 8