Diskreter Logarithmus

Kernidee und Bedeutung

Der diskrete Logarithmus ist in Gruppentheorie und Zahlentheorie das Gegenstück zum gewöhnlichen Logarithmus aus der Analysis. „Diskret“ kann hier etwa als „ganzzahlig“ verstanden werden. In einer endlichen zyklischen Gruppe ist die diskrete Exponentiation die Umkehrfunktion des diskreten Logarithmus, ähnlich wie die natürliche Exponentialfunktion auf den reellen Zahlen die Umkehrfunktion des natürlichen Logarithmus ist.

Besonders wichtig ist der diskrete Logarithmus beim Rechnen modulo einer Primzahl p. Dabei sucht man zu gegebenen natürlichen Zahlen m und a sowie einer Primzahl p den kleinsten Exponenten x, der die Kongruenz a^x ≡ m mod p erfüllt. Eine Kongruenz modulo p bedeutet, dass zwei Zahlen beim Teilen durch p denselben Rest haben.

Der diskrete Logarithmus ist für die Kryptografie bedeutsam, weil für seine Berechnung meist nur ineffiziente Algorithmen bekannt sind, während die Umkehrfunktion, also die diskrete Exponentialfunktion, leicht berechnet werden kann. Dadurch eignet sich die diskrete Exponentialfunktion als Einwegfunktion: Vorwärts lässt sie sich gut berechnen, rückwärts aber praktisch schwer umkehren. Anwendungen sind unter anderem der Diffie-Hellman-Schlüsselaustausch, das Elgamal-Signaturverfahren, das Schnorr-Signaturverfahren, das DSA-Verfahren und Elliptische-Kurven-Kryptosysteme.

Allgemeine Definition

Sei (G, ∘) eine endliche zyklische Gruppe mit Erzeuger g der Ordnung n. „Zyklisch“ bedeutet, dass alle Elemente der Gruppe durch wiederholtes Anwenden der Gruppenoperation auf einen Erzeuger g entstehen. Die Ordnung n ist die Anzahl der Elemente der Gruppe beziehungsweise die kleinste positive Zahl n mit g^n als neutralem Element.

Mit der Restklassengruppe Z/nZ ist die diskrete Exponentiation als Abbildung exp_g: Z/nZ → G, x ↦ g^x definiert. Diese Abbildung ist ein Gruppenisomorphismus, also eine strukturtreue Eins-zu-eins-Zuordnung zwischen den beiden Gruppen. Die zugehörige Umkehrfunktion log_g: G → Z/nZ, x ↦ log_g x heißt diskreter Logarithmus zur Basis g.

Die bekannte Basiswechselformel bleibt auch beim diskreten Logarithmus gültig. Ist h ein weiterer Erzeuger, dann gilt: log_h x = log_h g · log_g x mod n. Außerdem gilt eine Beziehung, die der Funktionalgleichung des gewöhnlichen Logarithmus entspricht: log_g x + log_g y = log_g(x ∘ y) mod n. Das bedeutet: Die Verknüpfung zweier Gruppenelemente entspricht beim Logarithmus der Addition ihrer diskreten Logarithmen modulo n.

Prime Restklassengruppe

Für die Kryptografie ist besonders der Fall wichtig, in dem die zyklische Gruppe eine prime Restklassengruppe ist, vor allem modulo einer Primzahl. Sei p eine Primzahl und g eine Primitivwurzel modulo p. Eine Primitivwurzel ist ein Erzeuger der primen Restklassengruppe (Z/pZ)^×, also der Gruppe der zu p teilerfremden Restklassen modulo p.

Der diskrete Logarithmus einer zu p teilerfremden Zahl x zur Basis g wird in diesem Zusammenhang auch Index genannt. Er ist die eindeutig bestimmte Zahl a aus der Menge {1, 2, ..., p−1}, für die gilt: g^a ≡ x mod p. Man schreibt a = log_g x oder a = ind_g x.

Diese Definition macht deutlich, dass der diskrete Logarithmus im modularen Rechnen nicht irgendeine reelle Zahl ist, sondern ein Exponent aus einem endlichen Wertebereich. Gesucht wird also, welche Potenz des Erzeugers g das Element x der Restklassengruppe ergibt.

Berechnung

Für die Berechnung des diskreten Logarithmus sind bisher keine schnellen Algorithmen bekannt, deren Laufzeit polynomial zur Länge der Eingabe wäre. Es gibt zwar Verfahren, die gezielter vorgehen als bloßes Ausprobieren, doch wegen ihres Laufzeitverhaltens und der in der Kryptografie üblichen Größenordnungen spielen sie praktisch kaum eine Rolle. In solchen Anwendungen können Numerus und Basis mehrere hundert Dezimalstellen haben.

Zu den bekanntesten Algorithmen zur Berechnung des diskreten Logarithmus zählen der Babystep-Giantstep-Algorithmus, der Pohlig-Hellman-Algorithmus, der Index-Calculus-Algorithmus, die Pollard-Rho-Methode und das Zahlkörpersieb. Ihre Existenz zeigt, dass man nicht völlig blind suchen muss; die Grundschwierigkeit des Problems bleibt für große Eingaben aber zentral für kryptografische Anwendungen.

Beispiel modulo 11

Ein Beispiel verwendet die Primzahl p = 11 und die prime Restklassengruppe G = (Z/11Z)^× = {1, 2, ..., 10}. Als Primitivwurzel wird g = 2 genommen. Die diskrete Exponentiation liefert die Werte: 2^1 ≡ 2 mod 11, 2^2 ≡ 4 mod 11, 2^3 ≡ 8 mod 11, 2^4 = 16 ≡ 5 mod 11, 2^5 = 32 ≡ 10 mod 11, 2^6 = 64 ≡ 9 mod 11, 2^7 = 128 ≡ 7 mod 11, 2^8 = 256 ≡ 3 mod 11, 2^9 = 512 ≡ 6 mod 11 und 2^10 = 1024 ≡ 1 mod 11.

Die Potenzen von 2 ergeben also nacheinander alle Elemente der Gruppe {1, 2, ..., 10}. Daran erkennt man, dass 2 tatsächlich eine Primitivwurzel modulo 11 ist. Durch Vertauschen und Sortieren der Zuordnung erhält man die Wertetabelle des diskreten Logarithmus zur Basis 2: log_2 1 = 10, log_2 2 = 1, log_2 3 = 8, log_2 4 = 2, log_2 5 = 4, log_2 6 = 9, log_2 7 = 7, log_2 8 = 3, log_2 9 = 6 und log_2 10 = 5.

Damit sieht man konkret: Der diskrete Logarithmus fragt nach dem Exponenten, mit dem eine Basis potenziert werden muss, um ein bestimmtes Element modulo p zu erhalten. Zum Beispiel ist log_2 5 = 4 modulo 11, weil 2^4 = 16 und 16 ≡ 5 mod 11 gilt.