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 ${\displaystyle t}$ entsprechen sollte. Bei einem Sicherheitsniveau von ${\displaystyle t=80}$ Bit, bei dem ein Angreifer ${\displaystyle 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: ${\displaystyle 4t}$ 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 ${\displaystyle (q,FR,a,b,DomainParameterSeed,G,n,h)}$ einigen. Die ersten Parameter beschreiben die verwendete Kurve: ${\displaystyle q}$ ist die Ordnung des Körpers, auf dem die Kurve definiert ist; ${\displaystyle FR}$ ist die Angabe der verwendeten Basis; ${\displaystyle a}$ und ${\displaystyle b}$ sind zwei Körperelemente, die die Gleichung der Kurve beschreiben; ${\displaystyle DomainParameterSeed}$ ist eine mögliche, zufällig erzeugte Zeichenkette, die vorliegt, wenn die Kurve nachweislich zufällig erzeugt wurde. Weiterhin werden benötigt:

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

Um ihr Schlüsselpaar zu generieren, erzeugt Alice als geheimen Schlüssel ${\displaystyle d_{A}}$ eine zufällige Ganzzahl im Intervall ${\displaystyle [1,n-1]}$. Der zugehörige öffentliche Schlüssel ist ${\displaystyle Q_{A}=d_{A}G}$.

Algorithmus zur Erzeugung einer Signatur

Will Alice eine Nachricht ${\displaystyle m}$ signieren, geht sie folgendermaßen vor:

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

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

Es ist entscheidend, dass für verschiedene Signaturen auch verschiedene ${\displaystyle k}$-Werte verwendet werden, ansonsten kann die Gleichung im Schritt 4 nach dem geheimen Schlüssel ${\displaystyle d_{A}}$ aufgelöst werden: Aus zwei Signaturen ${\displaystyle (r,s)}$ und ${\displaystyle (r,s')}$, die mit demselben, unbekannten ${\displaystyle k}$ verschiedene bekannte Nachrichten ${\displaystyle m}$ und ${\displaystyle m'}$ signieren, kann ein Angreifer ${\displaystyle z}$ und ${\displaystyle z'}$ berechnen. Weil ${\displaystyle s-s'=k^{-1}(z-z')}$ entspricht (alle Operationen in diesem Absatz werden mit modulo ${\displaystyle n}$ durchgeführt), kann dann auch ${\displaystyle k={\frac {z-z'}{s-s'}}}$ berechnet werden. Aus ${\displaystyle k}$ kann der Angreifer wegen ${\displaystyle s=k^{-1}(z+rd_{A})}$ auch den privaten Schlüssel ${\displaystyle d_{A}={\frac {sk-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 die Beschränkung auf offiziell veröffentlichte Software auszuhebeln.^[2]

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

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

Danach führt Bob folgende Schritte durch:

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

Mit Hilfe von Straus’ Algorithmus (auch bekannt als Shamir's Trick) kann die Summe zweier skalarer Multiplikationen (${\displaystyle u_{1}G+u_{2}Q_{A}}$) schneller berechnet werden.^[3][4]

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

NIST

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

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

ISO/IEC

Die International Organization for Standardization und die International Electrotechnical Commission definiert ECDSA in dem internationalen Standard ISO/IEC 14888-3^[8] (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^[9] 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^[10] implementiert.^[11][12]
• OpenSSL: Ab Version 0.9.8 (5. Juli 2005) implementiert.^[13]
• BouncyCastle: Ab 10. März 2014^[14]
• GnuTLS
• .Net-Framework ab Version 3.5^[15]
• Bitcoin^[16]

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

1. FIPS 186-4. (PDF; 0,7 MB) NIST, Juli 2013, S. 19 und 26.
2. Console Hacking 2010. (Memento des Originals vom 15. Dezember 2014 im Internet Archive; PDF; 9 MB)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/events.ccc.de CCC, 27C3, S. 123–128.
3. Das Doppel-Basen-Zahlen-System in der Elliptischen Kurven-Kryptografie. (PDF; 0,2 MB) lirmm.fr/~imbert (englisch)
4. 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 in Webarchiven)  Info: Der Link wurde automatisch als defekt markiert. Bitte prüfe den Link gemäß Anleitung und entferne dann diesen Hinweis.
5. ANSI X9.62-2005, Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)
6. NIST (Hrsg.): Digital Signature Standard (DSS). (nist.gov [PDF]).
7. www.secg.org – Standards for Efficient Cryptography Group (SECG)
8. ISO/IEC 14888-3 (2018)iso.org
9. TR-031111: Elliptische-Kurven-Kryptographie (ECC). (PDF) bsi.bund.de
10. RFC 5656 – Elliptic Curve Algorithm Integration in the Secure Shell Transport Layer. Dezember 2009 (englisch).
11. OpenSSH 5.7 has just been released. OpenBSD, abgerufen am 19. August 2011.
12. OpenSSH 5.7: Schneller durch die Kurve. Heise.de, 25. Januar 2011, abgerufen am 19. August 2011.
13. openssl.org
14. Supported Curves (ECDSA and ECGOST) – Java APIs 1.X. The Legion of the Bouncy Castle, abgerufen am 9. März 2018.
15. ECDsa Class (System.Security.Cryptography). In: msdn.microsoft.com. Abgerufen am 9. März 2018 (englisch).
16. Blair Marshall: How does ECDSA work in Bitcoin. 22. Februar 2018, abgerufen am 12. Oktober 2024 (englisch).