Digital Signature Algorithm

Grundidee und Geltungsbereich

Der Digital Signature Algorithm (DSA; deutsch „Digitaler Signaturalgorithmus“) ist ein Standard der US-Regierung für digitale Signaturen. Er wurde vom National Institute of Standards and Technology (NIST) im August 1991 für den Digital Signature Standard (DSS) empfohlen. DSA basiert auf dem diskreten Logarithmus in endlichen Körpern, orientiert sich am Elgamal-Signaturverfahren und ist mit der Schnorr-Signatur verwandt. Die Übertragung auf elliptische Kurven heißt ECDSA (Elliptic Curve Digital Signature Algorithm) und ist in ANSI X9.62 standardisiert.

Für DSA werden ein Hashverfahren H und eine mathematische Gruppe benötigt. Ursprünglich war nur SHA-1 zugelassen; spätere Standardversionen erlaubten auch SHA-2. Der DSS wurde zunächst in FIPS-PUB 186 veröffentlicht. FIPS-PUB 186-4 wurde durch PUB 186-5 ersetzt; seit Version 186-5 ist DSA ohne elliptische Kurven nicht mehr zulässig.

Die Sicherheit wird vor allem durch die Parameter L und N bestimmt. Im ursprünglichen Standard galt 512 ≤ L ≤ 1024, wobei L ein Vielfaches von 64 sein musste, und N = 160. Der noch gültige Standard lässt die Kombinationen (L, N) = (1024, 160), (2048, 224), (2048, 256) und (3072, 256) zu. N darf höchstens der Ausgabelänge des Hashalgorithmus entsprechen.

Öffentliche Parameter und Schlüssel

Zur Erzeugung der öffentlichen Parameter werden drei Werte festgelegt:

• Wähle eine Primzahl q mit N Bit.
• Wähle eine Primzahl p mit L Bit so, dass p − 1 ein Vielfaches von q ist.
• Wähle ein g, das in der Einheitengruppe (ℤ/pℤ)× die Ordnung q besitzt.

Ein möglicher Weg für den letzten Schritt ist: Man findet zunächst ein Gruppenelement h mit 1 < h < p − 1 und h^((p−1)/q) mod p ≠ 1. Danach setzt man g = h^((p−1)/q) mod p. Die Parameter (p, q, g) sind öffentlich und können von mehreren Benutzern gemeinsam verwendet werden.

Für ein Schlüsselpaar wird ein zufälliger geheimer Wert x mit 1 < x < q gewählt und anschließend y = g^x mod p berechnet. y ist der öffentliche Verifikationsschlüssel. x ist der geheime Signaturschlüssel und muss geheim bleiben.

Signatur erzeugen und prüfen

Zum Signieren genügt es, den Hashwert H(m) der Nachricht m zu signieren. Für jede Nachricht wird ein zufälliger Wert k mit 1 < k < q gewählt. Danach werden berechnet:

• r = (g^k mod p) mod q; falls r = 0 ist, muss ein neues k gewählt werden.
• s = k^−1 · (H(m) + r · x) mod q; falls s = 0 ist, muss der Signiervorgang mit einem neuen k begonnen werden.

Die Signatur ist das Tupel (r, s). Der Wert k muss geheim, schwer zu erraten und für jede Signatur neu sein.

Zur Überprüfung werden die Signatur (r, s) und die Nachricht m benötigt:

• Zuerst wird geprüft, ob 0 < r < q und 0 < s < q gilt. Andernfalls ist die Signatur ungültig.
• Berechne w = s^−1 mod q.
• Berechne u₁ = H(m) · w mod q und u₂ = r · w mod q.
• Berechne v = (g^u₁ · y^u₂ mod p) mod q.
• Gilt v = r, ist die Signatur gültig; andernfalls ist sie ungültig.

Sicherheitsanforderungen und verdeckte Kanäle

Die Sicherheit hängt wesentlich von den Zufallswerten ab, insbesondere vom Wert k. Er muss ausreichend Entropie besitzen, geheim bleiben und darf nur einmal verwendet werden.

Wird k bekannt, kann der geheime Schlüssel berechnet werden: x = (k · s − H(m)) · r^−1 mod q. Auch eine Wiederverwendung von k gefährdet den Schlüssel. Bei zwei Nachrichten m₁ und m₂ mit demselben k und Signaturen (r, s₁) und (r, s₂) lässt sich zunächst k = (H(m₁) − H(m₂))/(s₁ − s₂) berechnen; anschließend kann daraus x bestimmt werden. Hat k nur geringe Entropie, kann ein Angreifer mögliche k-Werte durchprobieren und mithilfe des öffentlichen Schlüssels den richtigen geheimen Schlüssel erkennen.

Gustavus Simmons entdeckte mehrere verdeckte Kanäle in DSA. Ein Implementierer kann dabei eine Nachricht in einer Signatur verbergen, die nur eine Person mit dem passenden Schlüssel des verdeckten Kanals lesen kann. Kennt der Empfänger den geheimen Signaturschlüssel, ist der Kanal breitbandig. Teilen Sender und Empfänger nur ein gemeinsames Geheimnis, ohne dass der Empfänger den Signaturschlüssel kennt, ist er schmalbandig. Ein böswilliger DSS-Entwickler könnte über solche Kanäle mit jeder Signatur Teile des geheimen Schlüssels übertragen. Deshalb sollte man nur DSS-Implementierungen vertrauen, deren Entwicklern man vollständig vertraut. NIST und NSA äußerten sich zu den Vorwürfen nicht.