Elliptic Curve DSA

Der Elliptic Curve Digital Signature Algorithm (ECDSA) ist eine Variante des Digital Signature Algorithm (DSA), die 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 <math>t</math> entsprechen sollte. Bei einem Sicherheitsniveau von <math>t=80</math> Bit, bei dem ein Angreifer <math> 2^{80}</math> 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: <math>4 t</math> Bit, also 320 Bit für ein Sicherheitsniveau von 80 Bit.

Schlüsselerzeugung

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

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

Um ihr Schlüsselpaar zu generieren, erzeugt Alice als geheimen Schlüssel <math>d_A</math> eine zufällige Ganzzahl im Intervall <math>[1, n-1]</math>. Der zugehörige öffentliche Schlüssel ist <math>Q_A = d_A G</math>.

Algorithmus zur Erzeugung einer Signatur

Will Alice eine Nachricht <math>m</math> signieren, geht sie folgendermaßen vor:

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

Wenn <math>s</math> berechnet wird, sollte der Wert <math>z</math>, der aus <math>\textrm{HASH}(m)</math> stammt, in eine Ganzzahl umgewandelt werden. Dabei ist zu beachten, dass <math>z</math> größer als <math>n</math> sein kann, aber nicht länger.<ref>FIPS 186-4. (PDF; 0,7 MB) NIST, Juli 2013, S. 19 und 26.</ref>

Es ist entscheidend, dass für verschiedene Signaturen auch verschiedene <math>k</math>-Werte verwendet werden, ansonsten kann die Gleichung im Schritt 4 nach dem geheimen Schlüssel <math>d_A</math> aufgelöst werden: Aus zwei Signaturen <math>(r,s)</math> und <math>(r,s')</math>, die mit demselben, unbekannten <math>k</math> verschiedene bekannte Nachrichten <math>m</math> und <math>m'</math> signieren, kann ein Angreifer <math>z</math> und <math>z'</math> berechnen. Weil <math>s-s' = k^{-1}(z-z')</math> entspricht (alle Operationen in diesem Absatz werden mit modulo <math>n</math> durchgeführt), kann dann auch <math>k = \frac{z-z'}{s-s'}</math> berechnet werden. Aus <math>k</math> kann der Angreifer wegen <math>s = k^{-1}(z + r d_A)</math> auch den privaten Schlüssel <math>d_A = \frac{s k - z}{r}</math> berechnen. Dieser Fehler in der Verschlüsselung wurde z. B. verwendet, um die Verschlüsselung in der Spielkonsole PlayStation 3 zu berechnen und damit die Beschränkung auf offiziell veröffentlichte Software auszuhebeln.<ref>Console Hacking 2010 (Memento vom 15. Dezember 2014 im Internet Archive; PDF; 9 MB) CCC, 27th Chaos Communication Congress, S. 123–128.</ref>

Ü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 <math>Q_A</math> besitzen. Wenn er sich nicht sicher ist, dass <math>Q_A</math> ordnungsgemäß erzeugt wurde, muss er überprüfen, ob es sich wirklich um einen Schlüssel handelt (das neutrale Element wird mit <math>O</math> bezeichnet):

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

Danach führt Bob folgende Schritte durch:

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

Mit Hilfe von Straus’ Algorithmus (auch bekannt als Shamir's Trick) kann die Summe zweier skalarer Multiplikationen (<math>u_1 G + u_2 Q_A</math>) schneller berechnet werden.<ref>Das Doppel-Basen-Zahlen-System in der Elliptischen Kurven-Kryptografie. (PDF; 0,2 MB) lirmm.fr/~imbert (englisch)</ref><ref>On the complexity of certain multi-exponentiation techniques in cryptography (PDF) caccioppoli.mac.rub.de @1@2Vorlage:Toter Link/caccioppoli.mac.rub.de (Seite nicht mehr abrufbar, festgestellt im März 2018. Suche im Internet Archive )</ref>

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.<ref>ANSI X9.62-2005, Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)</ref>

NIST

Das US-amerikanische National Institute of Standards and Technology empfiehlt im Standard FIPS 186-4 fünfzehn elliptische Kurven.<ref>NIST (Hrsg.): Digital Signature Standard (DSS). (nist.gov [PDF]). </ref>

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.<ref>www.secg.org – Standards for Efficient Cryptography Group (SECG)</ref>

ISO/IEC

Die International Organization for Standardization und die International Electrotechnical Commission definiert ECDSA in dem internationalen Standard ISO/IEC 14888-3<ref>ISO/IEC 14888-3 (2018)iso.org</ref> (der ältere Standard 15946-2 wurde 2007 zurückzogen). Darin 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 Technischen Richtlinie TR-03111<ref>TR-031111: Elliptische-Kurven-Kryptographie (ECC). (PDF) bsi.bund.de</ref> Vorgaben und Empfehlungen u. a. für die Implementierung des ECDSA fest.

Implementierungen

Open Source

• OpenSSH: Ab Version 5.7 (24. Januar 2011) ist ECDSA und der Schlüsselaustausch via Elliptic Curve Diffie-Hellman (ECDH) aus dem RFC 5656<ref>Vorlage:RFC-Internet</ref> implementiert.<ref name="openssh_57">OpenSSH 5.7 has just been released. OpenBSD, abgerufen am 19. August 2011. </ref><ref name="heise_1176443">OpenSSH 5.7: Schneller durch die Kurve. Heise.de, 25. Januar 2011, abgerufen am 19. August 2011. </ref>
• OpenSSL: Ab Version 0.9.8 (5. Juli 2005) implementiert.<ref>openssl.org</ref>
• BouncyCastle: Ab 10. März 2014<ref>Supported Curves (ECDSA and ECGOST) – Java APIs 1.X. The Legion of the Bouncy Castle, abgerufen am 9. März 2018. </ref>
• GnuTLS
• .Net-Framework ab Version 3.5<ref>ECDsa Class (System.Security.Cryptography). In: msdn.microsoft.com. Abgerufen am 9. März 2018 (). </ref>
• Bitcoin<ref>Blair Marshall: How does ECDSA work in Bitcoin. 22. Februar 2018, abgerufen am 12. Oktober 2024 (). </ref>

Literatur

• X9. American National Standard X9.62-2005, Public Key Cryptography for the Financial Services Industry, The Elliptic Curve Digital Signature Algorithm (ECDSA), Accredited Standards Committee, 16. November 2005.
• Standards for efficient cryptography, SEC 1: Elliptic Curve Cryptography. (PDF; 970 kB) Version 2.0. Certicom Research, 21. Mai 2009.
• J. López, R. Dahab: 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. In: Designs, Codes and Cryptography, 35, S. 119–152, 2005. ePrint version
• Ian F. Blake, Gadiel Seroussi, Nigel P. Smart (Hrsg.): Advances in Elliptic Curve Cryptography. In: London Mathematical Society Lecture Note, Series 317, Cambridge University Press, 2005.
• Darrel Hankerson, Alfred Menezes, Scott Vanstone: Guide to Elliptic Curve Cryptography. Springer, 2004.

Weblinks

• Digital Signature Standard; includes info on ECDSA. csrc.nist.gov
• Beispielhafte Implementierung von ECDSA in Excel. infsec.de

Einzelnachweise

<references />