Cryptography Reference
In-Depth Information
en sich auf eine gemeinsame Kurve einigen. In der Praxis möchte man eine Kurve mit mög-
lichst vielen Punkten haben, u.a. um Brute-Force-Angriffe zu erschweren. Die Bestimmung
der Anzahl der Punkte auf einer elliptischen Kurve ist für große Körper nicht trivial und lässt
sich schwer implementieren.
Große Standardisierungsbehörden, wie z.B. das amerikanische NIST (National Institute of
Standards and Technology), haben daher bestimmte elliptische Kurven standardisiert und für
die Verwendung in Kryptosystemen empfohlen [NIST99]. In der Empfehlung sind verschiede-
ne Kurven aufgelistet, je nach Schlüssellänge und Art des zugrunde liegenden Körpers, so dass
man für jede Anwendung und Implementierung eine passende Kurve finden kann.
4.5.6.1
Patentsituation bei ECC
Die Patentsituation bei ECC ist das größte Hindernis für die breite Verwendung von ellipti-
schen Kurven. Firmen wie z.B. Certicom haben weit über 100 Patente, die auf bestimmte Im-
plementierungstechniken beschränkt sind. Man stößt daher auf patentierte Verfahren, wenn
man besonders effiziente Implementierungen sucht. Allerdings gibt es immer Möglichkeiten,
eine patentfreie Implementierung zu erstellen, da die Verfahren selbst nicht geschützt sind.
4.5.7
Anwendung der elliptischen Kurven in Algorithmen
Wie anfangs erwähnt, ermöglichen elliptische Kurven die Konstruktion von Kryptosystemen,
indem sie Einwegfunktionen bieten, die dem diskreten Logarithmus ähnlich sind. Die Tatsa-
che, dass die diskrete Exponentiation eine Einwegfunktion ist, ist aus Kap. 4.1.4 bekannt. Man
kann im diskreten Fall eine Exponentiation leicht berechnen, die Berechnung des diskreten
Logarithmus ist jedoch praktisch unmöglich. Dieses Problem nennt man DLP (Discrete Loga-
rithm Problem).
Das DLP auf elliptischen Kurven (man nennt es ECDLP, Elliptic Curve Discrete Logarithm
Problem) ist der Berechnung eines diskreten Logarithmus nur ähnlich und vergleichbar. Wählt
man einen Punkt P der Kurve und eine ganze Zahl n, dann lässt sich der Punkt QnP
durch
Addition (nP+P=(n+1)P) und Multiplikation (nP+nP=2nP) leicht bestimmen, (4.5-2). Wenn
man aber P und Q kennt, dann ist es praktisch unmöglich, den Wert von n in sehr großen Kör-
pern zu bestimmen. Man kann nur alle möglichen Werte von n ausprobieren, also einen Brute-
Force-Angriff durchführen. Das ist für große Körper praktisch nicht durchführbar. Diese Ei-
genschaft nutzt man in Kryptosystemen. Elliptische Kurven kann man daher direkt auf Algo-
rithmen anwenden, die sonst auf dem diskreten Logarithmus basieren.
4.5.7.1
Geschwindigkeit von ECC
Sehr oft werden die aus Kapitel 4.3 und 4.4 bekannten Diffie-Hellman- und DSA-Algorithmen
mit elliptischen Kurven verwendet. Einzelheiten werden in den nächsten zwei Abschnitten
dargestellt. Die Operationen auf der elliptischen Kurve sind zwar relativ kompliziert, wenn
man sie mit den Operationen z.B. bei Diffie-Hellman vergleicht, man kann aber im Fall von
ECC wesentlich kürzere Schlüssel benutzten. Diese Tatsache macht ECC-Systeme relativ
