Wie alle Kategorien asymmetrischer Verfahren bietet auch das Diskrete-Logarithmus Verfahren Möglichkeiten digitale Signaturen zu erstellen. Hier am Beispiel des El Gamal Algorithmus.

Überblick: Anwendung asymmetrischer Verfahren

El Gamal digitale Signatur

Bermerkungen

1. 1985 vorgeschlagen
2. ist Basis für den weit verbreiteten Digital Sigature Algorithem (DSA)
3. Basiert auf dem DLP

Phase 1: Schlüsselerzeugung

1. Wähle große Primzahl p
2. Wähle primitives Element Alpha in Z_P^*
3. Wähle zufälliges Element a aus {2, 3, ..., p-2}.
4. Berechne Beta = Alpha^a mod p
5.  Kpub = (p, Alpha, Beta) Kpriv = a

Phase 2: Signaturerzeugung

1. Wähle zufälliges K aus { 2, 3, ..., p-2 } so dass: ggT( K, p-1) = 1 gilt.
2. Berechne Signatur: sig_Kpriv( x, K ) = ( Delta, Gamma)

Delta = Alpha^K mod  p

Gamma = (x - a * Delta) * K^-1 mod p-1

Phase 3: Verifikation

ver( x, (Delta, Gamma) = Ja oder Nein

Beta^Delta * Delta^Gamma = Alpha^x mod p falls die Signatur gültig ist.

funktionaler Beweis

 Beta^Delta * Delta^Gamma = (Alpha^a)^Delta * (Alpha^K)^Gamma = Alpha^a*Delta * Alpha^{K*((x -a*Delta)*K^-1 mod p-1) mod p} = Alpha^a*Delta * Alpha^{(x-a*Delta)*K*K^-1 mod p-1} mod P = Nach kleinem Fermat: Alpha^p-1 ist 1 mod p folgt: Alpha^a*Delta * Alpha^{(x - a*Delta)} = Alpha^x mod P _qed

Bemerkungen

1) Nachrichten Expansion

wir kennen aus der Informationstheorie  Bitlänge l = [log₂Nachricht]

Unsere Nachricht ist l Bit lang, Die Signatur besteht aus Delta mit l Bit und Gamma mit l Bit

Das Gesamtpaket  (Nachricht + Signatur) ist drei mal so lang wie die Nachricht alleine.

2) Deterministik

RSA-DS [ sig_Kriv( x ) = x^d mod n = y] ist ein s.g. deterministisches Signatur-Verfahren. El Gamal hingegen ist nicht deterministisch, d.h. für jede Nachricht wird eine neue Zufallszahl erzeugt, die in die Nachricht eingeht.

3) Sicherheit

El-Gamal beruht auf dem diskreten Logarithmus Problem. Durch einen diskrete Logarithmus Berechnung kann man das Signatur Verfahren brechen.

 Angreifer Oskar kennt: Alpha,Delta, Gamma, p, x Er versucht a = (Delta * K - x) / Gamma zu berechnen. Als Zwischenschritt muss er dazu K = log_AlphaDelta mod p berechnen. Diese DLP ist nicht lösbar, wenn alle Parameter entsprechend gewählt wurden. Insbesondere muss log₂P > 1024 gelten.

4) Parameterwahl

Warum werden Exponenten nicht diskreten Logarithmus Verfahren nicht aus der Menge { 1, 2, 3, ... , p-1} gewählt?

a = 1: Alpha¹ = Alpha mod p -> der Exponent kann direkt erkannt werden.

a = p-1: Alpha^p-1 = 1 mod p nach dem kleinen Fermatschem Theorem. Der Exponent kann auch hier direkt erkannt werden und das Ergebnis hat eine kleine Ordnung.