Quelltext der Seite 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 [[Elliptic Curve Cryptography|Elliptische-Kurven-Kryptographie]] die [[Faustregel]], dass die Bitlänge des Erzeugers der verwendeten Untergruppe etwa dem Doppelten des Sicherheitsniveaus&nbsp;<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 [[Digitale Signatur|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 und Bob|Alice]] möchte eine signierte Nachricht an [[Alice und Bob|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.&nbsp;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.&nbsp;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:
# Berechne <math>e = \textrm{HASH}(m)</math> und definiere <math>z</math> als die <math>L_n</math> [[Bitwertigkeit|höchstwertigen]] Bits von <math>e</math>.
# Wähle eine zufällige Ganzzahl <math>k</math> von <math>[1, n-1]</math>.
# 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&nbsp;2 zurück.
# Berechne <math>s = k^{-1}(z + r d_A) \pmod{n}</math>. Wenn <math>s = 0</math>, gehe zum Schritt 2 zurück.
# 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>[http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf FIPS 186-4.] (PDF; 0,7&nbsp;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&nbsp;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.&nbsp;B. verwendet, um die Verschlüsselung in der Spielkonsole [[PlayStation&nbsp;3]] zu berechnen und damit die Beschränkung auf offiziell veröffentlichte Software auszuhebeln.<ref>{{Webarchiv |url=https://events.ccc.de/congress/2010/Fahrplan/attachments/1780_27c3_console_hacking_2010.pdf |text=''Console Hacking 2010'' |format=PDF; 9&nbsp;MB |wayback=20141215140847 }} 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 [[Neutrales Element|neutrale Element]] wird mit <math>O</math> bezeichnet):
# Überprüfe, ob <math>Q_A</math> ungleich <math>O</math> ist und dass die Koordinaten ansonsten valide sind
# Überprüfe, ob <math>Q_A</math> auf der Kurve liegt
# Ü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:
# Ü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.
# 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>.
# Berechne <math>w = s^{-1} \pmod{n}</math>.
# Berechne <math>u_1 = zw \pmod{n}</math> und <math>u_2 = rw \pmod{n}</math>.
# Berechne <math>(x_1, y_1) = u_1 G + u_2 Q_A</math>.
# 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 ''[[Adi Shamir|Shamir]]'s Trick'') kann die Summe zweier skalarer Multiplikationen (<math>u_1 G + u_2 Q_A</math>) schneller berechnet werden.<ref>[http://www.lirmm.fr/~imbert/talks/laurent_Asilomar_08.pdf Das Doppel-Basen-Zahlen-System in der Elliptischen Kurven-Kryptografie.] (PDF; 0,2&nbsp;MB) lirmm.fr/~imbert (englisch)</ref><ref>''[http://caccioppoli.mac.rub.de/website/papers/multiexp.pdf On the complexity of certain multi-exponentiation techniques in cryptography]'' (PDF) caccioppoli.mac.rub.de {{Toter Link |date=2018-03 |url=http://caccioppoli.mac.rub.de/website/papers/multiexp.pdf}}</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>{{Literatur |Hrsg=NIST |Titel=Digital Signature Standard (DSS) |Datum= |Online=http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.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>[http://www.secg.org/ www.secg.org] – Standards for Efficient Cryptography Group (SECG)</ref>

=== ISO/IEC ===
Die [[Internationale Organisation für Normung|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)[https://www.iso.org/obp/ui/#iso:std:iso-iec:14888:-3:ed-4:v1:en 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>[https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/TechGuidelines/TR03111/BSI-TR-03111_V-2-1_pdf.pdf?__blob=publicationFile&v=2 TR-031111: Elliptische-Kurven-Kryptographie (ECC).] (PDF) bsi.bund.de</ref> Vorgaben und Empfehlungen u.&nbsp;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|Elliptic Curve Diffie-Hellman (ECDH)]] aus dem <nowiki>RFC&nbsp;5656</nowiki><ref>{{RFC-Internet |RFC=5656 |Titel=Elliptic Curve Algorithm Integration in the Secure Shell Transport Layer |Datum=2009-12}}</ref> implementiert.<ref name="openssh_57">{{Internetquelle |url=https://www.openssh.com/txt/release-5.7 |titel=OpenSSH 5.7 has just been released |hrsg=OpenBSD |datum= |abruf=2011-08-19}}</ref><ref name="heise_1176443">{{Internetquelle |url=https://heise.de/-1176443 |titel=OpenSSH 5.7: Schneller durch die Kurve |hrsg=Heise.de |datum=2011-01-25 |abruf=2011-08-19}}</ref>
* [[OpenSSL]]: Ab Version 0.9.8 (5. Juli 2005) implementiert.<ref>[https://www.openssl.org/news/changelog.html openssl.org]</ref>
* [[Bouncy Castle|BouncyCastle]]: Ab 10. März 2014<ref>{{Internetquelle |url=http://www.bouncycastle.org/wiki/pages/viewpage.action?pageId=362269 |titel=Supported Curves (ECDSA and ECGOST) – Java APIs 1.X  |hrsg=The Legion of the Bouncy Castle |abruf=2018-03-09}}</ref>
* [[GnuTLS]]
* [[.Net-Framework]] ab Version 3.5<ref>{{Internetquelle |url=https://msdn.microsoft.com/en-us/library/system.security.cryptography.ecdsa(v=vs.110).aspx |titel=ECDsa Class (System.Security.Cryptography) |werk=msdn.microsoft.com |sprache=en |abruf=2018-03-09}}</ref>
* [[Bitcoin]]<ref>{{Internetquelle |autor=Blair Marshall |url=https://medium.com/@blairlmarshall/how-does-ecdsa-work-in-bitcoin-7819d201a3ec |titel=How does ECDSA work in Bitcoin |datum=2018-02-22 |sprache=en |abruf=2024-10-12}}</ref>

== Literatur ==
* [https://www.x9.org/ 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.
* [http://www.secg.org/download/aid-780/sec1-v2.pdf ''Standards for efficient cryptography, SEC 1: Elliptic Curve Cryptography''.] (PDF; 970&nbsp;kB) Version 2.0. Certicom Research, 21. Mai 2009.
* J. López, R. Dahab: [http://citeseer.ist.psu.edu/333066.html ''An Overview of Elliptic Curve Cryptography''.] Technical Report IC-00-10. State University of Campinas, 2000.
* Daniel J. Bernstein: [https://cr.yp.to/papers/pippenger.pdf Pippenger’s exponentiation algorithm] (PDF; 293&nbsp;kB), 2002.
* Daniel R. L. Brown: ''Generic Groups, Collision Resistance, and ECDSA''. In: ''Designs, Codes and Cryptography'', 35, S. 119–152, 2005. [https://eprint.iacr.org/2002/026 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 ==
* [https://csrc.nist.gov/publications/detail/fips/186/4/final Digital Signature Standard; includes info on ECDSA.] csrc.nist.gov
* [https://infsec.de/elliptic-curve-digital-signature-algorithm-ecdsa/ Beispielhafte Implementierung von ECDSA in Excel.] infsec.de

== Einzelnachweise ==
<references />

[[Kategorie:Signaturverfahren]]