Elliptische Kurve-Geheimschrift (ECC) ist eine Annäherung an die Geheimschrift des öffentlichen Schlüssels, die auf der algebraischen Struktur von elliptischen Kurven über begrenzte Felder gestützt ist. Der Gebrauch von elliptischen Kurven in der Geheimschrift wurde unabhängig von Neal Koblitz und Victor S. Miller 1985 angedeutet.

Elliptische Kurven werden auch in mehrerer ganzer Zahl factorization Algorithmen verwendet, die Anwendungen in der Geheimschrift, wie Lenstra elliptische Kurve factorization haben.

Einführung

Geheimschrift des öffentlichen Schlüssels basiert auf der Hartnäckigkeit von bestimmten mathematischen Problemen. Frühe Systeme des öffentlichen Schlüssels sind das sichere Annehmen, dass es zum Faktor eine große aus zwei oder mehr großen Hauptfaktoren zusammengesetzte ganze Zahl schwierig ist. Weil elliptische Kurve Protokolle gestützt hat, wird es angenommen, dass die Entdeckung des getrennten Logarithmus eines zufälligen elliptischen Kurve-Elements in Bezug auf einen öffentlich bekannten Grundpunkt unausführbar ist. Die Größe der elliptischen Kurve bestimmt die Schwierigkeit des Problems. Der primäre durch ECC versprochene Vorteil ist eine kleinere Schlüsselgröße, Lagerung und Übertragungsvoraussetzungen reduzierend — d. h., dass eine elliptische Kurve-Gruppe dasselbe Niveau der Sicherheit zur Verfügung stellen konnte, die durch ein RSA-basiertes System mit einem großen Modul und entsprechend größerem Schlüssel — z.B gewährt ist, sollte ein ECC 256-Bit-Publikum-Schlüssel vergleichbare Sicherheit einem RSA 3072-Bit-Publikum-Schlüssel zur Verfügung stellen (sieh #Key_sizes).

Zu aktuellen kryptografischen Zwecken ist eine elliptische Kurve eine Flugzeug-Kurve, die aus den Punkten besteht, die die Gleichung befriedigen

zusammen mit einem ausgezeichneten Punkt an der Unendlichkeit, angezeigtem . (Die Koordinaten hier sollen aus einem festen begrenzten Feld der Eigenschaft gewählt werden, die 2 oder 3 nicht gleich ist, oder die Kurve-Gleichung wird etwas mehr kompliziert sein.)

Dieser Satz zusammen mit der Gruppenoperation der elliptischen Gruppentheorie bildet eine Gruppe von Abelian mit dem Punkt an der Unendlichkeit als Identitätselement. Die Struktur der Gruppe wird von der Teiler-Gruppe der zu Grunde liegenden algebraischen Vielfalt geerbt.

Bezüglich anderen populären öffentlichen Schlüssels cryptosystems ist kein mathematischer Beweis der Sicherheit für ECC veröffentlicht worden. Jedoch hat die amerikanische Staatssicherheitsagentur ECC durch das Umfassen von Schemas gutgeheißen, die darauf in seinem Gefolge B Satz von empfohlenen Algorithmen gestützt sind, und erlaubt ihren Gebrauch, um Information zu schützen, die bis zum Spitzengeheimnis mit 384-Bit-Schlüsseln klassifiziert ist. Während das RSA-Patent 2000 abgelaufen ist, gibt es Patente in der Kraft, die bestimmte Aspekte der ECC Technologie bedeckt, obwohl einige dass die elliptische Bundeskurve Digitalunterschrift-Standard behaupten (ECDSA; NIST FIPS 186-3), und bestimmte praktische ECC-basierte Schlüsselaustauschschemas (einschließlich ECDH) können durchgeführt werden, ohne sie zu brechen.

Kryptografische Proposition

Die komplette Sicherheit von ECC hängt von der Fähigkeit ab, eine Punkt-Multiplikation und die Unfähigkeit zu schätzen, den multiplicand gegeben die ursprünglichen Punkte und Produktpunkte zu schätzen.

Kryptografische Schemas

Mehrere getrennte Logarithmus-basierte Protokolle sind an elliptische Kurven angepasst worden, die Gruppe mit einer elliptischen Kurve ersetzend:

• das Schlüsselabmachungsschema der elliptischen Kurve Diffie-Hellman (ECDH) basiert auf dem Diffie-Hellman Schema,
• Elliptic Curve Integrated Encryption Scheme (ECIES), auch bekannt als Elliptische Kurve Vermehrtes Verschlüsselungsschema oder einfach das Elliptische Kurve-Verschlüsselungsschema,
• Elliptic Curve Digital Signature Algorithm (ECDSA) basiert auf dem Digitalunterschrift-Algorithmus,
• das ECMQV Schlüsselabmachungsschema basiert auf dem MQV Schlüsselabmachungsschema.
• das ECQV implizite Zertifikat-Schema.

Auf der RSA Konferenz 2005 hat National Security Agency (NSA) Suite B bekannt gegeben, der exklusiv ECC für die Digitalunterschrift-Generation und den Schlüsselaustausch verwendet. Das Gefolge ist beabsichtigt, um sowohl klassifizierte als auch nicht klassifizierte Staatssicherheitssysteme und Information zu schützen.

Kürzlich ist eine Vielzahl von kryptografischen Primitiven, die auf bilinearem mappings auf verschiedenen elliptischen Kurve-Gruppen wie die Paarung von Weil und Tate gestützt sind, eingeführt worden. Auf diesen Primitiven gestützte Schemas stellen effiziente Identitätsbasierte Verschlüsselung sowie Paarungsbasierte Unterschriften, signcryption, Schlüsselabmachung und Proxywiederverschlüsselung zur Verfügung.

Durchführungsrücksichten

Obwohl die Details jedes besonderen elliptischen Kurve-Schemas im über einigen allgemeinen Durchführungsrücksichten Verweise angebrachten Artikel beschrieben werden, werden hier besprochen.

Bereichsrahmen

Um ECC zu verwenden, müssen sich alle Parteien über alle Elemente einigen, die die elliptische Kurve, d. h. die Bereichsrahmen des Schemas definieren. Das Feld wird durch p im Hauptfall und dem Paar der M und f im binären Fall definiert. Die elliptische Kurve wird durch die Konstanten a und in seiner Definieren-Gleichung verwendeter b definiert. Schließlich wird die zyklische Untergruppe durch seinen Generator definiert (auch bekannt als. stützen Sie Punkt) G. Für die kryptografische Anwendung ist die Ordnung von G, der die kleinste nichtnegative Zahl n solch ist, dass, normalerweise erst. Da n die Größe einer Untergruppe davon ist, folgt aus dem Lehrsatz von Lagrange, dass die Zahl eine ganze Zahl ist. In kryptografischen Anwendungen muss diese Nummer h, genannt den cofactor, und vorzugsweise klein sein. Lassen Sie uns zusammenfassen: Im Hauptfall sind die Bereichsrahmen, und im binären Fall sind sie.

Wenn es keine Versicherung gibt, dass Bereichsrahmen von einer in Bezug auf ihren Gebrauch vertrauten Partei erzeugt wurden, müssen die Bereichsrahmen vor dem Gebrauch gültig gemacht werden.

Die Generation von Bereichsrahmen wird von jedem Teilnehmer nicht gewöhnlich getan, da das das Zählen der Zahl von Punkten auf einer Kurve einschließt, die zeitraubend und lästig ist, um durchzuführen. Infolgedessen haben mehrere Standardkörper Bereichsrahmen von elliptischen Kurven für mehrere allgemeine Feldgrößen veröffentlicht. Solche Bereichsrahmen sind als "Standardkurven" allgemein bekannt, oder "hat Kurven genannt"; in einer genannten Kurve kann entweder namentlich oder durch den einzigartigen in den Standard-Unterlagen definierten Gegenstand-Bezeichner Verweise angebracht werden:

• NIST, empfohlene elliptische Kurven für den Regierungsgebrauch
• SECG, SEC 2: Empfohlene Elliptische Kurve-Bereichsrahmen
• ECC Brainpool, ECC Brainpool Standardkurven und Kurve-Generation

SECG Testvektoren sind auch verfügbar.. NIST hat viele SECG-Kurven genehmigt, also gibt es ein bedeutendes Übergreifen zwischen den Spezifizierungen, die durch NIST und SECG veröffentlicht sind. Bereichsrahmen der europäischen Gemeinschaft können entweder durch den Wert oder namentlich angegeben werden.

Wenn ein (trotz vorerwähnten oben) jemandes eigene Bereichsrahmen bauen will, sollte man das zu Grunde liegende Feld auswählen und dann eine der folgenden Strategien verwenden, eine Kurve mit dem passenden (d. h., fast erst) Zahl von Punkten mit einer der folgenden Methoden zu finden:

• wählen Sie eine zufällige Kurve aus und verwenden Sie einen allgemeinen Punkt aufzählenden Algorithmus, zum Beispiel, den Algorithmus von Schoof oder Schoof-Elkies-Atkin Algorithmus,
• wählen Sie eine zufällige Kurve von einer Familie aus, die leichte Berechnung der Zahl von Punkten (z.B, Kurven von Koblitz), oder erlaubt
• wählen Sie die Zahl von Punkten aus und erzeugen Sie eine Kurve mit dieser Zahl von Punkten mit der komplizierten Multiplikationstechnik.

Mehrere Klassen von Kurven sind schwach und sollten vermieden werden:

• Kurven mit der NichthauptM sind für Abfallangriffe von Weil verwundbar.
• biegt sich solch, dass sich n teilt (wo p die Eigenschaft des Feldes - q für ein Hauptfeld ist, oder für ein binäres Feld) für genug kleinen B für den MOV-Angriff verwundbar sind, der übliche LDP in einem kleinen Grad-Erweiterungsfeld anwendet, ECDLP zu lösen. Der bestimmte B sollte gewählt werden, so dass getrennte Logarithmen im Feld mindestens so schwierig sind zu rechnen wie getrennte Anmeldungen der elliptischen Kurve.
• biegt sich solch, die für den Angriff verwundbar sind, der die Punkte auf der Kurve zur zusätzlichen Gruppe von kartografisch darstellt

Schlüsselgrößen

Seit allen schnellsten bekannten Algorithmen, die erlauben, den ECDLP (riesiger Schritt des Baby-Schritts, der rho von Pollard, usw.), Bedürfnis-Schritte zu lösen, hieraus folgt dass die Größe des zu Grunde liegenden Feldes grob zweimal der Sicherheitsparameter sein soll. Zum Beispiel für 128-Bit-Sicherheit braucht man eine Kurve, wo. Dem kann mit der Begrenzt-Feldgeheimschrift gegenübergestellt werden (z.B, DSA), der öffentliche 3072-Bit-Schlüssel und private 256-Bit-Schlüssel und ganze Zahl factorization Geheimschrift verlangt (z.B, RSA), der private und öffentliche 3072-Bit-Schlüssel verlangt.

Das härteste ECC Schema (öffentlich) gebrochen hatte bis heute einen 112-Bit-Schlüssel für den Hauptfeldfall und einen 109-Bit-Schlüssel für den binären Feldfall. Für den Hauptfeldfall wurde das im Juli 2009 mit einer Traube von mehr als 200 PlayStation 3 Spielkonsolen gebrochen und könnte in 3.5 Monaten mit dieser Traube beendet worden sein, wenn das Laufen unaufhörlich (sieht). Für den binären Feldfall wurde es im April 2004 mit 2600 Computern seit 17 Monaten gebrochen.

Ein aktuelles Projekt zielt darauf, die ECC2K-130-Herausforderung durch Certicom, durch das Verwenden einer breiten Reihe der verschiedenen Hardware zu brechen: Zentraleinheiten, GPUs, FPGA.

Projektive Koordinaten

Eine Nachforschung der Hinzufügungsregeln zeigt dass, um zwei Punkte hinzuzufügen, braucht man nicht nur mehrere Hinzufügungen und Multiplikationen in sondern auch eine Inversionsoperation. Die Inversion (für den gegebenen finden solch, dass) ist eine bis zwei Größenordnungen langsamer als Multiplikation. Glücklich können Punkte auf einer Kurve in verschiedenen Koordinatensystemen vertreten werden, die nicht verlangen, dass eine Inversionsoperation zwei Punkte hinzufügt. Solche mehreren Systeme wurden vorgeschlagen: Im projektiven System wird jeder Punkt durch drei Koordinaten mit der folgenden Beziehung vertreten:; im System von Jacobian wird ein Punkt auch mit drei Koordinaten vertreten, aber eine verschiedene Beziehung wird verwendet:; im System von López-Dahab ist die Beziehung; im modifizierten System von Jacobian werden dieselben Beziehungen verwendet, aber vier Koordinaten werden versorgt und für Berechnungen verwendet; und im System von Chudnovsky Jacobian werden fünf Koordinaten verwendet. Bemerken Sie, dass es verschiedene Namengeben-Vereinbarung, zum Beispiel, IEEE p1363-2000-Standardgebrauch "projektive Koordinaten" geben kann, um sich darauf zu beziehen, was Koordinaten von Jacobian allgemein genannt wird. Eine zusätzliche Beschleunigung ist möglich, wenn Mischkoordinaten verwendet werden.

Die schnelle Verminderung (NIST Kurven)

Die Verminderung modulo p (der für die Hinzufügung und Multiplikation erforderlich ist) kann viel schneller durchgeführt werden, wenn der erste p eine pseudo-Mersenne Blüte d. h. zum Beispiel ist, oder im Vergleich zur Verminderung von Barrett es eine Größenordnungsbeschleunigung geben kann. Die Beschleunigung hier ist eine praktische aber nicht theoretische, und ist auf die Tatsache zurückzuführen, dass die Module von Zahlen gegen Zahlen in der Nähe von Mächten zwei effizient durch Computer durchgeführt werden können, die auf Binärzahlen mit bitwise Operationen funktionieren.

Die Kurven mit pseudo-Mersenne p werden durch NIST empfohlen. Und doch ist ein anderer Vorteil der NIST-Kurven die Tatsache, dass sie = 3 verwenden, der Hinzufügung in Koordinaten von Jacobian verbessert.

NIST-empfohlene elliptische Kurven

NIST empfiehlt fünfzehn elliptische Kurven. Spezifisch hat FIPS 186-3 zehn empfohlene begrenzte Felder:

• Fünf Hauptfelder für die bestimmte Blüte p von Größen 192, 224, 256, 384, und 521 Bit. Für jedes der Hauptfelder wird eine elliptische Kurve empfohlen.
• Fünf binäre Felder für die M gleiche 163, 233, 283, 409, und 571. Für jedes der binären Felder, einer elliptischer Kurve und einer Kurve von Koblitz wurde ausgewählt.

Die NIST Empfehlung enthält so insgesamt fünf Hauptkurven und zehn binäre Kurven. Die Kurven wurden für die optimale Sicherheit und Durchführungsleistungsfähigkeit gewählt.

Seitenkanal-Angriffe

Verschieden von Systemen von LDP (wo es möglich ist, dasselbe Verfahren für das Quadrieren und die Multiplikation zu verwenden) ist die Hinzufügung der europäischen Gemeinschaft bedeutsam verschieden, um sich und allgemeine Hinzufügung zu verdoppeln , je nachdem das Koordinatensystem verwendet hat. Folglich ist es wichtig, Seitenkanalangriffen entgegenzuwirken (z.B, zeitlich festlegend oder einfache/unterschiedliche Macht-Analyse-Angriffe) das Verwenden hat zum Beispiel Muster-Fenster befestigt (auch bekannt als. Kamm) Methoden (bemerken, dass das die Berechnungszeit nicht vergrößert). Eine andere Sorge für ECC-Systeme ist die Gefahr von Schuld-Angriffen besonders, wenn sie auf klugen Karten läuft.

Quant-Rechenangriffe

Elliptische Kurve-Geheimschrift ist für einen Algorithmus von modifiziertem Shor verwundbar, für das getrennte Logarithmus-Problem auf elliptischen Kurven zu beheben.

Patente

Mindestens ein ECC Schema (ECMQV) und einige Durchführungstechniken werden durch Patente bedeckt.

Durchführungen

Offene Quelle

• OpenSSL - C Bibliothek mit der ECC Funktionalität
• Geheim-++ - C ++ Bibliothek mit der ECC Funktionalität
• Botan - eine BSD-lizenzierte kryptografische Bibliothek, die in C ++ geschrieben ist
• OpenSSH: Eine freie Version der SSH Nachrichtenwerkzeuge für Fernverbindungen
• NSS: Offene Quelle Geheimbibliotheken mit ECC
• seccure: minimaler Fußabdruck GPLed ECC Werkzeug mit der öffentlichen Schlüsselverschlüsselung und den Digitalunterschriften
• SKS: sehr kleines offenes Quellwerkzeug für ECC (wie ein vereinfachter PGP)
• eccGnuPG: Ein experimenteller Fleck zu GnuPG
• Curve25519: Ein modernster Diffie-Hellman fungiert durch Dan Bernstein
• NaCl: Der Netzwerkanschluss und Geheimschrift-Bibliothek
• TinyECC: Ein Softwarepaket, das ECC Operationen auf TinyOS zur Verfügung stellt
• libecc: Offene Quelle ECC Bibliothek
• Elastisches Schloss: Das Geheimpaket der offenen Quelle für Java und C#, der ECC einschließt
• Eiffel Verschlüsselungsbibliothek: Offene Quellgeheimschrift-Bibliothek für die Sprache von Eiffel
• RSA BSAFE(R) Share für die javanische Plattform und Anteil für C/C ++: Freie binäre Werkzeuge
• Durchführung der Elliptischen Kurve-Geheimschrift auf einem 8-Bit-Mikrokontrolleur
• LibTomCrypt

Eigentums-/kommerziell

• MIRACL: Ganze Mehrpräzisionszahl und vernünftiger arithmetischer C/C ++ Bibliothek
• CNG API in der Windows-Aussicht und dem Windows-Server 2008 mit geführten Streifbändern für CNG im.NET Fachwerk 3.5
• Sonne javanischer Systemwebserver 7.0 und später
• Java SE 6
• Javanische Karte
• Sicherheitsbaumeister Geheim-
• Elliptischer Kurve-Punkt multipliziert und prüft Kern nach
• RSA BSAFE(R) Crypto-J und Geheim-C ICH
• IAIK ECCelerate™: ECC javanischer Versorger

Alternative Darstellungen von elliptischen Kurven

• Jute biegt
• Edwards biegt
• Gedrehte Kurven
• Gedrehte Jute biegt
• Gedrehte Kurve von Edwards
• Verdoppelungsorientierte Doche-Icart-Kohel biegen
• Verdreifachungsorientierte Doche-Icart-Kohel biegen
• Jacobian biegen
• Kurve von Montgomery

Siehe auch

• DNSCurve
• ECC patentiert
• ECDH
• ECDSA
• ECMQV
• Geheimschrift des öffentlichen Schlüssels
• Quant-Geheimschrift
• Paarungsbasierte Geheimschrift
• Homomorphic Unterschriften für das Netz, das codiert
• Universal Metering Interface (UMI) ein offener Standard, der ursprünglich von Beratern von Cambridge für den Gebrauch in Klugen Messen-Geräten/Systemen und die Hausautomation geschaffen ist, die AES-128 neben ECC-256 zu verschiedenen Sicherheitszwecken verwendet.
• Elliptische Kurve-Punkt-Multiplikation

Referenzen

• Standards für Efficient Cryptography Group (SECG), SEC 1: Elliptische Kurve-Geheimschrift, Version 1.0, am 20. September 2000.
• D. Hankerson, A. Menezes, und S.A. Vanstone, Handbuch zur Elliptischen Kurve-Geheimschrift, Springer-Verlag, 2004.
• I. Blake, G. Seroussi, und N. Smart, Elliptische Kurven in der Geheimschrift, London Mathematische Gesellschaft 265, Universität von Cambridge Presse, 1999.
• I. Blake, G. Seroussi, und N. Smart, Redakteure, Fortschritte in der Elliptischen Kurve-Geheimschrift, London Mathematische Gesellschaft 317, Universität von Cambridge Presse, 2005.
• L. Washington, Elliptische Kurven: Zahlentheorie und Geheimschrift, Hausierer & Saal / CRC, 2003.
• Der Fall für die elliptische Kurve-Geheimschrift, Staatssicherheitsagentur
• Elliptischer Online-Kurve-Geheimschrift-Tutorenkurs, Certicom Corp.
• K. Malhotra, S. Gardner, und R. Patz, Durchführung der Geheimschrift der Elliptischen Kurve auf Beweglichen Gesundheitsfürsorge-Geräten, Netzwerkanschluss, Fühlend und Kontrolle, 2007 IEEE Internationale Konferenz für, London, am 15-17 April 2007 Seiten (N):239-244
• Saikat Basu, Eine Neue Parallele Fensterbasierte Durchführung der Elliptischen Kurve-Punkt-Multiplikation in Mehrkernarchitekturen, Internationaler Zeitschrift der Netzsicherheit, Vol. 13, Nr. 3, 2011, Seite (N):234-241
• Christof Paar, Jan Pelzl, "Elliptische Kurve Cryptosystems", Kapitel 9 des "Verstehens der Geheimschrift, Eines Lehrbuches für Studenten und Praktiker". (dazugehörige Website enthält Online-Geheimschrift-Kurs, der elliptische Kurve-Geheimschrift bedeckt), Springer, 2009.

Links

• Certicom ECC Tutorenkurs
• Elliptische Kurven und ihre Durchführung durch Adam Langley (OpenSSL dev).
• Interaktive Einführung in elliptische Kurven und elliptische Kurve-Geheimschrift mit dem WEISEN