Cryptography Reference
In-Depth Information
(Die Eigenschaft „primitv“ bedeutet, dass die Folge (x
i
)mod M(x), i=1, 2, ..., eine maximale Periode von
p=2
r
1 aufweist. Durch die Folge (x
i
)mod M(x) kann auch ein linear rückgekoppeltes Schieberegister
beschrieben werden, wobei das Rückkoppelschema den Koeffizienten von M(x) entspricht, vgl. Kap.
1.3.5.5 „PN-Generator“. Die Periode von (x
i
)mod M(x) ist gleich der Periode des linear rückgekoppelten
Schieberegisters.)
2.5.3
Axiome für Erweiterungskörper und Beispiel
Für das Rechnen in einem Erweiterungskörper benutzen wir Restpolynome als „Zahlen“. Da-
bei ist die Frage, welche Axiome erfüllt sind, wenn wir für die arithmetischen Operationen die
Regeln für das Addieren und Multiplizieren von Polynomen anwenden. Die Koeffizienten der
Polynome berechnen wir dabei in Arithmetik modulo 2. Die Ergebnisse sollen nicht davon
abhängen, wenn wir in jedem Rechenschritt ein Polynom durch ein anderes Polynom aus der
gleichen Restklasse modulo M(x) ersetzen.
Wir beziehen uns wieder auf die Axiome in Kap. 2.1.2 für Gruppe, Ring und Körper. Es wird
sich herausstellen, dass die Axiome 1 bis 10 für jedes Modularpolynom erfüllt sind und das
Axiom 11 nur dann erfüllt ist, falls M(x) ein irreduzibles Polynom ist. D.h. die Voraussetzun-
gen für Addieren, Subtrahieren und Multiplizieren sind für jedes M(x) erfüllt. Multiplikativ
inverse Elemente existieren zu jedem a(x)
0, bzw. das Dividieren durch jedes Element a(x)
0 ist nur dann möglich, falls M(x) irreduzibel ist, also nicht aufgespalten werden kann.
Die Erfüllung der Axiome 1 bis 10 lässt sich nachweisen, indem für die Elemente a(x), b(x)
bzw. c(x) beliebige Elemente der gleichen Restklasse bezüglich M(x) eingesetzt werden. Das
Ergebnis darf dann nur davon abhängen, welchen Restklassen die Operanden a(x) bzw. b(x)
angehören. Der Nachweis erfolgt beispielhaft für Axiom 1.
Axiom 1:
Axiom 1 fordert: Die Summe a+b von zwei beliebigen Elementen a und b ist definiert und
ebenfalls Element der Menge. Angewendet auf Polynome bei freier Wahl des Vertreters aus
den Restklassen R
a
bzw. R
b
ergibt sich:
a
b
(a
i M)
(b
j M)
(a
b)
(i
j) M
(a
b) mod M
(mod M)
(2.5-5)
für
a, b
{c
c
...c c }
und
i, j
{c c c ...}
r1 r 2
1 0
0 1 2
In (2.5-5) ist das Argument „(x)“ bei a(x), b(x) und M(x) der Übersichtlichkeit halber wegge-
lassen. Die Kurzschrift {c
r1
c
r2
…c
1
c
0
} bezeichnet die Menge aller 2
r
Polynome vom Grad
kleiner r. Jeder der r Koeffizienten kann den Wert 0 oder 1 haben. Entsprechend steht
{c
0
c
1
c
2
…} für die Menge aller Polynome mit Koeffizienten aus GF(2).
Wir sehen in (2.5-5), das Ergebnis (a+b)mod M hängt nur von den Restklassen a(x) und b(x)
ab, nicht jedoch von den beliebigen Polynomen i(x) und j(x). Damit ist die Addition mod M(x)
definiert. Die Angabe (mod M) rechts in (2.5-5) bezieht sich auf die Kongruenzen. Zusätzlich
steht (a+b)mod M, da die Summe (a(x)+b(x)) aus der Menge {c
r1
c
r2
…c
1
c
0
} herausfallen
könnte. Durch die Restbildung liegt das Ergebnis (a(x)+b(x))mod M(x) wieder in der Menge
{c
r1
c
r2
…c
1
c
0
}.
