Diskreter-Logarithmus-Problem

Diskreter-Logarithmus-Problem

In der Gruppentheorie 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 bildet eine Umkehrfunktion des diskreten Logarithmus. Als Vergleich: die stetige Exponentialfunktion ist eine Umkehrfunktion des gewöhnlichen Logarithmus.

Als ein Beispiel diene das Rechnen modulo n. Der diskrete Logarithmus ist hier die kleinste Lösung x der Gleichung a^x \equiv m \mod p

bei gegebenen natürlichen Zahlen m, a und der Primzahl p.

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

Inhaltsverzeichnis

Theorie

Allgemeine Definition

Es sei G eine endliche zyklische Gruppe mit Erzeuger g der Ordnung n. Dann ist die diskrete Exponentiation

\begin{align}
\exp_g: \mathbb{Z}/n\mathbb{Z} &\to G \\
 x &\mapsto g^x
\end{align}

ein Gruppenisomorphismus. Die zugehörige Umkehrfunktion

\begin{align}
\log_g\colon G &\to \mathbb{Z}/n\mathbb{Z}\\
x & \mapsto \log_g x
\end{align}

heißt diskreter Logarithmus zur Basis g.

Die bekannte Basiswechselformel bleibt gültig: sei h ein weiterer Erzeuger, dann ist

\log_h x = \log_g x \cdot \log_h g \mod n.

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

\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.

Sei p eine Primzahl und g mod p eine Primitivwurzel bzgl. der primen Restklassengruppe ( \mathbb{Z} /p \mathbb{Z} )^\times. Der diskrete Logarithmus (auch Index genannt) a einer Zahl A zur Basis g ist definiert als a=\operatorname{log}_g A bzw. a=\operatorname{ind}_g A, wobei A \equiv g^a \mod{p} gilt.

(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 den 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:

Beispiel

Als Beispiel diene die Primzahl p=11 und die sich dabei ergebende prime Restklassengruppe (\mathbb{Z} /11 \mathbb{Z})^\times=\{1,2,\ldots,10\}. Zur Primitivwurzel g=2 wird nun die Wertetabelle der diskreten Exponentiation bestimmt. Dies kann z. B. sehr schnell mit dem Square-and-Multiply-Algorithmus durchgeführt werden.

\begin{align}
2^0 &= 1 &\equiv\; & 1 &\mod{11}\\
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}
\end{align}
a 0 1 2 3 4 5 6 7 8 9
2a mod p \equiv A 1 2 4 8 5 10 9 7 3 6

Dass es sich bei g wirklich um eine Primitivwurzel handelt, ist an den paarweise verschiedenen diskreten Potenzen erkennbar. Mit anderen Worten, die gesamte prime Restklassengruppe kann mithilfe der diskreten Potenzen von g erzeugt werden. Durch Vertauschen der Zeilen und Sortieren erhält man die Wertetabelle des diskreten Logarithmus.

A 1 2 3 4 5 6 7 8 9 10
log2A 0 1 8 2 4 9 7 3 6 5

Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • DH-Protokoll — Der Diffie Hellman Schlüsselaustausch oder Diffie Hellman Merkle Schlüsselaustausch ist ein Protokoll aus dem Bereich der Kryptografie. Mit ihm erzeugen zwei Kommunikationspartner einen geheimen Schlüssel, den nur diese beiden kennen. Dieser… …   Deutsch Wikipedia

  • Diffie-Hellman — Der Diffie Hellman Schlüsselaustausch oder Diffie Hellman Merkle Schlüsselaustausch ist ein Protokoll aus dem Bereich der Kryptografie. Mit ihm erzeugen zwei Kommunikationspartner einen geheimen Schlüssel, den nur diese beiden kennen. Dieser… …   Deutsch Wikipedia

  • Diffie-Hellman-Algorithmus — Der Diffie Hellman Schlüsselaustausch oder Diffie Hellman Merkle Schlüsselaustausch ist ein Protokoll aus dem Bereich der Kryptografie. Mit ihm erzeugen zwei Kommunikationspartner einen geheimen Schlüssel, den nur diese beiden kennen. Dieser… …   Deutsch Wikipedia

  • Diffie-Hellman-Merkle-Algorithmus — Der Diffie Hellman Schlüsselaustausch oder Diffie Hellman Merkle Schlüsselaustausch ist ein Protokoll aus dem Bereich der Kryptografie. Mit ihm erzeugen zwei Kommunikationspartner einen geheimen Schlüssel, den nur diese beiden kennen. Dieser… …   Deutsch Wikipedia

  • Diffie-Hellman-Merkle-Schlüsselaustausch — Der Diffie Hellman Schlüsselaustausch oder Diffie Hellman Merkle Schlüsselaustausch ist ein Protokoll aus dem Bereich der Kryptografie. Mit ihm erzeugen zwei Kommunikationspartner einen geheimen Schlüssel, den nur diese beiden kennen. Dieser… …   Deutsch Wikipedia

  • Diffie-Hellman-Schlüsseltausch — Der Diffie Hellman Schlüsselaustausch oder Diffie Hellman Merkle Schlüsselaustausch ist ein Protokoll aus dem Bereich der Kryptografie. Mit ihm erzeugen zwei Kommunikationspartner einen geheimen Schlüssel, den nur diese beiden kennen. Dieser… …   Deutsch Wikipedia

  • Diffie-Hellman-Verfahren — Der Diffie Hellman Schlüsselaustausch oder Diffie Hellman Merkle Schlüsselaustausch ist ein Protokoll aus dem Bereich der Kryptografie. Mit ihm erzeugen zwei Kommunikationspartner einen geheimen Schlüssel, den nur diese beiden kennen. Dieser… …   Deutsch Wikipedia

  • Diffie-Hellman Key Exchange — Der Diffie Hellman Schlüsselaustausch oder Diffie Hellman Merkle Schlüsselaustausch ist ein Protokoll aus dem Bereich der Kryptografie. Mit ihm erzeugen zwei Kommunikationspartner einen geheimen Schlüssel, den nur diese beiden kennen. Dieser… …   Deutsch Wikipedia

  • Diffie-Hellman key exchange — Der Diffie Hellman Schlüsselaustausch oder Diffie Hellman Merkle Schlüsselaustausch ist ein Protokoll aus dem Bereich der Kryptografie. Mit ihm erzeugen zwei Kommunikationspartner einen geheimen Schlüssel, den nur diese beiden kennen. Dieser… …   Deutsch Wikipedia

  • Diffie Hellman — Der Diffie Hellman Schlüsselaustausch oder Diffie Hellman Merkle Schlüsselaustausch ist ein Protokoll aus dem Bereich der Kryptografie. Mit ihm erzeugen zwei Kommunikationspartner einen geheimen Schlüssel, den nur diese beiden kennen. Dieser… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”