Klausurvorbereitung 2 – Stromchiffren

2.1 Linear rückgekoppeltes Schieberegister

Gegeben sei das folgende linear rückgekoppelte Schieberegister (LFSR):

ruckgekoppeltes-schieberegister-begleitmatrix-rekursiv

Wie lauten charakteristisches Polynom, Begleitmatrix und Rekursionsgleichung?
Geben Sie die Bits einer Periode an, wenn der Anfangszustand $s = \left( {1,1,0,0,1} \right)$ gewählt wird.
Betrachtet wird nun ein LFSR mit Rückkopplungspolynom $f\left( x \right) = {x^5}+{x^3}+x+1$ . Bestimmen Sie die Länge einer Periode ausgehend vom Anfangszustand $s = \left( {1,1,0,0,1} \right)$ . Welche Erklärung haben Sie für das Ergebnis?

Lösung 2.1

Begleitmatrix:

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

Charakteristisches Polynom:

${c_5}: = 1$

$f\left( x \right) = \sum\limits_{i = 0}^5 {{c_i}{x^i}} + = 1 \cdot {x^0}+0 \cdot {x^1}+0 \cdot {x^2}+1 \cdot {x^3}+0 \cdot {x^4}+1 \cdot {x^5} = 1+{x^3}+{x^5}$

Rekursionsgleichung:

${s_{k+5}} = \left( {\sum\limits_{i = 0}^5 {{c_i}{s_{k+i}}} } \right)\bmod 2 = \left( {{s_k}+{s_{k+3}}} \right)\bmod 2$

Begleitmatrix, charakteristisches Polynom und Rekursionsgleichung sind drei äquivalente Beschreibungen für das LFSR.

Berechnung der nachfolgenden Bits mit Hilfe der Rekursionsgleichung:

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

Die ganze Periode ist: 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1

Die Periodenlänge ist mit 31 maximal, also $e = 31$ .
Erklärung: Polynom ${x^e}+1$ ist ohne Rest durch das charakteristische Polynom teilbar. Wenn das charakteristische Polynom nicht primitiv ist, kann man nicht wie hier die volle Periodenlänge ${2^n}-1$ erwarten.

Rückkoppelungspolynom: $f\left( x \right) = {x^5}+{x^3}+x+1$

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

Rekursionsgleichung: ${s_{k+5}} = {s_k}+{s_{k+1}}+{s_{k+3}}$

Periode: 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0

Periodenlänge: 15

2.2 Synchrone Stromchiffre (Übung 4.1)

Sei $\Sigma = \left\{ {A, \ldots ,Z} \right\}$ das Alphabet der 26 Großbuchstaben. Gegeben sei folgende synchrone Stromchiffre:

${\sigma _{i+1}} = \left( {{\sigma _i}+k} \right)\bmod 26$

${z_i} = \left( {3{\sigma _i}k+1} \right)\bmod 26$

${c_i} = \left( {{p_i}+{z_i}} \right)\bmod 26$

Sei ${\sigma _0} = 12$ und sei $k = 25$ .

Verschlüsseln Sie den Klartext p = STROMCHIFFRE.
Entschlüsseln Sie den Geheimtext c = MQRRSLSXXAPF.
Entschlüsseln Sie den Geheimtext c = MQRRSLXXAPF.
Entschlüsseln Sie den Geheimtext c = MQRRSLTAXXAPF.

Lösung 2.2

Der Geheimtext lautet MQRRSLTXXAPF.

b, c, d)

Die drei entschlüsselten Texte lauten:

STROMCGIFFRE
STROMCLIIUH
STROMCHLFCCOB

Die Berechnung des Schlüsselstroms braucht bei synchronen Stromchiffren nur einmal zu erfolgen und kann somit bereits vor der eigentlichen Ver- bzw. Entschlüsselung durchgeführt werden. Das Ergebnis der Teilaufgabe b) zeigt, dass ein fehlerhaftes Zeichen bei der Entschlüsselung keine Auswirkungen auf die folgenden hat – synchrone Stromchiffren haben also den Vorteil, dass sich Fehler dieser Art nicht fortpflanzen. Anders sieht es aus, wenn Zeichen fehlen (c) oder es mehr Zeichen als im Klartext gibt (d). In beiden Fällen geht die Synchronisation verloren und die Entschlüsselung schlägt fehl. Beim Einsatz von synchronen Stromchiffren in der Praxis sind deshalb zusätzliche Maßnahmen zur Synchronisation vorzusehen.

2.3 Selbstsynchronisierende Stromchiffre (Übung 4.2)

Sei $\Sigma = \left\{ {A, \ldots ,Z} \right\}$ das Alphabet der 26 Großbuchstaben. Gegeben sei folgende selbstsynchronisierende Stromchiffre:

${\sigma _i} = \left( {{c_{i-2}}+2 \cdot {c_{i-1}}} \right)\bmod 26$

${z_i} = \left( {3{\sigma _i}k+1} \right)\bmod 26$

${c_i} = \left( {{p_i}+{z_i}} \right)\bmod 26$

Sei ${c_0} = \left( {17,19} \right)$ und sei $k = 25$ .

Verschlüsseln Sie den Klartext p = STROMCHIFFRE.
Entschlüsseln Sie den Geheimtext c = KHYGJIFETKFX.
Entschlüsseln Sie den Geheimtext c = KHYGJFETKFX.
Entschlüsseln Sie den Geheimtext c = KHYGJJAFETKFX.

Lösung 2.3

Der Geheimtext lautet KHYGJJFETKFX.

b,c,d)

Die Klartexte lauten:

STROMBBFFFRE
STROMYIFFRE
STROMCCFHFFRE

Hier wird die Selbstsynchronisation sichtbar. Nach zwei fehlerhaften Zeichen ist der Rest der Nachricht wieder korrekt.

2.4 Lineares Schieberegister (Übung 4.3)

Gegeben sei das folgende binäre lineare Schieberegister (LFSR):

binares-lineares-schieberegister-begleitmatrix-rekursiv

Welche Periode ist mit diesem LFSR maximal möglich?
Geben Sie die Rekursionsgleichung, die Begleitmatrix sowie das charakteristische Polynom für folgende LFSRs an:
1. ${c_0} = 0,\quad {c_1} = 1,\quad {c_2} = 1,\quad {c_3} = 0$
2. ${c_0} = 1,\quad {c_1} = 1,\quad {c_2} = 1,\quad {c_3} = 1$
3. ${c_0} = 1,\quad {c_1} = 1,\quad {c_2} = 0,\quad {c_3} = 0$
Geben Sie die Ausgangsfolge (20 Elemente) der drei LFSRs aus Teilaufgabe b an. Der Anfangszustand sei jeweils (1, 1, 0, 0).
Zeigen Sie, dass das charakteristische Polynom von LFSR biii) primitiv ist.

Lösung 2.4

Der Zustandsvektor ist 4 Elemente lang. Damit lassen sich ${2^4} = 16$ Kombinationen darstellen. Die maximale Periodenlänge ist ${2^4}-1 = 15$ .

Begleitmatrizen:

${C_i} = \left( {\begin{array}{*{20}{c}} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ \end{array} } \right),\quad \quad {C_{ii}} = \left( {\begin{array}{*{20}{c}} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 \\ \end{array} } \right),$

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

Charakteristische Polynome:

${f_i}\left( x \right) = {x^4}+{x^2}+x$

${f_{ii}}\left( x \right) = {x^4}+{x^3}+{x^2}+x+1$

${f_{iii}}\left( x \right) = {x^4}+x+1$

Rekursionsgleichungen:

$s_{k+4}^{\left( i \right)} = {s_{k+1}}+{s_{k+2}}$

$s_{k+4}^{\left( {ii} \right)} = {s_k}+{s_{k+1}}+{s_{k+2}}+{s_{k+3}}$

$s_{k+4}^{\left( {iii} \right)} = {s_k}+{s_{k+1}}$

Die Periodenlänge beträgt 7.

Die Periodenlänge beträgt 5.

Die Periodenlänge beträgt 15, ist also maximal.

Man sieht, dass das dritte Polynom primitiv sein muss, da es die maximale Periodenlänge erzeugt. Man könnte auch zeigen, dass sich ${x^{15}}+1$ ohne Rest durch das dritte charakteristische Polynom teilen lässt.

2.5 Kombinationsgenerator (Übung 4.4)

Die nachfolgende Darstellung zeigt einen einfachen Kombinationsgenerator:

kombinationsgenerator-aufbau-nichtlinear

Wie viele Schlüssel umfasst der Schlüsselraum $\mathcal{K}$ des Generators?
Mit welchem geheimen Schlüssel $k \in \mathcal{K}$ wurde die Sequenz
${\left( {{z_i}} \right)_{0 \leq i \leq 29}} = \left( {0,1,1,0,1,0,0,0,1,1,1,1,0,1,0,0,1,1,0,1,1,1,1,1,0,1,0,1,0,1} \right)$

erzeugt?

Lösung 2.5

Der Kombinationsgenerator soll mittels eines Korrelationsangriffs gebrochen werden. Die Summe der Längen der drei LFSRs ist 3+5+4 = 12. Der geheime Schlüssel umfasst daher 12 Bit, weshalb der Schlüsselraum 2¹² = 4096 Elemente umfasst.

Um statistische Abhängigkeiten der Ausgangssequenz z von den intern erzeugten Bitfolgen a, b und c zu herauszufinden, muss zunächst die nichtlineare Funktion analysiert werden, die a, b und c verknüpft.

Wahrheitstabelle:

$\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}$

Wie man sieht, stimmt a in 6 von 8 Fällen mit z überein. Um den Anfangszustand des LFSRs a und damit den ersten Teil des geheimen Schlüssels zu finden, werden alle möglichen Zustände getestet und der jeweilige Ausgabestrom mit den Werten von z verglichen:

korrelationsangriff-kryptoanalyse

Die größte Anzahl an Übereinstimmungen und gleichzeitig die geringste Abweichung vom Erwartungswert 0,75 liefert der Zustand s_a = (0, 1, 1). Es kann davon ausgegangen werden, dass dies der gesuchte Teil des geheimen Schlüssels ist. Mit der gleichen Vorgehensweise ermittelt man die Anfangszustände von LFSR b und LFSR c. Diese lauten s_b = (0, 0, 1, 0, 1) bzw. s_c = (1, 0, 0, 1).
Im Vergleich zur vollständigen Schlüsselsuche müssen bei diesem Angriff anstelle von 2¹² Schlüsseln der Länge 12 Bit lediglich 2³+2⁵+2⁴ = 56 Teilschlüssel mit einer Länge von max. 5 Bit getestet werden.

2.6 Stromchiffre A5/1 (Aufgabe 4.5)

Betrachtet wird die Stromchiffre A5/1.

Wie lauten die drei charakteristischen Polynome der linear rückgekoppelten Schieberegister?
Geben Sie eine Wahrheitstabelle für die „Mehrheitsfunktion” an.

Lösung 2.6

Hier ein Diagramm von A5/1:

a51-stromchiffre-ruckkopplung-register-wahrheitstabelle

Die charakteristischen Polynome lauten:

${f_1}\left( x \right) = 1+x+{x^2}+{x^5}+{x^{19}}$

${f_2}\left( x \right) = 1+x+{x^{22}}$

${f_3}\left( x \right) = 1+x+{x^2}+{x^{15}}+{x^{23}}$

Wahrheitstabelle:

$\begin{array}{*{20}{c}} a &\vline & b &\vline & c &\vline & M \\ \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 & 0 \\ 1 &\vline & 0 &\vline & 1 &\vline & 1 \\ 1 &\vline & 1 &\vline & 0 &\vline & 1 \\ 1 &\vline & 1 &\vline & 1 &\vline & 1 \\ \end{array}$

2.7 Golombs Postulate (Prüfung WT2010 1.7)

Stimmt die folgende Aussage?
Golombs Postulate dienen zur Berechnung der Koeffizienten des Rückkopplungspolynoms von linear rückgekoppelten Schieberegistern. Auf Grundlage dieser Berechnung wird die Schieberegisterfolge eine gute Pseudozufallsfolge.

Lösung 2.7

Die Aussage ist falsch. Golombs Postulate sind lediglich ein Anhaltspunkt für gute Pseudozufallszahlenfolgen, sie geben aber keine Vorgaben zur Berechnung derselben.

2.8 RC-4 (Prüfung WT2010, Aufgabe 3)

Um welche Art von Stromchiffre handelt es sich bei RC4? (1 Punkt)
Sie übernehmen den Part von Bob. Alice hat Ihnen den mit RC4 verschlüsselten Geheimtext 0×54:16:15:2f:ec:db:71:20:2d:68 gesendet. Zur Entschlüsselung haben Sie mit dem vereinbarten Schlüssel den Schlüsselstrom 0×13:43:41:68:a9:96:30:63:65:3c berechnet. Wie lautet die Nachricht von Alice? (2 Punkte)
Stellen Sie dar, wie in RC4 der Schlüsselstrom generiert wird. Da der Aufwand der realen Stromchiffre für “Papier und Bleistift” jedoch zu hoch ist, sollen die Register auf die Länge 5 (statt 256) reduziert werden: Sie können also alle modulo 256 Operationen (vgl. Pseudocode) in Ihrer Darstellung modulo 5 durchführen. Wie lauten die ersten drei Zahlen des Schlüsselstroms, wenn der Schlüssel K = (3, 1, 2) verwendet wird? (3 Punkte)

Lösung 2.8

Pseudocode zu RC-4:

Initialize(byte[] K)
begin
	j = 0
	for i = 0 step 1 to 255
		S[i] = i
	end for
	for i = 0 step 1 to 255
		j = (j+S[i]+K[i mod l]) mod 256
		swap(S, i, j)
	end for
	i = 0
	j = 0
end

KeyStreamByte(byte out)
begin
	i = (i+1) mod 256
	j = (j+S[i]) mod 256
	swap(S, i, j)
	out = S[(S[i]+S[j]) mod 256]
end

Es handelt sich um eine synchrone Stromchiffre, da keine Rückkopplung vorhergehender Geheimtextzeichen erfolgt. Außerdem ist RC-4 eine softwareoptimierte Stromchiffre.

Die Entschlüsselung erfolgt als Bitweises XOR.

Nachricht: 0×54:16:15:2f:ec:db:71:20:2d:68

Key: 0×13:43:41:68:a9:96:30:63:65:3c

Umwandlung der Hexadezimalzahlen in Bitstrings:

54: 01010100
16: 00010110
15: 00010101
2f: 00101111
ec: 11101100
db: 11011011
71: 01110001
20: 00100000
2d: 00101101
68: 01101000

13: 00010011
43: 01000011
41: 01000001
68: 01101000
a9: 10101001
96: 10010110
30: 00110000
63: 01100011
65: 01100101
3c: 00111100

Entschlüsseln:

c:
01010100 00010110 00010101 00101111 11101100 11011011 01110001 00100000 00101101 01101000

k:
00010011 01000011 01000001 01101000 10101001 10010110 00110000 01100011 01100101 00111100

p:
01000111 01010101 01010100 01000111 01000101 01001101 01000001 01000011 01001000 01010100

= 47:55:54:47:45:4D:41:43:48:54

Klartext: GUTGEMACHT

Wir gehen nun auf die Schlüsselerzeugung ein. Gegeben ist K = (3, 1, 2). Initialisierung:

$S = \left( {\begin{array}{*{20}{c}} 0 & 1 & 2 & 3 & 4 \\ \end{array} } \right),\quad \quad K = \left( {\begin{array}{*{20}{c}} 3 & 1 & 2 \\ \end{array} } \right)$

$j = 0,\quad i = 0$

$j \leftarrow \left( {j+S\left[ i \right]+K\left[ {i\bmod l} \right]} \right)\bmod 5$

$\quad \Rightarrow \quad j \leftarrow \left( {0+S\left[ 0 \right]+K\left[ {0\bmod 3} \right]} \right)\bmod 5 = \left( {0+0+3} \right)\bmod 5 = 3$

$\quad \Rightarrow \quad S \leftarrow \left( {\begin{array}{*{20}{c}} 3 & 1 & 2 & 0 & 4 \\ \end{array} } \right)$

$j = 3,\quad i = 1$

$j \leftarrow \left( {3+S\left[ 1 \right]+K\left[ {1\bmod 3} \right]} \right)\bmod 5 = \left( {3+1+1} \right)\bmod 5 = 0$

$\quad \Rightarrow \quad S \leftarrow \left( {\begin{array}{*{20}{c}} 1 & 3 & 2 & 0 & 4 \\ \end{array} } \right)$

$j = 0,\quad i = 2$

$j \leftarrow \left( {0+S\left[ 2 \right]+K\left[ {2\bmod 3} \right]} \right)\bmod 5 = \left( {0+2+2} \right)\bmod 5 = 4$

$\quad \Rightarrow \quad S \leftarrow \left( {\begin{array}{*{20}{c}} 1 & 3 & 4 & 0 & 2 \\ \end{array} } \right)$

$j = 4,\quad i = 3$

$j \leftarrow \left( {4+S\left[ 3 \right]+K\left[ {3\bmod 3} \right]} \right)\bmod 5 = \left( {4+0+3} \right)\bmod 5 = 2$

$\quad \Rightarrow \quad S \leftarrow \left( {\begin{array}{*{20}{c}} 1 & 3 & 0 & 4 & 2 \\\end{array} } \right)$

$j = 2,\quad i = 4$

$j \leftarrow \left( {2+S\left[ 4 \right]+K\left[ {4\bmod 3} \right]} \right)\bmod 5 = \left( {2+2+1} \right)\bmod 5 = 0$

$\quad \Rightarrow \quad S \leftarrow \left( {\begin{array}{*{20}{c}} 2 & 3 & 0 & 4 & 1 \\ \end{array} } \right)$

Schlüsselstrom:

KeyStreamByte(byte out)
begin
	i = (i+1) mod 5
	j = (j+S[i]) mod 5
	swap(S, i, j)
	out = S[(S[i]+S[j]) mod 5]
end

$S = \left( {\begin{array}{*{20}{c}} 2 & 3 & 0 & 4 & 1 \\ \end{array} } \right)$

$i = j = 0$

$i \leftarrow \left( {i+1} \right)\bmod 5 = \left( {0+1} \right)\bmod 5 = 1$

$j \leftarrow \left( {j+S\left[ i \right]} \right)\bmod 5 = \left( {0+3} \right)\bmod 5 = 3$

$\quad \Rightarrow \quad S \leftarrow \left( {\begin{array}{*{20}{c}} 2 & 4 & 0 & 3 & 1 \\ \end{array} } \right)$

$ou{t_1}:\quad S\left[ {\left( {S\left[ i \right]+S\left[ j \right]} \right)\bmod 5} \right] = S\left[ 2 \right] = \boxed0$

$i \leftarrow \left( {i+1} \right)\bmod 5 = \left( {1+1} \right)\bmod 5 = 2$

$j \leftarrow \left( {j+S\left[ i \right]} \right)\bmod 5 = \left( {3+0} \right)\bmod 5 = 3$

$\quad \Rightarrow \quad S \leftarrow \left( {\begin{array}{*{20}{c}} 2 & 4 & 3 & 0 & 1 \\ \end{array} } \right)$

$ou{t_2}:\quad S\left[ {\left( {S\left[ i \right]+S\left[ j \right]} \right)\bmod 5} \right] = S\left[ 3 \right] = \boxed0$

$i \leftarrow \left( {i+1} \right)\bmod 5 = \left( {2+1} \right)\bmod 5 = 3$