Cryptography Reference
In-Depth Information
Axiom 4:
Das additiv inverse Element zu a(x)
ist a
1
(x)=a(x). Jedes Element ist zu sich selbst additiv
invers, denn in der Arithmetik modulo 2 für die Koeffizienten von a(x) addieren sich die Koef-
fizienten je zu 0: a(x)+a(x)0 (mod 2).
zu
a(x)
ist
a
a(x)
denn
a(x)
a(x)
0 (mod 2)
(2.5-6)
1
In entsprechender Weise kann die Erfüllung aller Axiome 1 bis 10 leicht nachgewiesen wer-
den. Auf der Basis der Axiome 1 bis 10 können wir jetzt in der Arithmetik modulo M(x) mit
den gewohnten Regeln für Addition, Subtraktion, Multiplikation, Klammerung usw. rechnen,
d.h. entsprechende algebraische Ausdrücke umformen und berechnen.
Axiom 11:
Nach Axiom 11 soll für jedes Element a(x)0 ein multiplikativ inverses Element a
1
(x)=b(x)
existieren, so dass a(x)·b(x)1 (modM(x)) ist. Diese Beziehung führt bei freier Wahl innerhalb
der entsprechenden Restklassen auf (vgl. (2.1-3) in Abschnitt 2.1.1).
a(x) b(x)
1
i(x)
mod M(x)
mit
i(x)
{c c c ...}
(2.5-7)
012
Dabei sind a(x) und b(x) Polynome vom Grad kleiner als r, und i(x) ist ein beliebiges Polynom
mit Koeffizienten aus GF(2). Es wird vorausgesetzt, dass M(x) ein irreduzibles Polynom vom
Grad r ist. In einem 1. Teilbeweis ist zu zeigen, dass das Produkt zweier Elemente a(x)0 und
b(x) 0 nicht auf das 0-Element führen kann:
a(x) b(x)
i(x) M(x)
0
(mod M(x))
(2.5-8)
für
a(x)
0,
b(x)
0,
M(x)...irreduzibel
Bei Gleichheit in (2.5-8) müsste M(x) in a(x)·b(x) als Faktor enthalten sein. M(x) kann in a(x)
oder in b(x) allein nicht als Faktor enthalten sein, da der Grad von M(x) größer ist als der Grad
von a(x) oder b(x). Andererseits kann ein Teilfaktor von M(x) in a(x) und der restliche Teil-
faktor von M(x) in b(x) nicht enthalten sein, da M(x) als irreduzibel vorausgesetzt wurde.
Damit ist die Ungleichheit in (2.5-8) sichergestellt. In einem 2. Teilbeweis ist zu zeigen, dass
die Produkte a(x)·b
1
(x) und a(x)·b
2
(x) verschieden sind, wobei a(x)0, b
l
(x)0, b
2
(x)0 und
b
1
(x)b
2
(x) vorausgesetzt werden:
a(x) b (x)
c (x)
1
1
a(x) b (x)
c (x)
(mod M(x))
(2.5-9)
1
1
a(x) [b (x)
b (x)]
c (x)
c (x)
1
2
1
2
Aus b
l
(x)b
2
(x) folgt wegen der mod2-Arithmetik b
l
(x)+b
2
(x)0. Dies, eingesetzt in (2.5-9),
führt mit (2.5-8) auf c
1
(x)+c
2
(x)0. Das heißt, es müssen auch c
l
(x) und c
2
(x) verschiedene
Elemente sein. Wenn nun in dem Produkt
a(x)·b(x) = c(x)
bei festgehaltenem a(x) für b(x) alle 2
r1
von Null verschiedenen Elemente eingesetzt werden,
dann ergeben sich für c(x) jeweils verschiedene Elemente (2. Teilbeweis). Wegen (2.5-8) ist
auch stets c(x)0. D.h. c(x) durchläuft alle 2
r1
von Null verschiedenen Elemente einmal, und
c(x) fällt genau einmal auf das 1-Element. Damit ist für genau ein b(x) die Gl. (2.5-7) erfüllt,
