Neue Standards für elliptische Kurven

Ordnungsmerkmale

erschienen in: <kes> 2006#1, Seite 56

Rubrik: BSI Forum

Schlagwort: Public-Key-Kryptographie

Zusammenfassung: Auf elliptischen Kurven basierende kryptographische Verfahren gewinnen immer mehr an Bedeutung, wie beispielsweise ihr Einsatz in den neuen deutschen Reisedokumenten zeigt. Für die praktische Verwendbarkeit ist es erforderlich, die Verfahren und die benötigten Parameter zu standardisieren. Es soll hier ein Überblick über einige neuere Ansätze und beteiligte Gremien gegeben werden.

Autor: Von Dr. Georg Illies, BSI, Uwe Krieger, cv cryptovision, und Dr. Manfred Lochter, BSI

Elliptic Curve Cryptography (ECC) bietet sich schon länger als alternative Public-Key-Kryptographie an. Bei den "klassischen", weit verbreiteten Public-Key-Verfahren (RSA-Signatur/-Verschlüsselung, Diffie-Hellman-Schlüsselaustausch, DSA-Signatur usw.) ist die Exponentiation von Restklassen natürlicher Zahlen die grundlegende mathematische Operation. Man kann analoge Public-Key-Verfahren angeben, bei denen stattdessen Vielfache von Punkten auf elliptischen Kurven über endlichen Körpern berechnet werden müssen, zum Beispiel ECIES-Verschlüsselung, ECDH-Schlüsselaustausch und ECDSA-Signatur. Für eine einführende Erläuterung der Begriffe "elliptische Kurve über einem endlichen Körper" und "Vielfaches eines Punktes" sei auf [1] verwiesen.

Die auf elliptischen Kurven beruhenden Public-Key-Verfahren werden unter dem Begriff Elliptic Curve Cryptography (ECC) zusammengefasst und haben in den letzten Jahren immer weitere Verbreitung gefunden. Beispielsweise hatte sich das BSI schon Anfang der 90er-Jahren entschieden, ECC den Vorzug vor RSA und anderen klassischen Verfahren zu geben.

Während die Sicherheit von RSA-Signatur und RSA-Verschlüsselung auf der Schwierigkeit der Faktorisierung (d. h. Zerlegung in Primfaktoren) sehr großer natürlicher Zahlen beruht, basiert die Sicherheit von DSA und DH-Verfahren auf der Schwierigkeit, diskrete Logarithmen (DL) in Restklassengruppen zu berechnen. Die Sicherheit von ECC-Verfahren basiert ebenfalls auf einem DL-Problem, allerdings in Punktegruppen elliptischer Kurven statt in Restklassengruppen.

Während man für die Faktorisierung und das klassische DL-Problem subexponentielle Algorithmen kennt, sind die besten bekannten DL-Algorithmen für elliptische Kurven exponentiell. Oder anders gesagt: Für den gleichen Zuwachs an Sicherheit müssen ECC-Schlüssellängen erheblich weniger erhöht werden als Schlüssellängen klassischer Public-Key-Verfahren. Schon heute sind ECC-Schlüssel deutlich kürzer, und dieser Unterschied wird signifikanter werden (vgl. [1]). Dass in Zukunft die für das RSA-Verfahren verwendeten Schlüssellängen erhöht werden müssen, zeigen auch neuere Faktorisierungsrekorde [2].

ECC-Brainpool

Der ECC-Brainpool wurde auf Initiative der cv cryptovision im Jahr 2000 ins Leben gerufen und beschäftigt sich mit Fragestellungen rund um das Thema der Kryptographie auf Basis elliptischer Kurven. Vorrangiges Ziel ist dabei, die Verwendung von ECC-Technik in Anwendungen zu fördern. Hierzu bündeln die Mitglieder des ECC-Brainpools ihre Aktivitäten und versuchen so, die dafür notwendige Grundlage zu schaffen.

Mitglieder des Brainpools sind neben cv cryptovision und dem BSI zahlreiche weitere Firmen und Universitäten, welche sich im Bereich der ECC engagieren. Insgesamt umfasst die Arbeitsgruppe heute circa 25 Firmen und Institute (weitere Informationen unter [externer Link] www.ecc-brainpool.org).

Die "Brainpool-Kurven"

Obwohl es eine Reihe von standardisierten elliptischen Kurven gibt, haben die Mitglieder des ECC-Brainpools festgestellt, dass die Festlegung zusätzlicher Kurven sinnvoll ist. In [3] wurden daher Anforderungen an die Domain-Parameter (vgl. Kasten) festgelegt und ein Satz von Standard-Parametersätzen erzeugt, der diesen Anforderungen genügt. Die Parametersätze sind über OIDs referenzierbar (s. u.). Nach dem Willen des ECC-Brainpools sollen sie in möglichst vielen ECC-Implementierungen Verwendung finden.

----------Anfang Textkasten----------

Domain-Parameter

Bei kryptographischen Verfahren auf Basis diskreter Logarithmen (z. B. DSA und alle ECC-Verfahren) ist neben den eigentlichen kryptographischen Schlüsseln (private/public keys) die Kenntnis weiterer Parameter notwendig, um die entsprechenden Berechnungen durchführen zu können. Diese so genannten Domain-Parameter umfassen im Fall der ECC-Verfahren im Wesentlichen Informationen über die konkret verwendete Kurve: Die Primzahl, welche den Grundkörper charakterisiert, die Koeffizienten der eigentlichen Kurve sowie die Koordinaten und die Ordnung eines ausgezeichneten Punktes auf der Kurve inklusive dem Kofaktor. Ein Parametersatz legt also insbesondere die Kurve fest.

Um diese Informationen in Zertifikaten abzulegen, gibt es im Wesentlichen zwei Möglichkeiten: Die entsprechenden Parameter können direkt als Teil des Zertifikates kodiert oder mithilfe eines Object-Identifiers (OID) referenziert werden. Ein Vorteil der zuletzt genannten Variante ist, dass damit die Verwendung standardisierter Kurvenparameter garantiert ist. Gerade im Umfeld einer Smartcard-Implementierung kommt die Einsparung von Speicherplatz und Bandbreite hinzu. Ein Nachteil bei dieser Vorgehensweise ist, dass eine Implementierung in der Lage sein muss, den angegebenen OID zu interpretieren beziehungsweise aufzulösen.

----------Ende Textkasten----------

Ein generelles Manko bisheriger Standards ist, dass sie ausschließlich die Kurvenparameter enthalten. Es gibt keine Hilfestellung zum Nachweis, dass die dort festgelegten Kurven nicht zu Klassen von Kurven gehören, für die effiziente kryptographische Angriffe existieren. Um diese Überprüfung zu erleichtern, sind in [3] daher Beweise enthalten, dass die vorgeschlagenen Kurven vorher festgelegten Sicherheitskriterien genügen. Weitere Beweggründe für die Erstellung von [3] waren:

Die technischen Anforderungen und Sicherheitsanforderungen an die Domain-Parameter wurden durch den ECC-Brainpool aufgrund von Implementierungserfahrungen und anhand des aktuellen Forschungsstandes erhoben; sie sind hier für Leser mit entsprechenden mathematischen Vorkenntnissen in zwei Textkästen aufgelistet. Diese Kriterien, die teilweise einen unmittelbaren Einfluss auf die Sicherheit einer Implementierung gegen Seitenkanalangriffe haben, werden in [3] detailliert erläutert, sodass Anwender sich nötigenfalls auch eigene Kurven generieren können, die diesen Vorgaben genügen.

----------Anfang Textkasten----------

Technische Anforderungen

----------Ende Textkasten----------

Sicherheitsanforderungen sind solche Anforderungen, die aufgrund bekannter mathematischer Angriffe notwendig sind oder die gestellt werden, um allgemein das Vertrauen in die vorgeschlagenen Kurven zu erhöhen. Zukünftige Ergebnisse können natürlich zu weiteren Sicherheitskriterien führen. Beispielsweise könnte man aus [5] die Forderung ableiten, dass q − 1 "fast" eine Primzahl sein sollte. Auf diese Bedingung wurde verzichtet, da sie aus einem noch unpraktikabel erscheinenden Angriff auf spezielle kryptographische Mechanismen stammt.

----------Anfang Textkasten----------

Sicherheitsanforderungen

----------Ende Textkasten----------

ASN.1-Kodierung und Anwendungen

Um Implementierungen zu erleichtern, wurden alle Kurvendaten in Abstract-Syntax-Notation-One-(ASN.1)-Kodierung zur Verfügung gestellt und tragen eindeutige Object Identifier (OIDs), die von TeleTrusT vergeben wurden. Auch diese Daten – neben Binärdateien mit den kodierten Werten zum Testen eigener Implementierungen – sind über die Webseiten des ECC-Brainpools verfügbar.

Es ist geplant, die Kurven der Internet Engineering Task Force (IETF) zur Standardisierung (als RFC) vorzuschlagen, um so eine größere Verbreitung zu erreichen. Bereits jetzt werden zwei der Kurven als Grundlage für die Berechnung von Signaturen zur Authentizitätssicherung der in den Radio-Frequency-(RF)-Chips der in deutschen Reisedokumenten gespeicherten Daten eingesetzt. So benutzt die deutsche Country Signing Certification Authority, die vom BSI betrieben wird, die Brainpool-Kurve brainpoolP256r1. Der deutsche Document Signer, betrieben von der Bundesdruckerei GmbH, verwendet brainpoolP224r1.

Wie erwähnt haben die in den Kästen genannten Kriterien Auswirkungen auf seitenkanalresistente Implementierungen der ECC-Technik auf den verschiedensten Plattformen. Das BSI hat in einer Machbarkeitsuntersuchung festgestellt, dass auf den neuesten Smartcard-Prozessoren der Infineon Technologies AG (SLE88er-Serie mit Crypto-Coprozessor Crypto@1408) auch bei Verwendung der höchsten Bitlängen und Berücksichtigung aller sinnvoll erscheinenden Gegenmaßnahmen unter Verwendung der Brainpool-Kurven eine hinreichende Rechengeschwindigkeit erreichbar ist. Diese Untersuchung ergänzt frühere Studien des BSI zur Implementierung von EC-basierten Kryptomechanismen auf Field-programmable Gate Arrays (FPGAs, vgl. [6] und [1]).

Bitlänge Skalarmultiplikation ECGDSA-Signatur
256 9 16
320 13 20
384 17 26
512 28 39

Laufzeiten in Millisekunden von Elliptic-Curve-Operationen in einer gegen Seitenkanalangriffe geschützten Implementierung auf SLE88 bei 66 MHz

Deutsches Signaturgesetz

Die Brainpool-Kurven lassen sich insbesondere für qualifizierte elektronische Signaturen verwenden, die den Vorgaben des deutschen Signaturgesetzes (SigG) genügen (für die gesetzlichen Grundlagen vgl. [externer Link] www.bundesnetzagentur.de). Gemäß der Signaturverordnung (SigV) werden die konkreten Anforderungen an Algorithmen und Parameter für qualifizierte elektronische Signaturen in dem von der Bundesnetzagentur (BNetzA), der früheren Regulierungsbehörde für Telekommunikation und Post (RegTP), veröffentlichten Algorithmenkatalog [7] festgelegt. Der Katalog wird nach den Angaben des BSI und unter Beteiligung von Experten aus Wirtschaft und Wissenschaft jährlich neu erstellt. Neben den klassischen Verfahren (z. B. RSA-Signaturen) sind gemäß [7] auch einige ECC-Signaturalgorithmen zulässig, insbesondere der international sehr verbreitete ECDSA sowie der ECGDSA. Alle Bedingungen, die der Algorithmenkatalog an die verwendeten Kurven (Domain-Parameter) stellt, werden von den Brainpool-Kurven erfüllt. Beim Vergleich der Bedingungen aus [7] mit denen des ECC-Brainpools (vgl. Kasten "Sicherheitsanforderungen") sieht man, dass letztere schärfer sind. Die Brainpool-Kurven liefern also sogar ein größeres "Sicherheitspolster" gegen eventuelle zukünftige Angriffsmethoden.

ETSI TS 102176-1

Auf europäischer Ebene gibt es bislang keine vergleichbare rechtlich verbindliche Festlegung der Anforderungen an Algorithmen und Parameter für qualifizierte oder fortgeschrittene elektronische Signaturen. Die Technical Specification ETSI TS 102176 "Electronic Signatures and Infrastructures: Algorithms and Parameters for Electronic Signatures" [8] des European Telecommunications Standards Institute (ETSI), die Mitte 2005 fertiggestellt wurde, enthält allerdings Empfehlungen: Interoperabilität ist eines der Ziele der ETSI TS, sodass die Liste empfohlener Signaturalgorithmen etwas kürzer ausfällt als im deutschen Algorithmenkatalog. Aber der ECDSA und – nicht zuletzt auf Anregung von ECC-Brainpool-Mitgliedern – auch der ECGDSA gehören dazu. Derzeit wird von ECC-Brainpool-Mitgliedern ein ECGDSA-Standard erstellt, der eine ASN.1-Beschreibung der verwendeten Datensätze enthält, sodass eine interoperable Implementierung wie beim ECDSA möglich wird.

Die Empfehlungen der ETSI TS an die Kurvenparameter sind stark an die des deutschen Algorithmenkatalogs angelehnt. Sie sind allerdings teilweise etwas schwächer. Insbesondere sind also die Brainpool-Kurven auch "ETSI-konform".

Fazit

ECC findet eine immer weitere Verbreitung in der kryptographischen Praxis. Mit dem Papier [3] hat der ECC-Brainpool zur Standardisierung von ECC-Kurvenparametern beigetragen. Bereits jetzt werden zwei der Kurven wegen ihrer kryptographischen Qualität als Grundlage für die Berechnung von Signaturen zur Authentizitätssicherung der in den RF-Chips der deutschen Reisedokumente gespeicherten Daten eingesetzt. Darüber hinaus eignen sich die Kurven aus [3] für SigG-konforme elektronische Signaturen.

Literatur

[1]
Uwe Dornseifer, Manfred Lochter, Kryptogeräte im Hochsicherheitsbereich (II), Einsatz von elliptischen Kurven auf FPGAs, <kes> 2004#3, S. 52
[2]
BSI, Presseinfo zur Faktorisierung der Zahl RSA200, [externer Link] www.bsi.de/presse/presseinf/090505primzahl.htm
[3]
ECC Brainpool Standard Curves and Curve Generation, Version 1.0, 2005-10-19, downloadbar von [externer Link] www.ecc-brainpool.org
[4]
L. Goubin, A refined power-analysis-attack on Elliptic Curve Cryptosystems, in: Public-Key-Cryptography – PKC2003, Lecture Notes in Computer Science, 2567, Springer 2003, ISBN 3-540-00324-X
[5]
D. R. L. Brown, R. P. Gallant, The static Diffie-Hellman Problem, Version datiert 2005-06-23, [externer Link] www.iacr.org/2004/306
[6]
Uwe Dornseifer, Kryptogeräte im Hochsicherheitsbereich (I), Einsatz von FPGAs in Sicherheitsmodulen, <kes> 2004#1, S. 51
[7]
Bundesnetzagentur, Bekanntmachung zur elektronischen Signatur nach dem SigG und der SigV (2. Januar 2005), [externer Link] www.bundesnetzagentur.de/media/archive/1507.pdf
[8]
ETSI, Electronic Signatures and Infrastructures (ESi), Algorithms and Parameters, Part 1: Hash Functions and Asymmetric Alg., Juli 2005, [externer Link] http://portal.etsi.org/esi/el-sig.asp