Digital Signature Algorithm (DSA)

Der DSA wurde 1991 vom NIST zum Standard erklärt für die Signatur von Dokumenten. Es setzt seine Sicherheit darin, dass man diskrete Logarithmen modulo einer Primzahl im allgemeinen nicht effizient berechnen kann. Zusätzlich braucht man noch eine kollisionsresistente Hashfunktion, welche man auf den Inhalt oder das Dokument anwendet.

Erzeugung Öffentlicher Schlüssel

Es werden eine Reihe von Zahlen mit modulo-Rechnung ermittelt.

Primzahl q mit genau 160 Bits
Primzahl p Bitgröße 512 + t * 64, t aus {0,1,...,8}
q ist ein Teiler von (p - 1)
Primitivwurzel x modulo p, daraus g = x^(p-1)/q modulo p
Zahl a zufällig aus {1,2,...,q-1} und A = g^a modulo p

Der öffentliche Schlüssel ist hierbei (q, p, g, A), der geheime Schlüssel a. Ersterer hat Bitgröße 160+(3*(512+t*64)), letzterer die Bitgröße 160.

Erzeugung digitale Signatur

Es werden zwei Werte ermittelt für die Signatur. Aus allen Daten des Textes x wird ein Hashwert berechnet, der nur schwer umkehrbar ist, d.h. zu einem Hashwert kann nur sehr schwer ein anderer, sinnvoller Text gefunden werden. Die Hashfunktion hat hierbei keine weiteren Parameter.

Text x: h{0,1}* -> {1,2,...,q-1}, kollisionsresistente Hashfunktion
Zufallszahl k aus {1,2,...,q-1}
r = (g^k modulo p) modulo q
s = k^-1 * (h(x) + a * r) modulo q

Die Signatur ist hierbei (r, s), k bleibt geheim. Ersterer hat die Bitgröße 2*160, letzterer die Bitgröße 160.

Prüfung einer Signatur

Folgende Schritte sind zu tun:

1 <= r <= q-1 prüfen
1 <= s <= q-1 prüfen
Anhand des öffentlichen Schlüssel und der Signatur berechnen:
wert = ((g^{(s^-1*h(x) modulo q)} * A^{(r*s^-1 modulo q)}) modulo p) modulo q =
((g^{(s^-1*(h(x) + a*r) modulo q)} modulo p) modulo q =
(g^k modulo p) modulo q == r

Anm.: die Modulo-Rechnung ist nicht kommutativ in der Reihenfolge vertauschbar, wie das Beispiel 11, 7, und 3 zeigen kann:
(13 % 7) % 3 = 6 % 3 = 0
(13 % 3) % 7 = 1 % 7 = 1
Damit kann der berechnete Wert mit r aus der Signatur verglichen werden. Im Fall der Ungleichheit wird der Inhalt nicht als authentisch akzeptiert und verworfen.

Angriffe auf die Signatur

Um Dokumente zu fälschen und mit einer gültigen Signatur zu versehen, so dass der Empfänger getäuscht wird, muss das geheime a geknackt werden. Dann kann man damit Paare (r, s) zum geänderten Text erzeugen. Der öffentliche und geheime Schlüssel des Senders muss ja unverändert bleiben, wird z.B. über eine PKI bereitgestellt.

über A des öffentl. Schlüssels auf a, mit disk. Logarithmusberechnung
über r der Signatur auf die Zufallszahl k mit disk. Logarithmusberechnung, dann a aus s

Java-Testprogramm mit dem DSA-Verfahren

... folgt noch ...