Symmetrische Verschlüsselung
Übersicht
Das Ver- und Entschlüsseln von Nachrichten wird schon seit der Antike betrieben. Folgende Übersicht zeigt eine mögliche Einteilung der bestehenden Verschlüsselungs-Verfahren:
Auf dieser Seite betrachten wir ein kleine Auswahl von symmetrischen Verschlüsselungsverfahren:
- Von den klassischen Substitutionsverfahren betrachten wir die Caesar-Verschlüsselung als Beispiel einer monoalphabetischen Substituion und
- die Vigenère-Chiffre als Beispiel einer polyalphabetischen Substitution.
- Ausserdem betrachten wir die XOR-Verschlüsselung als Beispiel einer modernen symmetrischen Verschlüsselung. Modern ist sie insofern, als sie mit Einsen und Nullen operiert und damit auf sämtliche Daten in digitaler Form anwendbar ist.
Begriffe
Folgende Begriffe solltest du kennen:
- Kryptologie: Wissenschaft / Lehre der Ver- und Entschlüsselung (altgr. kryptós = verborgen ). Zwei Teilbereiche:
- Kryptographie: Geheimschriften, Finden von sicheren Verschlüsselungsverfahren
- Kryptoanalyse: Verschlüsselungen analysieren und “knacken”
- Klartext – cleartext, plaintext
- Chiffrat – Geheimtext, ciphertex, verschlüsselter Text
- Schlüssel – key
- Verschlüsselungsverfahren, auch Chiffre: Wandelt den Klartext in das Chiffrat und umgekehrt.
- Schlüsselraum – Anzahl möglicher Schlüssel bei einem Verschlüsselungsverfahren:
- Angabe in Binärstellen: 4-Bit: 16 mögliche Schlüssel; 10 Bit: 1024 mögliche Schlüssel.
- Der Schlüsselraum für die Caesar-Verschlüsselung ist 25, also knapp 5 Bit.
- Geheimalphabet – Ordnet die Klartextbuchstaben den Geheimtextbuchstaben zu – gibt es so nur bei der monoalphabetischen Substitution
Caesar-Verschlüsselung (monoalphabetische Substitution)
Die Caesar-Verschlüsselung ist eine sehr einfache Form der monoalphabetischen Substitution. Bei der Substitution werden Buchstaben durch andere Buchstaben ersetzt (lat. substituere = „ersetzen“). Monoalphabetisch ist sie deshalb, weil sie nur ein (mono) Geheim-Alphabet benutzt. Bei der Caesar-Verschlüsselung ergibt sich das Geheimalphabet durch Verschiebung. Ist der Schlüssel 3, so wird jeder Buschstabe um 3 Stellen verschoben: Was im Geheim-Alphabet ein D ist, ist im richtigen Alphabet ein A usw.:
Der Name der Caesar-Verschlüsselung geht auf den römischen Feldherrn Gaius Julius Caesar zurück, der diese Methode zur Verschlüsselung vertaulicher Botschaften benutzte. Sicher ist die Methode heute keineswegs: Am Geheimtext lässt sich anhand von Mustern leicht erkennen, dass es sich um ein Substitutions-Verfahren mit Verschiebung des Alphabets handelt. Und es sind nur 25 verschiedene Schlüssel (Verschiebewerte) möglich. So geht es sehr schnell, diese durchzuprobieren und auf den richtigen Schlüssel zu kommen.
Caesar-Verschlüsselung mit python programmieren
Programmiere einen Verschlüsselsungs-Algorithmus mit python!
Wenn du keine Idee hast, wie das gehen könnte: Lies folgende Schritte genau durch und überlege für jede Code-Zeile, ob du sie verstehst.
Der Output zu den Codebeispielen (zum Beispiel das, was durch die Funktion print()
ausgegeben wird) folgt jeweils auf den Code: Nach >>>
.
Schritt 1 – Klasse String importieren
Wir importieren die Klasse string
für Elemente und Funkionen zu Zeichenketten (Texten).
Die Klasse string
enthält zum Beispiel die feste Zeichenkette ascii_uppercase
:
import string print(string.ascii_uppercase) >>> ABCDEFGHIJKLMNOPQRSTUVWXYZ
Schritt 2 – Position eines bestimmten Buchstabens finden
Die Funktion find()
gibt den Index (= die Position) eines bestimmten Buchstabens innerhalb einer Zeichenkette zurück. Wenn sie den gesuchten Buchstaben nicht findet, gibt sie den Wert -1
zurück.
import string print(string.ascii_uppercase) print(string.ascii_uppercase.find(‘C’)) >>> ABCDEFGHIJKLMNOPQRSTUVWXYZ >>> 2
Schritt 3 – Einen einzelnen Buchstaben verschlüsseln
Einen einzelnen Buchstaben können wir nun wie folgt „verschlüsseln“, also um x Stellen im Alphabet verschieben:
- Index herausfinden (Position dieses Buchstabens im Alphabet, von 0 bis 25).
- Index um Verschiebungswert (Schlüssel) erhöhen.
- Buchstaben ersetzen durch jenen unter neuem Index.
import string key = 5 # Um so viel wird verschoben letter = "A" print(letter) index = string.ascii_uppercase.find(letter) # 1. index = index + key # 2. letter = string.ascii_uppercase[index] # 3. print(letter) >>>A >>>F
Schritt 4 – Eine Zeichenkette verschlüsseln
Um nun eine Zeichenkette (ein Wort oder einen Text) zu verschlüsseln, führen wir die Befehle aus Schritt 3 für jeden Buchstaben der Zeichenkette aus. Dazu verwenden wir eine for-Schleife:
import string key = 5 # Um so viel wird verschoben plainText = “Veni vidi vici” cipherText = “” for letter in plainText.upper(): # für jeden Buchstaben in plainText... index = string.ascii_uppercase.find(letter) index = (index + key) % 26 letter = string.ascii_uppercase[index] cipherText = cipherText + letter print(cipherText) >>> AJSNEANINEANHN
Beachte Folgendes:
- Die Funktion
uppper()
macht aus jedem Buchstaben inplainText
einen Grossbuchstaben. Dadurch enthält die Variableletter
immer einen Grossbuchstaben – egal, ob der Buchstabe inplainText
gross oder klein war. Das ist wichtig, denn in der Zeichenketteascii_uppercase
befinden sich nur Grossbuchstaben und die Funktionfind()
würde darin nichts finden, wennletter
einen Kleinbuchstaben enthielte. - Damit
index
nicht grösser als 25 wird, wird die Addition index + key mit dem Modulo-Operator ergänzt: x modulo 26 (x % 26) gibt den Rest der Division x / 26 zurück: Für alle Werte grösser 26 gibt diese Operation also an, um wieviel grösser der Wert ist. Für index = 22 (Buchstabe 'W') und key = 5 ergäbe sich der Rest 1. Der neue Buchstabe wäre dann 'B' ('A' ist an Position 0). - In der letzten Zeile in der for-Schleife wird jeweils der neue Buchstabe zu der
Zeichenkette
cipherText hinzugefügt.
Aufgabe 1 – Verschlüsselungs-Algorithmus verbessern
Das Programm in Schritt 4 gibt ein Chiffrat ohne Leerschläge aus: Anstelle eines Leerschlags wird jeweils ein 'E' ausgegeben. Das macht Sinn: Wenn find()
ein Zeichen nicht findet, gibt es den Wert -1 zurück. -1 + 5 (Verschiebungswert) ergibt 4 – das ist die Position des Buchstabens E.
- Überlege, welches Chiffrat sich mit anderem Schlüssel (Verschiebungswert) ergäbe. Ändere den Schlüssel entsprechend und überprüfe deine Überlegung.
- Verbessere das Programm so, dass Leerschläge nicht verschoben werden, sodass das Chiffrat an den gleichen Stellen Leerschläge enthält wie der Klartext. Dein Programm soll erst den Klartext, dann das Chiffrat ausgeben.
Aufgabe 2 – Verschlüsselungs-Algorithmus als Funktion
- Schreibe eine Funktion
caesar(plainText, key)
:- Der Funktion übergibt man einen Klartext und den Schlüssel (Verschiebungswert).
- Die Funktion gibt das Chiffrat (den verschlüsselten Text) zurück.
- Leerschläge (Abstände) im Klartext bleiben Leerschläge im Chiffrat.
- Dein Programm soll nun Folgendes tun:
- Einen Schlüssel festlegen.
- Einen Klartext festlegen.
- Das Chiffrat dieses Klartext mit der Funktion caesar() generieren.
- Das Chiffrat ausgeben.
- Nutze die Funktion caesar(), um aus dem Chifrat wieder den Klartext zu generieren. Ergänze dein Programm, sodass es auch noch den dechiffrierten Klartext ausgibt.
Zufällige monoalphabetische Substitution
Eine zufällige monoalphabetische Substitution ist weniger leicht zu knacken als beispielsweise eine Substituion gemäss der Caesar-Methode. Hier wird für jeden Buchstaben eine andere (wenn möglich zufällige) Verschiebung festgelegt. So wird jedem Buchstaben ein anderer zugewiesen. Etwa so:
Wieder entsteht zwar nur ein Geheimalphabet, dieses zu knacken ist aber schwieriger als bei der Caesar-Methode, denn hier gibt es weit mehr mögliche Kombinationen:
“Der erste Buchstabe „A“ kann an eine von 26 möglichen Alphabetpositionen platziert werden. Für den zweiten Buchstaben „B“ gibt es dann noch 25 mögliche Plätze zur Auswahl, für den dritten 24, und so weiter. Insgesamt berechnen sich so 26·25·24·23···4·3·2·1 […] Möglichkeiten zur Verwürfelung des Alphabets. Das sind ungefähr 4·1026 Fälle und entspricht etwa 88 bit.” (wikipedia.org/wiki/Monoalphabetische_Substitution)
Ist die zufällige monoalphabetische Substitution damit sicher? Nein, denn dank der Häufigkeitsanalyse ist auch ein Geheimtext, der nach dieser Methode verschlüsselt wurde, leicht zu knacken:
Häufigkeitsanalsye
Die Häufigkeitsanalsye macht sich zu nutzen, dass die Buchstaben in einer Sprache in einer bestimmten Häufigkeit vorkommen, für einen Text in deutscher Sprache ist die Häufigkeit der einzelnen Buchstaben wie folgt:
Um nun einen Geheimtext zu entschlüsseln, könntest du wie folgt vorgehen:
- Du zählst, wie oft jeder Buchstabe im Geheimtext vorkommt und ordnest die Buchstaben des Geheimtexts nach Häufigkeit.
- Vorausgesetzt du weisst, dass der Klartext in deutscher Sprache verfasst ist, kannst du nun annehmen, dass der häufgiste Buchstaben im Geheimtext wohl einem 'E' im Klartext entspricht, der zweithäufigste einem 'N' usw.
Die Häufigkeiten der Geheimtext-Buchstaben stimmt nicht immer überein mit der Standard-Häufigkeit des entsprechenden Klartext-Buchstabens. Je kürzer der Text, desto eher kann sie abweichen. Klar: Im Text „Anna“ zum Beispiel kommt das 'E' überhaupt nicht vor und hat damit die Häufigkeit 0.
Du kannst diese Entschlüsselungsmethode hier ausprobieren:
- Wähle oben links unter Message
Sample Message (easy)
für die Caesar-Substitution undSample Message (hard)
für die zufällige monoalphabetishe Substitution. Bei letzterer kannst du die Buchstaben erst nach Häufigkeit ordnen und dann einzeln herumschieben.
Vigenère-Verschlüsselung (polyalphabetische Substitution)
Die Vigenère-Chiffre funktioniert ähnlich wie die Caesar-Verschlüsselung; es wird aber nicht jeder Buchstabe um eine feste Anzahl Stellen verschoben. Der Verschiebungswert ändert sich fortlaufend, abhängig von einem Schlüsselwort. Anders als bei der monoalphabetischen Subsitution wird hier also nicht jedem Klartext-Buchstaben ein Geheimtext-Buchstabe zugeordnet. Stattdessen hängt der Geheimtext-Buchstabe von der Kombination aus Schlüsselwort- und Klartextbuchstabe ab. Dadurch entsteht nicht ein Geheimalphabet, sondern mehrere: Je nach Kombination, können für den Klartext-Buchstaben 'A' verschiedene Geheimtextbuchstaben entstehen.
Für den Text »Als Anna abends ass, ass Anna abends Ananas« mit dem Schlüsselwort FISCHERSFRITZ
geht die Vigenère-Verschlüsselung wie folgt:
Klartext | A | L | S | A | N | N | A | A | B | E | N | D | S | A | S | S |
Position K | 0 | 11 | 18 | 0 | 13 | 13 | 0 | 0 | 1 | 4 | 13 | 3 | 18 | 0 | 18 | 18 |
Schlüsselwort | F | I | S | C | H | E | R | S | F | R | I | T | Z | F | I | S |
Position S | 5 | 8 | 18 | 2 | 7 | 4 | 17 | 18 | 5 | 17 | 8 | 19 | 25 | 5 | 8 | 18 |
Geheimtext | F | T | K | C | U | R | R | S | G | V | V | W | R | F | A | K |
Position G | 5 | 19 | 10 | 2 | 20 | 17 | 17 | 18 | 6 | 21 | 21 | 22 | 17 | 5 | 0 | 10 |
Beachte:
- Das Schlüsselwort wird ständig wiederholt (sofern es, wie üblich, kürzer ist als der Klartext).
- Unter jeder Textzeile ist die Position der jeweiligen Buchstaben im Alphabet angegeben:
- Die Modulo-Addition von Position K und Position S ergibt Position G (
G = (K+S) % 26
)
- Das Muster im Klartext ist, anders als bei der Caesar-Verschlüsselung, im Geheimtext nicht mehr erkennbar.
One-Time-Pad (OTP)
Ist die Vigenère-Verschlüsselung sicher? Das hängt von der Länge und Zufälligkeit des Schlüsselwortes ab: kurze, einfach zu merkende Schlüsselwörter wie etwa “geheim” sind relativ unsicher; längere und zufälligere wie “wpfuVNaubLdshkYs” sind sicherer.
Als nicht-knackbar gilt das one-time-pad (OTP), eine Einmalverschlüsselung, bei der das Schlüsselwort mindestens so lange wie der Klartext selbst und die eben nur ein einziges mal verwendet wird.
Auch das Vigenère-Verfahren (mit wiederholt verwendeten Schlüsselwörtern) gilt angesichts heutiger Entschlüsselungsmethoden als unsicher.
Vigenère-Verschlüsselung in python programmieren
Aufgabe 3 – Konzept
Die Funktion vigenere(message, key_word)
soll wie folgt funktionieren:
- Der Funktion übergibt man als Argumente die Nachricht (Klartext) und das Schlüsselwort.
- Die Funktion gibt den verschlüsselten Text zurück.
- Leerschläge und Satzzeichen sollen nicht verschlüsselt werden.
- Erstelle eine neue python-Datei.
- Kopiere deine Funktion
caesar(plainText, key)
und füge sie in die neue Datei ein. - Welche Änderungen bzw. Ergänzungen musst du an der Caesar-Funktion vornehmen, damit sie zur Vigenere-Funktion wird und obige Anforderungen erfüllt? Notiere deine Ideen als Kommentare im Code.
Aufgabe 4A – Vigenère-Funktion schreiben
Schreibe die Funktion vigenere(message, key_word)
. Beachte die Überlegungen aus Aufgabe 3 und wenn nötig die Tipps.
Aufgabe 4B – Vigenère-Funktion erweitern
Erweitere die Funktion um ein drittes Argument namens encrypt
: vigenere(message, key_word, encrypt)
.
- Wenn
encrypt
= 1 ist, soll die Funktion verschlüsseln, wenencrypt
= -1 ist, soll sie entschlüsseln. - Hierzu könnte
encrypt
einfach als Faktor verwendet werden, dann bräuchte es keine if-Abfrage.
Aufgabe 5 – Vigenère-Funktion testen
Teste deine (erweiterte) Vigenere-Funktion mit folgendem Code:
keyWord = "FischersFritz" cipherText = vigenere("Als Anna abends ass, ass Anna abends Ananas", keyWord, 1) print(cipherText) print(vigenere(cipherText, keyWord, -1))
Prüfe, ob dein Programm Folgendes ausgibt. Falls nicht, musst du noch Änderungen vornehmen.
>>> FTK CURR SGVVWR FAK, CZW RFSR IUDSLK CUEESX >>> ALS ANNA ABENDS ASS, ASS ANNA ABENDS ANANAS
Aufgabe 5plus – Vigenère-Funktion anwenden (2er-Gruppen)
Stellt euch gegenseitig verschlüsselte Rechenaufgaben in Textform, zum Beispiel „HUNDERTACHTUNDVIERZIG DURCH VIER“:
- Notiere eine Rechenaufgabe in Textform und verschlüssele sie mit einem beliebigen Schlüssel.
- Sende deiner Mitschüler:in die verschlüsselte Aufgabe und den Schlüssel.
- Dein:e Mitschüler:in muss die Aufgabe entschlüsseln und dir anschliessend die Lösung sagen oder zurücksenden.
Moderne Verschlüsselung
Dieser Abschnitt behandelt hauptsächlich die XOR-Verschlüsselung. Sie ist eines der einfachsten Beispiele moderner symmetrischer Verschlüsselungs-Verfahren. Moderne Verfahren verschlüsseln nicht gedruckte oder handgeschriebene Texte, sondern digitale Daten (Texte, Bilder, Audio-Dateien, Videos, Code). Eine Verschlüsselung über die Alphabet-Nummerierung macht wenig Sinn, denn:
- Jedes digitale Zeichen ist bereits eine Nummer; jedes Schrift- oder Codezeichen, jedes Pixel eines Bildes kommt durch eine Folge von Einsen und Nullen zustande.
- Der Buchstabe ‘A’ entspricht in der ASCII-Codierung der Binärzahl
100’0001
- Ein Pixel dieser Farbe entspricht in 8-Bit-RGB-Codierung der Binärzahl
1110’1101 0001’1100 0010’0100
Also kann die moderne Verschlüsselung bei den Einsen und Nullen ansetzen.
ASCII-Code
Der American Standard Code for Information Interchange wurde bereits 1963 veröffentlicht und dient, wie es der Name sagt, dem Austausch von Informationen. Die Idee ist klar: Wenn man schon in der Lage ist, Einsen und Nullen über Kupferleitungen hin- und her zu schicken, wäre es noch praktisch, auf diese Weise auch Information, also Text, auszutauschen. Dazu muss man sich einigen, welche Binährzahl welchem Text-Zeichen entspricht. Genau das macht der ASCII-Code:
In obenstehender Tabelle kann für jedes Zeichen die entsprechende Binärzahl (von links nach rechts) gelesen werden, indem man erst die Zahlenfolge der Spalte, dann jene der Zeile liest:
- Für den Buchstaben A ergibt sich die Binärzahl
100’0001
(Dezimal: 65) - Für den Buchstaben Z ergibt sich die Binärzahl
101’1010
(Dezimal: 90)
Der alte ASCII-Code weist nur 7 Bit auf, kann also maximal 128 Zeichen speichern. Er wurde mittlerweile vom UniCode-Standard abgelöst, damit auch Schriftzeichen anderer Sprachen Platz haben. Die Gross- und Kleinbuchstaben von A…Z haben auch im UniCode dieselben Nummern wie im ASCII-Code. So gesehen ist der ASCII-Code immer noch gültig.
XOR
XOR steht für Exclusive OR, also „Exklusives ODER“, und ist eine logische Verknüpfung. Logische Verknüpfungen finden wir auch in unserer Sprache:
- Das ODER im Satz: „Ich ziehe eine Jacke an, wenn es windet oder wenn es regnet“ ist ein normales ODER. Das Resultat (Jacke an) ist wahr, wenn die erste Bedingung (es windet) wahr ist oder dann, wenn die zweite Bedingung wahr ist (es regnet) – aber auch dann, wenn beide Bedingungen wahr sind und es sowohl windet als auch regnet.
- Das ODER im Satz: „Ich bin draussen, wenn ich durch die vordere oder durch die hintere Haustüre gegangen bin“ hingegen ist ein exklusives ODER. Denn ich kann nicht sowohl durch die vordere als auch durch die hintere Türen rausgegangen sein (wenn ich beide Türen passiere, bin ich wieder drin).
Wenn wir 0
als falsch und 1
als wahr ansehen, ergeben sich für ODER und für XOR folgende Wahrheitstabellen:
Beachte für die XOR-Wahrheitstabelle:
- Wenn
A
undB
gleich sind, ist dasResultat
0, wenn sie verschieden sind, ist das Resultat 1 - Die Operation funktioniert auch rückwärts:
Resultat
XORB
ergibtA
! - Deshalb eignet sich die XOR-Operation für eine symmetrische Verschlüsselung!
ASCII-Codes mit XOR verschlüsseln
Wenn wir XOR als logischen Operator verwenden, können wir damit Kombinationen von Nullen und Einsen verschlüsseln. Wir können sagen: Geheimtext = Klartext XOR Schlüsselwort. Folgend wird der erste Buchstabe des Klartexts mit dem ersten Buchstaben des Schlüsselworts „verXORt“ (=mit dem XOR-Operator verrechnet):
- Klartext: Aschenputtel, erster Buchstabe A hat ASCII-Code
100’0001
(= 65), - Schlüsselwort: Wolf, erster Buchstabe W hat ASCII-Code
101’0111
(= 87):
Die XOR-Operation ergibt 001’0110
(= 22). Dieser Zahl entspricht im ASCII-Code kein Buchstabe, sondern ein Steuerzeichen. Wenn es als Text angezeigt wird, sieht es vielleicht so aus: ‘<‘.
Die Verschlüsselung geht auch rückwärts: ‘<‘ XOR ‘W’ = ‘A’
Mit dieser Verschlüsselungsmethode können alle Binärzahlen und damit Daten in digitaler Form (Text, Videos, Fotos, etc.) verschlüsselt werden!
Aufgabe 6 – Geheimtext von Hand entschlüsseln
Gegeben ist folgender Geheimtext: 7 42 32 60
. Die ASCII-Codes sind hier als Dezimalzahlen angegeben. Das Schlüsselwort heisst WOLF
.
- Schreibe die Dezimalzahlen als 7-stellige Binärzahlen nebeneinander auf ein Blatt Papier. Wenn möglich ohne Taschenrechner.
- Schreibe unter die vier Binärzahlen die ASCII-Codes für die vier Buchstaben des Schlüsselworts. Dazu benutzt du die ASCII-Tabelle.
- Führe die XOR-Operation Bit-für-Bit für jedes Binärzahl-Paar durch. So erhältst du die Binärzahlen des Klartexts.
- Mit der ASCII-Tabelle kannst du nun die Binärzahlen in Buchstaben wandeln und erhälst den Klartext.
Aufgabe 7 – XOR-Verschlüsselung in python programmieren
Schreibe eine Funktion crypt_xor(message_in, key_word)
:
- Der Funktion übergibt man die Nachricht und das Schlüsselwort.
- Die Funktion gibt den ver- bzw. entschlüsselten Text zurück.
- Auch Satzzeichen und Leerschläge werden verschlüsselt.
Du kannst von der Vigenère-Funktion ausgehen, welche ebenfalls ein Schlüsselwort benutzt, das stets wiederholt wird. Überlege erst, welche Code-Zeilen du von der Vigenère-Funktion, die ja das Alphabet benutzt, nicht mehr brauchst. Beachte Folgendes:
- Die Funktion
ord()
gibt den ASCII-Code eines Zeichens zurück:ord('A')
gibt65
zurück. - Die Funktion
chr()
gibt das Zeichen eines ASCII-Codes zurück:chr(65)
gibt'A'
zurück. - Der XOR-Operator in python ist ein
^
(auf deiner Tastatur rechts neben dem Fragezeichen):
Aufgabe 8 – Funktion cryptXOR testen
Teste deine Funktion mit folgendem Code:
key = "WOLF" cipher = crypt_xor("Nur ein garstiges Aschenputtel ist noch da. Das sitzt unten in der Asche, dem kann der Pantoffel nicht passen!", key) print(cipher) print(crypt_xor(cipher, key))
Prüfe, ob dein Programm funktioniert: Die erste Ausgabezeile kann von der untenstehenden abweichen, die zweite aber sollte den Klartext 1:1 wiedergeben.
>>>:>f2&"f0.>5#&+#$o >>> 54')(':822#l/$;l(8,$f3.bf.?f$&8<#o9(#*"f>!l"2=l$,$#{o(#:o''9!l"2=l6!8)1))*w!%%?;l66<?#9n >>> Nur ein garstiges Aschenputtel ist noch da. Das sitzt unten in der Asche, dem kann der Pantoffel nicht passen!