Cryptography Reference
In-Depth Information
13 Elliptische Kurven *
Das ElGamal-Verschlüsselungsverfahren kann auf jeder zyklischen Gruppe im-
plementiert werden. In der additiven Gruppe
(
Z
n
,
+)
bietet das Verfahren keine
Sicherheit (vgl. Abschnitt 9.1.4), da in dieser Gruppe das diskrete Logarithmen-
problem mit dem euklidischen Algorithmus leicht gelöst werden kann. In der
Gruppe
Z
p
hingegen ist das Verfahren sehr rechenaufwändig, da die Primzahl
p
von der Größenordnung 1024 Bit zu wählen ist.
Im vorliegenden Kapitel führen wir elliptische Kurven ein. Das sind algebrai-
sche Kurven, die eine Gruppenstruktur tragen. Soweit bisher bekannt ist, hat
das ElGamal-Verschlüsselungsverfahren auf elliptischen Kurven zwei wesentli-
che Vorteile:
•
Das diskrete Logarithmenproblem ist im Allgemeinen
schwer
zu lösen.
•
Man kann effizient rechnen und kommt mit kleinen Schlüssellängen aus.
Die Gruppen scheinen also gut für die Praxis geeignet. Das ElGamal-Verfahren
auf elliptischen Kurven ist die bisher wohl bestuntersuchte und auch bestens
funktionierende Alternative für das RSA-Verfahren.
Um elliptische Kurven einführen zu können, ist ein Blick in die projektive Geome-
trie nötig. Wir führen die projektive Ebene PG
(
F
)
2,
über einem beliebigen Körper
3
aus. Wir erklären
F
ein. Dabei gehen wir vom dreidimensionalen Vektorraum
F
3
als Punkte und die zweidimen-
die eindimensionalen Untervektorräume im
F
3
als Geraden. Die Punktmenge
E
einer ellip-
tischen Kurve wird aus der Nullstellenmenge eines homogenen Polynoms vom
Grad 3 gewonnen. Durch die Wahl einer
unendlich fernen Geraden U
in PG
F
sionalen Untervektorräume im
(
F
)
2,
zerfällt
E
in einen
affinen
Teil und den
unendlich fernen Punkt
O
=
U
∩
E
. Wir de-
+
finieren auf der Punktmenge
E
eine Verknüpfung
, indem wir zeigen, dass jede
Gerade, die
E
in mindestens zwei Punkten schneidet, mit
E
genau drei Schnitt-
punkte hat (wobei Vielfachheiten zu berücksichtigen sind). Die Verknüpfung ist -
etwas salopp formuliert - so gemacht, dass die Summe dieser drei Schnittpunkte
das neutrale Element
O
O
ergibt. Dabei ist
der
unendlich ferne Punkt
.
In diesem Kapitel bezeichne
F
stets einen Körper.
13.1 Projektive Ebenen
Affine Ebenen wurden bereits im Abschnitt 5.3.1 eingeführt. Im Folgenden betra-
chen wir
projektive
Ebenen und den Zusammenhang zu ihren affinen Verwandten.
