Kryptographie VI

Kategorie: Technik

Schlüsselaustausch und Diskreter Logarithmus.

Zur Erinnerung: in der Kryptographie geht es um den verschlüsselten Austausch von Informationen (Teil 1). Public Key-Verfahren gelten zwar als sicherer, aber auch aufwendiger als Secret Key-Verfahren, weshalb man Public Key-Verfahren nur zur Übermittlung des geheimen Schlüssels verwendet (mit dem man dann ein Secret Key-Verfahren zur Übermittlung der eigentlichen Nachrichten verwendet, siehe Teil 2). Wir konzentrieren uns hier auf ein Public Key-Verfahren, nämlich den Diffie-Hellman-Schlüsselaustausch (Teil 5).

Im Diffie-Hellman-Verfahren nimmt man, daß der Schlüssel aus Elementen einer abelschen Gruppe (Teil 4) bestehen soll. (Zum Beispiel könnte man sich den Schlüssel aus ganzen Zahlen bestehend denken. Dies wäre aber eine sehr unsichere Methode, wie wir gleich sehen werden.)

Sei also eine abelsche Gruppe G und ein Element g aus G gegeben. Der Diffie-Hellman-
Schlüsselaustausch (Teil 5) zwischen Sender A und Empfänger B bestand darin, daß A und B sich ganze Zahlen a bzw. b denken, A dann das Gruppenelement 'ag' an B schickt, und B das Gruppenelement 'bg' an A schickt. Aus den ihnen vorliegenden Informationen können A und B dann jeweils den gemeinsamen Schlüssel 'abg' bestimmen, ohne daß dieser jemals übertragen worden ist.

Die Frage ist nun: kann ein Lauscher, der die übertragenen 'ag' und 'bg' mitgehört hat, daraus auf 'abg' schließen? Ein naheliegender Zugang zu diesem Problem wäre natürlich, aus der Kenntnis von 'g', 'ag' und 'bg' die Zahlen a und b zu berechnen, womit man dann natürlich auch 'abg' berechnen könnte. Dieses Problem heißt

Problem des diskreten Logarithmus: In einer abelschen Gruppe G seien ein Element 'g' und ein Vielfaches 'ag' gegeben. Berechne die ganze Zahl a.

Warum heißt a diskreter Logarithmus?
Ein Beispiel für eine abelsche Gruppe sind die positiven reellen Zahlen mit der Multiplikation. Da unsere Verknüpfung jetzt die Multiplikation (nicht die Addition) ist, sind die 'Vielfachen ag' dann natürlich die Potenzen g^a=g...g (und nicht die Vielfachen g+...+g). Die Berechnung von a aus g^a und g ist dann gerade die Berechnung des Logarithmus von g^a zur Basis g. In diesem Fall ist der diskrete Logarithmus also gerade der Logarithmus zur Basis g, wie man ihn aus der Schule kennt.

Sei etwa g=10 und h irgendeine Zehnerpotenz. Dann ist die Bestimmung derjenigen ganzen Zahl a, für die a-malige Multiplikation von g=10 gerade h ergibt, die Aufgabe den dekadischen Logarithmus von h zu bestimmen. Diese Aufgabe kann entweder jeder Taschenrechner lösen, oder man löst sie (weil h ja eine Zehnerpotenz ist) einfach durch Abzählen der Nullen in h.

In der Gruppe der positiven reellen Zahlen mit Multiplikation lassen sich Logarithmen also leicht berechnen, womit dann also auch der Diffie-Hellman-Schlüsselaustausch leicht zu knacken wäre.

Es gibt aber noch einen anderen Grund, warum man reelle Zahlen nicht gerne verwenden möchte: beim Rechnen mit reellen Zahlen muß man ständig mit Rundungsfehlern rechnen.

Deshalb verwendet man in der Kryptographie grundsätzlich nicht 'kontinuierliche' Gruppen wie die reellen Zahlen, sondern endliche Gruppen: diese haben den Vorteil, daß auch nach Rundungsfehlern beim Rechnen in aller Regel klar ist, welches das richtige Ergebnis ist.

Deshalb auch der Name diskreter Logarithmus: als diskret bezeichnet man in der Mathematik Strukturen, in denen die einzelnen Elemente einen Mindestabstand voneinander einhalten. (Zum Beispiel sind die ganzen Zahlen diskret, weil sie voneinander Abstand mindestens 1 haben. Die reellen Zahlen sind nicht diskret, weil es reelle Zahlen mit beliebig kleinen Abständen gibt.)

Ein Beispiel einer diskreten (unendlichen) Gruppe sind die ganzen Zahlen (mit der Addition als Verknüpfung). Für diese ist allerdings die Berechnung des diskreten Logarithmus noch einfacher als im vorigen Beispiel: hier geht es jetzt darum, aus 'ag' und 'g' die Zahl a zu berechnen, und dies ist natürlich eine einfache Divisionsaufgabe, die jeder 10-jährige lösen kann.

Wie man sieht, ist es für die naheliegenden Gruppen so, daß man leicht diskrete Logarithmen berechnen und damit dann auch den Diffie-Hellman-Schlüsselaustausch knacken kann.

Damit das Diffie-Hellman-Verfahren wirklich sicher ist, muß man also andere abelsche Gruppen finden, für die sich diskrete Logarithmen nicht (mit vernünftigem Aufwand) berechnen lassen. Darum soll es in den nächsten Teilen gehen.

Autor: Thilo· 0 Kommentare· Permalink· Trackback-URL

Tags: abelsche Gruppe· Diffie-Hellman· Diskreter Logarithmus· Schlüsselaustausch