Die Cäsar-Chiffre ist eines der einfachsten, aber auch unsichersten Verfahren, um Texte zu verschlüsseln. Das Verfahren wurde nach dem römischen Kaiser Julius Cäsar benannt, der auf diese Weise bereits vor über 2000 Jahren Nachrichten verschlüsselt haben soll.

Die Cäsar-Chiffre ist eine monoalphabetische Substitution, das heißt, jeder Buchstabe des Textes wird durch genau einen anderen Buchstaben des Alphabets ersetzt. Dieser Austausch geschieht jedoch nicht zufällig, sondern basiert auf zyklischer Rotation des Alphabets um $\text{[math]}$ Zeichen, wobei $\text{[math]}$ der verwendete Schlüssel ist.

Verschlüsselung

Die Verschlüsselung einer Nachricht erfolgt buchstabenweise mit einem Schlüssel $\text{[math]}$ aus der Menge $\text{[math]}$ , wobei der Wert $\text{[math]}$ nicht sinnvoll ist, da der Originaltext in diesem Fall keine Änderung erfährt.

Für einen gegebenen Buchstaben wird zunächst anhand der folgenden Tabelle seine Position $\text{[math]}$ im Alphabet bestimmt.

$\text{[math]}$

Anschließend erhält man den Wert $\text{[math]}$ des verschlüsselten Buchstaben durch folgende kurze Berechnungsformel:

Mit Hilfe obiger Tabelle kann dieser Wert $\text{[math]}$ wieder in einen Buchstaben transformiert werden.

Entschlüsselung

Die Entschlüsselung einer Nachricht erfolgt ähnlich wie die Verschlüsselung mit Schlüssel $\text{[math]}$ , wir verwenden jedoch die Formel

Beispiel


unverschlüsselt	O	T	T	O	K	O	M	M	T

$\text{[math]}$	$\text{[math]}$	$\text{[math]}$	$\text{[math]}$	$\text{[math]}$	$\text{[math]}$	$\text{[math]}$	$\text{[math]}$	$\text{[math]}$	$\text{[math]}$


$\text{[math]}$	$\text{[math]}$	$\text{[math]}$	$\text{[math]}$	$\text{[math]}$	$\text{[math]}$	$\text{[math]}$	$\text{[math]}$	$\text{[math]}$	$\text{[math]}$

verschlüsselt	R	W	W	R	N	R	P	P	W

Statt nur über dem Alphabet $\text{[math]}$ kann man analog allgemeine Cäsar-Chiffre über beliebigen endlichen Alphabeten $\text{[math]}$ definieren.

Kryptoanalyse mit Sprachstatistik

In diesem Abschnitt wollen wir beispielhaft anhand der Cäsar-Chiffre vorführen, wie die Methode der Sprachstatistik angewendet werden kann. Dazu sei eine allgemeine Cäsar-Chiffre über dem Alphabet $\text{[math]}$ gegeben.

Wir nehmen an, dass die Buchstaben des Klartextes unabhängig voneinander gemäß der Wahrscheinlichkeitsverteilung $\text{[math]}$ gewählt werden. Der Wert $\text{[math]}$ gibt also die Wahrscheinlichkeit für das Auftreten des Buchstabens $\text{[math]}$ an. Die Annahme über die Verteilung der Buchstaben kann man als in der Realität annähernd erfüllt ansehen.

Wenn $\text{[math]}$ der Schlüssel ist, dann hat das Kryptogramm die Wahrscheinlichkeitsverteilung $\text{[math]}$ , wobei die Indizes modulo $\text{[math]}$ gerechnet werden. Der Vektor der Wahrscheinlichkeitsverteilung $\text{[math]}$ ist also eine zyklische Rotation des Vektors der Verteilung $\text{[math]}$ . Wenn man die Größe der Verschiebung bestimmen kann, so hat man den Schlüssel gefunden. Die Größe der Verschiebung bestimmt man nun dadurch, dass man die Positionen beispielsweise der beiden häufigsten, also wahrscheinlichsten Buchstaben im verschobenen Vektor bestimmt und diese mit ihren nicht verschobenen Positionen vergleicht. Dazu überlegen wir uns folgendes.

Es sei $\text{[math]}$ die Länge eines Klartextes und $\text{[math]}$ die Zufallsvariable die angibt, wie oft der Buchstabe $\text{[math]}$ im Klartext vorkommt. Es ergibt sich als Wahrscheinlichkeit, dass der Buchstabe $\text{[math]}$ genau $\text{[math]}$ mal im Klartext der Länge $\text{[math]}$ vorkommt

denn man hat $\text{[math]}$ Möglichkeiten, $\text{[math]}$ der $\text{[math]}$ Positionen im Klartext auszuwählen und an diesen $\text{[math]}$ Positionen tritt jeweils mit Wahrscheinlichkeit $\text{[math]}$ der Buchstabe $\text{[math]}$ auf und jede andere der $\text{[math]}$ vielen restlichen Positionen enthält kein $\text{[math]}$ mit Wahrscheinlichkeit $\text{[math]}$ . Somit ergibt sich der Erwartungswert der Zufallsvariable $\text{[math]}$ als

Wir führen eine neue Zuvallsvariable $\text{[math]}$ ein mit $\text{[math]}$ . Die Zufallsvariable $\text{[math]}$ hat eine zentrierte und normierte Binomialverteilung, die sich für große $\text{[math]}$ wie eine Standardnormalverteilung verhält. Insbesondere gilt für große $\text{[math]}$

Also ist die Wahrscheinlichkeit, dass die relative Häufigkeit $\text{[math]}$ des Buchstaben $\text{[math]}$ um mehr als 0,015 von der Wahrscheinlichkeit $\text{[math]}$ des Auftretens von $\text{[math]}$ abweicht, kleiner als $\text{[math]}$ . Betrachtet man das englische Alphabet, so sind die Wahrscheinlichkeiten der beiden häufigsten Buchstaben e und t: $\text{[math]}$ und $\text{[math]}$ und somit $\text{[math]}$ . Es kann also mit großer Wahrscheinlichkeit in einem langen Text zwischen $\text{[math]}$ und $\text{[math]}$ unterschieden werden und die Cäsar-Chiffre mit Hilfe der Häufigkeitsanalyse geknackt werden.

Eine zweite Kryptoanalyse

Eine zweite Möglichkeit, Cäsar-Chiffren über dem Alphabet $\text{[math]}$ durch eine Häufigkeitsanalyse zu brechen, ist die folgende. Es sei $\text{[math]}$ eine Zufallsvariable mit der Verteilung $\text{[math]}$ wobei $\text{[math]}$ die Wahrscheinlichkeit für das Auftreten des Buchstaben $\text{[math]}$ im Klartext ist. Weiterhin seien $\text{[math]}$ die beobachteten relativen Häufigkeiten der Buchstaben im Kryptogramm. Bei Schlüssel $\text{[math]}$ ist $\text{[math]}$ (Indexrechnung modulo $\text{[math]}$ ) die Buchstabenverteilung im Klartext. Die Idee bei der Analyse besteht darin, ein $\text{[math]}$ zu bestimmen, bei dem die euklidische Norm

minimal ist. Da $\text{[math]}$ und $\text{[math]}$ für jedes $\text{[math]}$ konstant sind, reicht es, den Ausdruck

zu maximieren. Für große $\text{[math]}$ gilt mit einer Wahrscheinlichkeit von fast $\text{[math]}$ , dass $\text{[math]}$ klein ist, wenn $\text{[math]}$ korrekt ist, sowie dass $\text{[math]}$ groß ist, wenn $\text{[math]}$ nicht korrekt ist.

Übungen

Aufgabe 1
Gegeben sei eine Cäsar-Chiffre bei beliebigem Modulus $\text{[math]}$ . Ein Angreifer kenne nur einige Kryptogramme $\text{[math]}$ .

Diskutieren Sie in nachfolgenden Situationen, ob der Angreifer die Kryptogramme entschlüsseln kann:

Wie sind die Punkte 1. bis 4. zu beantworten, wenn der Angreifer für das Kryptogramm $\text{[math]}$ (und nur für dieses) den entsprechenden Klartext kennt?

Aufgabe 2
Diskutieren Sie Kryptosysteme in Analogie zur Cäsar-Chiffre, die die folgende Chiffrierfunktion $\text{[math]}$ mit $\text{[math]}$ verwenden; speziell hinsichtlich der geeigneten Parameterwahl.

Wie ändert sich die Situation, wenn man Chiffrierfunktionen der Form $\text{[math]}$ mit $\text{[math]}$ verwendet?

Aufgabe 3
Überlegen Sie sich ein Kryptosystem in Analogie zur Cäsar-Chiffre, das auf konsekutiven Paaren von Buchstaben operiert.

Aufgabe 4
Gegeben ist eine Cäsar-Chiffre über dem endlichen Alphabet $\text{[math]}$ . Bei einem ciphertext-only-attack erhalten Sie genau einen Chiffratbuchstaben $\text{[math]}$ . Gemäß der Gleichverteilung raten Sie zufällig einen Schlüssel $\text{[math]}$ . Nach Ihrer Wahl erfahren Sie, dass der Buchstabe $\text{[math]}$ mit $\text{[math]}$ nicht der Schlüssel ist. Sie haben nun die Möglichkeit, Ihre ursprüngliche Wahl einmalig zu revidieren. Würden Sie diese Möglichkeit wahrnehmen?