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 wird bei der Elliptische-Kurven-Kryptographie eine Faustregel angewandt, bei der die Größe des Public Keys (in Bit) etwa dem Doppelten des Sicherheitsniveaus entsprechen sollte. Bei einer Schlüssellänge von 80 Bits würde es bedeuten, dass der Angreifer 2⁸⁰ Operationen durchführen muss, um den privaten Schlüssel zu finden. Im Verhältnis entspricht ein 1024 Bit großer DSA-Schlüssel etwa einem 160-Bit-Schlüssel im ECDSA-Verfahren. Die Signatur-Größe ist jedoch bei beiden gleich groß: 4t Bit, wobei t das Sicherheitsniveau in Bit ist, d.h. 320 Bits für ein Sicherheitsniveau von 80 Bits.

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. q ist die Feldgröße; FR ist die Angabe der verwendeteten Basis; a und b sind zwei Feld-Elemente, 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;G ist die Basis der Primzahl-Ordnung in der Kurve (i.e., G = (x_G,y_G)); n ist die Reihenfolge im Punkt G; und h ist der Cofaktor (welcher gleich ist im der Kurve dividiert durch n).

Alice muss auch ein Schlüsselpaar verwenden, das für die Elliptische-Kurven-Verschlüsselung geeignet ist. Es besteht aus einem geheimen Schlüssel d_A (eine zufällig gewählte Ganzzahl [1,n − 1]) und dem öffentlichen Schlüssel Q_A (wobei Q_A = d_AG). Nimm an L_n ist die Bit-Länge der Gruppen Reinfolge von n.

Wenn Alice die Nachricht mit m verschlüsselt, geht sie nach den folgenden Schritten vor:

1. Berechne e = HASH(m), wobei HASH eine Kryptologische Hashfunktion ist, wie z.B. SHA-1, und lasse z die Bit-Werte ganz links von L_n dem Wert e entsprechen.
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. Beachte, dass z kann größer n sein aber nicht länger^[1].

Es ist entscheidend, dass verschiedene k Werte für verschiedene Signaturen verwendet werden, ansonsten kann die Gleichung im Schritt 4 für d_A gelöst werden, der geheime Schlüssel: Es sind zwei Signaturen gegeben (r,s) und (r,s'), mit dem jedes Mal unbekannten k für verschiedene bekannte Nachrichten-Inhalte m und m'. Ein Angreifer kann dann z und z' berechnen, weil s − s' = k ^{− 1}(z − z') entspricht (alle Operationen in diesem Absatz werden mit modulo n durchgeführt) daher kann dann auch $k = \frac{z-z'}{s-s'}$ berechnet werden. Weil s = k ^{− 1}(z + rd_A) entspricht kann der Angreifer auch den privaten Schlüssel $d_A = \frac{s k - z}{r}$ herausfinden. 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.^[2]

Signatur-Überprüfungsalgorithmus

Wenn Bob die Echtheit der Signatur von Alice prüfen möchte, muss er eine Kopie des öffentlichen Schlüssels Q_A haben. Wenn er der Quelle von Q_A nicht vertraut, muss er den Schlüssel überprüfen. (O beschreibt hierbei das Identitätselement (engl. identity element)):

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 macht Bob folgende Schritte:

1. Überprüfe, ob r und s Ganzzahlen sind [1,n − 1]. 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. Nimm an z ist L_n das Bit ganz links 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 nicht valide.

Beachte bei der Verwendung des Straus's Algorithmus (auch bekannt als der Shamir's Trick) bezüglich der Summe von skalaren Multiplikationen (u₁G + u₂Q_A) ^[3][4]

Normen und Standards

NIST

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

SECG

Die "Standards for Efficient Cryptography Group" (SECG) ist ein 1998 gegründetes Konsortium zur Förderung des Einsatzes von ECC-Algorithmen.^[6]

ANSI

ANSI X9.62-2005 ist die aktuelle Standardisierung des ECDSA.^[7]

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.^[8]

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. ^[9][10]
• OpenSSL: Seit Version 0.9.8 (5. Juli 2005) implementiert.^[11]

Weblinks

1. ↑ FIPS 186-3, pp. 19 and 26
2. ↑ http://events.ccc.de/congress/2010/Fahrplan/attachments/1780_27c3_console_hacking_2010.pdf, page 123–128
3. ↑ http://www.lirmm.fr/~imbert/talks/laurent_Asilomar_08.pdf Das Doppel-Basen-Zahlen-System in der Elliptischen Kurven-Kryptographie (engl.)
4. ↑ http://caccioppoli.mac.rub.de/website/papers/multiexp.pdf On the complexity of certain multi-exponentiation techniques in cryptography
5. ↑ NIST: Digital Signature Standard (DSS). (http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf).
6. ↑ http://www.secg.org/index.php?action=secg,about
7. ↑ ANSI X9.62-2005, Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)
8. ↑ KCDSA
9. ↑ OpenSSH 5.7 has just been released. OpenBSD, abgerufen am 19. August 2011. 
10. ↑ OpenSSH 5.7: Schneller durch die Kurve. Heise.de, 25. Januar 2011, abgerufen am 19. August 2011. 
11. ↑ http://www.openssl.org/news/changelog.html

Literaturverweise

• 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