2.7 – Affine Chiffre

2.7.1 Definition

Sei $\Sigma$ ein Alphabet mit $\left| \Sigma \right| = n$ Zeichen, sei $m \in \mathbb{N}$ die Länge des Klar- und Geheimtextes. Die Zeichen des Klartextes $p \in \mathcal{P},p = \left( {{p_1}, \ldots ,{p_m}} \right)$ und des Geheimtextes $c \in \mathcal{C},c = \left( {{c_1}, \ldots ,{c_m}} \right)$ werden mit der Abbildung $f:\Sigma \to {\mathbb{Z}_n}$ kodiert. Sei $\mathcal{K} = \mathbb{Z}_n^2$ und $k \in \mathcal{K}$ ein Schlüssel mit $k = \left( {a,b} \right)$ , wobei $ggT\left( {a,n} \right) = 1$ .

Verschlüsselung:

${c_i} = a \cdot {p_i}+b\quad \forall i = 1, \ldots ,m$

Entschlüsselung:

${p_i} = {a^{-1}} \cdot \left( {{c_i}+\left( {-b} \right)} \right)\quad \forall i = 1, \ldots ,m$

wobei ${a^{-1}} \in {\mathbb{Z}_n}$ invers zu $a$ bzgl. der Multiplikation.

2.7.2 Beispiele

Aufgabe 1:

Verschiebechiffre, $k = 7$ , $p = VERSCHLUESSELUNG$

1. Schritt: Kodierung der Zeichen:

Wir benutzen die Korrespondenztabelle

$\begin{array}{*{20}{c}}{a \in \Sigma } &\vline & A & B & C & D & E & F & G & H & I & J & K & L & M \\{f\left( a \right) \in {\mathbb{Z}_{26}}} &\vline & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & {10} & {11} & {12} \\ \hline{a \in \Sigma } &\vline & N & O & P & Q & R & S & T & U & V & W & X & Y & Z \\{f\left( a \right) \in {\mathbb{Z}_{26}}} &\vline & {13} & {14} & {15} & {16} & {17} & {18} & {19} & {20} & {21} & {22} & {23} & {24} & {25} \\ \end{array}$

und erhalten so:

$p = \left( {21,4,17,18,2,7,11,20,4,18,18,4,11,20,13,6} \right)$

2. Schritt: Berechnung des Geheimtextes:

Wir addieren 7 auf jedes Zeichen und rechnen dann Modulo 26:

$c = \left( {2,11,24,25,9,14,18,1,11,25,25,11,18,1,20,13} \right)$

3. Schritt: Dekodierung der Zeichen:

Wir benutzen wieder die Tabelle, um den Geheimtext zu erhalten:

$c = CLYJOSBLZZLSBUN$

Aufgabe 2:

Entschlüsselung einer Affinen Chiffre, Verschlüsselung mit ${c_i} = 15{p_i}+12$

$c = HCQNLCY$

1. Schritt: Kodierung:

$c = \left( {7,2,16,13,11,2,24} \right)$

2. Schritt: Berechnung:

Um keine negative Zahl zu haben, rechnen wir zunächst Modulo 26:

$15{p_i} = {c_i}-12 \equiv {c_i}+14$

Nun müssen wir das multiplikative Inverse von $15$ bestimmen:

${p_i} = {15^{-1}}\left( {{c_i}+14} \right)\bmod 26$

Wir verwenden zunächst den Euklidischen Algorithmus zum Berechnen des ggT:

$26 = 1 \cdot 15+11$

$15 = 1 \cdot 11+4$

$11 = 2 \cdot 4+3$

$4 = 1 \cdot 3+\boxed1$

$3 = 3 \cdot 1+0$

Nun fahren wir mit dem erweiterten Euklidischen Algorithmus fort, um das Inverse zu bestimmen:

$1 = 4-1 \cdot 3\quad |3 = 11-2 \cdot 4$

$1 = 4-1 \cdot 11+2 \cdot 4 = 3 \cdot 4-1 \cdot 11\quad |4 = 15-1 \cdot 11$

$1 = 3 \cdot \left( {15-1 \cdot 11} \right)-1 \cdot 11 = 3 \cdot 15-4 \cdot 11\quad |11 = 26-1 \cdot 15$

$1 = 3 \cdot 15-4 \cdot \left( {26-1 \cdot 15} \right) = 7 \cdot 15-4 \cdot 26$

$1 = 7 \cdot 15+\left( {-4} \right) \cdot 26$

$\quad \Rightarrow \quad 1 \equiv \left( {\boxed7 \cdot 15} \right)\bmod 26$

Nun können wir die einzelnen Zeichen entschlüsseln.

${p_i} = {15^{-1}}\left( {{c_i}+14} \right)\,\bmod \,26$

$\Rightarrow \quad {p_i} = 7\left( {{c_i}+14} \right)\,\bmod \,26$

$\Rightarrow \quad {p_i} = \left( {7{c_i}+20} \right)\,\bmod \,26$

Das erste Zeichen:

$\left( {7 \cdot 7+20} \right)\bmod 26 = 17$

Die restlichen Zeichen:

$p = \left( {17,8,2,7,19,8,6} \right)$

3. Schritt: Dekodierung:
$p = RICHTIG$

Aufgabe 3:

Wir haben folgenden Geheimtext abgefangen:

WTKVXWHOCVACHSSWOHCKHOSWXQOLLHWTEUOWWGAMENWOGHWAWO
KHWGWLWXOPMCUHCCWAUWXVILVTVTTWHOWNMWOHFHOVOWHOWCGW
OTSWXLVTWHOWOXVUCWOPMOTEUKVXBWCWIWOUMABUVSSWQOLOVW
USWQOLKHWTHWTMOVWUSWQOLOVEULWCTEUOWWVQGIAHENSWTSVE
UTHWTHEUCHSLWXOVLWAHOLWOGHOFWXQOLWTGHWAWOLXWHSXMZG
WOIAQSHOLWOTEUOWWQOLKWHALVTXMSWHCKWHTTWOTEUOWWTMTE

Dieser soll entschlüsselt werden.
Wir erstellen zunächst eine Strichstatistik. Dabei zählen wir nicht nur die Vorkommen der Zeichen, sondern schreiben jeweils das nachfolgende Zeichen auf und sortieren dann nach Häufigkeit:

W: AAAACCCGGHHHHHHHHILNOOOOOOOOOOOOOQQQQTTTTTTTTUUVWWWWXXXXXX
O: CFGGHHIKLLLLLLLLLPPSTTTTUVVVVVWWWWWWWWX
H: ACCCEEFOOOOOOOOOSSSTWWWWWWW
T: EEEEEEGHHHKMMSSTTVWWWX
L: HKKLOOVVVWWWWWWWX
V: AEEILOQSTTTTUWWXX
U: CCHKLMOOOOSSTVW
S: HLSSVWWWWWWWWX
C: CGHHKKTUVWWW
X: BLMMOOQQVVWW
A: BCHHLMQUWW
E: NNUUUUUUUU
M: ACEOOSTWZ
G: AHHHIWWW
Q: GOOOOOOS
K: HHHVVWW
I: AALW
N: MSW
B: UW
F: HW
P: MM
Z: G

Der häufigste Buchstabe ist in deutschen Texten das E. Wir ersetzen daher W durch e:

e: AAAACCCGGHHHHHHHHILNOOOOOOOOOOOOOQQQQTTTTTTTTUUVeeeeXXXXXX
O: CFGGHHIKLLLLLLLLLPPSTTTTUVVVVVeeeeeeeeX
H: ACCCEEFOOOOOOOOOSSSTeeeeeee
T: EEEEEEGHHHKMMSSTTVeeeX
L: HKKLOOVVVeeeeeeeX
V: AEEILOQSTTTTUeeXX
U: CCHKLMOOOOSSTVe
S: HLSSVeeeeeeeeX
C: CGHHKKTUVeee
X: BLMMOOQQVVee
A: BCHHLMQUee
E: NNUUUUUUUU
M: ACEOOSTeZ
G: AHHHIeee
Q: GOOOOOOS
K: HHHVVee
I: AALe
N: MSe
B: Ue
F: He
P: MM
Z: G

Das zweithäufigste Zeichen ist das n. Wir ersetzen also O durch n. Ein E wird häufig durch ein I gefolgt. Wir ersetzen H durch i:

e: AAAACCCGGiiiiiiiiILNnnnnnnnnnnnnnQQQQTTTTTTTTUUVeeeeXXXXXX
n: CFGGiiIKLLLLLLLLLPPSTTTTUVVVVVeeeeeeeeX
i: ACCCEEFnnnnnnnnnSSSTeeeeeee
T: EEEEEEGiiiKMMSSTTVeeeX
L: iKKLnnVVVeeeeeeeX
V: AEEILnQSTTTTUeeXX
U: CCiKLMnnnnSSTVe
S: iLSSVeeeeeeeeX
C: CGiiKKTUVeee
X: BLMMnnQQVVee
A: BCiiLMQUee
E: NNUUUUUUUU
M: ACEnnSTeZ
G: AiiiIeee
Q: GnnnnnnS
K: iiiVVee
I: AALe
N: MSe
B: Ue
F: ie
P: MM
Z: G

Eine Besonderheit des Deutschen ist, dass das C in 95% der Fälle von einem H gefolgt wird und in 5% der Fälle von einem K. Vor dem C steht meistens ein S, vor dem S ein E oder A. Es folgt:

e: AAAACCCGGiiiiiiiiILknnnnnnnnnnnnnQQQQsssssssshhaeeeeXXXXXX
n: CFGGiiIKLLLLLLLLLPPSsssshaaaaaeeeeeeeeX
i: ACCCccFnnnnnnnnnSSSseeeeeee
s: ccccccGiiiKMMSSssaeeeX
L: iKKLnnaaaeeeeeeeX
a: AccILnQSssssheeXX
h: CCiKLMnnnnSSsae
S: iLSSaeeeeeeeeX
C: CGiiKKshaeee
X: BLMMnnQQaaee
A: BCiiLMQhee
c: kkhhhhhhhh
M: ACcnnSseZ
G: AiiiIeee
Q: GnnnnnnS
K: iiiaaee
I: AALe
k: MSe
B: he
F: ie
P: MM
Z: G

Der Geheimtext sieht inzwischen aus wie folgt:

esKaXeinCaACiSSeniCKinSeXQnLLieschneeGAMckenGieAen
KieGeLeXnPMChiCCeAheXaILasasseinekMeniFinaneineCGe
nsSeXLaseinenXahCenPMnschKaXBeCeIenhMABhaSSeQnLnae
hSeQnLKiesiesMnaehSeQnLnachLeCschneeaQGIAickSesSac
hsiesichCiSLeXnaLeAinLenGinFeXQnLesGieAenLXeiSXMZG
enIAQSinLenschneeQnLKeiALasXMSeiCKeissenschneesMsc

Einzelne Wörter können schon erkannt werden. Es ist nicht weiter schwierig, die restlichen Buchstaben zuzuordnen. Wir erhalten:

eswareinmalmittenimwinterunddieschneeflockenfielen
wiefedernvomhimmelherabdasasseinekoeniginaneinemfe
nsterdaseinenrahmenvonschwarzemebenholzhatteundnae
hteundwiesiesonaehteundnachdemschneeaufblicktestac
hsiesichmitdernadelindenfingerundesfielendreitropf
enblutindenschneeundweildasroteimweissenschneesosc