Cryptography Reference
In-Depth Information
8.5.5.4 Lokatorpolynom nach BERLEKAMP-MASSEY und
EUKLID
Das in Abschn. 8.5.5.1 beschriebene PZG-Verfahren zur Bestimmung des Loka-
torpolynoms
σ
(
x
)
ist konzeptionell sehr einfach, eignet sich aber nur für einen
kleinen Fehlerkorrekturgrad
f
k
.
Die Regelmäßigkeit des linearen Gleichungssystems beim PZG-Verfahren wur-
de als Schieberegisterproblem formuliert und bildet die Grundlage des BERLE-
KAMP-MASSEY-(BM-)Verfahrens. Der Algorithmus findet das kürzeste rück-
gekoppelte Schieberegister mit den Rückkopplungsfaktoren
Λ
i
,Koezienten
des Lokatorpolynoms
Λ(
x
)
BM
:
ν
Λ(
x
)
BM
=1+Λ
1
x
+Λ
2
x
2
+
...
+Λ
ν
x
ν
=
(1 +
x
i
x
)
.
(8.44)
i
=1
Das Verfahren nach EUKLID zur Bestimmung des Lokatorpolynoms
Λ(
x
)
EUKL
basiert auf dem erweiterten EUKLIDischen Algorithmus, bekannt u. a. in der
Kryptographie, hier angewendet auf der Basis von Polynomen.
Im Folgenden werden beide Verfahren vorgestellt. Sie führen auf ein Lokator-
polynom mit
Λ(
x
)
BM
=Λ(
x
)
EUKL
. Dieses Polynom wird anschließend in die
Struktur des Lokatorpolynoms
σ
(
x
)
transformiert. Damit bestehen die bereits
bekannten Ausführungen zum 3. Bearbeitungsschritt fort (s. Abschn. 8.5.5.1).
Die Transformation von
Λ(
x
)
BM/EUKL
in
σ
(
x
)
erfolgt am Ende dieses Ab-
schnitts (S. 202).
Lokatorpolynom nach BERLEKAMP-MASSEY
Im Folgenden sei zunächst die Umsetzung der
ν
Gleichungen des PZG-Verfah-
rens (s. Abschn. 8.5.5.1) als rückgekoppeltes Schieberegister gezeigt:
...
...
Die Verzögerungskette der Länge
ν
wird mit den Fehlersyndromen
s
ν
,s
ν−
1
,...,s
1
initialisiert. Die Lokatorkoe
zienten
σ
i
sind die Rückkopplungsfaktoren zur
Berechnung der Syndrome
s
ν
+1
,s
ν
+2
, ..., s
2
ν
. Mit jeder Taktfortschreibung er-
geben sich dann:
s
ν
+1
=
σ
1
s
ν
+
σ
2
s
ν−
1
+
...
+
σ
ν
s
1
s
ν
+2
=
σ
1
s
ν
+1
+
σ
2
s
ν
+
...
+
σ
ν
s
2
.
s
2
ν
=
σ
1
s
2
ν−
1
+
σ
2
s
2
ν−
2
+
...
+
σ
ν
s
ν
.
