Elliptic Curve Cryptography

aus Wikipedia, der freien Enzyklopädie
Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 7. Juni 2016 um 01:59 Uhr durch Zmand (Diskussion | Beiträge) (JSTOR-Link geändert). Sie kann sich erheblich von der aktuellen Version unterscheiden.
Zur Navigation springen Zur Suche springen
Elliptische Kurve über

Unter Elliptic Curve Cryptography (ECC) oder deutsch Elliptische-Kurven-Kryptografie versteht man asymmetrische Kryptosysteme, die Operationen auf elliptischen Kurven über endlichen Körpern verwenden. Diese Verfahren sind nur sicher, wenn diskrete Logarithmen in der Gruppe der Punkte der elliptischen Kurve nicht effizient berechnet werden können.

Jedes Verfahren, das auf dem diskreten Logarithmus in endlichen Körpern basiert, wie z. B. der Digital Signature Algorithm, das Elgamal-Verschlüsselungsverfahren oder der Diffie-Hellman-Schlüsselaustausch, lässt sich in einfacher Weise auf elliptische Kurven übertragen und somit zu einem Elliptic-Curve-Kryptosystem umformen. Dabei werden die beim Originalverfahren eingesetzten Operationen (Multiplikation und Exponentiation) auf dem endlichen Körper ersetzt durch entsprechende Operationen (Punktaddition und Skalarmultiplikation) der Punkte auf der elliptischen Kurve. Das -fache Addieren eines Punktes zu sich selbst (also die Multiplikation mit dem Skalar ) wird mit bezeichnet und entspricht einer Exponentiation im ursprünglichen Verfahren.

Das Prinzip wurde Mitte der 1980er Jahre von Victor S. Miller[1] und Neal Koblitz[2] unabhängig voneinander vorgeschlagen.

Funktionsprinzip

Auf elliptischen Kurven kann eine additive zyklische Gruppe definiert werden, die aus den Vielfachen eines Punktes auf der Kurve, des Erzeugers der Gruppe, besteht. Das Addieren zweier Punkte in der Gruppe ist einfach, es gibt aber Kurven, auf denen die „Division“ zweier Punkte schwer ist, d. h. es ist kein effizientes Verfahren bekannt, um zu einem gegebenen Punkt in einer von einem Punkt erzeugten Gruppe eine natürliche Zahl mit zu finden. Damit gibt es auf diesen Kurven ein Analogon zum Diskreter-Logarithmus-Problem (DLP) in multiplikativen Gruppen, das ebenfalls DLP genannt wird.

Analog kann man das Computational-Diffie-Hellman-Problem (CDH, zu gegebenen und berechne ) und das Decisional-Diffie-Hellman-Problem (DDH) definieren. Dadurch können kryptographische Verfahren, deren Sicherheit auf diesen Problemen beruht, auf elliptische Kurven übertragen werden, für die diese Probleme vermutlich schwierig sind. Beispiele dafür sind

Darüber hinaus gibt es Kurven , auf denen eine Pairing genannte bilineare Abbildung in eine Gruppe existiert. In diesen Kurven ist zwar DDH leicht, da gilt, die Existenz des Pairings erlaubt aber viele neuartige Anwendungen.

Effizienz und Sicherheit

Da das Problem des diskreten Logarithmus in elliptischen Kurven (ECDLP) deutlich schwerer ist als die Berechnung des diskreten Logarithmus in endlichen Körpern oder die Faktorisierung ganzer Zahlen, kommen Kryptosysteme, die auf elliptischen Kurven beruhen – bei vergleichbarer Sicherheit – mit erheblich kürzeren Schlüsseln aus als die herkömmlichen asymmetrischen Kryptoverfahren, wie z. B. das RSA-Kryptosystem oder der Diffie-Hellman-Schlüsselaustausch. Die derzeit schnellsten Algorithmen sind der Babystep-Giantstep-Algorithmus und die Pollard-Rho-Methode, deren Laufzeit bei liegt, wobei die Bitlänge der Größe des zugrundeliegenden Körpers ist. Nach heutigem Kenntnisstand wird z. B. mit einer Schlüssellänge von 160 Bit eine ähnliche Sicherheit erreicht wie bei RSA mit 1024 Bit.[3] ECC eignet sich daher besonders dann, wenn die Speicher- oder Rechenkapazität begrenzt ist, z. B. in Smartcards oder anderen eingebetteten Systemen.

Beispielhaft werden hier die vom U.S.-amerikanischen National Institute of Standards and Technology (NIST) und ECRYPT angegebenen äquivalenten Schlüssellängen für RSA- bzw. Diffie-Hellman-Schlüssel für bestimmte Sicherheitsniveaus aufgelistet.

Vergleich der Verschlüsselungsstärken[4][5]
Sicherheitsniveau RSA/DH (NIST) RSA/DH (ECRYPT) ECDH
80 1024 1248 160
112 2048 2432 224
128 3072 3248 256
192 7680 7936 384
256 15360 15424 512[6]
Vergleich des Berechnungsaufwands[4]
Sicherheitsniveau (bit) Verhältnis bei DH : ECDH
80 3:1
112 6:1
128 10:1
192 32:1
256 64:1

Die mathematischen Operationen auf elliptischen Kurven sind aufwändiger zu berechnen als Operationen in vergleichbar großen endlichen Körpern oder RSA-Moduln. Allerdings kann mit erheblich kürzeren Schlüsseln ein Sicherheitsniveau erreicht werden, das mit Verfahren auf Basis des diskreten Logarithmus oder mit RSA vergleichbar ist. Unter anderem durch die kürzeren Schlüssel können Elliptische-Kurven-Kryptosysteme daher bei einem vergleichbaren Sicherheitsniveau schneller sein.[7] Ein Vergleich der Recheneffizienz dieser kryptographischen Verfahren hängt jedoch stark von den Details der Implementierung (kryptographische Parameter, Arithmetik, Optimierungen, Programmiersprache und Compiler, zugrunde liegende Hardware) ab.

Seitenkanalangriffe

Im Mai 2011 veröffentlichten die Forscher Billy Bob Brumley und Nicola Tuveri eine wissenschaftliche Arbeit,[8] in welcher sie einen erfolgreichen Timing-Angriff auf ECDSA beschreiben.[9] Dabei setzten die Forscher einen Server mit OpenSSL auf. Der Angriff erfolgte über die Tatsache, dass das Ver- und Entschlüsseln mit unterschiedlichen ECDSA-Schlüsseln unterschiedlich viel Zeit in Anspruch nimmt. So konnten Brumley und Tuveri ohne Zugriff auf den Server den privaten Schlüssel berechnen. Eine geeignete Wahl der Kurvenparameter erlaubt jedoch Algorithmen mit konstantem Zeitbedarf. [10]

Verwendung

Elliptic Curve Cryptography wird von modernen Windows-Betriebssystemen (ab Vista) unterstützt.[11]

Produkte der Mozilla Foundation (u. a. Firefox, Thunderbird) unterstützen ECC mit min. 256 Bit Key-Länge (P-256 aufwärts).[12]

Die in Österreich gängigen Bürgerkarten (e-card, Bankomat- oder a-sign Premium Karte) verwenden ECC seit ihrer Einführung 2004/2005, womit Österreich zu den Vorreitern in deren breitem Einsatz zählt.[13]

Die Reisepässe der meisten Europäischen Staaten (u. a. Deutschland) verwenden ECC zumindest für den Schutz des Zugriffs auf den Chip mittels Extended Access Control, einige Länder (u. a. Deutschland und Schweiz) verwenden es auch, um die auf dem Chip gespeicherten Daten mit Passive Authentication zu schützen.[14]

In Deutschland verwendet der neue Personalausweis ebenfalls ECC, sowohl für Extended Access Control als auch für Passive Authentication.[15]

Sony benutzt Elliptic Curve DSA zur digitalen Signierung von Software für die PlayStation 3. Im Jahr 2010 gelang einer Hackergruppe die Ermittlung des benutzten Private Key und somit ein fast vollständiger Bruch der Sicherheitssysteme. Dies war jedoch vor allem auf Implementierungsfehler von Sony zurückzuführen und nutzte keine Sicherheitslücken im verwendeten ECC-Verfahren aus.[16]

Patente

Laut der U.S.-amerikanischen National Security Agency (NSA) sind Implementierungen mit Patentproblemen konfrontiert. Vor allem die kanadische Certicom Inc. besitzt demnach mehr als 130 Patente, die für ECC oder Public-Key-Kryptographie benötigt werden. 26 davon wurden von der NSA lizenziert, um ECC-Verfahren zu Zwecken nationaler Sicherheit zu implementieren.[4]

In einer Studie des Zentrums für sichere Informationstechnologie Austria (A-SIT) wird auf Patente in effizienten Implementierungen hingewiesen, wobei ECC selbst „prinzipiell patentfrei“ sei.[17]

Standardisierungsgremien und Normen

ANSI

ANSI X9.62-2005 ist die aktuelle Standardisierung des ECDSA.[18]

  • ANSI X9.62 (ECDSA)
  • ANSI X9.63 (Key Agreement und Key Transport)

NIST

IETF

ISO

IEEE

ECC-Brainpool

Der ECC-Brainpool, eine Arbeitsgruppe von Firmen und Institutionen zum Thema Elliptic Curve Cryptography, hat 2005 eine Anzahl von elliptischen Kurven spezifiziert, welche im März 2010 im RFC 5639 der IETF standardisiert wurde. Bei diesen Kurven ist besonders die Wahl der Bitlänge 512 zu erwähnen, ein Gegensatz zur von vielen anderen Institutionen (z. B. NIST, SECG) präferierten Bitlänge 521.

SECG

Die „Standards for Efficient Cryptography Group“ (SECG) ist ein 1998 gegründetes Konsortium zur Förderung des Einsatzes von ECC-Algorithmen.[23]

BSI

Das Bundesamt für Sicherheit in der Informationstechnik legt in der Technical Guideline TR-03111 Vorgaben und Empfehlungen für die Implementierung von Elliptische-Kurven-Kryptographie auf Basis von ISO/IEC 15946 fest.

Siehe auch

Literatur

Weblinks

Einzelnachweise

  1. ↑ Victor S. Miller: Use of Elliptic Curves in Cryptography. In: Advances in Cryptology – CRYPTO ’85 Proceedings (= Lecture Notes in Computer Science). Band 218. Springer, 1986, S. 417–426, doi:10.1007/3-540-39799-X_31.
  2. ↑ Neal Koblitz: Elliptic Curve Cryptosystems. In: Mathematics of Computation. Band 48, Nr. 177. American Mathematical Society, 1987, S. 203–209, JSTOR:2007884.
  3. ↑ Cryptographic Key Length Recommendation. BlueKrypt, abgerufen am 3. November 2011 (englisch).
  4. ↑ a b c The Case for Elliptic Curve Cryptography. 15. Januar 2009, abgerufen am 3. November 2011 (englisch).
  5. ↑ ECRYPT II: ECRYPT II Yearly Report on Algorithms and Keysizes (2010–2011). 2011, S. 30 (www.ecrypt.eu.org/documents/D.SPA.7.pdf [PDF]).
  6. ↑ NIST hat nur eine 521-bit Kurve standardisiert und gibt daher als äquivalentes Sicherheitsniveau 521 bit an.
  7. ↑ R. Szerwinski, T. Güneysu: Exploiting the Power of GPUs for Asymmetric Cryptography. Proceedings of CHES 2008, pp. 79–99, 2008
  8. ↑ Billy Bob Brumley, Nicola Tuveri: Remote Timing Attacks are Still Practical. In: Cryptology ePrint Archive: Report 2011/232. 11. Mai 2011, abgerufen am 3. November 2011 (englisch, Abruf als PDF möglich).
  9. ↑ Erfolgreiche Timing-Angriffe auf Verschlüsselung mit elliptischen Kurven. heise.de, 23. Mai 2011, abgerufen am 3. November 2011 (deutsch).
  10. ↑ SafeCurves: choosing safe curves for elliptic-curve cryptography. Abgerufen am 7. Juni 2016 (englisch).
  11. ↑ Elisabeth Oswald: Kryptosysteme basierend auf Elliptischen Kurven Einsatz und Verbreitung in Standardsoftware. (PDF; 445 kB) Zentrum für sichere Informationstechnologie - Austria (A-SIT), 29. Juli 2009, abgerufen am 2. November 2011 (deutsch).
  12. ↑ Mozilla CA Certificate Maintenance Policy (Version 2.0). mozilla.org, 4. November 2011, abgerufen am 4. November 2011 (englisch): „We consider the following algorithms and key sizes to be acceptable and supported in Mozilla products: … Elliptic Curve Digital Signature Algorithm (using ANSI X9.62) over SECG and NIST named curves P-256, P-384, and P-512;“
  13. ↑ Elliptische Kurven. Abgerufen am 3. November 2011 (deutsch).
  14. ↑ Zdeněk Říha: Electronic passports. (PDF) JRC Ispra, European Commission, Masaryk University, Brno, 13. September 2008, archiviert vom Original am 15. Februar 2010; abgerufen am 3. November 2011 (englisch).
  15. ↑ Dr. Manfred Lochter und Dr. Johannes Merkle: Ein neuer Standard für elliptische Kurven. (PDF; 796 kB) Mai 2009, abgerufen am 3. November 2011 (deutsch, Vortrag vom 11. Deutschen IT-Sicherheitskongress 2009).
  16. ↑ 27C3: Sicherheitssystem der Playstation 3 ausgehebelt. heise.de, 30. Dezember 2010, abgerufen am 5. November 2011.
  17. ↑ Elisabeth Oswald: Einsatz und Bedeutung Elliptischer Kurven für die elektronische Signatur. (PDF; 443 kB) A-SIT, 2001, S. 27, abgerufen am 2. November 2011 (deutsch).
  18. ↑ ANSI X9.62-2005, Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)
  19. ↑ (ECDSA) Digital Signature Standard (DSS). (PDF; 1,2 MB) FIPS PUB 186-3. National Institute of Standards and Technology (NIST), Juni 2009, abgerufen am 3. November 2011 (englisch).
  20. ↑ Information technology -- Security techniques -- Digital signatures with appendix -- Part 3: Discrete logarithm based mechanisms. ISO/IEC, abgerufen am 3. November 2011 (englisch, Kostenpflichtiger PDF-Abruf): „ISO/IEC 14888-3:2006 specifies digital signature mechanisms with appendix whose security is based on the discrete logarithm problem. It provides a general description of a digital signature with appendix mechanism, and a variety of mechanisms that provide digital signatures with appendix.“
  21. ↑ Information technology -- Security techniques -- Cryptographic techniques based on elliptic curves. ISO/IEC, abgerufen am 3. November 2011 (englisch, Kostenpflichtiger PDF-Abruf): „ISO/IEC 15946 specifies public-key cryptographic techniques based on elliptic curves. It consists of five parts and includes the establishment of keys for symmetric cryptographic techniques, and digital signature mechanisms.“
  22. ↑ Standard Specifications For Public-Key Cryptography. The IEEE P1363 project develops Standard Specifications For Public-Key Cryptography, towards the goal of issuing a series of IEEE standards documents. IEEE, 10. Oktober 2008, abgerufen am 3. November 2011 (englisch).
  23. ↑ http://www.secg.org/index.php?action=secg,about
Abgerufen von „https://de.wikipedia.org/w/index.php?title=Elliptic_Curve_Cryptography&oldid=155056289“