Diskreter Logarithmus

In der Gruppentheorie und Zahlentheorie ist der diskrete Logarithmus das Analogon zum gewöhnlichen Logarithmus aus der Analysis; diskret kann in diesem Zusammenhang etwa wie ganzzahlig verstanden werden. Die diskrete Exponentiation in einer zyklischen Gruppe ist die Umkehrfunktion des diskreten Logarithmus. Als Vergleich: Die natürliche Exponentialfunktion auf den reellen Zahlen ist die Umkehrfunktion des natürlichen Logarithmus.

Ein wichtiger Anwendungsfall tritt beim Rechnen modulo p auf. Der diskrete Logarithmus von $m$ zur Basis $a$ ist hier der kleinste Exponent $x$ der Gleichung ${\textstyle a^{x}\equiv m\mod p}$ bei gegebenen natürlichen Zahlen $m$, $a$ und der Primzahl $p$. Zum Beispiel ist beim Rechnen modulo ${\textstyle 11}$ der diskrete Logarithmus von $5$ zur Basis $2$ gleich ${\textstyle 4}$, da ${\textstyle 2^{4}=16\equiv 5\mod 11}$ ist.

Da für den diskreten Logarithmus meist nur ineffiziente (im Sinne der Komplexitätstheorie) Algorithmen bekannt sind, während sich die Umkehrfunktion, die diskrete Exponentialfunktion, leicht (im Sinne der Komplexitätstheorie) berechnen lässt, eignet sich die diskrete Exponentialfunktion als Einwegfunktion in der Kryptografie. Anwendungsbeispiele sind u. a.

• Diffie-Hellman-Schlüsselaustausch
• Elgamal-Signaturverfahren
• DSA-Verfahren
• Elliptische-Kurven-Kryptosystem

Theorie

Allgemeine Definition

Es sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle (G,\circ)} eine endliche zyklische Gruppe mit Erzeuger Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle g} der Ordnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle n} . Dann ist die diskrete Exponentiation

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \begin{align} \exp_g\colon \Z/n\Z &\to G \\ x &\mapsto g^x \end{align}}

ein Gruppenisomorphismus. Die zugehörige Umkehrfunktion

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \begin{align} \log_g\colon G &\to \Z/n\Z\\ x & \mapsto \log_g x \end{align}}

heißt diskreter Logarithmus zur Basis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle g} .

Die bekannte Basiswechselformel bleibt gültig: Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h} ein weiterer Erzeuger, dann ist

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \log_h x = \log_g x \cdot \log_h g \mod n} .

Weiterhin gilt die folgende Beziehung für den diskreten Logarithmus, die der Funktionalgleichung des Logarithmus entspricht:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \log_g x + \log_g y = \log_g (x\circ y) \mod n} .

Prime Restklassengruppe

Von praktischem Nutzen in der Kryptografie ist der Spezialfall, wenn die zyklische Gruppe eine prime Restklassengruppe ist, insbesondere modulo Primzahlen.

Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle p} eine Primzahl und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g} eine Primitivwurzel modulo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle p} , also ein Erzeuger der primen Restklassengruppe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle (\Z /p \Z)^\times} . Der diskrete Logarithmus (auch Index genannt) einer zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle p} teilerfremden Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} zur Basis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g} ist definiert als die eindeutig bestimmte Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle a \in \{1,2,\dotsc,p-1\}} mit:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle g^a \equiv x \mod{p}}

und wird mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle a = \log_g x} bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle a = \operatorname{ind}_g x} bezeichnet (zur Schreibweise siehe Kongruenz (Zahlentheorie) und modulo).

Algorithmen zur Berechnung des diskreten Logarithmus

Es sind bisher keine schnellen Algorithmen zur Berechnung des diskreten Logarithmus bekannt. Deren Laufzeit verhielte sich polynomial zur Länge der Eingabe. Es gibt aber Algorithmen, die die Lösung gezielter finden als bloßes Ausprobieren. Aufgrund des angesprochenen Laufzeitverhaltens und der in der Kryptografie üblichen Größenordnungen (mehrere hundert Dezimalstellen in Numerus und Basis) spielen sie praktisch aber keine Rolle. Zu den bekanntesten Algorithmen zählen:

• Babystep-Giantstep-Algorithmus
• Pohlig-Hellman-Algorithmus
• Index-Calculus-Algorithmus
• Pollard-Rho-Methode
• Zahlkörpersieb

Beispiel

Als Beispiel diene die Primzahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle p = 11} und die zugehörige prime Restklassengruppe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle G = (\Z /11 \Z)^\times=\{1,2,\dotsc,10\}} . Zur Primitivwurzel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle g = 2} wird nun die Wertetabelle der diskreten Exponentiation bestimmt.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \begin{array}{lcrlrl} 2^1 &=& 2 &\equiv & 2 &\mod{11}\\ 2^2 &=& 4 &\equiv & 4 &\mod{11}\\ 2^3 &=& 8 &\equiv & 8 &\mod{11}\\ 2^4 &=& 16 &\equiv & 5 &\mod{11}\\ 2^5 &=& 32 &\equiv & 10 &\mod{11}\\ 2^6 &=& 64 &\equiv & 9 &\mod{11}\\ 2^7 &=& 128 &\equiv & 7 &\mod{11}\\ 2^8 &=& 256 &\equiv & 3 &\mod{11}\\ 2^9 &=& 512 &\equiv & 6 &\mod{11}\\ 2^{10} &=& 1024 &\equiv & 1 &\mod{11} \end{array}}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle a}	1	2	3	4	5	6	7	8	9	10
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle 2^a \mod 11}	2	4	8	5	10	9	7	3	6	1

Dass es sich bei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g} tatsächlich um eine Primitivwurzel modulo 11 handelt, ist an den paarweise verschiedenen diskreten Potenzen erkennbar. Mit anderen Worten, die gesamte prime Restklassengruppe kann mithilfe der diskreten Potenzen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g} erzeugt werden. Durch Vertauschen der Zeilen und Sortieren erhält man die Wertetabelle des diskreten Logarithmus.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle x}	1	2	3	4	5	6	7	8	9	10
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\textstyle \log_2 x}	10	1	8	2	4	9	7	3	6	5

Literatur

• Erich Härtter: Wahrscheinlichkeitsrechnung, Statistik und mathematische Grundlagen. Begriffe, Definitionen und Formeln. Verlag Vandenhoeck & Ruprecht, Göttingen 1987, ISBN 3-525-40731-9.