8  Caesar Chiffre

TippNotebook interaktiv ausführen

In der Kryptologie wird mit Verschlüsselung jener Prozess beschrieben, der eine Nachricht so transformiert, dass sie idealerweise nur von autorisierten Parteien gelesen werden kann. Dieser Prozess wandelt die ursprüngliche Darstellung der Informationen, bekannt als Klartext, in eine alternative Form, bekannt als Chiffretext, um. Trotz seines Ziels verhindert die Verschlüsselung nicht selbst die Interferenz, sondern verweigert dem potenziellen Abhörer den verständlichen Inhalt.

Aus Wikipedia

Das erste Beispiel für eine Chiffre, das wir uns ansehen werden, ist die Caesar-Chiffre.

Die Caesar-Chiffre ist eine einfache Substitutionsverschlüsselungstechnik, bei der jeder Buchstabe des zu verschlüsselnden Textes durch einen Buchstaben ersetzt wird, der sich um eine feste Anzahl von Positionen im Alphabet verschiebt. Zum Beispiel würde bei einer Verschiebung um vier Positionen nach rechts A durch E ersetzt werden, und das Wort CIPHER würde zu GMTLIV. Die Technik ist nach Julius Caesar benannt, der sie in seinen Briefen verwendete. Die Einfachheit der Caesar-Chiffre macht sie zu einer beliebten Quelle für Freizeit-Kryptogramme.

Aus Encyclopedia Britannica

8.1 Python Implementation

Um die Caesar-Chiffre in Python zu implementieren, bauen wir auf den von Python angebotenen String-Methoden auf. Die Funktion ord gibt den Unicode-Codepunkt für ein gegebenes Zeichen zurück, und die Funktion chr gibt das Zeichen zurück, das dem gegebenen Unicode-Codepunkt entspricht.

# Was ist der Unicode Wert des Buchstabens 'A'?

8.1.1 Simple (naive) Implementation

Als erstes definieren wir eine Funktion, die einen gegebenen Klartext verschlüsselt, indem sie jeden Buchstaben um eine bestimmte Anzahl von Positionen im Alphabet verschiebt.

plain = "CIPHER"
shift = 4

def caesar_encode(plain, shift):
    cipher = ""
    
    for char in plain:
        shifted = ord(char) + shift
        cipher += chr(shifted)
        
    return cipher

8.1.2 Verbesserte Implementation

Was geschieht aber, wenn wir das Ende des Alphabets erreichen? Zum Beispiel, wenn wir Z um 4 Positionen verschieben, würden wir über Z hinausgehen. Um dies zu handhaben, können wir den Modulo-Operator % verwenden, um im Alphabet von vorne zu beginnen. Der Modulo-Operator gibt den Rest einer Division zurück, was es uns ermöglicht, wieder bei Null zu beginnen, wenn wir die Länge des Alphabets überschreiten. Im Fall der Caesar-Chiffre können wir ihn verwenden, um sicherzustellen, dass unsere verschobenen Positionen innerhalb der Grenzen des Alphabets bleiben.

Daher verwenden wir modulo 26 (die Anzahl der Buchstaben im lateinischen Alphabet), um sicherzustellen, dass unsere verschobenen Positionen korrekt “herumwickeln”. Wenn wir Z um 4 Positionen verschieben, landen wir bei D. Dieses Wickelverhalten ist für die Funktionsweise der Caesar-Chiffre von entscheidender Bedeutung. Die Berechnung der neuen Position eines Buchstabens kann wie folgt ausgedrückt werden:

\[ x' = (x + n) \mod 26 \]

oder in einer kompakteren Form mit dem Modulo-Additionsoperator:

\[ x' = x \oplus_{26} n \]

In Python können wir dies wie folgt implementieren:

def caesar_encrypt_mod(plain, shift):
    cipher = ""
    
    for char in plain:
        shifted = (ord(char) - ord('A') + shift) % 26 + ord('A')
        cipher += chr(shifted)
        
    return cipher

Weil

ord('A')

65 zurückgibt, müssen wir 65 von dem Ergebnis von ord('A') subtrahieren, um 0 zu erhalten. Dies gibt uns den 0-basierten Index des Buchstabens im Alphabet, der für unsere Berechnungen nützlich ist.

Daher die oben gezeigte Berechnung.

Für die Entschlüsselung können wir einfach den Verschiebungswert subtrahieren anstatt ihn zu addieren:

def caesar_decrypt_mod(plain, shift):
    cipher = ""
    
    for char in plain:
        shifted = (ord(char) - ord('A') - shift) % 26 + ord('A')
        cipher += chr(shifted)
        
    return cipher

Für die Bequemlichkeit implementieren wir eine Funktion die sowohl ver- als auch entschlüsselt.

def caesar(text : str, shift : int, encrypt=True) -> str:
    text = text.upper()
    result = ""
    
    if encrypt:
        for char in text:
            shifted = (ord(char) - ord('A') + shift) % 26 + ord('A')
            result += chr(shifted)
    else:
        for char in text:
            shifted = (ord(char) - ord('A') - shift) % 26 + ord('A')
            result += chr(shifted)
            
    return result

8.2 Caesar Chiffre brechen

Es gibt zwei Hauptmethoden, um eine Caesar-Chiffre zu brechen:

1. Brute Force Attack: Versuchen Sie alle möglichen Verschiebungen (1-25) und sehen Sie, welche eine sinnvolle Ausgabe erzeugt.
2. Frequency Analysis: Analysieren Sie die Häufigkeit von Buchstaben im Chiffretext und vergleichen Sie sie mit der erwarteten Häufigkeit von Buchstaben in der Sprache.

8.2.1 Brute Force Attack

def caesar_bruteforce(ciphertext: str) -> None:
    for shift in range(1, 26):
        decrypted_text = caesar(ciphertext, shift, encrypt=False)
        print(f"Shift {shift}: {decrypted_text}")

8.2.2 Häufigkeitsanalyse

In der deutschen Sprache erscheinen bestimmte Buchstaben häufiger als andere. Zum Beispiel ist der Buchstabe ‘E’ der häufigste Buchstabe in deutschen Texten, gefolgt von ‘N’, ‘I’, ‘S’, ‘R’ und ‘A’. Durch die Analyse der Häufigkeit von Buchstaben im Chiffretext können wir fundierte Vermutungen darüber anstellen, welche Buchstaben im Klartext welchen im Chiffretext entsprechen.

Für eine genauere Analyse siehe die folgende Häufigkeitstabelle:

Platz	Buchstabe	Relative Häufigkeit
1.	E	17,40 %
2.	N	9,78 %
3.	I	7,55 %
4.	S	7,27 %
5.	R	7,00 %
6.	A	6,51 %
7.	T	6,15 %
8.	D	5,08 %
9.	H	4,76 %
10.	U	4,35 %
11.	L	3,44 %
12.	C	3,06 %
13.	G	3,01 %
14.	M	2,53 %
15.	O	2,51 %
16.	B	1,89 %
17.	W	1,89 %
18.	F	1,66 %
19.	K	1,21 %
20.	Z	1,13 %
21.	P	0,79 %
22.	V	0,67 %
23.	J	0,27 %
24.	Y	0,04 %
25.	X	0,03 %
26.	Q	0,02 %

Quelle: Wikipedia

Wir brauchen also eine Funktion, die die Häufigkeit jedes Buchstabens im Chiffretext zählt. Das Ergebnis sollte ein Dictionary sein, bei dem die Schlüssel die Buchstaben und die Werte die Zählungen jedes Buchstabens sind. Oder noch besser, die Häufigkeiten in Prozent.

Um die Sache einfach zu halten, nehmen wir an, dass der Eingabetext nur Großbuchstaben von A bis Z und keine Leerzeichen oder Satzzeichen enthält.

def letter_frequency(text: str) -> dict:
    frequency = {}
    total_letters = 0
    
    for char in text:
        if char not in frequency:
            frequency[char] = 1
        else:
            frequency[char] += 1
        total_letters += 1
        
    for key, value in frequency.items():
        frequency[key] = (value / total_letters) * 100
        
           
    return frequency

Nachdem wir den häufigsten Buchstaben im Chiffretext gefunden haben, können wir annehmen, dass er dem Buchstaben ‘E’ im Klartext entspricht. Indem wir die Verschiebung berechnen, die erforderlich ist, um den häufigsten Buchstaben in ‘E’ zu verwandeln, können wir dann den gesamten Chiffretext mit diesem Verschiebungswert entschlüsseln.

def find_shift(char: str, e = 'E') -> int:
    return (ord(char) - ord(e)) % 26