Cryptography Reference
In-Depth Information
für alle Punkte
P
der elliptischen Kurve. Das inverse Element eines Punktes erhält
man, indem man an ihn eine Gerade anlegt, die parallel zur
y
-Achse verläuft. Ist
diese Gerade eine Tangente, dann ist der Punkt selbst sein inverses Element. Ist
die Gerade keine Tangente, so gibt es nach obigen Eigenschaften genau einen wei-
teren Schnittpunkt. Dieser ist das inverse Element.
In der Kryptografie spielen nur die elliptischen Kurven der Form
E
(GF(
m
))
(also
E
(GF(
p
)) und
E
(GF(2
n
))) eine Rolle, obwohl alle der im Folgenden genann-
ten Verfahren auch bei Verwendung von
E
(GF(
p
n
)) funktionieren.
13.1.2
ECC-Verfahren
Die Verknüpfung einer Gruppe
E
(GF(
m
)) wird aus historischen Gründen »Addi-
tion« genannt. Wie erwähnt, wäre auch die Bezeichnung »Multiplikation« mög-
lich, weshalb für die mehrfache Addition von Punkten aus
E
(GF(
m
)) der Begriff
Potenzfunktion gerechtfertigt ist. Die Umkehrung dieser Rechenart kann aus den
gleichen Gründen als Logarithmus bezeichnet werden.
Folgende Eigenschaft von
E
(GF(
m
)) ist für die Kryptografie von zentraler
Bedeutung: Für die Berechnung einer Potenzfunktion existieren effektive Algo-
rithmen; für die Berechnung des Logarithmus dagegen nicht. Die Folge ist, dass
Alice und Bob alle kryptografischen Verfahren, die auf dem diskreten Logarith-
mus beruhen, auch mithilfe von
E
(GF(
m
)) einsetzen können. Ein
Krypto-System
auf Basis elliptischer Kurven ist somit ein asymmetrisches Verfahren auf Basis des
diskreten Logarithmus, bei dem statt Rechenoperationen in GF(
p
) Rechenopera-
tionen in
E
(GF(
m
)) verwendet werden. Statt auf einen Modulus müssen sich Alice
und Bob hierbei auf einen Körper GF(
m
) und eine darauf aufbauende Gruppe
E
(GF(
m
)) - und damit auf eine bestimmte elliptische Kurve - verständigen. Alle
Parameter, die im Exponenten stehen, sind (wie bisher) natürliche Zahlen, wäh-
rend die Basis einer Potenz ein Element von E(GF(
m
)) ist.
Die Addition zweier Punkte aus
E
(GF(
m
)) setzt sich aus mehreren Rechen-
operationen in GF(
m
) zusammen. Damit ist eine Exponentiation über GF(
m
)
weniger aufwendig als eine Exponentiation über
E
(GF(
m
)). Die zum Berechnen
des diskreten Logarithmus über GF(
p
) bekannten Verfahren sind jedoch wesent-
lich effektiver als diejenigen, die den Logarithmus über elliptischen Kurven
berechnen. Der zentrale Vorteil bei der Verwendung von
E
(GF(
m
)) ist daher, dass
Alice und Bob bei gleicher Sicherheit eine Gruppe kleinerer Kardinalität verwen-
den können. Dies hat kürzere Schlüssellängen, kürzere Signaturen und kürzere
Rechenzeiten zur Folge.
Die Komplexität des diskreten Logarithmus in
E
(GF(
m
)) nimmt mit
m
linear
zu, während die Komplexität in GF(
m
) nur logarithmisch ansteigt. Eine Schlüs-
sellänge von 1.024 Bit kann bei einem Krypto-System auf Basis des diskreten
Logarithmus durch die Verwendung elliptischer Kurven auf 200 Bit verkürzt wer-
den, ohne dass dabei Sicherheitseinbußen entstehen. Für die Einsparung an
Rechenzeit wird meist der Faktor zehn genannt.
