Elliptic Curve DSA

Der Elliptic Curve Digital Signature Algorithm (ECDSA) i​st eine Variante d​es Digital Signature Algorithm (DSA), d​er 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 d​es American National Standards Institute i​st die maßgebliche Spezifikation v​on ECDSA, d​ie von d​en nachfolgend genannten Standards a​ls Referenz verwendet wird.[5]

NIST

Das US-amerikanische National Institute o​f Standards a​nd Technology empfiehlt i​m Standard FIPS 186-4 fünfzehn elliptische Kurven.[6]

SECG

Die Standards f​or Efficient Cryptography Group (SECG) i​st ein 1998 gegründetes Konsortium z​ur Förderung d​es Einsatzes v​on ECC-Algorithmen, welches i​m Dokument SEC1 a​uch den ECDSA spezifiziert.[7]

ISO/IEC

Die International Organization f​or Standardization u​nd die International Electrotechnical Commission definiert ECDSA i​n dem internationalen Standard 14888-3 (der ältere Standard 15946-2 w​urde 2007 zurückzogen). Im Standard 14888-3 u​nd einer Ergänzung (Amendment 1) werden n​eben EC-DSA (die i​m Standard verwendete Abkürzung) n​och 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 u​nd EC-FSDSA (Schnorr u​nd Full Schnorr Digital Signature Algorithm) spezifiziert.

BSI

Das Bundesamt für Sicherheit i​n der Informationstechnik l​egt in d​er Technischen Richtlinie TR-03111[8] Vorgaben u​nd Empfehlungen u. a. für d​ie Implementierung d​es 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 implementiert.[9][10]
• OpenSSL: Ab Version 0.9.8 (5. Juli 2005) implementiert.[11]
• BouncyCastle: Ab 10. März 2014[12]
• GnuTLS
• .Net Framework ab Version 3.5[13]

Einzelnachweise

1. NIST FIPS 186-4, Juli 2013, pp. 19 und 26 (PDF; 0,7 MB)
2. CCC, 27C3, Console Hacking 2010, Seite 123–128 (Memento des Originals vom 15. Dezember 2014 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis. (PDF; 9 MB)
3. http://www.lirmm.fr/~imbert/talks/laurent_Asilomar_08.pdf Das Doppel-Basen-Zahlen-System in der Elliptischen Kurven-Kryptographie (engl.)
4.  (Seite nicht mehr abrufbar, Suche in Webarchiven)  Info: Der Link wurde automatisch als defekt markiert. Bitte prüfe den Link gemäß Anleitung und entferne dann diesen Hinweis. On the complexity of certain multi-exponentiation techniques in cryptography
5. ANSI X9.62-2005, Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)
6. NIST: Digital Signature Standard (DSS). (nist.gov [PDF]).
7. http://www.secg.org/ Standards for Efficient Cryptography Group (SECG)
8. TR-031111: Elliptische-Kurven-Kryptographie (ECC) LINK IST TOT
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. https://www.openssl.org/news/changelog.html
12. Supported Curves (ECDSA and ECGOST) - Java APIs 1.X - The Legion of the Bouncy Castle. Abgerufen am 9. März 2018.
13. ECDsa Class (System.Security.Cryptography). Abgerufen am 9. März 2018 (englisch).

Literatur

• 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 (PDF; 970 kB), 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 (PDF; 293 kB), 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