Cryptography Reference
In-Depth Information
Rechnen in GF (2
n
)
Wie in GF(
p
) gerechnet wird, wissen Sie bereits. In GF(2
n
) ist die Sache etwas
komplizierter. Die Elemente in GF(2
n
) werden nicht als natürliche Zahl, sondern
als Binärzahl oder als Polynom mit den Koeffizienten 0 und 1 geschrieben. Es fol-
gen einige Beispiele aus GF(2
4
):
x
2
+1
0101
≡
x
3
+
x
2
+
x
+1
1111
≡
x
3
+
x
1010
≡
Die Addition in GF(2
n
) ist als bitweise Exklusiv-oder-Verknüpfung zweier Binär-
zahlen definiert. Bei der Polynomschreibweise entspricht dies einer Polynomaddi-
tion mit Koeffizienten aus GF(2). Hier einige Beispiele aus GF(2
4
):
(
x
3
+1)+(
x
3
+
x
2
+
x
+1)=
x
2
+
x
1001+1111=0110
≡
(
x
3
)+(1)=
x
3
+1
1000+0001=1001
≡
Mit Polynom ist im Folgenden stets ein Polynom mit Koeffizienten aus GF(2)
gemeint. Die Multiplikation in GF(2
n
) ist als Polynommultiplikation modulo
einem irreduziblen Polynom vom Grad
n
definiert. Irreduzibel ist ein Polynom
dann, wenn es sich nicht als Produkt aus Polynomen kleineren Grades darstellen
lässt. Es gibt verschiedene Algorithmen, mit denen festgestellt werden kann, ob
ein Polynom irreduzibel ist. Bei unserer Betrachtung genügt es jedoch, ein Poly-
nom des gewünschten Grades einer Tabelle zu entnehmen. Es gibt zu jedem Grad
n
>1 irreduzible Polynome. In den folgenden Beispielen wird das irreduzible Poly-
nom
x
4
+
x
+1 verwendet, um die Multiplikation in GF(2
4
) zu definieren:
(
x
3
+1)
(
x
3
+
x
2
+1)=
x
6
+
x
5
+
x
2
+1=
x
3
+
x
2
+
x
+1 (mod
x
4
+
x
+1),
⋅
daher 1001
·
1101=1111
Gerade
elliptische
Kurve
Abb. 13-1
Zählt man Berührpunkte doppelt und nimmt man einen Punkt im Unendlichen hinzu, dann
gilt: Eine Gerade schneidet eine elliptische Kurve immer in genau drei Punkten.
