digitale_unterschrift

Digitale Unterschrift

Neben der Verschlüsselung von Nachrichten (Vertraulichkeit) ist es in der Praxis sehr wichtig, dass auch nachgewiesen werden kann, dass eine Nachricht von einer ganz bestimmten Person stammt (Authentifizierung). Dies wird durch die digitale Unterschrift möglich.

Das Elgamal-Verfahren eignet sich zum Signieren von Nachrichten. Dazu sind einerseits wieder die Primzahl p, die Basis g und die beiden geheimen und öffentlichen Schlüssel a, b, α und β erforderlich. Eine wesentliche Voraussetzung für den Signatur-Algorithmus ist nun das Bestimmen der Modulo-Inversen. Dies ist für eine Zahl r möglich, die zu p - 1 teilerfremd ist:

$tex:r \cdot r^{-1} \equiv 1$ (mod p - 1).

Hat man eine zu (p-1) teilerfremde Zufallszahl r (zwischen 1 und (p - 1)) gefunden, bestimmt man

tex:k = g^r (mod p).

Will Alice eine Nachricht N signieren, so bestimmt sie mit Hilfe der Inversen r^-1 den folgenden Ausdruck:

$tex:s = (N - a \cdot k) \cdot r^{-1}$ (mod p - 1)

Die digitale Unterschrift ist nun durch das Paar (k, s) gegeben.

Sendet Alice (k, s) an Bob, so muss Bob überprüfen, ob

$tex:g^N = \alpha^k \cdot k^s$ (mod p)

gilt - Bob kennt jedenfalls den öffentlichen Schlüssel α von Allice und das Paar (k, s). Wir rechnen (mod p) nach:

$tex:\alpha^k \cdot k^s = (g^a)^k \cdot (g^r)^s = g^{a \cdot k} \cdot g^{r \cdot s} = g^{a \cdot k + r \cdot s}$ (mod p)

Aus $tex:s \equiv (N - a \cdot k) \cdot r^{-1}$ (mod p-1) erhalten wir $tex:s \cdot r \equiv N - a \cdot k$ (mod p-1) und daraus $tex:a \cdot k + r \cdot s \equiv N$ (mod p-1). Diese Modulo-Gleichung kann mit Hilfe der Unbekannten x durch die folgende Gleichung ausgedrückt werden:

$tex:a \cdot k + r \cdot s = x \cdot (p-1) + N$

Damit können wir die obige Umformung fortsetzen:

$tex:g^{a \cdot k + r \cdot s} = g^{x \cdot (p - 1) + N} = g^{x \cdot (p-1)} \cdot g^N$

Wieder wenden wir den Kleinen Satz von Fermat an: $tex:g^{x \cdot (p - 1)} \equiv 1$ (mod p), sodass wir das gewünschte Ergebnis erhalten:

$tex:\alpha^k \cdot k^s \equiv g^N$ (mod p)

Wähle im folgenden GeoGebra-Beispiel p,g, die Zufallszahlen a, b und eine zu (p-1) teilerfremde Zahl r. Bestimme dann die Modulo-Inverse r_inv und weise diese in der Eingabezeile der Variablen r_{inv} zu. Gib dann eine Nachricht N ein und überprüfe aus der Sicht von Bob, ob die Signatur tatsächlich von Alice stammt!

Download der GeoGebra-Datei

Aufgaben:

Begründe: Die Nachricht darf nur Großbuchstaben enthalten, deren Indizes im Alphabet kleiner als p sind.
Untersuche die Auswirkungen auf die Signatur, wenn nicht gcd(r,p-1) = 1 gilt (r und p nicht teilerfremd)!
Untersuche die Auswirkungen auf die Signatur, wenn keine Modulo-Inverse bestimmt wurde!
Technologie: Erweitere obiges GeoGebra-Modell für einen größeren Zahlenbereich!

Zurück zu Lernpfad Kryptographie | Elgamal | GeoGebra 3.2: Texte codieren, Listen bearbeiten, Restklassenarithmetik ...