4.3 – Pseudozufallsbitgeneratoren mit Schieberegistern

4.3.1 Rückgekoppelte Schieberegister

Ein rückgekoppeltes Schieberegister (FSR) der Länge $L$ besteht aus $L$ Zuständen ${s_0}, \ldots ,{s_{L-1}}$ , die jeweils ein Bit speichern können und jeweils einen Ein- und einen Ausgang haben. Mittels eines Taktgebers werden die Daten im Schieberegister bewegt. Während einer Zeiteinheit werden folgende Operationen durchgeführt:

Der Inhalt des Zustandes 0 wird als nächstes Ausgabebit verwendet
Der Inhalt des Zustandes $i$ wird an den Zustand $i-1$ weitergeschoben, $1 \leq i \leq L-1$ /li>
Der neue Inhalt von Zustand $L-1$ ist das „Feedback-Bit”, das mit Hilfe der Rückkopplungsfunktion erzeugt wird.

Schematischer Aufbau eines rückgekoppelten Schieberegisters:

ruckgekoppeltes-schieberegister-schlusselstrom-erzeugung

Rekursionsgleichung:

Sei $s = \left( {{s_0},{s_1}, \ldots ,{s_{L-1}}} \right)$ der Zustand eines linear rückgekoppelten Schieberegisters. Die Ausgangsfolge lässt sich für $k \geq 0$ mit der folgenden Rekursionsgleichung berechnen:

${s_{k+L}} = \left( {\sum\limits_{i = 0}^{L-1} {{c_i}{s_{k+i}}} } \right)\bmod 2$

Lineare Rückkopplungsfunktion:

Wenn sich das Feedback-Bit linear aus den anderen Bits zusammensetzt, sprechen wir von einer linearen Rückkopplungsfunktion:

$f:\mathbb{F}_2^L \to {\mathbb{F}_2},\quad \left( {{s_0}, \ldots ,{s_{L-1}}} \right) \mapsto {c_0}{s_0}+{c_1}{s_1}+ \ldots +{c_{L-1}}{s_{L-1}}$

Begleitmatrix:

Sei ${s_t}$ der Statusvektor eines linear rückgekoppelten Schieberegisters zum Zeitpunkt $t$ . Mit der Begleitmatrix lässt sich der Status für den Zeitpunkt ${s_{t+1}}$ berechnen:

${s_{t+1}} = \left( {\begin{array}{*{20}{c}} 0 & 1 & 0 & 0 & \ldots & 0 \\ 0 & 0 & 1 & 0 & \ldots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \ldots & 1 \\{{c_0}} & {{c_1}} & {{c_2}} & {{c_3}} & \ldots & {{c_{L-1}}} \\ \end{array} } \right){s_t}$

4.3.2 Beispiel für Rückgekoppeltes Schieberegister

linear-ruckgekoppeltes-schieberegister-beispiel

${c_0} = 1,\quad {c_1} = 1,\quad {c_2} = 0,\quad {c_3} = 0,\quad L = 4$

Dieses Register kann wie folgt mit Flipflops geschaltet werden:

linear-ruckgekoppeltes-schieberegister-beispiel-flipflop-schaltkreis

Rekursionsgleichung:

${s_{k+4}} = \sum\limits_{i = 0}^3 {{c_i}{s_{k+i}}} = {s_k}+{s_{k+1}}$

Begleitmatrix:

$C = \left( {\begin{array}{*{20}{c}} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ \end{array} } \right)$

Anfangszustand:

$\hat s = \left( {1,0,0,1} \right)$

Es wird diese Folge erzeugt:

$s = \left( {\underbrace {1,0}_+,0,1,\boxed1,0,1,0,1,1,1,1,0,0,0,\underline {1,0,0,1} } \right)$

Die Periode ist 15. Wir wollen nun einen Folgezustand mit Hilfe der Begleitmatrix berechnen:

${s_0} = \left( {\begin{array}{*{20}{c}} 1 \\ 0 \\ 0 \\ 1 \\ \end{array} } \right)\quad \Rightarrow \quad {s_1} = \left( {\begin{array}{*{20}{c}} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ \end{array} } \right)\left( {\begin{array}{*{20}{c}} 1 \\ 0 \\ 0 \\ 1 \\ \end{array} } \right) = \left( {\begin{array}{*{20}{c}} 0 \\ 0 \\ 1 \\ 1 \\ \end{array} } \right)$

Feststellungen:

Zustand $\left( {0, \ldots ,0} \right)$ erzeugt Nullfolge
LFSR (linear feedback shift register) der Länge $L$ hat eine maximale Periodenlänge von ${2^L}-1$ ,da der Zustand der Nullfolge nicht auftreten darf.

4.3.3 Charakteristisches Polynom

Sei $C$ die Begleitmatrix eines linear rückgekoppelten Schieberegisters der Länge $L$ . Die Determinante

$\det \left( {X{I_L}-C} \right) \in {\mathbb{F}_2}\left[ X \right]$

wird als charakteristisches Polynom des Schieberegisters bezeichnet:

$f\left( X \right) = \det \left( {X{I_L}-C} \right) = {c_0}+{c_1}X+ \ldots +{c_{L-1}}{X^{L-1}}+{X^L}$

$f\left( X \right) = \sum\limits_{i = 0}^L {{c_i}{X^i}}$

wobei ${c_L} = 1$ gemäß Definition gilt und ${c_0} = 1$ angenommen wird.

Rückkoppelungspolynom ist reziprokes Polynom:

$f\left( X \right)$ : charakteristisches Polynom

${f^*}\left( X \right) = {X^n}f\left( {{X^{-1}}} \right) = \sum\limits_{i = 0}^n {{c_i}{X^{n-i}}}$

Sei $f \in {\mathbb{F}_2}\left[ X \right]$ ein irreduzibles Polynom (keine Faktorisierung des Polynoms möglich). Die kleinste natürliche Zahl $e \in \mathbb{N}$ , für die $\left( {{X^e}+1} \right)\bmod \left( {f\left( X \right)} \right) = 0$ gilt, heißt Exponent von $f$ .

Sei $f \in {\mathbb{F}_2}\left[ X \right]$ ein irreduzibles Polynom vom Grad $L$ und mit Exponent $e$ . Wenn $e = {2^L}-1$ gilt, dann nennt man das Polynom $f$ primitiv.

Ein linear rückgekoppeltes Schieberegister (LFSR) der Länge $L$ erzeugt genau dann die maximale Periode, wenn das charakteristische Polynom primitiv ist.

4.3.4 Weitere Beispiele, Korrelationsangriff

Filtergenerator:

filtergenerator-nicht-linear-funktion

Kombination mehrerer LFSR:

kombination-mehrerer-linearer-schieberegister-verschlusselung

Der Filtergenerator und die Kombination mehrerer LFSR sind anfällig für sogenannte Korrelationsangriffe. Dabei wird zunächst eine Wahrheitstabelle aufgestellt:

$\begin{array}{*{20}{c}} a &\vline & b &\vline & c &\vline & z \\ \hline 0 &\vline & 0 &\vline & 0 &\vline & 0 \\ 0 &\vline & 0 &\vline & 1 &\vline & 0 \\ 0 &\vline & 1 &\vline & 0 &\vline & 0 \\ 0 &\vline & 1 &\vline & 1 &\vline & 1 \\ 1 &\vline & 0 &\vline & 0 &\vline & 1 \\ 1 &\vline & 0 &\vline & 1 &\vline & 0 \\ 1 &\vline & 1 &\vline & 0 &\vline & 1 \\ 1 &\vline & 1 &\vline & 1 &\vline & 1 \\ \end{array}$

In etwa 75% der Fälle entspricht $a$ der Ausgabe $z$ . Wir raten also so lange Anfangssequenzen für $a$ , bis wir einen Zustand finden, der zu 75% mit der Ausgabe übereinstimmt. Anschließend verfahren wir analog mit $b$ und $c$ .

Im Fall des abgebildeten Systems würde ein Brute-Force Angriff hier ${2^{12}} = 4096$ Versuche brauchen. Mit dem Korrelationsangriff braucht man nur ${2^3}+{2^5}+{2^4} = 56$ Versuche.

Shrinking Generator:

shrinking-generator-linear-pseudozufallsbit

Der geheime Schlüssel wird in $a$ und $s$ geladen. $a$ erzeugt dabei die Pseudozufallsfolge, $s$ selektiert, indem ausgewählt wird, ob das aktuelle Bit von $a$ verwendet oder verworfen wird.