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.

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.

Ü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.

Normen und Standards

Implementierungen

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

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