Kryptologie

Dies ist eine alte Version des Dokuments!

Die Kryptologie ist die Wissenschaft (bzw. die Kunst), eine Nachricht mit meist geheimem Inhalt an einen Empfänger zu senden, sodass sie von Unbefugten nicht gelesen werden kann. Die Geschichte der Kryptologie verläuft fast parallel zur Entwicklung der Schrift, denn seit jeher hatten die Menschen das Bedürfnis, Nachrichten geheim zu halten.
Etliche Menschenschicksale und sogar der Ausgang von Kriegen wurden direkt beeinflusst durch die Qualität einer guten Verschlüsselung, bzw. durch die Möglichkeit, geheime Botschaften zu entschlüsseln. In der Kryptologie geht es um zwei Hauptprinzipien:

Steganografie: das Verbergen von Informationen. Eine Nachricht wird „versteckt“, sodass Dritte überhaupt nichts von der Nachrichtenübergabe bemerkt.
Kryptografie: das Verschlüsseln einer codierten Nachricht. Eine Nachricht wird verschlüsselt, sodass sie für Drittpersonen ohne Schlüssel nutzlos ist.
Als Kryptoanalyse bezeichnet man das Gebiet, welches darauf abzielt, eine geheime Botschaft zu knacken, d.h. zu entschlüsseln.

Abbildung 1: Sender und Empfänger - oft Alice und Bob genannt, und dazwischen der unbefugte „Mithörer“ namens Mallory. Quelle: Wikipedia

Abbildung 2: Überblick der Kryptologie

Das Verbergen von Informationen hat eine lange und oft sehr spannende Geschichte. Hier sind nur einige Beispiele der „Kunst des Versteckens“ von Nachrichten erwähnt.

Abbildung: In diesem Bild ist eine Nachricht versteckt, wo genau?

Die Nachricht unter dem Wachs

Die Kunst, eine Nachricht zu verbergen, sodass sie nur durch den designierten Empfänger gelesen wird, würde eine eigene Abhandlung füllen. Bereits in den Schriften von Herodot finden sich Beispiele von Steganografie. So soll beispielsweise der ins Exil verbannte Grieche Demaratos um 480 v.Chr. seine Landsleute vor der Invasion der Perser gewarnt haben, indem er das Wachs einer Schreibtafel entfernte und seine Nachricht auf das darunter liegende Holz kratzte. Danach erneuerte er die Wachsschicht der Schreibtafel und sandte sie den Griechen. Dadurch, dass die Schreibtafel leer war, passierte sie die persische Zensur und die Griechen waren vom Angriff des damaligen Perserkönigs Xerxes gewarnt.

Abbildung: Nachbildung einer röm. Wachstafel. Quelle: Wikipedia

Die Nachricht im rohen Ei

Bereits im 15. Jahrhundert war bekannt, wie man eine Nachricht in einem Ei verstecken kann. Das Ei zuerst mindestens einige Stunden in Essig eingelegt werden. Sobald die Eierschale aufgeweicht ist, wird in die Schale mit einem Messer ein kleiner Schlitz eingebracht. In diesen lässt sich dann ein möglichst eng gefaltetes Papierstück mit einer in Eisengallustinte geschriebene Botschaft in das Ei stecken. Das anschliessende Wasserbad härtet die Schale wieder.

<html> <center></html> Quelle:Deutsches Spionagemuseum. <html> </center></html>

Die Nachricht im Mikrofilm

Im zweiten Weltkrieg wurde häufig eine geheime Botschaft der Länge einer Textseite per Mikrofilm auf die Grösse eines kleinen Punktes verkleinert, welcher dann in einem scheinbar harmlosen Brief als Satzzeichen auftauchte oder an einem kleinen Ort in einen Alltagsgegenstand eingepackt bzw. eingebaut werden konnte. Siehe Film von Minute 12:15 bis 13.00.

Die Steganografie hat den Nachteil, dass die Nachricht sofort offen liegt, wenn die Botschaft abgefangen bzw. gefunden wird, die Nachricht wird ja nur gut versteckt.
Daher wurde nicht nur die Nachricht versteckt, sondern auch begonnen, diese je länger je stärker zu verschlüsseln.
Jedesmal wenn eine Geheimschrift entwickelt wurde, gab es bald darauf Kryptoanalythiker, die diese Nachricht entziffern wollten. Sie entwickelten Verfahren und Methoden, die das Knacken der Verschlüsselung möglich machten. Dadurch war das angewandte Chiffrierungsverfahren wertlos und eine neue Verschlüsselungsmethode musste gefunden werden.
Dieses Prinzip der Entwicklung von Chiffrierverfahren und bald darauf der Entwicklung von Krypto-Algorithmen zum Knacken dieser Verschlüsselungen zieht sich über Jahrhunderte bis in die Gegenwart.

In der Kryptografie geht es jeweils darum, eine Nachricht, die in Klartext (K) vorliegt, zu verschlüsseln. Es resultiert ein Geheimtext (G), der im Optimalfall nur vom Empfänger wieder in den Originalzustand (K) überführt werden kann.
Die Ausdrücke verschlüsseln, codieren und chiffrieren werden hier als Synonyme verwendet.

https://info-bw.de/_media/faecher:informatik:oberstufe:kryptographie:einfuehrung:substitution:konzepte_und_fs.drawio.png| Verschluesselung

Grundsätzlich werden beim Verschlüsseln (genauer gesagt beim Chiffrieren von Buchstaben) zwei Methoden unterschieden:

die Transposition
die Substitution

Die Buchstaben bleiben was sie sind, aber nicht wo sie sind.
Wird ein Text durch ein Transpositionsverfahren verschlüsselt, so werden die Buchstaben untereinander vertauscht, ohne dass sie sich selbst ändern, wodurch die Nachricht unkenntlich wird. Beim Knacken resp. decodieren der Botschaft geht es dann darum, die ursprüngliche Reihenfolge der Buchstaben wieder herzustellen. Transpositionsalgorithmen werden hier nicht im Detail behandelt. Dennoch sollen hier zwei Beispiele angeführt werden.
In der Transposition ist oft kein Schlüssel im eigentlichen Sinne nötig, jedoch sind oft Zusatzinformationen nützlich, um die Nachricht einfach und zuverlässig entschlüsseln zu können, diese also nicht knacken zu müssen.

A: „Gartenzaun-Transposition“

Die sogenannte „Gartenzaun-Transposition“ wird z.T. bereits von Schulkindern verwendet. Dabei wird ein Klartext K auf zwei (oder mehr) Linien verteilt, wobei immer abwechslungsweise ein Buchstabe des Textes auf die erste und ein Buchstabe auf die zweite Linie geschrieben wird. Der Geheimtext G entsteht dann dadurch, dass man die Buchstaben der zweiten Linie an die erste Linie anfügt. Leerzeichen werden weggelassen.
Der „Schlüssel“ hier ist, dass der Sender und der Empfänger abmachen, auf wie viele Zeilen sie die Nachricht verteilen, um anschliessend anders zusammenzufügen.

"Wir sind Lernende des Kollegiums"

wird durch die „Gartenzaun-Transposition“ verschlüsselt:

W r i d e n n e e K l e i m
 i s n L r e d d s o l g u s

und daraus ergibt sich der Geheimtext G:

WridenneeKleimisnLreddsolgus

Aufgabe: Verschlüsseln und entschlüsseln mit der „Gartenzaun-Transposition“
Arbeiten Sie zu zweit. Verschlüsseln Sie jeweils einen kurzen selbst gewählten Satz. Tauschen Sie untereinander die Zettel und entschlüsseln Sie die Nachricht des anderen! Für jene, die die Sache schwieriger machen wollen, verschlüsseln Sie die Nachricht auf mehr als 2 Zeilen, behalten Sie die Anzahl Zeilen aber für sich…Wie muss Ihr Gegenüber vorgehen, um diese Nachricht zu entschlüsseln?

Es gibt natürlich unzählige Varianten dieser einfachen Transpositionsverschlüsselung. So könnte man z.B. zusätzlich jeweils den ersten mit dem zweiten Buchstaben vertauschen, bevor man die „Gartenzaun-Transposition“ anwendet etc.

B: Skytale
Die Skytale ist das erste bekannte Kryptografieverfahren, welches militärisch Verwendung fand. Dieses Verfahren wurde bereits im 5. Jahrhundert n.Chr. durch die Spartaner benutzt. Für die Verschlüsselung wird lediglich ein (kantiger) Holzstab verwendet, um welchen ein Streifen Papier (damals Paier oder auch Leder) gewickelt wird. Die Nachricht wird nun der Länge nach auf den Stab, quer über die Streifen geschrieben, sodass die Buchstaben beim Lösen des Pergaments anscheinend sinnlos aneinandergereiht sind. Für das Entschlüsseln der Botschaft benötigt man lediglich einen Stab mit derselben Kantenzahl und Grösse, auf welchen der Pergamentstreifen aufgerollt auf gleiche Weise aufgerollt werden kann und so die Botschaft „quer“ über die Streifen gelesen sichtbar wird.

Abbildung: Skytale mit ledernem Band und der geheimen Botschaft. Quelle

Aufgaben: Verschlüsseln und entschlüsseln mit der Stytale

Beschreiben Sie, wie eine Nachricht entschlüsselt werden kann, wenn man den Holzstab nicht zur Hand hat. Beispiele liegen bereit!
Wie sicher schätzen Sie eine Nachricht, die nach diesen Prinzipien chiffriert wurde?

C: Schablonen
Die Fleissner Schablonen (Nach Eduard Fleissner von Wostrowitz benannt) ist eine Quadratische Schablone (meist aus Karton), mit mehreren kleineren quadratischen Löchern. Die Schablone wird auf ein Papier gelegt. Jeder Buchstabe des Klartextes wird der Reihenfolge nach in ein Quadratloch eingetragen. Sobald alle Löcher beschrieben sind, wird die Schablone um neunzig Grad gedreht und die folgenden Buchstaben werden in die Lücken eingetragen. Die Schablone wird drei mal gedreht, es werden somit viermal Buchstaben in die Löcher geschrieben. Sind nicht alle Stellen in im quadratisch angeordneten Geheimtext gefüllt, werden diese mit willkürlich gewählten Buchstaben gefüllt. Für längere Nachrichten ist ein zweites Quadrat (ein Neuanfang) nötig. Quelle

Abbildung: Fleissner Schablone zum Verschlüsseln einer Botschaft über das Drehen der Schablone (3 mal um 90 Grad) und füllen der Löcher durch die Botschaft Quelle

Aufgaben: Verschlüsseln und entschlüsseln mit einer Schablone

Arbeiten Sie zu zweit. Verschlüsseln Sie jeweils einen kurzen selbst gewählten Satz. Schablonen liegen bereit. Tauschen Sie untereinander die Zettel und entschlüsseln Sie die Nachricht des anderen!
Fragen zur Schablone:
1. Wie dürfen die Löcher nicht angeordnet sein?
2. Wie viele darf die Schablone der Kante nach haben, um kein leeres Kästen in der Mitte zu erhalten, welches dann mit einem willkürlich gewählten Buchstaben gefüllt werden muss?
3. Wieviele Löcher musst du ausschneiden, damit nach drei Drehungen alle Kästchen komplett mit Buchstaben ausgefüllt sind?
4. Warum ist dieses Verschlüsselungsverfahren, gleich wie die „Gartenzaun-Transposition“ oder das Skytale nicht sicher?
Eine Nachricht wurde verschlüsselt, Eine Ecke der Schablone ist allerdings beschädigt. Wie gehen Sie vor, um die Nachricht zu entschlüsseln? Welche wichtigen Überlegungen (Argumente) sind hier zu nennen? Quelle

Die Buchstaben bleiben wo sie sind, aber nicht was sie sind.
Was könnte hinter folgenden Zeichen stecken?

Bei diesem ersten Beispiel wurde die Nachricht durch ein so genanntes Substitutionsverfahren verschlüsselt. Der Schlüssel ist ein allgemein bekannter Code.

Im Gegensatz zur Transposition, bei welcher jeder Buchstabe seine Position ändert, behält bei der Substitution jeder Buchstabe seine Stelle bei. Was die Nachricht unleserlich macht, ist die Tatsache, dass die Buchstaben selbst ihre Gestalt ändern.
Eine weitere geheime Botschaft ist hier notiert. Welche Botschaft könnte hier versteckt sein.

Tipp

Die Substitutionsverschlüsselung kann entweder monoalphabetisch (sich dem gleichen Alphabet bedienend) oder polyalphabetisch (für jeden zu verschlüsselnden Buchstaben ein neues Alphabet nutzen) sein.

Allgemeine monoalphabetische Verschlüsselung

„Monoalphabetisch“ wird ein Verschlüsselungsalgorithmus genannt, wenn das Geheimalphabet im Verlaufe der Verschlüsselung gleich bleibt. So wird z.B. ein A immer in ein f verwandelt, ein P immer in ein z etc.
Beispiel:
Eine einfache monoalphabetische Verschlüsselung wäre z.B. durch folgende Tabelle gegeben:

Verschlüsselungstabelle 1

Klar	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
Geheim	f	o	b	t	h	x	n	y	i	a	s	g	l	d	u	z	m	v	p	j	e	w	q	c	r	k

So würde die Nachricht

"Ich kenne das Geheimnis"

anhand dieser Tabelle verschlüsselt zu

iby shiddh tfp nhyhildip

Bei dieser Verschlüsselung reicht es Eve (der Angreiferin bzw. Kryptoanalytikerin) nicht aus, zu wissen, was der Verschlüsselungsalgorithmus war, es muss auch der Schlüssel, die Zuordnungstabelle oder ein Stück Klartext vorhanden sein. Verallgemeinert kann diese Überlegung werden durch die Maxime von Kerckoff.

Der holländische Kryptograph (Jean Guillaume Hubert Victor François Alexandre) Auguste Kerckhoffs stellte 1883 eine bis heute unbestrittene Maxime (ein Prinzip) auf:
„Die Sicherheit eines Kryptosystems darf nicht von der Geheimhaltung des Algorithmus¹⁾ abhängen. Die Sicherheit gründet sich nur auf die Geheimhaltung des Schlüssels“
(A. Kerckhoffs, zitiert aus Simon Singh, 2000).
^{1)Algorithmus: eindeutige Handlungsvorschrift zur Lösung eines Problems}

Abbildung: A. Kerckoff, Quelle: Wikipedia]]

Der konkrete Schlüssel ist in unserem Fall durch die Verschlüsselungstabelle 1 von oben gegeben, durch welche die Verschlüsselung definiert ist. Dieser Schlüssel muss unbedingt geheim bleiben. Er dient zusammen mit dem Algorithmus dem Sender und dem Empfänger dazu, die Nachricht zu ver- bzw. entschlüsseln.

Die Maxime von Kerckhoffs ist recht einleuchtend, denn die verschiedenen Möglichkeiten, wie man eine Nachricht verschlüsseln kann, sind jeweils recht begrenzt und neue Dechiffrier-Chiffrier-Algorithmen sprachen und sprechen sich recht schnell herum. Ein gutes Verschlüsselungsverfahren verdient diese Auszeichnung nur dann, wenn man die Nachricht nicht entschlüsseln kann, auch wenn man weiss, nach welchem Prinzip sie verschlüsselt wurde.

ENIGMA und die Schlüssel

Die Sicherheit und Geheimhaltung eines Schlüssels war vor allem in Kriegen von grosser Bedeutung. Als Beispiel sei hier die Verschlüsselungsmaschine der Deutschen im zweiten Weltkrieg namens ENIGMA genannt. Diese hatte den Ruf, unknackbar zu sein.
Die ENIGMA war so etwas wie eine elektrische „Verschlüsselungsschreibmaschine“. Diese hatte ein sog. Schlüsselbuch für die genaue Einstellung der Maschine, um die Nachricht zu verschlüsseln. Dies war der erste Schlüssel. Danach wurde aber die Nachricht ein zweites Mal verschlüsselt, entweder mit einem „Tagesschlüssel“, welcher täglich gewechselt wurde, oder gar eines für jede Nachricht wechselnden Nachrichtenschlüssels.
Übringens: Neben viel Wissen in Mathematik, Kreativität und Spionen gelang das Knacken der chiffrierten Nachrichten der Deutschen den Briten aber doch, nicht zuletzt durch Alan Turing, dem eigentlichen „Erfinder“ des ersten Computers.

Abbildung: Enigma Quelle:

Für unser Beispiel scheint dies (zumindest nach unserem aktuellen Wissensstand) gewährleistet zu sein. Auch wenn man weiss, dass für jeden Buchstaben im Klartext einfach ein anderer Buchstabe des gleichen Alphabets anhand der Verschlüsselungstabelle zugenordet wurde, scheint es fast unmöglich, den Text zu entschlüsseln. Wer allerdings im Besitz des Schlüssels (der Verschlüsselungstabelle) ist, kann kinderleicht entschlüsseln.

Aufgaben Schlüssel-Überlegungen

Wie viele verschiedene Schlüssel gibt es bei der Monoalphabetischen Verschlüsselung, wenn für den gesamten Geheimtext der gleiche Schlüssel gebraucht wird?
„Wenn für die Botschaft mehrere Schlüssel verwendet werden, und zwischen diesen immer gewechselt wird, dann wird der Text viel sicherer, als wenn für die gesamte Botschaft nur ein Schlüssel (eine Schlüsseltabelle) verwendet wird.“ Nehmen Sie Stellung zu der Aussage. Machen Sie auch ein Beispiel.

Caesar Verschlüsselung
Ein Spezialfall der monoalphabetischen Verschlüsselung (für militärische Zwecke), wurde zum ersten Mal von Julius Caesar im Gallischen Krieg erwähnt. Caesar schrieb an Stelle des Klartextbuchstabens jeweils den Buchstaben, welcher im Alphabet drei Stellen weiter steht.

Verschlüsselungstabelle 2

Klar	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
Geheim	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	z	a	b	c

Beispiel:

"Wir sind Lernende des Kollegiums"

wird durch die Caesar Verschlüsselung (Verschiebung 3) chiffriert:

Zlu vlqg Ohuqhqgh ghv Nroohjlxpv

Natürlich kann man die Verschiebung des Geheimalphabetes beliebig verändern. Bei dieser Verschiebung des Alphabets bleibt jedoch die Reihenfolge der Buchstaben im Klartextalphabet und im Geheimalphabet gleich.

Aufgabe: Verschlüsseln und entschlüsseln wie Caesar

Verschlüsseln Sie einen kurzen Text in Caesarverschlüsselung mit einer Verschiebung ihrer Wahl. Tauschen Sie die Nachrichten, ohne dabei die Verschiebung mitzugeben.
Wie viele verschiedene Schlüssel gibt es für die Caesar-Verschiebung?
Welche Schwachstellen offenbart sich bei diesem Verfahren (vergl. Kerckhoff’s Maxime)?

Es gibt noch viele andere monoalphabetische Verschlüsselungsverfahren, welche hier genannt werden könnten. Die Gemeinsamkeit dieser Verfahren ist jedoch, dass diese allesamt durch starke Kryptoanalysealgorithmen geknackt werden können.

Kryptoanalyse: Knacken monoalphabetischer Texte

Lange Zeit galt ein monoalphabetisch verschlüsselter Text als unknackbar, denn es war schlicht unmöglich, die riesige Anzahl von verschiedenen Schlüsseln durchzuprobieren, bis man zufällig auf den Richtigen stiess.
Doch schliesslich entdeckte man in Arabien im neunten Jahrhundert eine Möglichkeit, wie man derartige Texte entschlüsseln konnte, während es in Europa noch einige hundert Jahre dauern sollte.

AUFGABE: Kryptoanalyse, wie die Chiffre geknackt wird
Die unten abgedruckte Chiffre soll entschlüsselt werden. Es handelt sich um eine Substitution. » Nutzen Sie das Tool.

bdgtsbbpzdgongyztbesnpevwkazgynprnysbetskvnskuzsnyuqnwpkgzcbnwpnptncvcnpasouqancfqocjmbwnunpgsprnycbwnunpsprfwnyvwkzprnplsprnpzctzbzwysnunyknunpwouqnwpkhnylwpnfnynccunwbnzcctnenwnycnrzbspcnypngonpzorwnpbczkqycbvnwcrnpzubdgwnrrnyuqnwpkebwnunpgsprnycbwnunpsprfwnyvwkrnylqnpwkwprnytsnecnfqybczprbczprnztbmyzdgfqpnwpnoetskvnskrzbrwnhntcesnywoonyfnyznprnycnuqnwpkgzccnrzbmyqrslcwqpbnprnzsekysprozpkntprnypzdgeyzknunynwcbfqyrynwazgynpzpknlsnprwkcwpbknbzocbcnttcnuqnwpksnunyczsbnpresnpegsprnycninomtzynrnbywnbnpetwnknybgnyrwnzwytwpnbvwngnpwpvhwbdgnpltnwpnynsprbmzybzonynozbdgwpnpowcvhnwbczccfwnycywnuhnylnpfqyrnynwpbckyqnbbcnmzbbzkwnyancrnyhntcgzccnbnwpnpaspkenypetskwopnspsprbndgvwkzubqtfwnycysprnwpazgybmzncnykwpkrzbnybcnninomtzyunwrnyrzoztwknpsbetskknbnttbdgzecmzpzowprnptwpwnprwnpbcowcrnyasnpkbcnpfzywzpcnbwnunpgsprnycbwnunpsprfwnyvwkbcywdgzdgcrwnsnunynwptznpknynbqunyrndlpnsncyzketzndgnpbqhwnbmzybzonyncywnuhnylnfnyesnkcsprmtzcvesnyongyztbbndgbgsprnycmzbbzkwnynuwncnclqppcnuqnwpkzunypsypqdgunwhnpwknpzwytwpnbmsplcnpwpvhwbdgnpbncvnprwnonwbcnpetskknbnttbdgzecnpzsernytzpkbcyndlnzsepwdgckzpvbqkyqbbnoqrnttnvstncvchsyrnrwnbwnunpgsprnycbwnunpsprfwnyvwkmyzlcwbdgpsypqdgztbeyzdgcfnybwqpmyqrsvwnyc

zu verstecken Schlüssel zudrnekgwaltopqmxybcsfhijv
Text: https://www.freiburger-nachrichten.ch/koenigin-der-luefte-boeing-uebergibt-letzten-jumbo-jet-747/

schlussnachmehralsfuenfzigjahrenderusflugzeugbauerboeinghatseinenletztenjumbojetvomtypsiebenhundertsiebenundvierzigandenkundenatlasairuebergebenimboeingwerkineverettbeiseattlefeiertedasunternehmenamdienstagortszeitdenabschiedderboeingfsiebenhundertsiebenundvierzigderköniginderlueftevorstandstandealsprachvoneinemflugzeugdasdieweltfuerimmerveraenderteboeinghattedasproduktionsendeaufgrundmangelndernachfragebereitsvordreijahrenangekuendigtinsgesamtstellteboeinguebertausendfuenfhundertexemplaredesriesenfliegersherdieairlineszieheninzwischenkleinereundsparsameremaschinenmitzweistattviertriebwerkenvordereinstgrösstepassagierjetderwelthatteseinenjungfernflugimneunundsechzigabsolviertrundeinjahrspaetergingdasersteexemplarbeiderdamaligenusfluggesellschaftpanamindenliniendienstmitderjuengstenvariantesiebenhundertsiebenundvierzigstrichachtdieuebereinlaengeresoberdeckneuetragflaechensowiesparsameretriebwerkeverfuegtundplatzfuermehralssechshundertpassagierebietetkonnteboeingabernurnochbeiwenigenairlinespunkteninzwischensetzendiemeistenfluggesellschaftenaufderlangstreckeaufnichtganzsogrossemodellezuletztwurdediesiebenhundertsiebenundvierzigpraktischnurnochalsfrachtversionproduziert bis hier

Al-Kindi (800 n. Chr. Kufa im heutigen Irak), der als „Philosoph der Araber“ bekannte Gelehrte, welcher über 290 Bücher über jegliche Wissenschaften veröffentlichte, war der Erste, welcher die Gedankengänge aufzeichnete, die zum Entschlüsseln eines monoalphabetisch chiffrierten Textes nötig sind.
Er stellte fest, dass im Arabischen die Buchstaben „a“ und „l“ sehr häufig vorkommen, während der Buchstabe „j“ zehn mal weniger häufig auftaucht. Ist ein Geheimtext genügend lang, so wird sich nach dem Gesetz der grossen Zahlen die Häufigkeit der einzelnen Buchstaben der allgemein in der jeweiligen Sprache vorhandenen Häufigkeit annähern. So werden bei einem arabischen Text die zwei Symbole, welche am häufigsten vorkommen, mit grösster Wahrscheinlichkeit für die Buchstaben „a“ und „l“ stehen.
Verfeinert man diese Überlegungen, so muss man nicht alle möglichen Schlüssel durchprobieren, sondern man kann mit Hilfe von logischen Schlussfolgerungen den Text knacken, sogar bei unbekannter Sprache kann diese Häufigkeitsanalyse wertvolle Hinweise liefern.
Dies soll anhand eines deutschen Textes exemplarisch durchgeführt werden. Dazu benötigt man eine Zusammenstellung der Häufigkeitsverteilung der einzelnen Buchstaben und der häufigsten Bigramme (Buchstabenpaare) der deutschen Sprache.

Häufigkeit der Buchstaben in der deutschen Sprache

Tabelle Bigramme, häufigste Buchstabenpaare

Der Text aus der obigen Aufgabe umfasst 1187 Zeichen ohne die Leerschläge mitzuzählen. Die Buchstabenhäufigkeit ist wie folgt:

a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	z
8	79	74	22	25	16	37	11	2	1	46	13	15	217	24	116	28	55	54	39	31	20	92	x	91	71
0.67%	6.66%	6.23%	1.85%	2.11%	1.35%	3.12%	0.93%	0.17%	0.08%	3.88%	1.96%	1.26%	18.28%	2.02%	9.77%	2.36%	4.63%	4.55%	3.29%	2.61%	1.68%	7.75%	0%	7.67%	5.98%

Anhand dieser zweiten Tabelle und dem Vergleich der beiden Tabellen - und mit dem Wissen, dass der Text in deutscher Sprache, nur mit Hilfe von Substiturionen chiffriert wurde, können Rückschlüsse auf die zusammengehörenden Buchstabenpaare der Substitution gemacht werden. Auch kann es helfen, die Häufigkeit der meistgenutzen zwei aufeinanderfolgenden Buchstaben aufzulisten. Das könnten dann die Bigramme sein. Durch einge Versuche und etwas Ausprobieren kann man den Geheimtext oft dechiffrieren.

Das von Al-Kindi beschriebene Kryptoanalyseverfahren war ein sehr mächtiges Werkzeug, welches die Entschlüsselung von monoalphabetischen Texten ermöglichte. Doch auch dieses Verfahren hat gewisse Grenzen und Schwachstellen.
Bespielsweise kann die Botschaft: „Ein Traktat über die amurösen Aventüren des Balthasar Matzbach am Rande des Panamakanals“ nur sehr schwer mit der Häufigkeitstabelle entschlüsselt werden. Zum einen, weil der Text ziemlich kurz ist und zum andern, weil er nicht die gleiche Häufigkeitsverteilung hat wie ein „durchschnittlicher“ Text.

Denn Grundlage dieses Verfahrens ist die Häufigkeitsverteilung (der jeweiligen) der Buchstaben in einem Text. Diese Häufigkeitsverteilung kann in einem Text jedoch ganz anders gegeben sein.
Sehr gute Beispiele für Texte, die nicht diesen Verteilungen folgen, sind sogenannte lipogrammatische Texte. In diesen Texten wird ein zuvor festgelegter Buchstabe vermieden. Ein gutes Beispiel dafür gibt uns der Roman „La Disparition“ („Anton Voyls Fortgang“) von Georges Perec (1969 erschienen, übersetzt ins Deutsche von Eugen Helmlé). In diesem 200-seitigen Roman wird kein einziges Mal der Buchstabe e verwendet. Hier die ersten Seiten des Romans.
Die verschlüsselte Variante dieses Textes wäre nicht ganz einfach zu knacken, da der normalerweise häufigste Buchstabe e nie vorkommt. Ähnliche Überlegungen und Finten können natürlich auch die „Verschlüssler“ angewendet haben. Beispielsweise:

den Text absichtlich orthografisch falsch schreiben
Füllworte wie „und“ etc., die sehr häufig vorkommen, weglassen
Füllworte oder Füllzeichen ohne Bedeutung „einbauen“
Codeworte oder Codezeichen im Text einbauen

Die beiden letzten genannten Punkte können als sog. Nomenklator zusammengefasst werden, besteht aus einem Verschlüsselungsalphabet, evtl. einigen Füllzeichen und einer Liste von Codewörtern.
Diese Technik wurde auch von Maria Stuart genutzt, um einen Komplott gegen die englische Königin zu schmieden. Genauere Informationen zur Nomenklatora von Maria Stuart finden Sie hier.

Das Schicksal der Maria Stuart zeigte in dramatischer Art und Weise, dass auch die zusätzlichen Sicherheitsmechanismen einen gewieften Kryptoanalytiker nicht an der Entschlüsselung eines Textes hindern konnten. Dies war der Grund, warum man nach einem neuen System der Verschlüsselung suchte, welches ein grösseres Mass an Sicherheit bieten würde.

Die Schwachstellen - die Häufigkeitsverteilung der entsprechenden Sprache bleibt im Geheimtext relativ gut erhalten, zum einen und auch die Tatsache, dass jeder Klartextbuchstabe immer durch denselben Geheimtextbuchstaben verschlüsselt wird, macht die reine Transposition zu einem unsicheren Chiffrierverfahren.

Um diese Schwachstellen auszumerzen, wurden neue Algorithmen entwickelt, bei welchen nicht immer dasselbe Geheimtextalphabet für die Verschlüsselung verwendet wird. Die Pioniere auf diesem Gebiet waren Leon Battista Alberti (um 1470) und Johannes Trithemius(1508), deren Idee wurde von Blaise de Vigenère (1523 bis 1596) weiterenwickelt. Die bis heute bekannte Vigenère-Verschlüsselung wurde entwickelt.

Vigenère-Verschlüsselung

1586 veröffentlicht der französische Diplomat Blaise de Vigenère die Grundidee seiner Verschlüsselungsmethode, welche nicht ganz neu aber durch ihn sehr bekannt wurde. Es geht darum, zwischen mehreren Verschlüsselungsalphabeten hin und her zu wechseln. Dies war der Anfang der sogenannten polyalphabetischen Verschlüsselung, hier bleiben die Buchstaben wo sie sind, aber nicht was sie sind. Was sie sind, ist immer wieder verschieden.

Grundidee der Vigenèreverschlüsselung ist:
Sender und Empfänger einigen sich auf ein Schlüsselwort. Beispielsweise „VENUS“. Dieses wird über oder unter die Nach- richt geschrieben.

V	E	N	U	S	V	E	N	U	S	V	E	N	U	S	V
p	o	l	y	a	l	p	h	a	b	e	t	i	s	c	h

Über jeden Buchstaben der Nachricht wird ein Buchstabe des Schlüsselwortes geschrieben. Das Schlüsselwort wird dabei ständig wiederholt.

Danach muss das Vigènere-Quadrat genutzt werden, und zwar wie folgt:

Man nimmt jeweils einen Buchstaben der Nachricht und sucht ihn in der ersten Zeile des Vigenère-Quadrates (horizontal).
Von da aus geht man nach unten (vertikal) bis zu dem Alphabet, das ganz links mit dem entsprechenden Buchstaben des Schlüsselwortes beginnt.
Der Buchstabe, den man dort findet, ist der verschlüsselte Buchstabe.

Dieses Vorgehen muss für jeden Buchstaben wiederholt werden. Die Chiffre sieht dann wie folgt aus:

V	E	N	U	S	V	E	N	U	S	V	E	N	U	S	V
p	o	l	y	a	l	p	h	a	b	e	t	i	s	c	h
K	S	Y	S	S	G	T	U	U	T	Z	X	V	M	U	C

Den Vorteil der polyalphabetischen Verschlüsselung erkennt man auf Anhieb, denn gleiche Buchstaben werden mit verschiedenen Geheimtextbuchstaben ersetzt und dadurch wird die Häufigkeitsverteilung der Buchstaben durch dieses stete Wechseln des Geheimalphabets extrem verwischt. Dadurch steht ein Kryptoanalytiker (Eve) vor sehr viel grösseren Herausforderungen, den Geheimtext zu knacken.
Oft wird durch eine Vigenère-Verschlüsselung quasi eine Gleichverteilung der Buchstabenhäufigkeit erreicht.

Aufgabe - Vigenère
Wählen Sie ein Schlüsselwort (gemeinsam mit Ihrem Lernpartner bzw. Ihrer Lernpartnerin). Verschlüsseln Sie anschliessend einen kurzen Satz Ihrer Wahl, diesen Satz muss dann Ihre Lernpartnerin bzw. Ihr Lernpartner entschlüsseln. Somit ist der Inhalt des Geheimtextes nicht im Klartext zu teilen!

Kryptoanalyse: Knacken polyalphabetische Texte

Lange Zeit galten die polyalphabetisch verschlüsselten Texte als „unknackbar“, so wurde z.B. die Vigenère-Verschlüsselung auch „le code indéchiffrable“ genannt. In der Tat gestaltet sich die Suche nach einer Methode zum brechen eines polyalphabetischen Textes als sehr schwierig. Ein und derselbe Geheimbuchstabe kann für verschiedene Klarbuchstaben stehen. Auf den ersten Blick hat man kaum einen Anhaltspunkt, welcher zum knacken Verwendung finden könnte. Doch Charles Babbage verblüffte 1846 die Experten, indem es ihm gelang, polyalphabetische Texte durch Phantasie, Intuition und mit endloser Geduld bei der Suche nach wahrscheinlichen Worten im Text, zu entschlüsseln.

[[https://de.wikipedia.org/wiki/Charles_Babbage|Quelle]]
Podcast von 100-Sekunden-Wisen über Babbage

Zehn Jahre nach Babbage war es F. W .Kasiski, der eine systematische Beschreibung für die Entschlüsselung polyalphabetisch chiffrierter Texte gab. Die beiden hatten unabhängig voneinander die gleiche Idee. Sie hielen sich an die einzige Konstante, sozusagen den einzigen Strohhalm, an welchen man sich als Codeknacker halten kann: die Länge des Schlüsselwortes.

Es wird nun eine von zwei Methoden zur Auffindung der Schlüssellänge dargestellt werden:

die Parallelstellensuche nach Kasiski
die sogenannte Koinzidenzindexmethode nach Friedman (wird nicht vorgestellt, ist aber äusserst spannend ).

Parallelstellensuche nach Kasiski

Kasiski (und Babbage schon früher) hatten gemerkt, dass man gegebenenfalls die Länge des Schlüsselwortes herausfinden kann, wenn man im Geheimtext Stellen mit gleichen Buchstabenfolgen aufsucht. Solche Parallelstellen können durch gleiche Buchstabenfolgen im Klartext entstehen, die durch dieselben Schlüssel- buchstaben chiffriert wurden. Natürlich besteht auch die Möglichkeit, dass diese Stellen zufällig entstehen.

Um den Kasiski-Test (oder eigentlich Babbage-Test ;) ) und dessen zündende Idee zu erläutern, schauen wir uns das ganze an dem folgenden Beispiel an:

Die Schatten werden länger,
Der graue, grame Grillenfänger
Streicht um das Haus.
Der Tag ist aus.
Die Ängste kommen näher,
Sie stell‘n sich größer, krall‘n sich zäher
In der Seele fest,
In deinem Traumgeäst.
Manchmal ist es bis zum anderen Ufer der Nacht
Wie ein lichtloser Tunnel, ein nicht enden wollender Schacht.
Ich bring dich durch die Nacht,
Ich bring dich durch die raue See
Ich bring dich durch die Nacht,
Ich bringe dich von Luv nach Lee.
Ich bin dein Lotse, ich bin dein Mann,
Bin deine Schwester, lehn dich an,
Ich bin der Freund, der mit dir wacht,
Ich bring dich durch die Nacht.
Alles erscheint dir schwerer,
Bedrohlicher und hoffnungsleerer.
Mit der Dunkelheit
Kommen aus dunkler Zeit
Ferne Erinnerungen,
Die Nacht wispert mit tausend Zungen:
"Sie alle sind aus,
Du bist allein zuhaus!"
Mit deiner stummen Verzweiflung und dem Knistern im Parkett
Und als einzigem Trost das warme Licht des Radios an deinem Bett. Ich bring dich durch die Nacht...
Laß los, versuch zu schlafen.
Ich bring dich sicher in den Hafen.
Dir kann nichts gescheh‘n,
Wolfsmann und böse Feen
Sind nur ein Blätterreigen
Vorm Fenster, der Wind in den Zweigen
Im Kastanienbaum,
Ein böser Traum,
Der‘s nicht wagt, wiederzukommen, bis der neue Tag beginnt.
Laß los, ich halt dich fest, ich kenn den Weg aus dem Labyrinth. Ich bring dich durch die Nacht...

Dieser Klartext sind die ersten Zeilen des Liedtexts von Reinhard Mey, Ich bring’ dich durch die Nacht

Die ersten Zeilen verschlüsselt mit Vigenère, ohne Leerschläge, nur in Kleinbuchstaben und ohne Umlaute (ä, ö, ü…)

omlecunexlzwreoiuxarariypeetcebqgenxindiyyprmmeatpvzfrrvnlagmqndlhgsqrcxhsifglyzpirnprnetrxzqtqnanplldsvrdxlxlaftgosrbrdwldkenwpueipukelteevyhldsrrwimqsgvyhlunrzevhgmtrlizfmnanltmlvfeiznifmfqhzdreprbreeqpvumcughmlqiaytgoflbfpvagnarwipznvpsxlzdrahssxeaqpvzohnpsxpohoetrnpipuoyyohqvprhohgvnlidiatomjtdhenlkueenfizqevpsfyuntqtgopuepshpqnnpsxpohoetrnqdvpszvzlhiyejtlrrtgoniaqpmuxogfpmjtbvaoipzmnayfpzdrvyizohjrdxldlruyhpohnatgoniaqpvmdehaohldmvgomyiapuemjtbevykkucuqfvjtdvryejttnywizqrfpsipztqvcwjtwrepviqdebsppohrefrktossyyussyrpvldmvgoiypuaxppoqigxzqtqnnhdhbzkyrcdlutsrcrlqrvayiygntryhpqnnpsxduscrcxtutgnfwlzdmhyklz

Schritt 1: der Kasiski-Test und die Bestimmung der Länge des Schlüsselwortes

Nehmen wird das Beispiel, einne Teil des Liedtextes von Reinhard Mey und dem Schlüsselwort lehmann.

Es gibt einige Textfragmente, die mehrmals vorkommen. In unserem überschaubaren Beispiel haben wir auch Parallelstellen der Länge 2 gesucht. Normalerweise sind nur Stellen mit der Länge 3 oder mehr aufzusuchen, da Stellen mit der Länge 2 sehr oft zufällig zustande kommen. So wäre es durchaus möglich, dass das zweimalige go durch verschiedene Buchstabenfolgen im Klartext mit verschiedenen Schlüsselteilen erzeugt wurde.
Es ist aber auch denkbar, dass es durch gleiche Folgen mit demselben Teil des Schlüssels chiffriert wurde (in diesem Fall war es CH, welches durch eh chiffriert wurde). Dies wäre dann ein sehr guter Hinweis für die Kryptoanalytikerin Eve.
Bei dem sehr langen Textfragment ipumvpzgqvnlkgrpuoml ist es extrem unwahrscheinlich, dass es zufällig mit unterschiedlichen Text- resp. Schlüsselteilen entstand. Durch solche Funde kommen wird dem Knacken der Chiffrierung ein ganzes Stück näher!
Der Abstand zwischen den Parallelstellen kann bestimmt werden. Sind diese tatsächlich durch das Zusammentreffen von identischen Text- und Schlüsselstellen entstanden, so muss der Abstand zwischen den Parallelstellen natürlich ein Vielfaches des Schlüssels sein.

Für unsere Beispielzeile ergeben sich folgende Abstände der Parallelstellen:

zwischen dem ersten „go“ und dem nächsten “go“: 7 Buchstaben an Abstand, (7 hat nur die Faktoren 7 und 1)
zwischen dem ersten „ipum…“ und dem nächsten “ipum…“: 28 Buchstaben an Abstand, (28 hat die Faktoren 1,2,4,7,14,28)
zwischen dem ersten„ipu“ und dem nächsten “ipu“: 35 Buchstaben an Abstand,(35 hat die Faktoren 1,5,7,35)
zwischen dem zweiten „ipu“ und dem dritten “ipu“ : 63 Buchstaben an Abstand, (63 hat die Faktoren 1,3,7,9,21,63)

Damit das Schlüsselwort für all diese Parallelstellen von der Länge her funktioniert, sollte die Länge des Schlüssels als grösster Faktor in all den Zahlen 7, 28, 35 und 63 vorkommen. Für unser (durch die vielen Wiederholungen etwas unrealistisches) Beispiel deutet also alles auf eine Schlüssellänge von 7 hin, was auch stimmt („lehmann“).

Bemerkungen:

Die Parallelstellensuche ist extrem mühsam, da man in peinlicher Kleinstarbeit zunächst die Parallelstellen aufsuchen muss, um danach die Abstände auszählen zu können.
Eskönnen „falsche“ Parallelstellen (d.h. Parallelstellen, die zufällig zustande kommen) die Auswertung und die Suche nach der Länge des Schlüsselwortes stören. Der Zufall kann somit einen Streich spielen!
Die Schlüssellänge ist nicht berechnet, es gibt nur starke Indizien, dass die Schlüsselwortlänge gefunden ist. Es kann aber auch sein, dass das Schlüsselwort ein vielfaches dieser Länge besitzt.
Die meisten Texte haben nicht so viele Wiederholungen wie diese ersten Liedtextzeilen und es wird schwieriger, passende Wiederholungen zu finden.

Schritt 2: Knacken des mit Vigenère chiffrierten Textes

Falls nun die Länge des Schlüsselwortes bestimmt werden konnte, dann ist die Bestimmung des Schlüsselwortes, das Herausfinden des Schlüssels und somit das dechiffrieren der Nachricht, nicht mehr schwierig. Dazu ist die statistische Verteilung der Buchstaben und die Sprache - des Textes und des Schlüsselwortes nötig. Ein mögliches vorgehen wird im folgenden erklärt.

Idee zum Knacken
Der chiffrierte Text wird in Pakete der Schlüsselwortlänge aufgeteilt. Ist jeder erste Buchstabe eines Paketes mit dem gleichen Buchstaben des Schlüsselworts chiffriert worden.

`o`mlecun	`e`xlzwre	`o`iuxara	`r`iypeet	`c`ebqgen	`x`indiyy	`p`rmmeat	`p`vzfrrv
`n`lagmqn	`d`lhgsqr	`c`xhsifg	`l`yzpirn	`p`rnetrx	`z`qtqnan	`p`lldsvr	`d`xlxlaf
`t`gosrbr	`d`wldken	`w`pueipu	`k`elteev	`y`hldsrr	`w`imqsgv	`y`hlunrz	`e`vhgmtr
`l`izfmna	`n`ltmlvf	`e`iznifm	`f`qhzdre	`p`rbreeq	`p`vumcug	`h`mlqiay	`t`goflbf
`p`vagnar	`w`ipznvp	`s`xlzdra	`h`ssxeaq	`p`vzohnp	`s`xpohoe	`t`rnpipu	`o`yyohqv
`p`rhohgv	`n`lidiat	`o`mjtdhe	`n`lkueen	`f`izqevp	`s`fyuntq	`t`gopuep	`s`hpqnnp
`s`xpohoe	`t`rnqdvp	`s`zvzlhi	`y`ejtlrr	`t`goniaq	`p`muxogf	`p`mjtbva	`o`ipzmna
`y`fpzdrv	`y`izohjr	`d`xldlru	`y`hpohna	`t`goniaq	`p`vmdeha	`o`hldmvg	`o`myiapu
`e`mjtbev	`y`kkucuq	`f`vjtdvr	`y`ejttny	`w`izqrfp	`s`ipztqv	`c`wjtwre	`p`viqdeb
`s`ppohre	`f`rktoss	`y`yussyr	`p`vldmvg	`o`iypuax	`p`poqigx	`z`qtqnnh	`d`hbzkyr
`c`dlutsr	`c`rlqrva	`y`iygntr	`y`hpqnnp	`s`xduscr	`c`xtutgn	`f`wlzdmh	`y`klz

Die ersten Buchstabe (später dann alle zweiten Buchstaben usw.) werden gezählt. Die Häufigkeitsverteilung 2 der Buchstaben wird zu hilfe genommen. Dadurch kann als starke Vermutung der häufigste erste Buchstabe (zweite Buchstabe…) dem e zuzuordnen etc.
In diesem Beispiel sind die drei häufigsten Buchstaben p gefolgt von y gefolgt von o. Daher könnte einer der drei Buchstaben ein chiffriertes e sein. Wir müssen bedenken, dass das gewählte Beispiel im Klartext (wir kennen ja die Lösung, den Liedtext), viele Wiederholungen beinhaltet, was die Verteilung verändern kann.
Vermutung: p, y oder o könnte im Klartext das e sein.

Hat man die häufigsten Buchstaben gefunden, dann muss das Vigenère-Quadrat her. In der e-Spalte können jetzt die häufigsten Buchstaben p und y gesucht werden. Das Schlüsselwort könnte als erster Buchstabe somit ein l oder ein u haben.

Dann wird für den zweiten Buchstaben jedes Bündels das gleiche gemacht. Die drei häufgsten Buchstaben an zweiter Stelle jedes Bündels wären i und etwas weniger dann x. Wird nun in der e-Spalte nachgeschaut, dann ergibt sich für den zweiten Buchstaben des Schlüsselworts entweder ein e oder ein t.

Auf diese kann nun das gesamte Schlüsselwort herausgeknobelt werden. Sicher ist schlussendlich immer eine gute Portion Kreativität und Knobelei dabei ;) .

Hier das genannte Vorgehen in einem Erklärvideo:

Vigenère Knacken - Schritt 2 - Aufgabe
Gegeben ist die folgende Geheimchiffre mit Vigenère verschlüsselt (Schlüssellänge 5).

EYRYC	FWLJH	FHSIU	BHMJO	UCSEG
TNEER	FLJLV	SXMVY	SSTKC	MIKYS
JHZVB	FXMXK	PMMVW	OZSIA	FCRVF
TNERH	MCGYS	OVYVF	PNEVH	JAOVW
UUYJU	FOISH	XOVUS	FMKRP	TWLCI
FMWVZ	TYOIS	UUIIS	ECIZV	SVXVF
PCOUC	HYRGO	MUWKV	BNXVB	VHHWI
FLMYF	FNEVH	JAOVW	ULYER	AYLER
VEEKS	OJVFA	PHEKP	FEEDS	OYWNI
SXIUO	GOIIU	FMSIU	UXEJG	TCINO
FBVVB	ECLIS	SUVSS	JNRZO	INKVG
UIIIH	XOVUS	OMMVR	VLJKS	OCLIS
COIIC	TUFVF	BOGYB	JWLKJ	FLPRG
TYRSS	WIVJW	FYMES	HYWKS	MFXVO
VZKRP	FAICC	FMXYO	UNIE

<WRAP center round todo 80%> Vigenère Knacken - Schritt 1 - Aufgabe
Gegeben ist die folgende Geheimchiffre mit Vigenère verschlüsselt und einem kurzen Schlüssel (in deutscher Sprache)

Kryptologie

Steganografie - Versteckte Nachrichten

Die Nachricht unter dem Wachs

Die Nachricht im rohen Ei

Die Nachricht im Mikrofilm

Grundlegende Kryptografietechniken

Transposition

Substitution

Tipp

Monoalphabetische Algorithmen