Elgamal-Kryptosystem

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

Das Elgamal-Kryptosystem (auch al-Dschamal-Kryptosystem) ist ein Schema zur Verschlüsselung, das auf dem mathematischen Problem des diskreten Logarithmus beruht. Elgamal ist ein asymmetrischer Verschlüsselungsalgorithmus aufbauend auf der Idee des Diffie-Hellman-Algorithmus, der mit diesen diskreten Logarithmen arbeitet.

Elgamal kann sowohl zur Signaturerzeugung als auch zum Verschlüsseln verwendet werden. Elgamal unterliegt keinem Patent.

Wie das Elliptische-Kurven-Kryptosystem basiert auch die Sicherheit des Elgamal-Kryptosystems auf der Annahme, dass diskrete Logarithmen eine Trapdoor-Einwegfunktion darstellen.

Inhaltsverzeichnis

1 Geschichte
2 Schlüsselerzeugung
3 Verschlüsselung
4 Entschlüsselung
5 Bewertung
- 5.1 Effektivität
- 5.2 Effizienz
6 Literatur

[Bearbeiten] Geschichte

Das Elgamal-Kryptosystem wurde 1985 von Taher Elgamal (Tahir al-Dschamal) entwickelt.

[Bearbeiten] Schlüsselerzeugung

Wie alle asymmetrischen Kryptosysteme verwendet auch das Elgamal-Kryptosystem einen öffentlichen und einen geheimen Schlüssel. Der öffentliche dient später der Verschlüsselung und kann veröffentlicht werden, während der geheime nur den Empfängern der Nachricht bekannt sein darf.

Es folgt nun eine genaue mathematische Beschreibung der Schlüsselerzeugung:

Zur Schlüsselerzeugung benötigt man eine Primzahl $p$ , sodass $p - 1$ einen großen Primfaktor $q$ besitzt. Typischerweise wird $q$ vorgewählt und man errechnet $p = 2 q + 1$ und prüft dann die Primzahleigenschaft von $p$ (Sophie-Germain-Primzahl). Außerdem benötigt man eine Primitivwurzel $g \, \bmod \, p$ der Ordnung $q$ und ein gleichverteilt zufälliges $a \in \{ 0, ..., p-2 \}$ . Man berechne außerdem $A = g^a \, \bmod \, p$ . Hierbei steht $mod$ für den Modulo-Operator. Für eine Erläuterung solcher Kongruenzbedingungen siehe Modulo.

Der öffentliche Schlüssel besteht nun aus dem Tripel $(p, g, A)$ . Der geheime Schlüssel entspricht $a$ .

Seien beispielhaft $p = 17$ und $a = 6$ . Als Primitivwurzel sei $g = 3$ gewählt. Man berechne $A = g^a \, \bmod \, p = 3^6 \, \bmod \, 17 = 15$ .

Somit ergibt sich im Beispiel der öffentliche Schlüssel $(p = 17, g = 3, A = 15)$ und der geheime Schlüssel $a = 6$ .

[Bearbeiten] Verschlüsselung

Verschlüsselung

Man kann sich eine Verschlüsselung so vorstellen, dass ein Text, etwa aus einem Buch, durch ein geeignetes Verfahren in eine Zeichenfolge gewandelt wird, die nicht mehr ohne größeren Aufwand lesbar ist.

Nebenstehende Abbildung veranschaulicht die Verschlüsselung von Klartexten mit asymmetrischen Kryptosystemen wie dem in diesem Artikel beschriebenen. Ein Klartext wird in einen Geheimtext unter Verwendung eines öffentlichen Schlüssels verwandelt. Zur Handhabung im Rechner verwendet man jedoch eine Folge von Zahlen, in die sich ein solcher Textabschnitt jedoch leicht verwandeln lässt.

Für das Elgamal-Kryptosystem wird nachfolgend dieser Prozess auf mathematischem Weg präzisiert:

Der Klartext $m$ ist aus der Menge ${0,..., p - 1}$ zu wählen. Man wähle nun zufällig ein $b \in \{ 1, ..., p-2 \}$ . Nun berechne man $B = g^b \, \bmod \, p$ und $c = A^bm \, \bmod \, p$ . Der Geheimtext besteht nun aus dem Paar $(B, c)$ .

In unserem Beispiel sei der Klartext $m = 9$ . Willkürlich sei $b = 5$ gewählt. So berechne sich $B = g^b \, \bmod \, p = 3^5 \, \bmod \, 17 = 5$ und $c = A^bm \, \bmod \, p = 1$ . Somit ergibt sich der Geheimtext $(B = 5, c = 1)$ .

[Bearbeiten] Entschlüsselung

Entschlüsselung

Auch die Entschlüsselung in asymmetrischen Kryptosystemen im Allgemeinen und im Elgamal-Kryptosystem im Speziellen ist nebenstehend in einer Abbildung dargestellt. Der zuvor durch Verschlüsselung entstandene Geheimtext wird unter Verwendung des geheimen Schlüssels wieder in den Klartext gewandelt.

Das genaue mathematische Vorgehen wird nun beschrieben:

Zur Entschlüsselung ist $B^xc \, \bmod \, p$ mit $x = p - 1 - a$ zu berechnen. Dies lässt sich folgendermaßen veranschaulichen:

$B^xc = B^{p-1-a}c \equiv g^{b(p-1-a)}A^bm$ $\equiv (g^{p-1})^b(g^a)^{-b}A^bm$ $\equiv$ (wegen kleiner fermatscher Satz) $\equiv A^{-b}A^bm$ $\equiv m \, \bmod \, p$ .

Im Beispiel gilt $m = B^{p-1-a}c \, \bmod \, p = 5^{10} \cdot 1 \, \bmod \, 17 = 9$ .

[Bearbeiten] Bewertung

[Bearbeiten] Effektivität

Momentan kann Elgamal als ein effektives Kryptosystem angesehen werden:

Wer diskrete Logarithmen berechnen kann, der kann Elgamal brechen („knacken“)! Es gibt derzeit jedoch keine effizienten Algorithmen zur Berechnung diskreter Logarithmen, so dass sich diese – für genügend große Zahlen – nicht in „annehmbarer“ Zeit berechnen lassen. Deshalb wird heute davon ausgegangen, dass das Elgamal-Kryptosystem nicht in vertretbarer Zeit gebrochen und demnach als sicher eingestuft werden kann.

Wer nun das Diffie-Hellman-Problem lösen kann, der kann das Elgamal-Kryptosystem brechen. Wer das Elgamal-Kryptosystem brechen kann, der kann $g^{ab} \, \bmod \, p$ bestimmen.

[Bearbeiten] Effizienz

Zur Verschlüsselung sind beim Elgamal-Kryptosystem zwei modulare Exponentiationen nötig: $A^b \, \bmod \, p$ und $g^b \, \bmod \, p$ . Da diese nachrichtenunabhängig sind, sind sie vorberechenbar und abspeicherbar. Die Folge ist nur noch eine Multiplikation modulo $p$ .

Das Verfahren erfordert zur Entschlüsselung eine modulare Exponentiation. Im Gegensatz zum Rabin-Kryptosystem lässt es sich nicht mit dem chinesischen Restsatz beschleunigen.

[Bearbeiten] Literatur

Johannes Buchmann: Einführung in die Kryptographie, 3., erweiterte Auflage. Springer, Berlin u. a. 2004, ISBN 3540405089
Dietmar Wätjen: Kryptographie, 1. Auflage. Spektrum Akademischer Verlag, Heidelberg, 2004, ISBN 3827414318

Von „http://de.wikipedia.org../../../e/l/g/Elgamal-Kryptosystem_192a.html“

Kategorie: Verschlüsselungsverfahren