Vigenère-Verschlüsselung in Python

Was du hier lernst

Polyalphabetische Verschlüsselung
Modulo-Rechnung
Listen und join()
Zeichen und Zeichencodes
bytes und UTF-8
Animation

So funktioniert die Vigenère-Verschlüsselung

Die Caesar-Verschlüsselung hat einen Konstruktionsfehler: Jeder Buchstabe wird um denselben Betrag verschoben. Deshalb bleibt die Häufigkeitsverteilung der Sprache sichtbar, und eine Statistik knackt die Nachricht. Das nach Blaise de Vigenère benannte Verfahren aus dem 16. Jahrhundert behebt genau diesen Fehler. Die Verschiebung wechselt von Zeichen zu Zeichen, und ein Passwort legt fest, in welcher Reihenfolge. Rund 300 Jahre lang galt es als unknackbar.

1. Ein Passwort ist eine Liste von Verschiebungen

Jeder Buchstabe des Passworts steht für eine Zahl, nämlich seine Position im Alphabet. Aus "geheim" werden die Verschiebungen 6, 4, 7, 4, 8 und 12. Das Passwort wird unter den Klartext geschrieben und so oft wiederholt, bis es reicht:

unverschluesselter text
geheimgeheimgeheimgehei

Jede Spalte wird dann für sich wie bei Caesar verschlüsselt, nur eben mit ihrer eigenen Verschiebung. Die Animation zeigt das Spalte für Spalte.

2. Der Zeiger ins Passwort

encrypt geht den Klartext Zeichen für Zeichen durch. Die Variable keyIndex merkt sich, welcher Passwortbuchstabe gerade dran ist:

shift = symbols.index(password[keyIndex])
encryptedLetter = symbols[(symbols.index(letter) + shift) % len(symbols)]
keyIndex += 1
keyIndex %= pwdLength

Nach dem letzten Passwortbuchstaben setzt keyIndex %= pwdLength den Zeiger wieder auf 0, und das Passwort beginnt von vorn. Die Ergebnisse sammelt das Programm in einer Liste. "".join(encrypted) fügt sie am Ende zu einem String zusammen. Das ist schneller, als bei jedem Schritt einen neuen String zu bauen.

Schon im ersten Schritt zeigt sich eine Besonderheit: »u« (20) plus »g« (6) ergibt 26, und an dieser Stelle steht im Alphabet das Leerzeichen. Der Geheimtext beginnt deshalb mit einem Leerzeichen, das in der Animation als »␣« erscheint.

3. Entschlüsseln ist Rückwärtsrechnen

decrypt sieht fast genauso aus, zieht die Verschiebung aber ab:

decryptedLetter = symbols[(symbols.index(letter) - shift + len(symbols))
                          % len(symbols)]

Das + len(symbols) sorgt dafür, dass vor dem Modulo nie eine negative Zahl steht. In Python wäre das nicht nötig, denn % liefert dort auch bei negativen Zahlen ein Ergebnis zwischen 0 und 26. In vielen anderen Sprachen ist das aber anders, und der Trick schadet nicht.

4. Warum die Statistik ins Leere läuft

Im Klartext kommt das »e« fünfmal vor. Im Geheimtext wird es zu »i«, »m«, »i«, »m« und »l«, je nachdem, unter welchem Passwortbuchstaben es gerade steht. Umgekehrt kann dasselbe Geheimzeichen für verschiedene Klartextbuchstaben stehen. Die Häufigkeiten verteilen sich dadurch gleichmäßiger, und der Fingerabdruck der Sprache verschwimmt.

Die Schwachstelle: Wiederholung

Das Passwort wiederholt sich, und damit auch das Muster der Verschiebungen. Verschlüsselst du einen Text aus lauter »e«, entsteht kilimqkilimq…, ein Muster mit der Länge des Passworts. Wer die Länge kennt, zerlegt den Geheimtext in sechs Caesar-Texte und knackt jeden einzeln per Häufigkeitsanalyse. Friedrich Kasiski hat diesen Weg 1863 veröffentlicht.

5. Version 2: Bytes statt Buchstaben

Version 1 kennt nur ihre 27 Zeichen. Schon ein »ü« oder ein Großbuchstabe bringt symbols.index() aus dem Tritt. Die zweite Fassung aus dem Buch rechnet deshalb nicht mit Positionen im Alphabet, sondern mit den Zahlenwerten der Zeichen, modulo 256:

encrypted.append((byte + password[keyIndex]) % 256)

In Python 3 heißen solche Zahlenfolgen bytes. "unverschlüsselter Text".encode("utf-8") wandelt den Text in Bytes um. Das »ü« belegt dabei zwei Bytes, deshalb ist der Geheimtext 23 Bytes lang, obwohl der Text nur 22 Zeichen hat. Die verschlüsselten Bytes sind meist keine lesbaren Zeichen mehr. Das Programm zeigt sie deshalb mit .hex(" ") als Hexadezimalzahlen an.

6. Die Animation

drawStep(step) zeichnet das komplette Bild für einen Schritt: die drei Zeilen, eine gelbe Markierung für die aktuelle Spalte und darunter die Rechnung. Die Schleife ruft die Funktion für jede Stelle auf und wartet mit await screen.frame(stepsPerSecond) jeweils bis zum nächsten Bild. Am Ende steht da, welche Zeichen aus dem »e« geworden sind.

Probier mal

Jede Variante ändert den Code oben. Ein Klick auf »Ausprobieren« übernimmt die Änderung in den Editor und startet das Programm. »Zurücksetzen« holt das Original zurück.

01Ein längeres Passwort

Je länger das Passwort, desto seltener wiederholt sich das Muster der Verschiebungen. Erlaubt sind alle 27 Zeichen des Alphabets, also auch Leerzeichen.
```
- password    = "geheim"
+ password    = "coding for fun"
```
02Ein Buchstabe – und es ist wieder Caesar

Besteht das Passwort nur aus einem »e«, wird jede Stelle um 4 verschoben. Das ist genau die Caesar-Verschlüsselung aus dem Buch mit dem Schlüssel 4. Vigenère ist also eine Verallgemeinerung von Caesar.
```
- password    = "geheim"
+ password    = "e"
```
03Das Muster im Geheimtext

Verschlüssle einen Text aus lauter »e«. Der Geheimtext wiederholt sich alle sechs Zeichen, genau so lang ist das Passwort. Solche Wiederholungen hat Friedrich Kasiski 1863 genutzt, um die Passwortlänge zu erraten und das Verfahren zu brechen.
```
- plainText   = "unverschluesselter text"
+ plainText   = "eeeeeeeeeeeeeeeeeeeeeee"
```
04Umlaute und Emojis in Version 2

Version 1 kennt nur ihre 27 Zeichen, bei einem »ü« bricht symbols.index() ab. Version 2 rechnet mit Bytes und verschlüsselt deshalb alles, was sich in UTF-8 schreiben lässt, auch Emojis. Achte auf die Länge: Das »ü« belegt zwei Bytes, die Schlange vier.
```
- plainText2 = "unverschlüsselter Text"
+ plainText2 = "Grüße aus Ingolstadt! 🐍"
```
05Schneller animieren

stepsPerSecond legt fest, wie viele Spalten pro Sekunde verschlüsselt werden. await screen.frame(stepsPerSecond) wartet entsprechend kürzer.
```
- stepsPerSecond = 4
+ stepsPerSecond = 12
```

Vom Buch in den Browser

Im Buch gibt es zwei getrennte Python-2-Programme: vigenere_v1.py mit dem Alphabet aus 26 Buchstaben plus Leerzeichen und vigenere_v2.py, das mit chr() und ord() modulo 256 rechnet. Hier stehen beide in einer Datei. Die Funktionen aus Version 2 heißen deshalb encryptBytes und decryptBytes, damit sie die gleichnamigen Funktionen aus Version 1 nicht überschreiben. Die Animation ist neu.

print "plain Text =", plainText wird zu print("plain Text =", plainText).
In encrypt und decrypt steht die Verschiebung jetzt in einer eigenen Variablen shift. Die Rechnung ist dieselbe, die Zeile wird nur kürzer und lesbarer.
Die größte Änderung betrifft Version 2. In Python 2 war "unverschlüsselter Text" eine Folge von Bytes, bei Latin-1 genau ein Byte pro Zeichen, und chr((ord(letter) + ord(key)) % 256) rechnete direkt damit. In Python 3 ist ein String eine Folge von Unicode-Zeichen. ord("🐍") ergibt 128013, und das % 256 würde Information vernichten. Die Portierung wandelt den Text deshalb zuerst mit .encode("utf-8") in echte Bytes um und rechnet mit bytes/bytearray. Beim Entschlüsseln holt .decode("utf-8") den Text zurück.
Im Original wurde der verschlüsselte Text direkt ausgegeben, mit Steuerzeichen und Zeichensalat im Terminal. Hier zeigt .hex(" ") die Bytes als Hexadezimalzahlen.

Original aus dem Buch ansehen vigenere_v1.py · Python 2

#coding: latin1
'''
Created on 07.12.2009

@author: Lars Heppert
'''

symbols     = "abcdefghijklmnopqrstuvwxyz "
plainText   = "unverschluesselter text"
password    = "geheim"

print "plain Text =", plainText
print "password   =", password

def encrypt(plainText, password):
    pwdLength   = len(password)
    # die aktuelle Position innerhalb
    # des Passwortes wird in keyIndex vermerkt
    keyIndex    = 0
    encrypted   = []
    for letter in plainText:
        # der aktuelle Klartextbuchstabe wird zum
        # aktuellen Passwortbuchstaben addiert, um Überläufe
        # abzufangen wird zum Schluss Modulo der Anzal der Symbole gerechent
        encryptedLetter = symbols[(symbols.index(letter) + symbols.index(password[keyIndex])) % len(symbols)]
        # der Index innerhalb des Passwortes
        # wird um eins erhöht
        keyIndex += 1
        # es wird Sichergestellt, dass der keyIndex
        # innerhalb der Passwortlänge bleibt
        keyIndex %= pwdLength
        encrypted.append(encryptedLetter)
    
    # es wird ein Leerstring erzeugt um die Methode
    # join der entstanden Sting-Instance für die Umwandlung
    # der Liste in einen String zu verwenden    
    return "".join(encrypted)

encryptedText = encrypt(plainText, password)

print "encrypted Text =", encryptedText

def decrypt(encryptedText, password):
    pwdLength   = len(password)
    keyIndex    = 0
    decrypted   = []
    for letter in encryptedText:
        # der aktuelle Passwortbuchstaben wird vom
        # aktuellen Geheimtextbuchstabe subtrahiert, um negative Werte
        # abzufangen wird zum Schluss die Symbolanzahl addiert und
        # Modulo der Anzal der Symbole gerechent um Überläufe abzufangen
        decryptedLetter = symbols[(symbols.index(letter) - symbols.index(password[keyIndex]) + len(symbols)) % len(symbols)]
        keyIndex += 1
        keyIndex %= pwdLength
        decrypted.append(decryptedLetter)
        
    return "".join(decrypted)

decryptedText = decrypt(encryptedText, password)

print "decrypted Text =", decryptedText

Original aus dem Buch ansehen vigenere_v2.py · Python 2

#coding: latin1
'''
Created on 07.12.2009

@author: Lars Heppert
'''

plainText   = "unverschlüsselter Text"
password    = "geheim"

print "plain Text =", plainText
print "password   =", password

def encrypt(plainText, password):
    pwdLength   = len(password)
    # die aktuelle Position innerhalb
    # des Passwortes wird in keyIndex vermerkt
    keyIndex    = 0
    encrypted   = []
    for letter in plainText:
        # der aktuelle Klartextbuchstabe wird mit dem
        # aktuellen Passwortbuchstaben addiert, um Überläufe
        # abzufangen wird zum Schluss Modulo 256 gerechent
        encryptedLetter = chr((ord(letter) + ord(password[keyIndex])) % 256)
        # der Index innerhalb des Passwortes
        # wird um eins erhöht
        keyIndex += 1
        # es wird Sichergestellt, dass der keyIndex
        # innerhalb der Passwortlänge bleibt
        keyIndex %= pwdLength
        encrypted.append(encryptedLetter)
    
    # es wird ein Leerstring erzeugt um die Methode
    # join der entstanden Sting-Instance für die Umwandlung
    # der Liste in einen String zu verwenden    
    return "".join(encrypted)

encryptedText = encrypt(plainText, password)

print "encrypted Text =", encryptedText

def decrypt(encryptedText, password):
    pwdLength   = len(password)
    keyIndex    = 0
    decrypted   = []
    for letter in encryptedText:
        decryptedLetter = chr((ord(letter) - ord(password[keyIndex]) + 256) % 256)
        keyIndex += 1
        keyIndex %= pwdLength
        decrypted.append(decryptedLetter)
        
    return "".join(decrypted)

decryptedText = decrypt(encryptedText, password)

print "decrypted Text =", decryptedText

Was du hier lernst

So funktioniert die Vigenère-Verschlüsselung

1. Ein Passwort ist eine Liste von Verschiebungen

2. Der Zeiger ins Passwort

3. Entschlüsseln ist Rückwärtsrechnen

4. Warum die Statistik ins Leere läuft

5. Version 2: Bytes statt Buchstaben

6. Die Animation

Probier mal

01Ein längeres Passwort

02Ein Buchstabe – und es ist wieder Caesar

03Das Muster im Geheimtext

04Umlaute und Emojis in Version 2

05Schneller animieren

Vom Buch in den Browser

Passt dazu

Caesar-Verschlüsselung

RSA-Verschlüsselung

Goethe-Generator