www.wikidata.de-de.nina.az

Elliptic Curve DSA Der Elliptic Curve Digital Signature Algorithm ECDSA ist eine Variante des Digital Signature Algorith

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 Bearbeiten

Generell gilt bei der Elliptische-Kurven-Kryptographie die Faustregel, dass die Bitlänge des Erzeugers der verwendeten Untergruppe etwa dem Doppelten des Sicherheitsniveaus  entsprechen sollte. Bei einem Sicherheitsniveau von Bit, bei dem ein Angreifer 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: Bit, also 320 Bit für ein Sicherheitsniveau von 80 Bit.

Schlüsselerzeugung Bearbeiten

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

  • , ein fester Erzeuger der -Torsionsuntergruppe der Kurve (i. e., );
  • , die Ordnung des Punktes , und , der Cofaktor (gleich der Ordnung der Kurve geteilt durch die Gruppenordnung );
  • , die Bitlänge der Gruppenordnung ;
  • eine kryptologische Hashfunktion HASH, wie z. B. SHA-2.

Um ihr Schlüsselpaar zu generieren, erzeugt Alice als geheimen Schlüssel eine zufällige Ganzzahl im Intervall . Der zugehörige öffentliche Schlüssel ist .

Algorithmus zur Erzeugung einer Signatur Bearbeiten

Will Alice eine Nachricht signieren, geht sie folgendermaßen vor:

  1. Berechne und definiere als die höchstwertigen Bits von .
  2. Wähle eine zufällige Ganzzahl von .
  3. Berechne , wobei . Wenn , gehe zum Schritt 2 zurück.
  4. Berechne . Wenn , gehe zum Schritt 2 zurück.
  5. Die Signatur ist das Paar .

Wenn berechnet wird, sollte der Wert , der aus stammt, in eine Ganzzahl umgewandelt werden. Dabei ist zu beachten, dass größer als sein kann, aber nicht länger.

Es ist entscheidend, dass für verschiedene Signaturen auch verschiedene -Werte verwendet werden, ansonsten kann die Gleichung im Schritt 4 nach dem geheimen Schlüssel aufgelöst werden: Aus zwei Signaturen und , die mit demselben, unbekannten verschiedene bekannte Nachrichten und signieren, kann ein Angreifer und berechnen. Weil entspricht (alle Operationen in diesem Absatz werden mit modulo durchgeführt), kann dann auch berechnet werden. Aus kann der Angreifer wegen auch den privaten Schlüssel 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 Bearbeiten

Wenn Bob die Echtheit einer von Alice erzeugten Signatur prüfen möchte, muss er eine Kopie ihres öffentlichen Schlüssels besitzen. Wenn er sich nicht sicher ist, dass ordnungsgemäß erzeugt wurde, muss er überprüfen, ob es sich wirklich um einen Schlüssel handelt (das neutrale Element wird mit bezeichnet):

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

Danach führt Bob folgende Schritte durch:

  1. Überprüfe, ob und ganze Zahlen sind und im Intervall liegen. Wenn dies nicht der Fall ist, ist die Signatur ungültig.
  2. Berechne , wobei HASH die gleiche Funktion wie bei der Erzeugung der Signatur ist. Bezeichne mit die höchstwertigen Bits von .
  3. Berechne .
  4. Berechne und .
  5. Berechne .
  6. Die Signatur ist gültig, wenn , ansonsten ist sie ungültig.

Mit Hilfe von Straus’ Algorithmus (auch bekannt als Shamir's Trick) kann die Summe zweier skalarer Multiplikationen () schneller berechnet werden.

Normen und Standards Bearbeiten

ANSI Bearbeiten

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.

NIST Bearbeiten

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

SECG Bearbeiten

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.

ISO/IEC Bearbeiten

Die International Organization for Standardization und die International Electrotechnical Commission definiert ECDSA in dem internationalen Standard ISO/IEC 14888-3 (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 Bearbeiten

Das Bundesamt für Sicherheit in der Informationstechnik legt in der Technischen Richtlinie TR-03111 Vorgaben und Empfehlungen u. a. für die Implementierung des ECDSA fest.

Implementierungen Bearbeiten

Open Source Bearbeiten

Literatur Bearbeiten

  • 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 Bearbeiten

Einzelnachweise Bearbeiten

  1. FIPS 186-4. (PDF; 0,7 MB) NIST, Juli 2013, S. 19 und 26.
  2. (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).
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der Elliptic Curve Digital Signature Algorithm ECDSA ist eine Variante des Digital Signature Algorithm DSA die Elliptische Kurven Kryptographie verwendet Inhaltsverzeichnis 1 Unterschiede zum normalen DSA Verfahren 2 Schlusselerzeugung 3 Algorithmus zur Erzeugung einer Signatur 4 Uberprufung einer Signatur 5 Normen und Standards 5 1 ANSI 5 2 NIST 5 3 SECG 5 4 ISO IEC 5 5 BSI 6 Implementierungen 6 1 Open Source 7 Literatur 8 Weblinks 9 EinzelnachweiseUnterschiede zum normalen DSA Verfahren BearbeitenGenerell gilt bei der Elliptische Kurven Kryptographie die Faustregel dass die Bitlange des Erzeugers der verwendeten Untergruppe etwa dem Doppelten des Sicherheitsniveaus t displaystyle t nbsp entsprechen sollte Bei einem Sicherheitsniveau von t 80 displaystyle t 80 nbsp Bit bei dem ein Angreifer 2 80 displaystyle 2 80 nbsp elementare Operationen durchfuhren muss um den privaten Schlussel zu finden hatte ein DSA Schlussel eine Lange von circa 1024 Bit ein ECDSA Schlussel aber nur eine Lange von 160 Bit Eine Signatur ist jedoch bei beiden Verfahren gleich lang 4 t displaystyle 4t nbsp Bit also 320 Bit fur ein Sicherheitsniveau von 80 Bit Schlusselerzeugung BearbeitenAlice mochte eine signierte Nachricht an Bob schreiben Zu Beginn muss man sich auf die Kurvenparameter q F R a b D o m a i n P a r a m e t e r S e e d G n h displaystyle q FR a b DomainParameterSeed G n h nbsp einigen Die ersten Parameter beschreiben die verwendete Kurve q displaystyle q nbsp ist die Ordnung des Korpers auf dem die Kurve definiert ist F R displaystyle FR nbsp ist die Angabe der verwendeten Basis a displaystyle a nbsp und b displaystyle b nbsp sind zwei Korperelemente die die Gleichung der Kurve beschreiben D o m a i n P a r a m e t e r S e e d displaystyle DomainParameterSeed nbsp ist eine mogliche zufallig erzeugte Zeichenkette die vorliegt wenn die Kurve nachweislich zufallig erzeugt wurde Weiterhin werden benotigt G displaystyle G nbsp ein fester Erzeuger der n displaystyle n nbsp Torsionsuntergruppe der Kurve i e G x G y G displaystyle G x G y G nbsp n displaystyle n nbsp die Ordnung des Punktes G displaystyle G nbsp und h displaystyle h nbsp der Cofaktor gleich der Ordnung der Kurve geteilt durch die Gruppenordnung n displaystyle n nbsp L n displaystyle L n nbsp die Bitlange der Gruppenordnung n displaystyle n nbsp eine kryptologische Hashfunktion HASH wie z B SHA 2 Um ihr Schlusselpaar zu generieren erzeugt Alice als geheimen Schlussel d A displaystyle d A nbsp eine zufallige Ganzzahl im Intervall 1 n 1 displaystyle 1 n 1 nbsp Der zugehorige offentliche Schlussel ist Q A d A G displaystyle Q A d A G nbsp Algorithmus zur Erzeugung einer Signatur BearbeitenWill Alice eine Nachricht m displaystyle m nbsp signieren geht sie folgendermassen vor Berechne e HASH m displaystyle e textrm HASH m nbsp und definiere z displaystyle z nbsp als die L n displaystyle L n nbsp hochstwertigen Bits von e displaystyle e nbsp Wahle eine zufallige Ganzzahl k displaystyle k nbsp von 1 n 1 displaystyle 1 n 1 nbsp Berechne r x 1 mod n displaystyle r x 1 pmod n nbsp wobei x 1 y 1 k G displaystyle x 1 y 1 kG nbsp Wenn r 0 displaystyle r 0 nbsp gehe zum Schritt 2 zuruck Berechne s k 1 z r d A mod n displaystyle s k 1 z rd A pmod n nbsp Wenn s 0 displaystyle s 0 nbsp gehe zum Schritt 2 zuruck Die Signatur ist das Paar r s displaystyle r s nbsp Wenn s displaystyle s nbsp berechnet wird sollte der Wert z displaystyle z nbsp der aus HASH m displaystyle textrm HASH m nbsp stammt in eine Ganzzahl umgewandelt werden Dabei ist zu beachten dass z displaystyle z nbsp grosser als n displaystyle n nbsp sein kann aber nicht langer 1 Es ist entscheidend dass fur verschiedene Signaturen auch verschiedene k displaystyle k nbsp Werte verwendet werden ansonsten kann die Gleichung im Schritt 4 nach dem geheimen Schlussel d A displaystyle d A nbsp aufgelost werden Aus zwei Signaturen r s displaystyle r s nbsp und r s displaystyle r s nbsp die mit demselben unbekannten k displaystyle k nbsp verschiedene bekannte Nachrichten m displaystyle m nbsp und m displaystyle m nbsp signieren kann ein Angreifer z displaystyle z nbsp und z displaystyle z nbsp berechnen Weil s s k 1 z z displaystyle s s k 1 z z nbsp entspricht alle Operationen in diesem Absatz werden mit modulo n displaystyle n nbsp durchgefuhrt kann dann auch k z z s s displaystyle k frac z z s s nbsp berechnet werden Aus k displaystyle k nbsp kann der Angreifer wegen s k 1 z r d A displaystyle s k 1 z rd A nbsp auch den privaten Schlussel d A s k z r displaystyle d A frac sk z r nbsp berechnen Dieser Fehler in der Verschlusselung wurde z B verwendet um die Verschlusselung in der Spielkonsole PlayStation 3 zu berechnen und damit die Beschrankung auf offiziell veroffentlichte Software auszuhebeln 2 Uberprufung einer Signatur BearbeitenWenn Bob die Echtheit einer von Alice erzeugten Signatur prufen mochte muss er eine Kopie ihres offentlichen Schlussels Q A displaystyle Q A nbsp besitzen Wenn er sich nicht sicher ist dass Q A displaystyle Q A nbsp ordnungsgemass erzeugt wurde muss er uberprufen ob es sich wirklich um einen Schlussel handelt das neutrale Element wird mit O displaystyle O nbsp bezeichnet Uberprufe ob Q A displaystyle Q A nbsp ungleich O displaystyle O nbsp ist und dass die Koordinaten ansonsten valide sind Uberprufe ob Q A displaystyle Q A nbsp auf der Kurve liegt Uberprufe ob n Q A O displaystyle nQ A O nbsp Hier wird uberpruft ob Q A displaystyle Q A nbsp ein Vielfaches des Erzeugers G displaystyle G nbsp ist Falls in den Kurvenparametern der Kofaktor h 1 displaystyle h 1 nbsp ist kann dieser Schritt weggelassen werden Danach fuhrt Bob folgende Schritte durch Uberprufe ob r displaystyle r nbsp und s displaystyle s nbsp ganze Zahlen sind und im Intervall 1 n 1 displaystyle 1 n 1 nbsp liegen Wenn dies nicht der Fall ist ist die Signatur ungultig Berechne e HASH m displaystyle e textrm HASH m nbsp wobei HASH die gleiche Funktion wie bei der Erzeugung der Signatur ist Bezeichne mit z displaystyle z nbsp die L n displaystyle L n nbsp hochstwertigen Bits von e displaystyle e nbsp Berechne w s 1 mod n displaystyle w s 1 pmod n nbsp Berechne u 1 z w mod n displaystyle u 1 zw pmod n nbsp und u 2 r w mod n displaystyle u 2 rw pmod n nbsp Berechne x 1 y 1 u 1 G u 2 Q A displaystyle x 1 y 1 u 1 G u 2 Q A nbsp Die Signatur ist gultig wenn r x 1 mod n displaystyle r x 1 pmod n nbsp ansonsten ist sie ungultig Mit Hilfe von Straus Algorithmus auch bekannt als Shamir s Trick kann die Summe zweier skalarer Multiplikationen u 1 G u 2 Q A displaystyle u 1 G u 2 Q A nbsp schneller berechnet werden 3 4 Normen und Standards BearbeitenANSI Bearbeiten Der Standard X9 62 2005 des American National Standards Institute ist die massgebliche Spezifikation von ECDSA die von den nachfolgend genannten Standards als Referenz verwendet wird 5 NIST Bearbeiten Das US amerikanische National Institute of Standards and Technology empfiehlt im Standard FIPS 186 4 funfzehn elliptische Kurven 6 SECG Bearbeiten Die Standards for Efficient Cryptography Group SECG ist ein 1998 gegrundetes Konsortium zur Forderung des Einsatzes von ECC Algorithmen welches im Dokument SEC1 auch den ECDSA spezifiziert 7 ISO IEC Bearbeiten Die International Organization for Standardization und die International Electrotechnical Commission definiert ECDSA in dem internationalen Standard ISO IEC 14888 3 8 der altere Standard 15946 2 wurde 2007 zuruckzogen Darin werden neben EC DSA die im Standard verwendete Abkurzung 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 Bearbeiten Das Bundesamt fur Sicherheit in der Informationstechnik legt in der Technischen Richtlinie TR 03111 9 Vorgaben und Empfehlungen u a fur die Implementierung des ECDSA fest Implementierungen BearbeitenOpen Source Bearbeiten OpenSSH Ab Version 5 7 24 Januar 2011 ist ECDSA und der Schlusselaustausch 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 Marz 2014 14 GnuTLS Net Framework ab Version 3 5 15 Literatur BearbeitenX9 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 Lopez 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 BearbeitenDigital Signature Standard includes info on ECDSA csrc nist govEinzelnachweise Bearbeiten FIPS 186 4 PDF 0 7 MB NIST Juli 2013 S 19 und 26 Console Hacking 2010 Memento des Originals vom 15 Dezember 2014 im Internet Archive PDF 9 MB nbsp Info Der Archivlink wurde automatisch eingesetzt und noch nicht gepruft Bitte prufe Original und Archivlink gemass Anleitung und entferne dann diesen Hinweis 1 2 Vorlage Webachiv IABot events ccc de CCC 27C3 S 123 128 Das Doppel Basen Zahlen System in der Elliptischen Kurven Kryptografie PDF 0 2 MB lirmm fr imbert englisch On the complexity of certain multi exponentiation techniques in cryptography PDF caccioppoli mac rub de 1 2 Vorlage Toter Link caccioppoli mac rub de Seite nicht mehr abrufbar festgestellt im Marz 2018 Suche in Webarchiven nbsp Info Der Link wurde automatisch als defekt markiert Bitte prufe den Link gemass Anleitung und entferne dann diesen Hinweis ANSI X9 62 2005 Public Key Cryptography for the Financial Services Industry The Elliptic Curve Digital Signature Algorithm ECDSA NIST Hrsg Digital Signature Standard DSS nist gov PDF www secg org Standards for Efficient Cryptography Group SECG ISO IEC 14888 3 2018 iso org TR 031111 Elliptische Kurven Kryptographie ECC PDF bsi bund de RFC 5656 Elliptic Curve Algorithm Integration in the Secure Shell Transport Layer Dezember 2009 englisch OpenSSH 5 7 has just been released OpenBSD abgerufen am 19 August 2011 OpenSSH 5 7 Schneller durch die Kurve Heise de 25 Januar 2011 abgerufen am 19 August 2011 openssl org Supported Curves ECDSA and ECGOST Java APIs 1 X The Legion of the Bouncy Castle abgerufen am 9 Marz 2018 ECDsa Class System Security Cryptography In msdn microsoft com Abgerufen am 9 Marz 2018 englisch Abgerufen von https de wikipedia org w index php title Elliptic Curve DSA amp oldid 235431056