Elliptic Curve Cryptography

Elliptische Kurve über $\mathbb {R}$

Unter deutsch Elliptische-Kurven-Kryptografie oder Elliptic Curve Cryptography (ECC) 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 Potenzieren) auf dem endlichen Körper ersetzt durch entsprechende Operationen (Punktaddition und Skalarmultiplikation) der Punkte auf der elliptischen Kurve. Das $n$-fache Addieren eines Punktes $P$ zu sich selbst (also die Multiplikation mit dem Skalar $n$) wird mit $nP$ bezeichnet und entspricht einer Potenz $x^{n}$ im ursprünglichen Verfahren.

Das Prinzip wurde Mitte der 1980er Jahre von Victor S. Miller und Neal Koblitz 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 „skalare Division“ für einen Punkt $A$ schwer ist, d. h., es ist kein effizientes Verfahren bekannt, um zu dem gegebenen Punkt $A$ in einer von einem Punkt $P$ erzeugten Gruppe eine natürliche Zahl $a$ mit $aP=A$ zu finden. Damit gibt es auf diesen Kurven ein Analogon zum Diskreten Logarithmus-Problem (DLP) in multiplikativen Gruppen, das ebenfalls DLP genannt wird.

Analog kann man das Computational-Diffie-Hellman-Problem (CDH, zu gegebenen $aP$ und $bP$ berechne $abP$) 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

• Elliptic Curve Diffie-Hellman (ECDH)
• Elliptic Curve Integrated Encryption Scheme (ECIES), auch Integrated Encryption Scheme (IES) genannt
• Elliptic Curve Digital Signature Algorithm (ECDSA)
• ECMQV, ein von Menezes, Qu und Vanstone vorgeschlagenes Protokoll zur Schlüsselvereinbarung

Darüber hinaus gibt es Kurven $E$, auf denen eine Pairing genannte bilineare Abbildung $e\colon E\times E\to G$ in eine Gruppe $G$ existiert. In diesen Kurven ist zwar DDH leicht, da $e(aP,bP)=e(P,abP)$ 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 ${\mathcal {O}}(2^{n/2})$ liegt, wobei $n$ 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. 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 US-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

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

Vergleich des Berechnungsaufwands

Sicherheitsniveau (bit)	Verhältnis bei DH: ECDH
80	3:1
112	6:1
128	10:1
192	32:1
256	64:1

Die Spalte Sicherheitsniveau bezieht sich auf die Bitlänge eines vergleichbar sicheren symmetrischen Verschlüsselungsalgorithmus.

Die mathematischen Operationen auf elliptischen Kurven sind aufwändiger zu berechnen als Operationen in vergleichbar großen endlichen Körpern oder RSA-Modulen. 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. 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, in welcher sie einen erfolgreichen Timing-Angriff auf ECDSA beschreiben. 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 in der Implementierung von OpenSSL (Versionen 0.9.8o und 1.0.0.a) unterschiedlich viel Zeit in Anspruch nimmt. So konnten Brumley und Tuveri ohne Zugriff auf den Server den privaten Schlüssel berechnen. Eine Implementierung mit randomisierten Parametern oder eine geeignete Wahl der Kurvenparameter erlaubt jedoch Operationen mit konstantem Zeitbedarf.

Verwendung

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

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

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.

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.

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

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.

Patente

Laut der US-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.

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.

RFC 6090 beschreibt grundlegende ECC-Algorithmen, die bereits 1994 oder vorher veröffentlicht wurden (und daher heute keinen Patenten mehr unterliegen können). Die im Internet heute weit verbreiteten ECC-Verfahren basieren auf diesen Algorithmen, so dass sie sich nach Veröffentlichung von RFC 6090 recht unproblematisch durchsetzen konnten.

Standardisierungsgremien und Normen

ANSI

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

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

Die Kurven von X9.62-2005 wurden vom Geheimdienst NSA entworfen und eine Hintertür kann aufgrund der Freiheitsgrade in der Kurvenauswahlmethode nicht ausgeschlossen werden. Nach einer Analyse von Dan Bernstein ist der Beweis für die Zufälligkeit der Kurven, den die Kurvenauswahlmethode nach der Behauptung des Standards darstellt, schlichtweg nicht existent.

NIST

• FIPS 186-5

Die NIST-Kurven wurden vom Geheimdienst NSA entworfen und basieren auf Grundkonstanten ungeklärter Herkunft, wodurch eine Hintertür nicht ausgeschlossen werden kann. Sie sind auch bezüglich einiger wünschenswerter Eigenschaften nicht sicher.

IETF

• Algorithmen für ECC
  • RFC: 6090 – Fundamental Elliptic Curve Cryptography Algorithms. Februar 2011 (englisch).
• Nutzung von ECC in X.509 Zertifikaten
  • RFC: 3279 – Algorithms and Identifiers for the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile. April 2002 (englisch).
  • RFC: 5480 – Elliptic Curve Cryptography Subject Public Key Information. März 2009 (englisch).
  • RFC: 5758 – Internet X.509 Public Key Infrastructure: Additional Algorithms and Identifiers for DSA and ECDSA. Januar 2010 (englisch).
• Nutzung von ECC in IKE
  • RFC: 2409 – The Internet Key Exchange (IKE). November 1998 (englisch).
  • RFC: 4754 – IKE and IKEv2 Authentication Using the Elliptic Curve Digital Signature Algorithm (ECDSA). Januar 2007 (englisch).
  • RFC: 5903 – Elliptic Curve Groups modulo a Prime (ECP Groups) for IKE and IKEv2. Juni 2010 (englisch).
• Nutzung von ECC in TLS
  • RFC: 4492 – Elliptic Curve Cryptography (ECC) Cipher Suites for Transport Layer Security (TLS). Mai 2006 (englisch).
  • RFC: 5246 – The Transport Layer Security (TLS) Protocol Version 1.2. August 2008 (englisch).
  • RFC: 5289 – TLS Elliptic Curve Cipher Suites with SHA-256/384 and AES Galois Counter Mode (GCM). August 2008 (englisch).
  • RFC: 5489 – ECDHE_PSK Cipher Suites for Transport Layer Security (TLS). März 2009 (englisch).
  • RFC: 6040 – Tunnelling of Explicit Congestion Notification. November 2010 (englisch).
• Nutzung von ECC in SSH
  • RFC: 5656 – Elliptic Curve Algorithm Integration in the Secure Shell Transport Layer. Dezember 2009 (englisch).
  • RFC: 6239 – Suite B Cryptographic Suites for Secure Shell (SSH). Mai 2011 (englisch).
  • RFC: 6594 – Use of the SHA-256 Algorithm with RSA, Digital Signature Algorithm (DSA), and Elliptic Curve DSA (ECDSA) in SSHFP Resource Records. April 2012 (englisch).
• Nutzung von ECC in CMS
  • RFC: 5753 – Use of Elliptic Curve Cryptography (ECC) Algorithms in Cryptographic Message Syntax (CMS). Januar 2010 (englisch).
  • RFC: 6161 – Elliptic Curve Algorithms for Cryptographic Message Syntax (CMS) Encrypted Key Package Content Type. April 2011 (englisch).
  • RFC: 6162 – Elliptic Curve Algorithms for Cryptographic Message Syntax (CMS) Asymmetric Key Package Content Type. April 2011 (englisch).
  • RFC: 6278 – Use of Static-Static Elliptic Curve Diffie-Hellman Key Agreement in Cryptographic Message Syntax. Juni 2011 (englisch).
• Nutzung von ECC in XML-Signaturen
  • RFC: 4050 – Using the Elliptic Curve Signature Algorithm (ECDSA) for XML Digital Signatures. April 2005 (englisch).
• Nutzung von ECC in OpenPGP
  • RFC: 6637 – Elliptic Curve Cryptography (ECC) in OpenPGP. Juni 2012 (englisch).
• Nutzung von ECC in DNSSEC
  • RFC: 6605 – Elliptic Curve Digital Signature Algorithm (DSA) for DNSSEC. April 2012 (englisch).
• Nutzung von ECC in Kerberos
  • RFC: 5349 – Elliptic Curve Cryptography (ECC) Support for Public Key Cryptography for Initial Authentication in Kerberos (PKINIT). September 2008 (englisch).
• Elliptic Curve Private Key Structure, z. B. für PKCS#8
  • RFC: 5915 – Elliptic Curve Private Key Structure. Juni 2010 (englisch).
• zusätzliche elliptische Kurven für X.509 Zertifikate, IKE, TLS, SSH und S/MIME
  • RFC: 5114 – Additional Diffie-Hellman Groups for Use with IETF Standards. Januar 2008 (englisch).
• zusätzliche elliptische Kurven für X.509 Zertifikate, IKE, TLS, XML Signaturen und CMS
  • RFC: 5639 – Elliptic Curve Cryptography (ECC) Brainpool Standard Curves and Curve Generation. März 2010 (englisch).
• Identitätsbasierte Elliptische-Kurven-Kryptosysteme
  • RFC: 5901 – Extensions to the IODEF-Document Class for Reporting Phishing. Juli 2010 (englisch).
  • RFC: 6507 – Elliptic Curve-Based Certificateless Signatures for Identity-Based Encryption (ECCSI). Februar 2012 (englisch).

Die RFCs greifen auf die Brainpool-Kurven zurück.

ISO

• ISO 14888-3
• ISO 15946

IEEE

• IEEE 1363

Der IEEE-Standard greift auf die gleiche Kurvenauswahlmethode wie der ANSI-Standard zurück, so dass die gleiche Kritik daran geäußert wurde.

ECC-Brainpool

Der ECC-Brainpool, eine Arbeitsgruppe des staatlich-industriellen Vereins TeleTrusT (Mitglieder u. a. BKA, BSI) 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, abweichend zur von vielen anderen Institutionen (z. B. NIST, SECG) präferierten Bitlänge 521.

Der Designraum der Brainpool-Kurven enthält so viele Freiheitsgrade, dass eine Hintertür nicht sicher ausgeschlossen werden kann. Die Brainpool-Kurven sind auch bezüglich einiger wünschenswerter Eigenschaften nicht sicher.

SECG

Die „Standards for Efficient Cryptography Group“ (SECG) ist ein 1998 gegründetes Konsortium zur Förderung des Einsatzes von ECC-Algorithmen. SECG hat als erste die 521-Bit-Kurve spezifiziert, die dann vom NIST übernommen wurde. Diese spezielle Wahl beruht auf der Tatsache, dass auf Primzahlen der Form $2^{n}-1$ zurückgegriffen werden sollte, um das Rechnen mit Restklassen modulo dieser Primzahl zu beschleunigen. Für $300<n<600$ ist jedoch nur $2^{521}-1$ eine Primzahl.

SECG SEC 2 greift auf die Kurven der NSA aus dem NIST-Standard zurück und übernimmt zusätzlich die nicht zutreffende Behauptung des ANSI-Standards, sie seien verifizierbar zufällig gewählt worden.

BSI

Das Bundesamt für Sicherheit in der Informationstechnik legt in der Technical Guideline TR-03111 Version 2.0 bzw. 2.1 Vorgaben und Empfehlungen für die Implementierung von Elliptische-Kurven-Kryptographie fest. Man beachte jedoch, dass der in der Version 2.0 definierte Algorithmus EC-Schnorr nicht kompatibel zu den in ISO 14888-3 definierten Schnorr-Signaturen EC-SDSA und EC-FSDSA ist.

SafeCurves

Das SafeCurves-Projekt von Bernstein hat mit den sicheren, akademischen Kurven Curve25519 (bzw. Ed25519), Ed448-Goldilocks und E-521 inzwischen einen De-facto-Standard geschaffen. Die staatlichen Kurven haben das Vertrauen mancher führenden Kryptographen verloren, da die Kurvenwahl nicht vollständig transparent nachvollziehbar ist und somit eine ähnliche kleptographische Hintertür wie bei Dual EC DRBG oder eine sonstige Hintertür nicht sicher ausgeschlossen werden kann.

Siehe auch

• DNSCurve
• Elliptic Curve DSA

Literatur

• Annette Werner: Elliptische Kurven in der Kryptographie. Springer, 2002, ISBN 3-540-42518-7. 
• Lawrence C. Washington: Elliptic Curves: Number Theory and Cryptography. CRC, 2008, ISBN 978-1-4200-7146-7. 
• David H. von Seggern: CRC Standard Curves and Surfaces with Mathematica, Third Edition. CRC, 2016, ISBN 978-1-4822-5021-3. 

Weblinks

• Video einer Vorlesung von Neal Koblitz ´über Elliptic-Curve-Cryptology, 1998, (MPG; 1,8 GB, englisch)
• ECC-Arbeitsgruppe, Domainparameter (PDF; 0,1 MB)
• Freie Implementation des „Elliptic Curve DSA“ für Windows und Linux, Download und Anleitung (englisch)