Elliptic Curve DSA

Der Elliptic Curve Digital Signature Algorithmus (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⁸⁰ 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: 4t 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-1.

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_AG) besteht.

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

1. Berechne e = 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₁(mod n), wobei (x₁,y₁) = kG. Wenn r = 0, gehe zum Schritt 2 zurück.
4. Berechne s = k ^{− 1}(z + rd_A)(mod 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 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 kann 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 + rd_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 der Quelle von Q_A nicht vertraut, 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

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 = 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}(mod n).
4. Berechne u₁ = zw(mod n) und u₂ = rw(mod n).
5. Berechne (x₁,y₁) = u₁G + u₂Q_A.
6. Die Signatur ist gültig, wenn r = x₁(mod 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₁G + u₂Q_A) schneller berechnet werden.

Normen und Standards

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.

ANSI

ANSI X9.62-2005 ist die aktuelle Standardisierung des ECDSA.

EC-GDSA

Das Bundesamt für Sicherheit in der Informationstechnik (BSI) hat in Kooperation mit Brainpool und secunet im März 2010 IETF-RFC 5639 herausgebracht. In diesem Vorschlag "Elliptic Curve Cryptography (ECC) Brainpool Standard - Curves and Curve Generation" ist besonders die unterschiedliche Wahl der Bitlänge 512 zu erwähnen, ein Gegensatz zur von vielen anderen Institutionen (z.b. NIST, SECG) präferierten Bitlänge 521.

EC-KCDSA

Kurven welche der koreanische Staat als Standard definiert hat.

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, 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, 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