Elliptic Curve DSA

Der Elliptic Curve Digital Signature Algorithm (ECDSA) (deutsch: digitaler Signatur-Algorithmus mit elliptischen Kurven) ist eine Variante des Digital Signature Algorithm (DSA), der Elliptische-Kurven-Kryptographie verwendet.

Unterschiede zum normalen DSA-Verfahren

Generell gilt bei der Elliptische-Kurven-Kryptographie die Faustregel, dass die Bitlänge des Erzeugers der verwendeten Untergruppe etwa dem Doppelten des Sicherheitsniveaus $t$ entsprechen sollte. Bei einem Sicherheitsniveau von $t=80$ Bit, bei dem ein Angreifer $2^{80}$ elementare Operationen durchführen muss um den privaten Schlüssel zu finden, hätte ein DSA-Schlüssel eine Länge von circa 1024 Bit, ein ECDSA-Schlüssel aber nur eine Länge von 160 Bit. Eine Signatur ist jedoch bei beiden Verfahren gleich lang: $4 t$ Bit, also 320 Bit für ein Sicherheitsniveau von 80 Bit.

Algorithmus zur Erzeugung einer Signatur

Alice möchte eine signierte Nachricht an Bob schreiben. Zu Beginn muss man sich auf die Kurvenparameter $(q, FR, a, b,DomainParameterSeed, G, n, h)$ einigen. Die ersten Parameter beschreiben die verwendete Kurve: $q$ ist die Ordnung des Körpers, auf dem die Kurve definiert ist; $FR$ ist die Angabe der verwendeteten Basis; $a$ und $b$ sind zwei Körperelemente, die die Gleichung der Kurve beschreiben; $DomainParameterSeed$ ist eine mögliche, zufällig erzeugte Zeichenkette, die vorliegt, wenn die Kurve nachweislich zufällig erzeugt wurde. Weiterhin werden benötigt:

• $G$, ein fester Erzeuger der $n$-Torsionsuntergruppe der Kurve (i. e., $G = (x_G, y_G)$);
• $n$, die Ordnung des Punktes $G$, und $h$, der Cofaktor (gleich der Ordnung der Kurve geteilt durch die Gruppenordnung $n$);
• $L_n$, die Bitlänge der Gruppenordnung $n$;
• eine kryptologische Hashfunktion HASH, wie z. B. SHA-2.

Alice muss im Besitz eines geeigneten Schlüsselpaars sein, das aus einem geheimen Schlüssel $d_A$ (einer zufällig gewählten Ganzzahl im Intervall $[1, n-1]$) und dem zugehörigen öffentlichen Schlüssel $Q_A = d_A G$) besteht.

Wenn Alice die Nachricht $m$ signieren möchte, geht sie folgendermaßen vor:

1. Berechne $e = \textrm{HASH}(m)$ und definiere $z$ als die $L_n$ höchstwertigen Bits von $e$.
2. Wähle eine zufällige Ganzzahl $k$ von $[1, n-1]$.
3. Berechne $r = x_1 \pmod{n}$, wobei $(x_1, y_1) = k G$. Wenn $r = 0$, gehe zum Schritt 2 zurück.
4. Berechne $s = k^{-1}(z + r d_A) \pmod{n}$. Wenn $s = 0$, gehe zum Schritt 2 zurück.
5. Die Signatur ist das Paar $(r, s)$.

Wenn $s$ berechnet wird, sollte der Wert $z$, der aus $\textrm{HASH}(m)$ stammt, in eine Ganzzahl umgewandelt werden. Dabei ist zu beachten, dass $z$ größer als $n$ sein kann, aber nicht länger.

Es ist entscheidend, dass für verschiedene Signaturen auch verschiedene $k$-Werte verwendet werden, ansonsten kann die Gleichung im Schritt 4 nach dem geheimen Schlüssel $d_A$ aufgelöst werden: Aus zwei Signaturen $(r,s)$ und $(r,s')$, die mit demselben, unbekannten $k$ verschiedene bekannte Nachrichten $m$ und $m'$ signieren, kann ein Angreifer $z$ und $z'$ berechnen. Weil $s-s' = k^{-1}(z-z')$ entspricht (alle Operationen in diesem Absatz werden mit modulo $n$ durchgeführt), kann dann auch $k = \frac{z-z'}{s-s'}$ berechnet werden. Aus $k$ kann der Angreifer wegen $s = k^{-1}(z + r d_A)$ auch den privaten Schlüssel $d_A = \frac{s k - z}{r}$ berechnen. Dieser Fehler in der Verschlüsselung wurde z. B. verwendet, um die Verschlüsselung in der Spielkonsole PlayStation 3 zu berechnen und damit den Kopierschutz auszuhebeln.

Überprüfung einer Signatur

Wenn Bob die Echtheit einer von Alice erzeugten Signatur prüfen möchte, muss er eine Kopie ihres öffentlichen Schlüssels $Q_A$ besitzen. Wenn er sich nicht sicher ist, dass $Q_A$ ordnungsgemäß erzeugt wurde, muss er überprüfen, ob es sich wirklich um einen Schlüssel handelt (das neutrale Element wird mit $O$ bezeichnet):

1. Überprüfe, ob $Q_A$ ungleich $O$ ist und dass die Koordinaten ansonsten valide sind
2. Überprüfe, ob $Q_A$ auf der Kurve liegt
3. Überprüfe, ob $nQ_A = O$. Hier wird überprüft, ob $Q_A$ ein Vielfaches des Erzeugers $G$ ist. Falls in den Kurvenparametern der Kofaktor $h = 1$ ist, kann dieser Schritt weggelassen werden.

Danach führt Bob folgende Schritte durch:

1. Überprüfe, ob $r$ und $s$ ganze Zahlen sind und im Intervall $[1, n-1]$ liegen. Wenn dies nicht der Fall ist, ist die Signatur ungültig.
2. Berechne $e = \textrm{HASH}(m)$, wobei HASH die gleiche Funktion wie bei der Erzeugung der Signatur ist. Bezeichne mit $z$ die $L_n$ höchstwertigen Bits von $e$.
3. Berechne $w = s^{-1} \pmod{n}$.
4. Berechne $u_1 = zw \pmod{n}$ und $u_2 = rw \pmod{n}$.
5. Berechne $(x_1, y_1) = u_1 G + u_2 Q_A$.
6. Die Signatur ist gültig, wenn $r = x_1 \pmod{n}$, ansonsten ist sie ungültig.

Mit Hilfe von Straus' Algorithmus (auch bekannt als der Shamir's Trick) kann die Summe zweier skalarer Multiplikationen ($u_1 G + u_2 Q_A$) schneller berechnet werden.

Normen und Standards

ANSI

Der Standard X9.62-2005 des American National Standards Institute ist die maßgebliche Spezifikation von ECDSA, die von den nachfolgend genannten Standards als Referenz verwendet wird.

NIST

Das US-amerikanische National Institute of Standards and Technology empfiehlt im Standard FIPS 186-3 fünfzehn elliptische Kurven.

SECG

Die "Standards for Efficient Cryptography Group" (SECG) ist ein 1998 gegründetes Konsortium zur Förderung des Einsatzes von ECC-Algorithmen, welches im Dokument SEC1 auch den ECDSA spezifiziert.

ISO/IEC

Die International Standardization Organization und die International Electrotechnical Commission definiert ECDSA in dem internationalen Standard 14888-3 (der ältere Standard 15946-2 wurde 2007 zurückzogen). Im Standard 14888-3 und einer Ergänzung (Amendment 1) werden neben EC-DSA (die im Standard verwendete Abkürzung) noch die Varianten EC-GDSA (Elliptic Curve German Digital Signature Algorithm), EC-KCDSA (Korean Certificate-based Digital Signature Algorithm), EC-RDSA (Russian Digital Signature Algorithm), EC-SDSA und EC-FSDSA (Schnorr und Full Schnorr Digital Signature Algorithm) spezifiziert.

BSI

Das Bundesamt für Sicherheit in der Informationstechnik legt in der Technical Guideline TR-03111 Vorgaben und Empfehlungen u. a. für die Implementierung des ECDSA fest.

Implementierungen

Open Source

• OpenSSH: Seit Version 5.7 (24. Januar 2011) ist ECDSA und der Schlüsselaustausch via Elliptic Curve Diffie-Hellman (ECDH) aus dem RFC 5656 implementiert.
• OpenSSL: Seit Version 0.9.8 (5. Juli 2005) implementiert.

Literatur

• Accredited Standards Committee X9, American National Standard X9.62-2005, Public Key Cryptography for the Financial Services Industry, The Elliptic Curve Digital Signature Algorithm (ECDSA), November 16, 2005.
• Certicom Research, Standards for efficient cryptography, SEC 1: Elliptic Curve Cryptography (PDF; 970 kB), Version 2.0, May 21, 2009.
• López, J. and Dahab, R. An Overview of Elliptic Curve Cryptography, Technical Report IC-00-10, State University of Campinas, 2000.
• Daniel J. Bernstein, Pippenger's exponentiation algorithm (PDF; 293 kB), 2002.
• Daniel R. L. Brown, Generic Groups, Collision Resistance, and ECDSA, Designs, Codes and Cryptography, 35, 119–152, 2005. ePrint version
• Ian F. Blake, Gadiel Seroussi, and Nigel P. Smart, editors, Advances in Elliptic Curve Cryptography, London Mathematical Society Lecture Note Series 317, Cambridge University Press, 2005.
• Darrel Hankerson, Alfred Menezes and Scott Vanstone, Guide to Elliptic Curve Cryptography, Springer, Springer, 2004.

Weblinks

• Digital Signature Standard; includes info on ECDSA