Hauptmenü öffnen

Wikipedia β

Elliptic Curve DSA

(Weitergeleitet von ECDSA)

Der Elliptic Curve Digital Signature Algorithm (ECDSA) ist eine Variante des Digital Signature Algorithm (DSA), der Elliptische-Kurven-Kryptographie verwendet.

Inhaltsverzeichnis

Unterschiede zum normalen DSA-VerfahrenBearbeiten

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üsselerzeugungBearbeiten

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 SignaturBearbeiten

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

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

Überprüfung einer SignaturBearbeiten

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.[3][4]

Normen und StandardsBearbeiten

ANSIBearbeiten

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]

NISTBearbeiten

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

SECGBearbeiten

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/IECBearbeiten

Die International Organization for Standardization und die International Electrotechnical Commission definiert ECDSA in dem internationalen Standard 14888-3 (der ältere Standard 15946-2 wurde 2007 zurückzogen). Im Standard 14888-3 und einer Ergänzung (Amendment 1) 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.

BSIBearbeiten

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

ImplementierungenBearbeiten

Open SourceBearbeiten

EinzelnachweiseBearbeiten

  1. NIST FIPS 186-4, Juli 2013, pp. 19 und 26 (PDF; 0,7 MB)
  2. CCC, 27C3, Console Hacking 2010, Seite 123–128 (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. http://caccioppoli.mac.rub.de/website/papers/multiexp.pdf@1@2Vorlage:Toter Link/caccioppoli.mac.rub.de (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)
  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).

LiteraturBearbeiten

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

WeblinksBearbeiten