« vorheriger Beitrag  · nächster Beitrag »

15.05.08 · 13:13 Uhr

Kryptographie VII

Kategorie: Technik

Sicherer Schlüsselaustausch durch Rechnen mit Restklassen.

In der Kryptographie geht es um verschlüsselte Übertragung von Nachrichten. Während früher der Geheimhaltung des Schlüssels große Bedeutung zukam, braucht man sich seit den 70er Jahren mit der Verwendung des Diffie-Hellman-Verfahrens darüber keine Gedanken mehr machen.

Aus der Wikipedia: Der langen Tradition von Streichlisten und Codebüchern setzte das Diffie-Hellman-Verfahren ein Ende. Noch während des Zweiten Weltkrieges mussten die Benutzer der ausgeklügelten Verschlüsselungsmaschinen (zum Beispiel die Enigma) Codebücher mit sich führen, um für jeden einzelnen Tag des Jahres zu wissen, welchen Schlüssel der Absender verwendet. Wurde ein solches Codebuch geraubt, war die Verschlüsselung hinfällig. Besonders beim Militär war die Zuteilung und der Transport solcher hochgeheimer Codebücher stets das größte Sorgenkind.

Der Diffie-Hellman-Schlüsselaustausch (Teil 5) funktioniert nach folgendem Prinzip: A denkt sich eine Zahl a, B denkt sich eine Zahl b, dann schickt A g^a an B, der daraus g^ab berechnet, und B schickt g^b an A, der daraus g^ab berechnet.
g^ab ist dann der gemeinsame Schlüssel.

Dabei war g ein Element einer Gruppe G, zum Beispiel eine reelle Zahl.
(Als Verknüpfung in G nehmen wir hier die Multiplikation.)
Das Problem bei der Verwendung reellen Zahlen ist aber, daß ein Hacker (der g^a und g^b abgefangen hat) durch Logarithmieren a und b bestimmen könnte.
(Und daraus könnte er den Schlüssel g^ab berechnen.)

Eine sicherere Möglichkeit zum Schlüsselaustausch ist das Rechnen mit Restklassen.

Sei p eine fest gewählte natürliche Zahl. (Aus Gründen, die später einsichtig werden, verwendet man für p Primzahlen.)

Dann gibt es für die Division natürlicher Zahlen durch p die möglichen Reste 0,1,...,p-1.
Diese kann man nun auf die naheliegende Weise addieren, subtrahieren und multiplizieren: zum Beispiel: 5 + p-1 = 4 oder 2(p-1)=p-2.
(Nicht so offensichtlich ist die Division, die wir hier aber nicht brauchen werden.)
Man schreibt in der Regel 'modulo p' wenn man den Rest einer Zahl bei Division durch p meint. (Diese Schreibweise hatten wir auch schon in Teil 1 für die Cäsar-Chiffrierung benutzt.) Es ist also etwa 2p+3 = 3 modulo p oder 49 = 10 modulo 13.

Wenn man jetzt nicht Potenzen g^a, sondern ihre Restklassen modulo p betrachtet, wird das Logarithmieren plötzlich viel schwieriger:

Zum Beispiel p=23, g=5, a=17:
dann ist g^a=15 modulo p, wie man wie folgt recht schnell berechnen kann:
5¹⁷=5x5¹⁶=5x5²²²²=5x2²²²=5x(-7)²=5x3=15
(Hierbei haben wir 5²=2 und 2²²=-7 benutzt.)
Aber man versuche einmal die Gleichung 5^a=15 mod 23 zu lösen.
Wie man sieht, ist modulo p Logarithmieren erheblich schwieriger als Potenzieren (wofür wir nur 5 Multiplikationen benötigt haben).

Im Prinzip könnte man in unserem Beispiel die Gleichung natürlich durch Probieren lösen, weil es für a ja nur 22 verschiedene Werte gibt. (Nach dem Kleinen Satz von Fermat ist g^p-1=1 modulo p, womit es eine Lösung bereits im Bereich zwischen 1 und p-1 geben muß.)

In der Praxis verwendet man für p aber ca.300-stellige Zahlen, womit Probieren (auch mit Computer-Hilfe) also ausscheidet. (Ob es nicht doch andere Verfahren zum Berechnen des diskreten Logarithmus gibt, ist natürlich damit noch nicht bewiesen.)

Um es mathematisch zusammenzufassen: die Gruppe mit der wir hier arbeiten sind die Restklassen (außer 0) modulo p, die Verknüpfung ist die Multiplikation. (Die 0 müssen wir herauslassen, weil sonst Division nicht immer definert wäre.) In solch einer Gruppe ist (zumindest dem Anschein nach) die Berechnung des diskreten Logarithmus sehr aufwendig (und damit der Diffie-Hellman-Schlüsselaustausch sehr sicher, siehe Teil 6 ). Ob dies tatsächlich so ist, muß man natürlich überprüfen, indem man sich mögliche Strategien für Hacker-Angriffe anschaut und analysiert, wie praktikabel diese wären.

Übrigens: Computeralgebra-Programme, z.T. auch für den Schulunterricht geeignet, zu diesem Schlüsselaustausch wie auch zu einigen anderen kryptographischen Verfahren findet man in dem Artikel Sichere Kommunikation über unsichere Leitungen von StR Meiringer auf Seite 48-52 des Rundbriefs der Fachgruppe Computeralgebra.

 

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

Tags: Diffie-Hellman· Logarithmen· Square-and-multiply· Zahlenkongruenzen