Hochschule Wismar

Transcrição

Hochschule Wismar

Hochschule Wismar
Fachbereich Wirtschaft
Projektarbeit
Kryptographie 2004
Klassische Chiffren
eingereicht von:
Marcel Brätz
geboren am 09. Mai 1977 in Brandenburg(Havel)
Studiengang Wirtschaftsinformatik
Matrikel Nr. : 102433
Betreuer:
Prof. Dr. J. Cleve
Wismar, den 15. Juni 2004
Inhaltsverzeichnis
I
Klassifikation der Klassischen Chiffren
3
1 Monoalphabetische Chiffren
1.1 Allgemeines . . . . . . . . . . . . . . .
1.2 Additive Chiffren . . . . . . . . . . . .
1.3 Multiplikative Chiffren . . . . . . . . .
1.4 Transpositionschiffren / Tauschchiffren
1.5 Substitutionschiffren . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4
4
4
5
6
7
2 Polyalphabetische Chiffren
2.1 Allgemeines . . . . . . . .
2.2 Homophone Chiffrierung .
2.3 Le Chiffre indechiffrable .
2.4 Play-Fair . . . . . . . . .
2.5 One-Time-Pad . . . . . .
2.6 Enigma . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
9
9
9
10
13
13
15
II
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Kryptoanalyse
17
3 Kryptoanalyse
3.1 Kryptoanalyse monoalphabetischer Chiffren
3.2 Kryptoanalyse polyalphabetischer Chiffren .
3.2.1 Allgemeines . . . . . . . . . . . . . .
3.2.2 Das Wichtigste ist die Mustersuche...
3.2.3 ...und wieder monoalphabetisch! . .
3.2.4 Der Weisheit letzter Schluß... . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
18
18
19
19
19
20
21
4 Mathematische Grundlagen
4.1 Häufigkeitstabellen . . . . . . . . . . . .
4.2 Verfahren zur Analyse . . . . . . . . . .
4.2.1 Häufigkeit . . . . . . . . . . . . .
4.2.2 Kasiski-Test . . . . . . . . . . . .
4.2.3 Koinzidenzindex / Friedman-Test
4.2.4 Entropie . . . . . . . . . . . . . .
4.2.5 Autokorrelation / Korrelation . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
22
22
23
23
23
24
26
26
III
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Anhang
28
5 Kurze Geschichte der Kryptographie
29
6 Begriffe, Definitionen und Abkürzungen
32
7 Sourcecode
33
1
Einleitung/Vorwort
Das Verschlüsseln von Nachrichten aller Art war schon immer eine Notwendigkeit, deshalb ist die Geschichte der
klassischen Chiffren fast ebenso lang, wie die Geschichte der Schriftsprache. Erst mit der verstärktem Einsatz
moderner Computer, also um 1950, endete die Zeit der klassischen Chiffren, da der Einsatz mächtiger Rechenmaschinen bis dahin ünknackbare¨ Verschlüsselungen plötzlich angreifbar machte. Die zum Einsatz kommenden
Computer machten den notwendigen rechentechnischen Aufwand für statistische Berechnungen beherrschbar.
Ich werde im Zuge dieser Ausarbeitung verschiedentlich darauf hinweisen, wo dies Anwendung fand und werde
am Ende auch ein praktisches Beispiel geben, wieso die lange Zeit als unknackbar angesehene Vigenère-Chiffre
plötzlich unsicher war.
In dieser Ausarbeitung kann ich natürlich nicht alle Chiffren, die in den vielen Jahrhunderten erfunden und
eingesetzt worden sind, näher beleuchten, zumal auch nicht alle Chiffren geknackt worden sind.[4, 7] Ich werde
mich also an dieser Stelle auf grundsätzliche und klassische Chiffren beschränken. Viele an dieser Stelle ungenannt bleibende Chiffren, arbeiten grundsätzlich nach ähnlichen Algorithmen und sollen daher nicht näher
behandelt werden.
Nun stellt sich die Frage: Brauchen Privatpersonen überhaupt so etwas wie Kryptographie? Es gibt Dinge,
die jedem wichtig sind, von denen man nicht will, daß jedermann diese liest. Also lautet die Antwort: Ja! Angefangen vom einfachen Tagebuch bis zu streng geheimen Wirtschaftsdaten, brauchen wir Kryptographie um für
deren Sicherheit zu sorgen. Früher war Verschlüsselung größtenteils dem Militär und der Diplomatie vorbehalten.
Als das Thema Kryptographie in der Öffentlichkeit populärer wurde, wurde sie in einigen Ländern sogar teilweise verboten. In den USA, dem Land mit den höchsten Ausgaben für derartige Technologien, beispielsweise
werden Verschlüsselungstechnologien, mit der selben Sicherheitsstufe eingestuft, wie Waffentechnologieen.
Die Wahl des jeweilig verwendeten Verfahren hängt vom notwendigen Schutz und von der Person / Organisation ab, vor der man Daten schützen will. Allerdings gibt es keinen Grund, schwächere Kryptoalgorithmen zu
verwenden, wenn man nur einen einfachen Gegner hat.
Im folgenden werde ich auf die grundlegenden Eigenschaften der einzelnen Verfahren eingehen, diese klassifizieren und anhand ausgewählter Vertreter erläutern und jeweils mit einem Beispiel dokumentieren. Ich füge
außerdem Programmierbeispiele bei. Dabei kommt die Programmiersprache PHP zum Einsatz, um Algorithmen
zu implementieren und deren Funktionsweise zu erläutern. Desweiteren habe ich eine Webseite[5] zusammengestellt, auf der es möglich ist, interaktiv, die hier behandelten Verschlüsselungstechnologien auszuprobieren.
Nachdem das Implementieren der einzelnen Chiffren beleuchtet wird, stellt sich die Frage nach der Dekodierung
der Chiffren, wenn der Schlüssel unbekannt ist. Das sogenannte ¨Brechen¨ von Verschlüsselungen, die Kryptoanalyse, stellt die einzelnen Verschlüsselungen auf eine harte Probe. Ich werde in einem gesonderten Kapitel
darauf eingehen und einige der Techniken, die dabei zur Anwendung kommen, beleuchten. Ich erhebe keinen
Anspruch auf Vollständigkeit. Ich möchte lediglich Ansätze aufzeigen.
2
Teil I
Klassifikation der Klassischen Chiffren
3
Kapitel 1
Monoalphabetische Chiffren
1.1
Allgemeines
In diesem Kapitel geht es um sehr einfache kryptographische Verfahren. Diese Verfahren sind nicht sicher, bilden
aber ein wichtiges Fundament der modernen Kryptographie. Viele der Techniken, die schon bei den klassischen
Chiffren zum Einsatz kamen, finden weiter Verwendung in modernen Verfahren.
Man unterscheidet bei den bei den klassischen Chiffren:
• monoalphabetische Chiffren und
• polyalphabetische Chiffren
Unter monoalphabetischen Chiffrierungen versteht man Verfahren, bei denen jeder Buchstabe des Alphabets
zu dem selben Geheimtext-Buchstaben verschlüsselt wird. Man kann z.B. jedem Buchstaben ein bestimmtes
Zeichen (oder einen anderen Buchstaben) zuordnen.
Beispiele:
Klartext:
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
Geheimtext: Q A Y W S X E D C R F V T G B Z H N U J M I K O L P
Klartext:
Geheimtext: ! " § $ % & / ( ) = ? + * # - { 3 2 7 5 > | ] [ @ 5
Für diese Art der Chiffrierung gibt es tatsächlich 26 · 25 · 24 · ... 3 · 2 · 1 = 26! = ˜ 4 · 1026 Möglichkeiten!
Warum diese Verfahren leider trotzdem (meistens) leicht zu knacken sind, wird im Kapitel Kryptoanalyse gezeigt.
Wenn ein Buchstabe oder Zeichen durch einen anderen Buchstaben bzw. Zeichen ersetzt wird, nennt man
das auch Substitution. Wie Transpositions-Algorithmen sind Substitutions-Algorithmen ein wichtiger Baustein
für moderne Algorithmen.
1.2
Additive Chiffren
Die einfachsten Verfahren sind Additive Chiffren, Verschiebechiffren. Diese Art der Chiffrierung soll schon Julius
Caesar benutzt haben. Man verschlüsselt dabei einen beliebigen Text indem man das Klartextalphabet unter
das Geheimtextalphabet schreibt, aber um k Stellen nach links oder 26 - k Stellen nach rechts verschoben.
1. Beispiel (Caesar-Chiffre):
Klartext:
Geheimtext: 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
4
Hier wurde das Alphabet um 3 Stellen nach links verschoben. Man chiffriert nun eine Nachricht, indem man
den Klartextbuchstaben durch den darunterstehenden Geheimtextbuchstaben ersetzt. Aus dem Wort klartext
würde in unserem Fall NODUWHAW. Für k gibt es genau 26 Möglichkeiten. k wäre hier der Schlüssel. Man
kann dieses äußerst simple Verfahren knacken, indem man einfach alle Möglichkeiten ausprobiert! Es gibt nur
26 verschiedene Schlüssel.
2. Beispiel (ROT13):
Klartext:
Geheimtext: N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
ROT13 ist eine in Foren und Bulletin-Boards recht beliebte Chiffre. Sie hat den Reiz, dann man mit nochmaliger
Verschlüsselung erneut den Klartext erhält.
Solche Chiffrierungen werden also als additive Chiffrierungen bezeichnet, da wir eigentlich den Wert k zum
Klartextbuchstaben addieren, um den Geheimtextbuchstaben zu erhalten. Dazu numerieren wir das Alphabet
von 1 bis 25 durch, wobei wir z mit 0 belegen:
a = 1
... y = 25, z = 0
Um zu verschlüsseln, addieren wir k zu einem Buchstaben:
a + 3 = D entspricht 1 + 3 = 4
Wenn die Summe größer als 26 ist, muss man diese Summe durch 26 teilen und den entstandenen Divisionsrest
in einen Buchstaben zurückübersetzen. Dies nennt man auch Modulo-Operation, bzw. Modulo-Division.
Beispiele:
(y + 4) mod 26 = (25 + 4) mod 26 = 3 = C
Zur Dechiffrierung subtrahiert man k vom Geheimtextbuchstaben. Dann addiert man 26 hinzu und führt eine
Modulo-Operation durch:
k = 3, Geheimtextbuchstabe: B
(B - 3 + 26) mod 26 = (2 - 3 + 26) mod 26 = 25 = y
k = 19, Geheimtextbuchstabe: X
(X - 19 + 26) mod 26 = (24 - 19 + 26) mod 26 = 5 = e
1.3
Multiplikative Chiffren
Bei dieser Chiffrierung verwendet man statt Addition Multiplikation modulo 26 (siehe vorheriges Kapitel). Wir
multiplizieren jeden Klartextbuchstaben mit dem Schlüssel k.
Ein Beispiel mit k = 2:
Klartext:
Geheimtext: B D F H J L N P R T V X Z B D F H J L N P R T V X Z
Auffallend ist hier, dass jeweils zwei unterschiedliche Buchstaben dasselbe Produkt ergeben! Daher können wir
diese Substitution nicht als Chiffre verwenden. Damit die Chiffre bei der Dekodierung wieder eindeutige Resultate liefert darf es nicht zu Überlappungen bzw. Uneindeutigkeiten in der Chiffrierung kommen. Der Klartext
muss also mit Hilfe des Schlüssels eindeutig aus dem Geheimtext rekonstruierbar sein! Also gilt: es kommen nur
Alphabete in Frage, deren Elemente nur einmal vorkommen.
Es kommen also nur Zahlen in Frage die mit 26 keine gemeinsamen Teiler haben. Das sind
1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 und 25
5
12 Stück. Höhere Zahlen kommen nicht in Frage, weil die Modulo-Division wieder kleinere Zahlen liefert, welche
den selben kriterien unterworfen werden.
Nehmen wir nun mal einen Kandidaten aus dier zulässigen Liste: k = 3:
Klartext:
Geheimtext: C F I L O R U X A D G J M P S V Y B E H K N Q T W Z
Diese Chiffrierung funktioniert! Leider ist die Schlüsselzahl noch geringer als bei der Verschiebechiffre.
1.4
Transpositionschiffren / Tauschchiffren
Bei einem Transpositions-Algorithmus bleiben die Buchstaben was sie sind, aber nicht wo sie sind. Ein Beispiel
für solch einen Algorithmus ist die Skytale von Sparta, die vor ungefähr 500 v. Chr. benutzt worden sein soll.
Der Sender wickelte ein schmales Band aus Pergament spiralförmig um die Skytale (ein Zylinder mit einem
bestimmten Radius, der auch gleichzeitig der Schlüssel ist) und schrieb dann der Länge nach seine Nachricht
auf das Band. Diese Nachricht wurde dann abgewickelt und an den Empfänger geschickt. Hatte dieser eine
Skytale mit demselben Radius, konnte er die Nachricht lesen.[6]
Ein Beispiel:
H A L L O L E U T E W I E G E H T E S E U C H
Wir verschlüsseln nun diesen Text mit einer Skytale des Umfangs U = 5, indem wir den Text in 5 Spalten
aufteilen:
H
L
W
H
U
A
E
I
T
C
L
U
E
E
H
L
T
G
S
O
E
E
E
Das Ergebnis ergibt sich, indem man jede Spalte dieses Textes von oben nach unten liest und alles hintereinander
aufschreibt:
H L W H U A E I T C L U E E H L T G S O E E E
Diese Art der Transposition wird auch Spaltentransposition genannt.
Es gibt auch komplizierte Transpositionschiffrierungen, die jedoch fast ausnahmslos von Computern geknackt
werden können. Die deutsche ADFGVX-Chiffrierung[6], die im ersten Weltkrieg verwendet wurde, stellt solch
eine Chiffrierung dar. Für damalige Verhältnisse war dieser Algorithmus sehr komplex; er wurde jedoch von
dem französischen Kryptoanalytiker Georges Painvin innerhalb weniger Wochen geknackt. Nach der Einführung
durch das deutsche Militär im März 1918 war sie bereits Anfag Juni des selben Jahres nicht mehr sicher. Diese
Chiffre war eine der berühmteren Transpositionschiffren, weil sie trotz ihrer Stärke sehr schnell geknackt wurde.
Zur Funktionsweise soll folgendes Beispiel dienen[6]:
Man ordnete die Buchstaben A-Z und die Ziffern 0-9 in einer 6x6 Matrix an wie folgt an.
A
D
F
G
V
X
A
8
l
7
j
x
9
D
p
t
k
u
s
e
F
3
4
b
6
v
y
6
G
d
o
c
w
i
0
V
1
a
5
g
r
f
X
n
h
z
m
2
q
Dies ist der erste Schlüssel. Die Anordnung der Zeichen ist einem Codebuch entnommen und nicht willkührlich.
Damit wurde die Nachricht als erstes verschlüsselt. In der Folge ergab sich eine Reihe von Bigrammen aus den
Buchstaben A, D, F, G, V und X. Die Wahl der Buchstaben folgete aus der Unterschiedlichkeit der Darstellung
im Morse-Code[5], um Übermittlungsfehler zu vermeiden.
Mitteilung: a n g r i f f u m 1 0 u h r
Geheimtext: DV AX GV VV VG XV XV GD GX AV XG GD DX VV
In der 2. Stufe der Verschlüsselung werden alle Buchstaben des Geheimtextes unter einem Schlüsselwort angeordnet, welches dann alphabetisch sortiert wird. Dies vertauscht die darunter angeordneten Buchstaben und
fragmentiert die Bigramme. Im folgenden wird da Schlüsselwort MARK verwendet:
M
D
G
V
X
G
X
D
A
V
V
G
V
X
G
X
R
A
V
X
G
A
G
V
K
X
V
V
D
V
D
V
A
V
V
G
V
X
G
X
K
X
V
V
D
V
D
V
M
D
G
V
X
G
X
D
R
A
V
X
G
A
G
V
Nach dem Tauschen ergibt sich:
Im Ergebnis steht nun folgender Text:
VX DA VV GV GV VX VD XG XV GA GD XG XV DV
Die Sicherheit dieses Algorithmus ist recht hoch. Dennoch würde ein mit ensprechenden Regeln programmierter
Computer nur wenige Sekunden brauchen, um diesen Algorithmus zu brechen.
Transposition ist eine wichtige Technik der Kryptographie und wird auch bei modernen Verfahren eingesetzt.
1.5
Substitutionschiffren
Neben den bisher genannten monoalphabetischen Chiffren möchte ich auch die Substitutionschiffren einreihen,
auch wenn diese Zuordnung nicht immer ganz richtig ist. Grundsätzlich sind sie aber Vertreter der sogenannten
starken monoalphabetischen Chiffren, weil ganze Worte oder Silben auf einmal chiffriert werden. Anhand folgender zwei Vertreter wird die grundlegende Funktionsweise kenntlich gemacht. Genannt seien die Beale-Chiffre
und die ¨Große Chiffre¨ vom französichen Sonnenkönig Ludwig dem XIV. Beide sind zu Lebzeiten der Urheber
nicht geknackt worden.
Beide verwenden ein rechtumfangreiches Alphabet. Die Beale-Chiffre greift beispielsweise auf ein Dokument
als Schlüssel zurück. In diesem Dokument werden die Worte durchnummeriert und dann werden im zu verschlüsselnden Text Worte durch entsprechende Zahlen ersetzt. Im Ergebnis steht eine langen Liste von Zahlen,
die nur noch mit Hilfe des Original Schlüsseldokuments entschlüsselt werden kann. Beal hatte Mitte des 19.
Jahrhunderts 3 Dokumente, die in dieser Weise verschlüsselt waren hinterlassen, die auf einen Silberschatz im
Wert von ca. 20 Mio. Dollar weisen sollten. Bis heute ist nur das 2. der 3 Dokumente entschlüsselt worden. Trotz
der Tatsache, dass sich bereits Tausende Hobbykryptographen und auch die NSA damit beschäftigt haben bleibt
unbekannt, was die anderen Dokumente für einen Inhalt haben. Beale hatte für das 2. Dokument eine besondere
7
Fassung der Unabhängigkeitserklärung von 1776 verwendet. Für die anderen beiden Texte hat er aber andere
Schlüsselwörter genommen.
Die Große Chiffre geht auf Antoine und Bonaventure Rossignol zurück. 1626 hatte der Vater Antoine einen
Brief in die Hände bekommen und damit erfahren, dass das Hugenottenheer in Réalmont kurz vor der Aufgabe
stand. Der Brief wurde unverschlüsselt zurück geschickt und die Verteidiger gaben auf.
Nun im Dienste des Königs Ludwigs XIII und später unter seinem Nachfolger entwarfen sie die ¨Große Chiffre¨.
Ende des 19. Jahrhunderts erst wurde sie durch französische Kryptoanalytiker geknackt. Auf diese Weise wurde
unter anderem die lange umstrittene Identität des Mannes mit der eisernen Maskeaufgedeckt.
8
Kapitel 2
Polyalphabetische Chiffren
2.1
Allgemeines
Bei den sogenannten polyalphabetischen Chiffrierungen wird derselbe Klartextbuchstabe nicht stets mit demselben Geheimtextbuchstaben verschlüsselt. Bei dieser Technik kommen mehrere monoalphabetische Chiffrierungen zum Einsatz (poly [gr.] = viele).
2.2
Homophone Chiffrierung
Die homophone Chiffrierung dient dazu, die Häufigkeiten von Buchstaben zu verschleiern. Dabei ordnet man
einem Buchstaben nicht ein, sondern mehrere Zeichen zu. Man ordnet allen 26 Buchstaben z. B. die Zahlen
von 0 bis 99 zu; je höher die Häufigkeit des Buchstabens, desto größer die zugeordnete Zeichenmenge. Dem
Buchstaben e würde man in unserem Beispiel 17 Zahlen zuordnen. Beim Chiffrieren ordnet man einem Klartextbuchstaben zufällig ein dazugehöriges Geheimtextzeichen zu. Der Empfänger kann dann mit einer Tabelle,
die der Absender ihm hoffentlich übergeben hat, dechiffrieren. Leider ist dieses Verfahren nicht sicher, da bestimmte Buchstabengruppen nicht verborgen werden
Der entscheidende Nachteil bei monoalphabetischen Chiffren ist, wie wir eben gesehen haben, die leidige Tatsache, dass Buchstabenhäufigkeiten nicht verborgen werden. So wird die Kryptoanalyse kinderleicht. Indem
man einem Klartextbuchstaben nicht nur ein, sondern mehrere Geheimtextzeicnen zu ordnet, kann man die
Häufigkeiten so verschleihern! Die Anzahl der Geheimtextzeichen sollte dabei der allgemeinen Häufigkeit des
Klartextbuchstabens entsprechen. Das bedeutet, dass z.B. das e (Häufigkeit: ca. 17%) 17 Geheimtextzeichen
von 100 Paaren 00 bis 99 zugewiesen bekäme. Ein Beispiel hierfür gestaltet sich wie folgt[2]:
a:
b:
c:
d:
e:
f:
g:
h:
i:
j:
k:
l:
m:
n:
o:
p:
q:
10
20
28
04
09
00
08
07
14
57
23
16
27
30
02
31
25
21
34
06
19
18
41
12
24
39
52 59 71
03
11
35
05
84
49
43 62 63 67 68 72 77 79
82
80
70 81 87
33 38 40 42 53 54 55 60 66 75 85 86 92 93 99
97
47 89
46 50 65 76 88 94
9
r:
s:
t:
u:
v:
w:
x:
y:
z:
17
15
13
29
37
22
44
48
64
36
26
32
01
51 69 74 78 83
45 56 61 73 96
90 91 95 98
58
Um eine Nachricht zu chiffrieren, ordnet man jedem Klartextbuchstaben ein zufällig gewähltes Zeichen aus
der Menge der möglichen Geheimtextzeichen für diesen Buchstaben zu. Da nun jeder Buchstabe mit etwa
der gleichen Häufigkeit auftritt, wird die Kryptoanalyse mit ¨herkömmlichen¨ Methoden nun viel schwieriger.
Allerdings ist auch bei dieser Chiffre eine Kryptoanalyse möglich: Zwar werden die Häufigkeiten einzelner Buchstaben verschleiert, Buchstabengruppen wie st, sch, ck bleiben jedoch erhalten. Ein Kryptoanalytiker kann den
Geheimtext z. B. daraufhin analysieren, welche Geheimtextzeichen ganz bestimmte Nachfolger oder Vorgänger
haben; z. B. das c mit Nachfolgern wie h und k, oder das e mit Nachfolger oder Vorgänger i (ei, ie). Diese
Methoden sind natürlich noch keine richtige Kryptoanalyse, aber zeigen die Ansätze, wie ein Kryptoanalytiker
an einen solchen Text herangehen kann.
2.3
Le Chiffre indechiffrable
Der französische Diplomat Blaise de Vigenère (1523-1596) veröffentlichte um 1586 neben anderem eine polyalphabetische Chiffre, welche von der Idee her auf den florentiner Mathematiker Leon Battista Alberti (1404-1472)
zurückgeht. Jener hatte 1466 eine Abhandlung zum verwenden mehrerer Geheimalphabete anstatt nur eines einzigen. Dies sollte die Stärke der Verschlüsselung dramatisch erhöhen.
Klartextalphabet: 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
1. Geheimtextalphabet: W F O X G P Y H Q Z I R A J S B K T C L U D M V E N
2. Geheimtextalphabet: O X G P Y H Q Z I R A J S B K T C L U D M V E N W F
Eine Nachricht sollte dabei abwechselnd buchstabenweise mit beiden Geheimtextalphabeten verschlüsselt werden. Hier ein Beispiel:
Nachricht:
Kodierung mit dem 1. Geheimtextalphabet:
Kodierung mit dem 2. Geheimtextalphabet:
DIESERTEXTISTGEHEIM
XQGCGTLGVLQCLYGHGQA
PIYUYLDYNDIUDQYZYIS
Im Ergebnis steht nun dieser Text:
XIGUGLLYVDQULQGZGIA
Der Text ist nun mit mehreren Alphabeten verschlüsselt und ist nicht mehr mit einfachen Häufgkeitsanalysen,
die bei monoalphabetischen Chiffren so erfolgreich waren, zu brechen.
Dieser Ansatz und auch weitere Werke, die de Vigenère während seines diplomatischen Dienstes las, inspirierten
ihn dazu wesentlich stärkere Chiffren zu entwickeln. Die Schwarzen Kammern in Europa (Dechiffrierdienste)
konnten die diplomatische Post auf grund der benutzten schwachen monoalphabetischen Chiffren praktisch
mitlesen, was eine starke Motivation war. In seinem Werk Traictè de Chiffres (1586) gibt er den Stand der
Chiffierkunst wieder und veröffentlichte ausserdem die nach ihm benannte Vigenère-Chiffre.
Die Idee ist die selbe, wie bei Alberti, mit dem Unterschied, dass mehr als 2 Alphabete zum Einsatz kommen sollten. Das folgende Schema soll demonstrieren, wie die Chiffre funktioniert.
Klartext:
Schlüsselwort:
Geheimtext:
p o l y a l p h a b e t i s c h
K R Y P T O K R Y P T O K R Y P
Z F J N T Z Z Y Y Q X H S J A W
10
Klartext
| 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
------------------------------------------------------------------Geheimtext A | 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
B | 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 A
C | C 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
D | 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
E | 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 D
F | F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G | G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H | H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
I | I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
J | J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
K | K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L | L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
M | M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N | N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
O | O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
P | P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
Q | Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
R | R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
S | S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
T | T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
U | U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
V | V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
W | W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
X | X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Y | Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Z | Z 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
Tabelle 2.1: Vigeneré-Quadrat
Das Schlüsselwort wird so oft aneinander gehängt, bis man genau so viele Buchstaben zusammen hat, dass
man jeden Buchstaben des Klartextes mit einem korrespondierem den Buchstaben aus dem Schlüsselwort verschlüsselt. Hierzu dient das von Vigenère vorgestellte Vigenere-Quadrat: Hierbei befindet sich der Geheimtextbuchstabe in der Spalte in der sich der zu verschlüsselnde Buchstabe seht und der Zeile, die dem Schlüsselbuchstaben der diesem Buchstaben zugeordnet wird. Also Aus Klartextbuchstabe P und Schlüsselbuchstabe K wird
der Geheimtextbuchstabe Z.
Dies läßt sich auch mathematisch ausdrücken, indem wir die Buchstaben als Zahlen darstellen (a=0..z=25):
(p+K) mod 26 = (15+10) mod 26 = 25 = Z
Entschlüsselung ist analog dazu:
(26+Z-K) mod 26 = (26 + 25 - 10) mod 26 = 15 = p
Die Kerneigenschaft der Vigenère-Ciffre ist also die zyklische Verwendung mehrerer Alphabete. Auf diese Weise
wurden sehr effektiv wesentliche Eigenschaften des verschlüsselten Textes verschleiert. Durch die ständig andere
Verschlüsselung gleicher Buchstaben war es nicht länger möglich mit einer einfachen Häufigkeitsanalyse den
Text zu entschlüsseln.
Eine Schwäche hat die Vigenère-Chiffre. Die Verwendung mehrerer Alphabete zur Verschlüsselung sorgt zwar
dafür dass die typischen Häufigkeitsverteilungen von Buchstaben verwischt werden. Dennoch fällt bereits bei
kurzen Texten auf, dass ein Buchstabe gleich verschlüsselt wird, wenn er an einer Stelle steht, die ein Vielfaches
der Schlüssellänge von einem anderen Vorkommen des selben Buchstaben ist. Im Beispiel oben wird das Wort
¨polyalphabetisch¨ mit dem Schlüsselwort KRYPTO verschlüsselt. Nun wird das p 2 mal gleich verschlüsselt
11
Abbildung 2.1: Schema der Vigenère-Chiffre [5]
weil es an 1. und an 6. Stelle steht, beide sind 5 Stelle auseinander, was der Schlüsselwortlängeentspricht.
Diese Schwäche war auch Blaise de Vigenère bewußt. Daher entwickelte er nur wenig später die AutokeyStromchiffre[10].
Abbildung 2.2: Schema der Autokey-Chiffre [5]
Diese funktioniert genau, wie die bereits beschriebene Vigenère-Chiffre. Im Gegensatz zur Vigenère-Chiffre wird
aber nach der ersten Verwendung des Schlüsselwortes die Klartextnachricht als weiterer Schlüssel verwendet.
Klartextnachricht: DIESENACHRICHTISTGEHEIM
Schlüssel: HUCHDIESENACHRICHTISTGE
Geheimtextnachricht: KCGZHVEULEIEOKQUAZMZXOQ
Diese Art der Verschlüsselung hat 2 Vorteile. Sie ist nicht mehr durch den Kasiski-Test oder gar den Verteilungstest von Willam Friedman (dazu mehr im Kapitel Kryptoanalyse) angreifbar. Außerdem ist es möglich
auch aus einer teilweise zerstörten Nachricht noch Informationen zu gewinnen, indem man die Information aus
Schlüssel und Klartext verwendete um die Nachricht zu vervollständigen.
Damit Blaise de Vigenère die erste selbst synchronisierende, selbstkorrigierende Stromchiffre erfunden. Sie hatte
also auch eine gewisse Fehlertoleranz zu bieten. Diese Eigenschaften und die Tatasache, dass sie mit damaligen
Mittel vollständig unknackbar war, machte die Autokey-Chiffre zur ¨le chiffre indechiffrable¨.
Beide Chiffren, die Vigenère-Chiffre und die Autokey-Chiffre, sollten bis ins 19. Jahrhundert keine große Rolle
spielen. Nur so ist es zu erklären, dass der Beiname der Autokey-Chiffre auf die wesentlich schwächere Vigenère-Chiffre überging, dass quasi eine Verwechslung stattfand. Ausserdem findet man in der Literatur nur
ganz unzureichende Referenzen. (Dies ist die Meinung des Autors)
12
Erst 200 Jahre später gelang es 2 Männern unabhängig voneinander die Vigenère-Verschlüsselung zu brechen.
Dies waren die Herren Kasiski und Friedman. Eigendlich gehört der Tribut Charles Babbage, einem genialen Erfinder, aber seine Erfolge wurde erst bekannt, als man Ende des 19. Jahrhundert seinen umfangreichen Nachlass
sichtete. Es heisst er habe im Gegensatz zu Friedman und Kasiski nicht nur die Vigenère-Chiffre geknackt, sondern auch die Autokey-Chiffre[10], da ich leider keinen genaueren Quellen zum Thema gefunden habe sei auf die
Quelle [5] verwiesen. Der Kryptographiespielplatz beinhaltet eine sehr aufwendige Implementierung mehrerer
Klassischer Chiffren, unter anderen auch der Autokey-Chiffre, sowie einer Reihe von Mechanismen zum Brechen
der Vigenère-Chiffre und der Autokey-Chiffre. Dort sind genauere Informationen über die Funktionsweise zu
finden.
2.4
Play-Fair
Das Playfair-Verschlüsselungsverfahren arbeitet nach einem Algorithmus von Charles Wheatstone (1854). Es
sei als Vertreter vieler kleinerer recht anspruchsvoller Chiffren aus dem 19. Jahrhundert genannt.
Man benötigt zunächst ein Schlüsselwort. Das Schlüsselwort ist hier PEGASOS und wird an den Anfang der
Matrix geschrieben. Da in der Matrix keine zwei gleichen Buchstaben auftauchen dürfen, werden doppelte
Zeichen im Schlüsselwort durch das nächste freie Zeichen im Alphabet ersetzt. Die übrigen Zellen der Matrix
werden dann mit den restlichen Zeichen des Alphabets aufgefüllt. Schon vorhandene Buchstaben werden dabei
weggelassen.
Im Fall der 5x5-Matrix wird im Alphabet das J weggelassen.
P
O
H
N
V
E
B
I
Q
W
G
C
K
R
X
A
D
L
T
Y
S
F
M
U
Z
Die Nachricht, die verschlüsselt werden soll, wird dann in Gruppen von je zwei Buchstaben (Bigramme) aufgeschrieben. Wir benutzen:
AL LE SI ST HE RA US FL IE HE SO FO RT
Zum Verschlüsseln nimmt man nun das erste Buchstabenpaar AL. Diese beiden Buchstaben bilden in der
Tabelle die Endpunkte der Diagonalen eines Rechtecks (A-L von unten nach oben). Die Endpunkte der anderen
Diagonalen (auch von unten nach oben gelesen) sind die Punkte P und M. Also wird das Buchstabenpaar AL
durch das Paar PM ersetzt. Aus LE wird XR. Probleme gibt es bei dem Paar ST, da beide Buchstaben in der
gleichen Zeile stehen. In diesem Fall nimmt man jeweils den Buchstaben rechts davon - TW. Steht links davon
kein Buchstabe mehr, dann geht man einfach wieder an das Ende der Zeile. Stehen die Buchstaben eines Paares
in der Tabelle übereinander wie beim Paar FL, so nimmt man jeweils die nächsten Buchstaben darunter - LY.
Die verschlüsselte Botschaft lautet dann:
PM XR TH TW KB UP BA LY KC KB TP KP CP
Um die Sicherheit zu erhöhen, kann man vor dem Verschlüsseln Zeichenverdopplungen durch Einfügen von zum
Beispiel X auflösen, da diese eine leichte Angriffsmöglichkeit bieten.
Durch die Verwendung von Zeichenpaaren ist das Brechen des Algorithmus im Vergleich zu Verfahren, die
nur einzelne Zeichen verwenden, schwieriger. So ist zum Beispiel eine Häufigkeitsanalyse weniger aussagekräftig
und das Erstellen von Codebüchern aufwändiger. Eine Erkenntnis die auch bei der ADFGVX-Chiffre aus Kapitel 1 umgesetzt wurde. Moderne Verfahren benutzen deshalb nicht nur zwei Zeichen, so arbeitet etwa IDEA
auf 64 Bit (also 8 Zeichen) Blöcken.
2.5
One-Time-Pad
Im 1. Weltkrieg wurde die Schwäche vieler Verschlüsselungen dramatisch sichtbar, da viele Schlachtenausgänge
durch die Durchbrechung vermeintlich sicherer Verschlüsselungen durchbrochen wurde. So zum Beispiel die
13
Zimmermann-Chiffre als auch die bereits erwähnte ADFGVX-Chiffre.
Dies weckte Bedarf nach neueren stärkeren Verfahren zur Verschlüsselung. Eines dieser Verfahren ist das OneTime-Pad. Dieses ist das einzige bekannte Verfahren, das nicht nur praktisch, sondern auch theoretisch unknackbar ist. Leider ist dieses One-Time-Pad, welches 1917 von Major Joseph Mauborgne und Gilbert Vernam
von AT&T erfunden wurde, in der Praxis schwierig umzusetzen. Folgende Bedingungen müssen nämlich erfüllt
sein:
Der Schlüssel
• muss genauso lang sein wie der Klartext
• muss streng zufällig gewählt sein
• darf nur ein einziges Mal verwendet werden
Verschlüsselt wird mit dem One-Time-Pad genauso, wie mit der Vigenère-Chiffre oder der Autokey-Chiffre, also
indem wir die Buchstaben als Zahlen darstellen (a = 0 ... z = 25):
(o + T) mod 26 = (14 + 19) mod 26 = 7 = H
Entschlüsselung:
(26 + H - T) mod 26 = (26 + 7 - 19) mod 26 = 14 = o
Wenn man nun sehr lange Texte verschlüsseln muss, steht man vor dem Problem, einen sehr langen sehr zufälligen Schlüssel erzeugen. Die Entschlüsselung dieses Textes setzt voraus, dass der Schlüssel dem Empfänger bereits
übermittelt wurde. Dies ist ein enormes logistisches Problem. Das ist auch der Grund, weshalb es nur sehr selten
eingesetzt wird. Es gibt noch ein weiteres Problem. Der Schlüssel muss einem echten Zufallsprozess entstammen.
Ein echter Zufallsprozess ist z.B. Würfeln oder eine Münze werfen oder Ausschläge eines Geigerzählers beim
Messen von radioaktivem Zerfall. Computer-Zufallsgeneratoren erzeugen leider keine echten Zufallszahlen, sie
berechnen nur die Zahlen mit Hilfe eines bestimmten Startwertes. Um also einen ¨guten¨ Schlüssel zu erhalten,
müssen man sehr, sehr oft würfeln ...
Als Schlüssel darf natürlich kein ¨richtiger¨ Text benutzt werden, da dieser wieder bestimmte statistische Eigenschaften hat. Die letzte Bedingung scheint auf den ersten Blick kein Problem darzustellen. Aber dem ist dennoch
so. Selbst wenn der Schlüsselblock mehrere Gigabytes umfasst, kann ein Kryptoanalytiker den Klartext rekonstruieren, sofern er über mehrere Chiffretexte verfügt, deren Schlüssel sich überschneiden. Dazu verschiebt er
die Chiffretexte paarweise gegeneinander und zählt die Anzahl der Übereinstimmungen (Siehe Autokorrelation
S.26). Mitunter kann das soweit gehen dass ganze Textpassagen mit dem selben Verfahren wie für die VigenèreChiffre geknackt werden kann.
Warum ist dieses für heutige Verhältnisse einfache Verfahren so sicher[6]?
Der Grund ist ein bestimmter Chiffretext kann mit derselben Wahrscheinlichkeit zu jedem der möglichen Klartexte gleicher Länge gehören. Da jede Schlüsselsequenz gleich wahrscheinlich ist (der Schlüssel muss absolut
zufällig sein!), besitzt ein Analytiker keinerlei Informationen, mit denen der den Chiffretext einer Kryptoanalyse unterziehen könnte.
Beispiel:
Klartext:
o n e t i m e p a d
Schlüssel: T B F R G F A R F M
Geheimtext: I P K L P S F H G Q
Der Schlüssel könnte ebensogut POYYAEAAZX lauten, was entschlüsselt salmoneggs ergibt oder BXFGMTMXM, was dechiffriert greenfluid bedeutet[6].
Im zweiten Weltkrieg wurde das One-Time-Pad von der englischen Entschlüsselungstruppe von Bletchley Park
14
benutzt, um dem Premierminister die Nachrichten zu übermitteln, die von den Deutschen mit der Enigma verschlüsselt worden waren und die Engländer geknackt hatten. Bis vor wenigen Jahren sollen die Gespräche über
den ¨heißen Draht¨ zwischen dem Weißen Haus und dem Kreml mit Hilfe eines One-Time-Pads verschlüsselt
worden sein.
2.6
Enigma
Unter den Spezialmaschinen, die zur Erleichterung der routinemäßigen Chiffrierung und Dechiffrierung erfunden und über Jahre und Jahrzehnte weiterentwickelt wurden, ist die Enigma[12] wahrscheinlich weltweit die
bekannteste. Mit ihr wurde während des Zweiten Weltkriegs der größte Teil der Funksprüche der deutschen
Wehrmacht und Marine vor dem Absenden verschlüsselt und nach dem Empfang wieder entschlüsselt. Man
nimmt an, daß während des Zweiten Weltkriegs 100 000 bis 200 000 Enigma Maschinen gebaut wurden.
Die Geschichte der Computertechnik wird von der Zeit der Enigma bis heute von der Chiffrierung und den
Bemühungen um die Brechung unbekannter Codes mitbestimmt. Wenn in der heutigen Situation des stürmischen Zusammenwachsens von Computern und digitalisierter Telekommunikation die Chiffrierung eine größere
Rolle spielt als jemals zuvor in der Geschichte, läßt die Historie der Enigma ein wenig ahnen, was alles durch
die systematische Veränderung von Buchstaben in der Weltgeschichte bewegt werden kann. Ein anderer Aspekt
betrifft sicherlich unser wachsendes Wissen über die historischen Zusammenhänge während des Zweiten Weltkriegs, wodurch die Einschätzungen der Rolle von Chiffrierung und Code-Brechen fundierter und differenzierter
wurden. So ist die Heldenrolle der Enigma eher eine negative, was ihre technische Überlegenheit und ihre Bedeutung für den deutschen Endsieg betrifft. Sie wurde, um im Bild zu bleiben, zum Podest, auf dem die Helden
des Code-Knackens heute stehen.
Die mit der Enigma chiffrierten Funksprüche wurden während des Kriegs in der Britischen Chiffrierstelle in
Bletchley Park trotz immer neuer technischer Raffinessen dechiffriert, so daß die Alliierten diesen Teil des militärischen Funkverkehrs mit einigen Ausnahmen mithören konnten. Hierbei kam der Colossus (Abb 2.3) zum
Einsatz, für damalige Begriffe ein Großrechner.
Abbildung 2.3: Collossus
Die Erfindung des in der Enigma verwendeten Arbeitsprinzips geht auf die Jahre des Ersten Weltkriegs zurück,
als der amerikanische Bauunternehmer Edward Hugh Hebern (1869 - 1952) 1917 eine rotierende Vorrichtung zur
polyalphabetischen Substitution mit unabhängigen Alphabeten erfand. Er bot seine Chiffriermaschinen vergeblich dem amerikanischen Militär an. 1918 meldete der Ingenieur Arthur Scherbius (1878 - 1929) das Rotorprinzip
zum Patent an. Er stellte in seiner Chiffriermaschinen AG in Berlin die mit dem griechischen Wort für Rätsel
als Enigma bezeichnete Maschine her und führte sie 1923 in Bern und 1924 beim Weltpostkongreß in Stockholm
15
der Öffentlichkeit vor.
Die Enigma war damals nicht geheim. 1927 kaufte Scherbius die Patente des Niederländers Hugo Alexander Koch, der 1919 das Rotorprinzip selbst neu erfunden hatte. Die technische Weiterentwickelung der Enigma
leitete nach Scherbius Tod 1929 Willi Korn. Auch in Schweden war das Rotorprinzip 1919 unabhängig erfunden
worden. In allen Ländern war das Interesse staatlicher Stellen an diesen Maschinen zunächst gering. In Deutschland übernahm die Reichswehr die Enigma, und als mit Hitler 1933 die massive Aufrüstung eingeleitet wurde,
gehörte die Enigma zum Programm. Während des Zweiten Weltkriegs war die Enigma zwar die meistverwendete, jedoch nicht die einzige Verschlüsselungsmaschine der deutschen Stellen. Die strategischen Nachrichten
wurden mit wenigen noch komplexeren Geräten chiffriert.
Seit 1933 wurde die Enigma beim Heer, bei der Marine und beim diplomatischen Dienst weiterentwickelt.
Schon Scherbius hatte das Rotorsystem 1928 durch ein Steckbrett ergänzt, mit dem die Verschlüsselung noch
komplizierter wurde. Das Funktionsprinzip beruht auf einfachen Stromkreisen, von denen jeder eine Buchstabentaste des schreibmaschinenüblichen Tastenfelds mit einem elektrischen Lämpchen verbindet, das auf dem
Anzeigenfeld einen Buchstaben aufleuchten läßt. Mit jedem Tastendruck leuchtet ein neuer Buchstabe auf. Jeder
einzelne Stromweg führt durch jede der drei Walzen über jeweils einen vorderen und einen hinteren Kontakt bis
zur sogenannten Umkehrwalze und von dort wieder zurück durch sämtliche Walzen und zusätzlich durch die
Stecker des Steckfeldes.
Die Verschlüsselung findet durch ein recht kompliziertes System statt:
• in jeder Walze sind nicht die sich gegenüberliegenden Ein- und Ausgangskontakte miteinander galvanisch
verbunden, sondern sie sind nach einem bestimmten System gegeneinander verschränkt
• die Steckanordnung auf dem Steckbrett wird variiert
• bei jedem Tastendruck werden die Walzen nach einem bestimmten System um eine Stelle weitergedreht
• aus einem Satz von fünf werden jeweils drei ausgewählt und in jeweils neu festgelegter Reihenfolge eingesetzt
• auch die Anfangseinstellung der Walzen wird immer neu festgelegt
• an jeder einzelnen Walze wird ein Einstellring eingestellt
Beim Betrieb während des Kriegs wurden die verschiedenen Einstellungen alle acht Stunden gewechselt.
16
Teil II
Kryptoanalyse
17
Kapitel 3
Kryptoanalyse
3.1
Kryptoanalyse monoalphabetischer Chiffren
Die Kryptoanalyse ist die Wissenschaft, die sich mit dem Brechen der Verschiedenen Chiffren beschäftigt. Kryptographen und Kryptoanalytiker sind Gegenspieler. Während sich die Kryptoanalytiker mühen die Chiffren der
Kryptographen zu brechen, mühen sich Kryptographen Chiffren zu entwickeln, die eine geeignete Sicherheit
bieten.
Jahrhundertelang verwendeten die Menschen in aller Welt ausschließlich monoalphabetische Chiffren, welche
mittels einer einfachen Häufigkeitsanalyse zu knacken sind.
Hier ein Beispiel:
EHLGHUFHDVDUFKLIIUHKDWFHDVDUIXHUMHGHQWHAWGDVDOIDEHWXPGUHLEXFKVWDEHQY
HUVFKREHQDXIGLHVHZHLVHZDUHQVHLQHEHIHKOHYRUXQEHUXIHQHQDXJHQJHVFKXHWCW
Die Häufigkeitsanalyse dieses Textes liefert folgendes Ergebnis: Das geübte Auge sieht ohne jede weitere Ana-
Abbildung 3.1: Häufigkeitsanalyse und Diagramme
lyse, dass es sich bei diesem Text um einen monoalphabetisch verschlüsselten Text handelt. Diesen Clou liefert
einerseit der Koinzidenzindex (KI-Index:= 0.8338..) der nahe bei 1 liegt und anderer seits die Ähnlichkeit der
beiden Diagramme. Der Unterschied liegt im wesentlichen in einer Verschiebung beispielsweise der schwarz hervorgehobenen Säulen.
Bei einer einfachen Chiffre, wie der Ceasarchiffre, kann man sich bei deutschen Texten dabei ganz einfach
an dem ë¨ orientieren. Dies ist der häufigste Buchstabe sowohl im Deutschen als auch im Englischen (siehe
Häufigkeitstabellen 4.1 auf Seite 22), um so die Alphabetverschiebung zu ermitteln. Die Analyse ergibt nun also
ein Alphabetverschiebung um 3 Buchstaben und folgenden Klartext:
BEI DER CAESAR CHIFFRE HAT CAESAR FUER JEDEN TEXT DAS ALPHABET UM
18
DREI BUCHSTABEN VERSCHOBEN AUF DIESE WEISE WAREN SEINE BEFEHLE VOR
UNBERUFENEN AUGEN GESCHUETZT
Dies ist natürlich nur ein einfaches Beispiel. Generell kann man daraus aber folgende Erkenntnis ableiten:
Es gibt Buchstaben, die ihrer Häufigkeit wegen auffallen. So etwa die Buchstaben e und s. Und genau da
liegt das Problem: Leider kommen nicht alle Buchstaben mit gleicher Häufigkeit vor. Das e kommt mit einer
Häufigkeit von durchschnittlich 17,4 Prozent, das s mit 7,3, r mit 7, a mit 6,5 usw. vor (siehe Tabelle unten).
Das klägliche Schlusslicht dieser Reihe ist übrigens das q, das nur mit 0,02 Prozent vertreten ist.
Um einen verschlüsselten Text zu knacken, untersucht man zunächst die Häufigkeiten von jedem Geheimtextzeichen und probiert dann verschiedene Buchstaben aus, die aufgrund ihrer Häufigkeit passen könnten. Die
Tatsache, dass sich die Häufigkeiten je nach Art des Textes (wissenschaftlich, politisch, privat ...) unterscheiden,
stellt in der Regel kein großes Hindernis dar, da der Angreifer, der den Text abgefangen/gefunden hat, oft schon
erraten kann, um was für eine Art es sich handelt.
Führen die Einzelbuchstabenanalysen nicht zum Ziel sucht man nach Bigrammen (4.2 auf Seite 22) Kurze
Texte sind schwieriger zu knacken, aber Computer können viele Möglichkeiten in kurzer Zeit durchprobieren
(jeder normale Home-PC vielleicht 1 Million pro Sekunde) und daher auch Buchstaben ausprobieren, die normalerweise weniger häufig vorkommen. (siehe Häufigkeitstabellen 4.1 auf Seite 22)
Bei Substitutionschiffren wie der ¨Großen Chriffre¨(siehe Seite 7) muss man anders herandgehen, da es sich
beim Geheimtext um eine Ersetzung ganzer Silben und Wörter handelt. Aber auch hier kann man mit dem
gleichen Ansatz Treffer landen. So führt auch hier eine Häufigkeitsanalyse zum Ziel. Die häufigsten der 578
Zahlen repräsentieren auch hier die in der französichen Sprache am häufigsten vorkommenden Silben. Hat man
einen solchen Ansatz erstmal gefunden ist der Rest ein Kinderspiel.
3.2
3.2.1
Kryptoanalyse polyalphabetischer Chiffren
Allgemeines
Im 18. und vorallem im 19. Jahrhundert waren die Schwarzen Kammern in Europa sehr aktiv beider massenweise Entschlüsselung diplomatischer Post. Am effektivsten arbeitete die Wiener schwarze Kammer. Sie arbeitete
wie die Post. Morgens um 7 Uhr kam die diplomatische Post der ausländischen Botschaften zur Analyse herein
umd dann vollständig kopiert zu werden und dann an die entsprechenden Empfänger weitergeleitet zu werden.
Mittags war die ganze Post abgearbeitet. Eine enorme Leistung wenn man bedenkt, dass hunderte, wenn nicht
sogar tausende Briefe kopiert wurden. Danach wurden die Texte praktisch am Laufband entschlüsselt.
Das ist eine beeindruckende Leistung. Doch wie geht man dabei vor?
3.2.2
Das Wichtigste ist die Mustersuche...
Bei der Enschlüsselung monoalphabetischer Verschlüsselungen wurde erklärt, dass es häufig genügt einen Text
auf Häufigkeitsverteilungen von Buchstaben und Buchstabenkombinationen zu untersuchen, um zu einem zufriedenstellenden Ergebnis zu kommen. Das geht bei polyalphabetischen Chiffren nicht.
Der Grund dafür ist, dass es der der Sinn von polyalphabetischen Chiffren ist, Buchstabenhäufigkeiten zu
verwischt. Das stellte Kryptoanalytiker lange Zeit vor große Probleme. Abhilfe schafften Analyseverfahren, wie
der Kasiski-Test und Schätzverfahren, wie der Friedman-Test. Beide dienen dazu, bei der Vigenère-Chiffre die
Schlüsselwortlänge zu ermitteln. Der Kasiski-Test ist sehr aufwendig und den Friedman-Test, der sich auf aufwendige statistische Berechnungen und Annahmen stützt, liefert recht ungenaue Ergebnisse. Trotzdem ist die
Kombination sehr effektiv, um die Vigenère-Chiffre zu kompromitieren.
Aus der Nachrichtentechnik stammt eine weitere Technik, welche man weit effektiver und auch vielseitiger einsetzen kann als die oben erwähnten. Es heißt Autokorrelation[1](siehe Seite 26). Hierbei wird der verschlüsselte
19
buchstabenweise an sich selbst vorbeigeführt. Bei jedem Schritt wird die Anzahl gleicher Buchstaben notiert,
die untereinanderstehen. Das Ergebnis kann man als Säulendiagramm darstellen:
Abbildung 3.2: Autokorrelation vigenère-verschlüsselter Text
Abbildung 3.3: Autokorrelation autokey-verschlüsselter Text
Auffällig ist das unterschiedliche Ergebnis der Autokorelation . Während das Ergebnis der Vigenèrechiffre eine
typische Kammstruktur aufweist, liefert die Autokey-Chiffre lediglich einen einzigen Ausschlag. Dieser ist im
übrigen die einzige Schwäche, die diese Chiffre aufzuweisen scheint. Da die Gleichverteilung der mit Autokey
verschlüsselter Texte sehr hoch ist. Dies ist messbar mit Hilfe eine Entropieanalyse (siehe Seite 26). Je näher
der Wert bei 4.7 liegt desto stärker die Chiffre. Bei Autokey-verschlüsselten Texten liegt dieser Wert meist über
4.5.
Der Graph den die Autokorrelation bei einer Vigenèrechiffre liefert über den mittleren Abstand der ¨Kammzähne¨
die Schlüssellänge. Bei der Autokeychiffre liegt der eine starke Ausschlag genau an der Stelle, welche die genaue
Schlüssellänge beschreibt.
An diesen beiden Beispielen sieht man bereits, wie unterschiedlich die einzelnen Chiffren auf die Analyseverfahren reagieren. Das Ergebnis ist wie ein Fingerabdruck und erlaubt eine schnelle Identifikation der Chiffre.
3.2.3
...und wieder monoalphabetisch!
Bei der Vigenère-Chiffre geht man nach erfolgreicher Schlüsselwortlängenermittlung so vor, dass man den Text
buchstabenweise nacheinander ind soviele Haufen teilt, wie die ermittelte Schlüsselwortlänge es vorgibt. Jeder
dieser Haufen ist mit dem selben Buchstaben verschlüsselt worden. Wir wenden jetzt also ganzz elementare Techniken an, um die Alphabetverschiebung zu ermitteln. Danach werden die ermittelten Verschiebungen
Buchstaben zugeordnet und man erhält das Schlüsselwort.
(A..Z) := (0..25)
Die Autokeychiffre erfordert ein anderes Vorgehen. Auch hier wird die Chiffre in so viele Einzelströme zerlegt, wie es die ermittelte Schlüsselwortlänge vorgibt. Jeder dieser Ströme ist mit einem anderen Buchstaben
verschlüsselt. Im Gegensatz zur Vigenèrechiffre hilft uns eine Häufigkeitanalyse nicht weiter. Hier müssen wir
probieren...
Die Ströme werden mit jedem Buchstaben des Alphabets dekodiert und dann wird eine Häufigkeitsanalyse
durchgeführt. Die Buchstabenverteilung wird mit der normalen Buchstabenverteilung des Alphabetes korreliert. Zur Kontrolle wird gleichzeitig mittels Friedman-Test darauf getestet, ob der Text monoalphabetisch ist.
Von den 26 Ergebnissen, wählen wir die beiden mit dem niedrigsten Wert für den Friedman-Test und Treffer
ist derjenige, welcher bei der erwähnten Korrelation die genaueste Übereinstimmung erziehlt.
Nach dem Ermitteln der einzelnen Schlüsselwortbuchstaben ergibt sich das Schlüsselwort. Ist die Chiffre beschädigt
20
kann man das Verfahren trotzdem verwenden. Es ergibt sich ein anderes Schlüsselwort aber der Text bleibt ermittelbar (siehe 2.2)[5].
3.2.4
Der Weisheit letzter Schluß...
... ist dies sicher nicht.
Diese beiden Beispiele sind sicherlich nicht die einzigen Ansätze die es gibt um diese beiden Chiffren zu knacken.
Aber die Komplexität des Lösungsverfahrens ist lediglich N 2 . Damit ist es wesentlich effizienter als das von Kasiski, welcher sich nicht unterhalb von N 3 implementieren läßt.
Wenn jemand sich selbst an den beschriebenen Chiffren versuchen will, sei der ¨Kryptographiespielplatz¨[5]
wärmstens empfohlen. Auserdem sei auf den beiliegenden Quellcode verwiesen, mit denen es möglich ist, wesentliche Elemente nachzubauen ... und nachzu vollziehen (siehe Seite 33).
Eines wird beim Experimentieren mit den verschiedenen Chiffren klar. Die Kombination verschiedener polyalphabetischer Chiffren führt zu einer stärkeren Chiffre. So ist die Kombination
Autokey→Vigenère→Autokey→Vigenère
so stark, auch wenn man das selbe Schlüsselwort für jeden Verschlüsselungsschritt nimmt, dass es zu einer
derartigen Gleichverteilung der Buchstaben führt, dass der resultierende Geheimtext mit den vorgestellten
Verfahren nicht mehr zu brechen ist, und es wird um so schwerer je länger die Texte sind.
21
Kapitel 4
Mathematische Grundlagen
4.1
Häufigkeitstabellen
Buchstabe
Häufigkeit[%]
Buchstabe
Häufigkeit[%]
Buchstabe
Häufigkeit[%]
A
6.51
J
0.27
S
7.27
B
1.89
K
1.21
T
6.15
C
3.06
L
3.44
U
4.35
D
5.08
M
2.53
V
0.67
E
17.40
N
9.78
W
1.89
F
1.66
O
2.51
X
0.03
G
3.01
P
0.79
Y
0.04
H
4.76
Q
0.02
Z
1.13
I
7.55
R
7.00
Tabelle 4.1: Häufigkeitstabelle für Buchstaben in deutschen Texten[2]
Buchstabe
Häufigkeit[%]
EN
3.88
ER
3.75
CH
2.75
TE
2.26
DE
2.00
ND
1.99
EI
1.88
IE
1.79
IN
1.67
ES
1.52
Tabelle 4.2: Häufigkeitstabelle für Bigramme in deutschen Texten[2]
Sprache
Deutsch
Englisch
Esperanto
Flämisch
Französisch
Interlingua
Italiänisch
Latein
Portugisisch
Spanisch
Schwedisch
Reihenfolge
E N I R S A
E T A O N I
A I E O N S
E N I A R D
E A N R S I
E A I L N O
E A I O L N
I E U T A M
E A O S I D
E A O S R N
A E N R T S
der
D T
R S
L T
T O
T U
S T
R T
S N
R T
I D
I O
Buchstaben nach
U G H O L B M C
H L D C U P F M
R J U K M P D G
G L S H V R M U
O L D C M P V B
R U D C M P V G
S C D M P U V G
R O D L V C P Q
N C P U M L V F
L C T U M P G W
M G K L D V F B
Häufigkeit
W F K V Z P
W Y B G V K
C V B F Z H
W J B Z C P
F G H Q J Z
B F H X Q J
Z F B H Q
B F G X H J
G Q H J X Z
B Q V H F Z
C H P U Y J
J
Q
Q
F
X
W
Q
X
W
X
Y
Y
X
J
X
Y
Z K
K W Y Z
B K W Y
X Q W Z
Tabelle 4.3: Buchstaben-Rangfolge verschiedenener Sprachen[8]
22
Y
Z
Y
Q
4.2
Verfahren zur Analyse
Die hier vorgestellten Verfahren sind nur eine kleine Auswahl an Techniken, die bei der Enschlüsselung von
klassischen Chiffren zum Einsatz kommen können. Dennoch reichen sie bereits aus elaborate Chiffren, wie die
Vigenère-Ciffre oder gar die Autokey-Stromchiffre, zu brechen[5].
4.2.1
Häufigkeit
Die Häufigkeitsanalyse stellt das elementarste Werkzeug zur Analyse dar. Mit ihr kann man ermitteln, welcher die Verteilung von Buchstaben, Wörtern oder Symbolen in Texten ist. Dokumentierte Verwendung dieser
Techniken gehen bis ins 9. Jahrhundert zurück.
4.2.2
Kasiski-Test
Der Kasiski-Test wurde 1863 von dem preußischen Infanteriemajor Friedrich Wilhelm Kasiski veröffentlicht. Er
beruht auf folgender Überlegung:
Wenn zwei gleiche Buchstabenfolgen verschlüsselt werden, entstehen daraus im Normalfall verschiedene Geheimtexte, da über ihnen verschiedene Buchstaben des Schlüssels stehen und sie somit mit verschiedenen Geheimtextalphabeten verschlüsselt werden.
Hier ein Beispiel:
Klartext: DERKLARTEXTWIRDZUMGEHEIMTEXT
Schlüssel: PLUTOPLUTOPLUTOPLUTOPLUTOPLU
Geheimtext: SPLDZPCNXLIHCKROFGZSWPCFHTIN
Wenn der Abstand dieser Buchstabenfolgen aber ein Vielfaches der Schlüssellänge ist, dann werden beide Buchstabenfolgen mit den gleichen Geheimtextalphabeten verschlüsselt und es entsteht zweimal der gleiche Geheimtext.
Hier ein Beispiel:
Klartext: DERKLARTEXTWERDEGEHEIMTEXT
Schlüssel: PLUTOPLUTOPLUTOPLUTOPLUTOP
Geheimtext: SPLDZPCNXLIHYKRTRYASXXNXLI
Um auf die Schlüsselwortlänge zu kommen, muss der Text allerdings länger sein, als der dieses Beispiels, denn
es ist schon ein großer Zufall, wenn ein so kurzer Klartext überhaupt zwei gleiche Buchstabenfolgen enthält. Die
Wahrscheinlichkeit dafür, dass ihr Abstand auch noch ein Vielfaches der Schlüsselwortlänge ist, ist sehr gering.
Bei langen Texten funktioniert das Verfahren allerdings sehr gut:
Man sucht also gleiche Buchstabenfolgen im Geheimtext und bestimmt ihren Abstand. Buchstabenfolgen, die
kürzer als drei Zeichen sind, sollten dabei ignoriert werden, da sie oft zufällig entstehen. So tritt im ersten
Beispiel die Zeichenfolge PC im Geheimtext zweimal auf, sie ist aber einmal aus dem Klartext AR und beim
zweiten Mal aus EI entstanden.
Natürlich können auch längere gleiche Zeichenfolgen im Geheimtext zufällig entstehen, dies geschieht aber
deutlich seltener. Die gesuchte Schlüssellänge ist also ein Teiler der Abstände der gleichen Zeichenfolgen, die
aus mindestens drei Buchstaben bestehen. Vorsichtiger ausgedrückt ist sie ein Teiler der meisten dieser Zeichenfolgen. Wenn man die Primfaktorzerlegung aller Abstände vergleicht, lassen sich gleiche Teiler schnell finden
und außerdem fallen auch die zufällig entstandenen Abstände auf, da sie meist keine gemeinsamen Teiler mit
den übrigen Abständen haben. Nachdem man die gleichen Teiler bestimmt hat, ist die genaue Schlüssellänge
allerdings noch nicht bekannt, es ist lediglich anzunehmen, dass der größte gemeinsame Teiler der Abstände ein
Vielfaches der gesuchten Schlüssellänge ist.
Die ermittelten Abstände könnten beispielsweise 30, 75 und 105 sein, woraus man allerdings nicht schließen
23
kann, dass die Schlüssellänge 15 ist, denn 3 und 5 wären ebenfalls möglich. Der Kasiski-Test liefert also nur ein
Vielfaches der Schlüssellänge.
4.2.3
Koinzidenzindex / Friedman-Test
Mit dem Friedman-Test[2], der 1925 von William Friedman entwickelt wurde, lässt sich hingegen die Größenordnung der Schlüssellänge berechnen. Als Grundlage für die Herleitung der entsprechenden Formel dienen folgende
Überlegungen:
¡n1 ¢
n · (ni − 1)
¡n2 ¢ = i
(4.1)
n · (n − 1)
2
Es sei eine beliebige Buchstabenfolge der Länge n gegeben. Die Anzahl der einzelnen darin enthaltenen Buchstaben werden mit n1 (für das A) bis n26 (für das Z ) bezeichnet. Es soll jetzt die Wahrscheinlichkeit dafür
berechnet werden, dass zwei zufällig herausgegriffene Buchstaben gleich sind. Dazu bestimmt man zuerst die
Wahrscheinlichkeit dafür, dass zwei beliebige Buchstaben dieser Buchstabenfolge As sind. Sie beträgt:
26
X
ni · (ni − 1)
i=1
n · (n − 1)
=
P26
ni · (ni − 1)
n · (n − 1)
i=1
(4.2)
Für B gilt dasselbe mit n2 statt n1 usw. Werden alle diese Einzelwahrscheinlichkeiten von A bis Z addiert,
enthält man die gesuchte Wahrscheinlichkeit für ein Paar aus zwei gleichen Buchstaben:
P26
ni · (ni − 1)
I = i=1
(4.3)
n · (n − 1)
Dieser Wert wird mit I (oder k, dem griechischen κ Kappa) bezeichnet und stellt den sogenannten Koinzidenzindex dar:
P26
ni · (ni − 1)
I = i=1
(4.4)
n · (n − 1)
Als nächstes sollen die Wahrscheinlichkeiten für das Auftreten eines bestimmten Buchstaben bekannt sein. Die
Wahrscheinlichkeit, dass ein zufällig gewählter Buchstabe ein A ist, sei p1 usw. Dann wäre die Wahrscheinlichkeit,
zufällig zwei As zu finden etwa p21 . Sie wäre genau p21 , wenn es erlaubt wäre, einen Buchstaben zweimal zu wählen.
Der Text soll so lang sein, dass der dadurch entstehenden Fehler nicht ins Gewicht fällt. Durch Summieren dieser
Werte soll wieder die Wahrscheinlichkeit für ein Buchstabenpaar aus gleichen Buchstaben bestimmt werden.
Der auf diese Weise errechnete Wert entspricht also etwa dem Koinzidenzindex:
I≈
26
X
p2i
(4.5)
i=1
Für die deutsche Sprache lassen sich für die Wahrscheinlichkeiten p1 bis p26 die Häufigkeiten aus Tabelle 1
einsetzen. Man erhält in diesem Fall folgenden Wert:
I≈
26
X
p2i = 0.0762
(4.6)
i=1
Für eine Buchstabenfolge, in der jeder Buchstabe mit der gleichen Wahrscheinlichkeit auftritt, gilt pi =
Dann erhält man einen deutlich kleineren Wert:
I≈
26
X
1
( )2 = 0.0385
26
i=1
1
26 .
(4.7)
Als nächstes soll die Wahrscheinlichkeit berechnet werden, mit der zwei zufällig aus einem Vigenère-chiffrierten
Geheimtext gewählte Buchstaben gleich sind. Diese Wahrscheinlichkeit hängt von der Länge des Schlüssels ab,
die im folgenden Text mit L bezeichnet wird. Wenn der Geheimtext zeilenweise in eine Tabelle mit L Spalten
geschrieben wird, dann wurden alle Buchstaben einer Spalte mit dem selben Geheimtextalphabet verschlüsselt.
Da alle Buchstaben einer Spalte mit der gleichen monoalphabetischen Chiffrierung verschlüsselt wurden, ist die
24
Häufigkeitsverteilung unter ihnen erhalten geblieben. Die Wahrscheinlichkeit, hier zwei gleiche Buchstaben zu
n
finden ist also etwa 0,0762. Da es L Spalten mit jeweils L
Buchstaben gibt (Rundungsfehler können bei großen
Texten vernachlässigt werden), lässt sich die Anzahl der Buchstabenpaare aus gleichen Spalten folgendermaßen
errechnen:
1 n−L
n · (n − L)
1 n n
)=
(4.8)
L · · · ( − 1) = n · · (
2 L L
2
L
2·L
n
n
Zur Erläuterung: Es gibt L
Möglichkeiten, den ersten Buchstaben in einer Spalte zu wählen und L
− 1 Möglich1
keiten für den zweiten Buchstaben. Da die Reihenfolge keine Rolle spielt, wird mit 2 multipliziert. Dies wäre
die Anzahl der Buchstabenpaare pro Spalte, also wird noch mit L multipliziert und man erhält die gesamte
Anzahl der Buchstabenpaare aus gleichen Spalten. Da unter ihnen jedes mit einer Wahrscheinlichkeit von etwa
0,0762 aus gleichen Buchstaben besteht, findet man in gleichen Spalten voraussichtlich
n · (n − L)
= 0.0762
2·L
(4.9)
Paare aus gleichen Buchstaben. Wenn das Buchstabenpaar allerdings Buchstaben aus verschiedenen Spalten
erhält, wurden sie auch mit verschiedenen Chiffrierungen verschlüsselt (Voraussetzung ist, dass der Schlüssel
nur aus verschiedenen Buchstaben besteht). Die Häufigkeitsverteilung der Geheimtextbuchstaben ist dann also
echt zufällig. Daraus ergibt sich, dass die Wahrscheinlichkeit für zwei gleiche Buchstaben in verschiedenen
Spalten etwa 0,0385 beträgt. Die Anzahl der Buchstabenpaare mit Buchstaben aus verschiedenen Spalten ist
die Anzahl aller Paare minus die oben errechnete Anzahl von Paaren mit Buchstaben aus gleichen Spalten:
µ ¶
n
n · (n − L)
n · (n − 1) n · (n − L)
n · (n − 1) · L − n · (n − L)
n2 · L − n2
n2 · (L − 1)
−
=
−
=
=
=
2
2·L
2
2·L
2·L
2·L
2·L
(4.10)
Da jedes dieser Paare mit einer Wahrscheinlichkeit von 0,0385 aus gleichen Buchstaben besteht, gibt es in
verschiedenen Spalten etwa
n2 · (L − 1)
= 0.0385
(4.11)
2·L
Paare aus gleichen Buchstaben. Addiert man die oben errechnete Anzahl, so erhält man die Anzahl aller Buchstabenpaare des Textes, die aus gleichen Buchstaben bestehen:
n · (n − L)
n2 · (L − 1)
· 0.0762 +
· 0.0385
2·L
2·L
(4.12)
Teilt man diesen Term durch die Anzahl aller Buchstabenpaare des Textes, erhält man die Wahrscheinlichkeit,
zufällig ein Paar aus gleichen Buchstaben zu finden:
n·(n−L)
2·L
2
· 0.0762 + n
¡n¢
·(L−1)
2·L
· 0.0385
(4.13)
2
Durch Umformung erhält man folgenden Term, der also eine Annäherung des Koinzidenzindexes darstellt (Die
einzelnen Zwischenschritte können im Anhang nachgelesen werden):
I≈
0.0377 · n
0.0385 · n − 0.0762
+
L · (n − 1)
n−1
(4.14)
Da man den Koinzidenzindex durch Zählen der einzelnen Buchstaben leicht ermitteln kann, muss die Gleichung
nur noch nach L aufgelöst werden und man erhält eine Formel für die Länge des Schlüssels:
L≈
0.0377 · n
(n − 1) · I − 0.0385 · n + 0.0762
(4.15)
Die Werte, die diese Formel liefert, sind zwar nicht sehr genau, aber zusammen mit den Ergebnissen des KasiskiTests lässt sich die Schlüssellänge in den meisten Fällen eindeutig bestimmen.
25
4.2.4
Entropie
Mit Hilfe des Informationsgehaltes[1] der einzelnen Nachrichten kann nun die mittlere Information berechnet
werden, die eine Quelle mit einer gegebenen Verteilung liefert. Für die Durchschnittsbildung werden die einzelnen
Nachrichten mit der Wahrscheinlichkeit ihres Auftretens gewichtet.
Entropie(p[1], p[2], ..., p[r]) := −[p[1] ∗ log(p[1]) + p[2] ∗ log(p[2]) + ... + p[r] ∗ log(p[r])]
Die Entropie einer Quelle bezeichnet somit die sie charakterisierende Verteilung. Sie misst die Information, die
man durch Beobachten der Quelle im Mittel gewinnen kann, oder umgekehrt die Unbestimmtheit, die über die
erzeugten Nachrichten herrscht, wenn man die Quelle nicht beobachten kann.
Anschauliche Beschreibung der Entropie
Die Entropie gibt die Unsicherheit als Anzahl der notwendigen Ja / Nein-Fragen zur Klärung einer Nachricht
oder eines Zeichens an. Hat ein Zeichen eine sehr hohe Auftrittswahrscheinlichkeit, so hat es einen geringen Informationsgehalt. Dies entspricht etwa einem Gesprächspartner, der regelmäßig mit ja antwortet. Diese Antwort
lässt auch keine Rückschlüsse auf Verständnis oder Aufmerksamkeit zu. Antworten, die sehr selten auftreten,
haben einen hohen Informationsgehalt.
Extremwerte der Entropie
Für Dokumente, die ausschließlich Großbuchstaben enthalten, ist die Entropie mindestens 0 bit/char (bei einem
Dokument, das nur aus einem Zeichen besteht) und höchstens log(26) bit/char = 4,700440 bit/char (bei einem
Dokument, in dem alle 26 Zeichen gleich oft vorkommen).
Für Dokumente, die jedes Zeichen des Zeichensatzes (0 bis 255) enthalten können, ist die Entropie mindestens 0 bit/char (bei einem Dokument, das nur aus einem Zeichen besteht) und höchstens log(256) bit/char =
8 bit/char (bei einem Dokument, in dem alle 256 Zeichen gleich oft vorkommen).
4.2.5
Autokorrelation / Korrelation
Autokorrelation[1]
Die Autokorrelation eines Dokuments ist eine Kennzahl für die Ähnlichkeit von Teilen des Dokuments. Mit
Hilfe der Autokorrelation kann unter Umständen die Schlüssellänge eines verschlüsselten Dokuments ermittelt
werden. (z.B. bei Vigenère und Autokey)
Die Autokorrelationsfunktion C(t) misst die Ähnlichkeit einer Folge (s[i]) = s[1]s[2]... und der um t Stellen
verschobenen Folge (s[i + t]) = s[t]s[t + 1]... .
Man betrachtet einen Folgenabschnitt der Länge n und definiert: A(t) := Anzahl der übereinstimmenden Glieder der Folgen (s[i]) und (s[i + t]) im betrachteten Abschnitt. D(t) := Anzahl der nicht übereinstimmenden
Glieder der Folgen (s[i]) und (s[i + t]) im betrachteten Abschnitt.
Die Autokorrelationsfunktion C(t) =
A(t)−D(t)
n
.
Im Falle von endlichen Folgen wird die Folge s (azyklisch) um t Positionen verschoben, das heißt die Folge
(s[i + t]) hat nur n-t Folgenglieder (wenn n die Länge der Folge (s[i]) ist). Zur Berechnung der Autokorrelation
betrachtet man nun die Folgen s[1]s[2]...s[n − t + 1] und s[t]s[t + 1]...s[n] und berechnet deren Korrelation.
Die Autokorrelationsfunktion wird unter anderem bei der Ermittlung der Periodenlänge zur automatischen
Analyse des Vigenère-Verschlüsselungsverfahrens und Verschlüsselung durch byteweise Addition und exklusives
Oder benutzt. Siehe dazu das Kapitel Szenarien.
26
Korrelation[1]
Die folgenden Aussagen über Korrelation gelten hier für eine unabhängige gleichverteilte Binärfolge:
• Binärfolge heißt, dass die einzelnen Ereignisse der Zufallsfolge den Wert 1 oder 0 annehmen.
• Unabhängig heißt, dass die Wahrscheinlichkeit für das Eintreffen des (n+1)-ten Ereignisses unabhängig
von allen Werten der n vorherigen Ereignisse ist.
• Gleichverteilt bedeutet für die Ereignisse der Zufallsfolge, dass die Wahrscheinlichkeit einer 0 gleich der
Wahrscheinlichkeit einer 1 ist.
Die Ähnlichkeit zweier Folgen wird üblicherweise durch ihre Korrelation gemessen. Die Korrelation C zweier
Folgenabschnitte der Länge n berechnet sich als die Zahl A der übereinstimmenden und der Zahl D der nicht
übereinstimmenden Folgenglieder nach der Formel:
C :=
A−D
n
Der Erwartungswert für die Korrelation zweier unabhängiger Zufallsfolgen ist demnach also Null. Zwei Folgen,
die häufiger übereinstimmen, haben dagegen einen positiven Korrelationswert. Im Grenzfall völliger Übereinstimmung ist A = n, D = 0 und daher C = 1. Umgekehrt erhält man bei weniger als n2 Übereinstimmungen
eine negative Korrelation. Der Betrag der Korrelation zweier Folgen ist daher ein Maß für deren Abhängigkeit.
27
Teil III
Anhang
28
Kapitel 5
Kurze Geschichte der Kryptographie
Menschliche Schrift gibt es seit rund 6000 Jahren; seit über 3000 Jahren wird diese verschlüsselt.
ca.
ca.
ca.
ca.
ca.
ca.
1900 v.Chr.
1000 v.Chr.
600 v.Chr.
500 v.Chr.
200 v.Chr.
100 - 44 v.Chr.
ca. 500
n.Chr.
855 n. Chr.
1412
1397
1466
1518
-
1400
Non-standard Zeichen
Mesopotamien
In Palästina werden Texte mit der Atbash verschlüsselt.
Die Griechen verschlüsseln Nachrichten mit Hilfe der Skytale.
Der Grieche Polybios beschreibt erstmals sein Polybios-System.
Julius Cäsar schreibt vertrauliche Botschaften in dem nach ihm
benannten Caesar-Code. Dies ist der bekannteste aller
monoalphabetischen Algorithmen.
In Europa beginnt die ¨Dunkle Zeit der Kryptographie¨,
d.h. sie wurde der schwarzen Magie zugeordnet. In dieser Zeit
ging viel Wissen über die Kryptographie verloren, im Gegensatz
dazu blühte die Kryptographie im persischen Raum auf.
Im arabischen Raum erscheint das erste Buch über Kryptologie.
Abu Abd al-Raham al-Khahil ibn Ahmad ibn Amr ibn Tammam al
Farahidi al-Zadi al Yahamadi beschreibt stolz in seinem Buch
unter anderem die geglückte Entschlüsselung eines für den
byzantinischen Kaiser bestimmten griechischen Codes.
Eine 14-bändige arabische Enzyklopädie beschreibt auch kryptographische
Methoden. Dabei wird neben der Substitution und der Transposition
erstmals die Methode der mehrmaligen Substitution an einem Klartextzeichen
erwähnt.
Auf Wunsch Clemens des VII. erfindet Gabrieli di Lavinde die erste
Nomenklatur (Nomenklatur-Code). Dieser Nomenklatur-Code wurde wegen seiner
Einfachheit in den nächsten 450 Jahren vor allem in diplomatischen Kreisen
verwendet.
Leon Battista Alberti (1404 - 1472), einer der führenden Kräfte der
italienischen Renaissance, veröffentlicht sein Buch ¨Modus scribendi in
ziferas¨, in dem erstmals die von ihm erfundenen Chiffrierscheiben erwähnt
werden. Albertis zahlreiche kryptologischen Leistungen beruhen auf der
Tatsache, dass er Sekretär jener Behörde war, die sich an der römischen
Kurie (päpstlicher Hof) mit Geheimschriften befasste. Er wird als ¨Vater
der Kryptographie¨ bezeichnet.
Im deutschsprachigen Raum erscheint das erste gedruckte Buch über
Kryptologie. Der Verfasser ist Johannes Trithemius.
29
1586
1628
1700
1795
1854
1854
1857
1860
1883
1891
1917
1919
1921
1922
1923
1929
1941
1949
1973
1975
1976
1977
1978
Das Buch ¨Tractié de Chiffre¨ des französischen Diplomaten Blaise
de Vigenère erscheint. Seine Verschlüsselungsmethode, die später nach ihm als
Vigenère-Code benannt wurde, wird so der Öffentlichkeit zugänglich gemacht.
Dieser Code ist der bekannteste unter allen polyalphabetischen Algorithmen.
Antione Rissignol wird der erste vollzeitlich angestellte Kryptoanalytiker,
nachdem seine Entschlüsselung einer feindlichen chiffrierten Botschaft die
Belagerung Realmonts durch die Hugenotten beendete. Seitdem sind Kryptoanalytiker
ein fester Bestandteil des militärischen Apparats.
Der russische Zar benutzt eine große Code-Tabelle von 2000-3000 Silben und Worten
zur Chiffrierung seiner Botschaften.
Thomas Jefferson entwickelt den ersten Chiffrierzylinder namens ¨wheel
cipher¨. Er benutzte sie aber nie, so dass sie in Vergessenheit geriet bzw. nie
der Öffentlichkeit zugänglich wurde. Deshalb wurde der Chiffrierzylinder parallel
zu Jeffersons an unterschiedlichen Orten nochmals erfunden.
Der Engländer Charles Babbage erfindet einen Chiffrierzylinder, ähnlich der
¨wheel cipher¨.
Der englische Physiker Charles Wheatstone erfindet eine Chiffre, die mit einer
5*5 Matrix arbeitet. Sein Freund Lord Lyon Playfair Baron von St. Andrews
machte diese Chiffre in den höheren militärischen und diplomatischen Kreisen des
viktorianischen Englands bekannt. Die Chiffre bekam so den Namen Playfair-Code.
Beauforts Cipher
Friedrich Kasiski und William F. Friedman entwickeln statistische Methoden zur
Kryptoanalyse, die auch den bis dahin als unknackbar geltenden Vigenère-Code
entschlüsseln.
¨La Cryptographie militaire¨ von Auguste Kerckhoff von Nieuwendhoff
erscheint. Es gilt als Meilenstein in der Kryptographie der Telegraphenzeit.
Beinhaltet die ¨Prinzipien von Kerckhoff¨ für die Kryptologie.
Der französische Major Etienne Bazeries erfindet einen Chiffrierzylinder:
sein Bazeries-Zylinder war der ¨wheel cipher¨ im Prinzip ähnlich.
Der Amerikaner Gilbert S. Vernam entdeckt und entwickelt das Öne Time-Pad¨.
Magelin Maschinen
Der Kalifornier Edward Hebern baut die erste Chiffriermaschine nach dem Rotor-Prinzip.
Thomas Jeffersons ¨wheel cipher¨ wird in den USA entdeckt, von der US-Marine
weiterentwickelt und fand so bis in den 2. Weltkrieg Anwendung.
Vorstellung der vom deutschen Ingenieur Arthur Scherbius entwickelten Rotormaschine
Ënigma¨ auf dem internationalen Postkongress. Mit der Gründung der
¨Chiffriermaschinen AG¨ vermarktet A. Scherbius seine Enigma in alle Welt.
Hill-Chiffre
Dekodierung der japanischen Angriffsmeldung für den 2. Weltkrieg (viele
Historiker meinen, dass die Kryptologie im 2. Weltkrieg ein Jahr Krieg erspart hat).
Shannon
La Padula
Diffie und Hellman zeigen, dass Public Key-Verfahren theoretisch möglich
sind, obwohl sie das Gegenteil beweisen wollten.
Diffie-Hellman Schlüsselaustausch
Der ab 1975 von IBM entwickelte DES (Data Encryption Standard) wird zum
Standardverfahren auserkoren.
Das nach seinen Entwicklern Ronald Rivest, Adi Shamir und Leonard Adleman
benannte RSA-Verfahren wird veröffentlicht. Es ist das erste praktisch
einsetzbare Public Key-Verfahren und es gilt als innovativster Beitrag der
kryptologischen Forschung unseres Jahrhunderts.
30
1985
1986
1990
1991
1997
10/2000
Goldwasser, Micali und Racoff stellen sog. Zero Knowledge-Verfahren vor (Blind
Signatures).
Unabhängig voneinander schlagen Neal Koblitz und Victor Miller vor,
Elliptische Kurven im Bereich der Public Key-Kryptographie einzusetzen.
Xueija Lai und James Massey entwickeln das IDEA-Verfahren, das z.B. in der
Kryptologiesoftware PGP (Pretty Good Privacy) von Phil Zimmermann eingesetzt wird.
DSA, eingeführt durch das NIST.
Known-Plaintext-Attacke auf DES erfolgreich von EFF durchgeführt.
Als AES (Advanced Encryption Standart) wird von NIST nach einem langen
öffentlichen Ausschreibungsverfahren der Algorithmus Rijndael zum Nachfolger
von DES gewählt.
31
Kapitel 6
Begriffe, Definitionen und
Abkürzungen
mod
Kryptographie
Krypt(o)analyse
Kryptoanalytiker
Angriff, Attacke
Kryptologie
Chiffre
Chiffrierung
Dechiffrierung
Geheimtext
Klartext
Modulo, Operator für Restdivision
ist die Wissenschaft von der Verschlüsselung von Daten.
Ein Kryptograph entwickelt kryptographische Verfahren zur
Verschlüsselung von Daten.
beschäftigt sich mit der Analyse von verschlüsselten
Daten. Das Ziel eines Kryptoanalytiker ist es, eine
verschlüsselte Nachricht zu knacken. Er versucht
Schwachstellen in einem kryptographischen System zu
finden und diese für das ¨Knacken¨ des Verfahrens
auszunutzen.
(Angreifer) ist jemand, der versucht, ein kryptographisches
System anzugreifen, z.B. mit Hilfe von Kryptoanalyse.
Ein sog. Ängriff ¨ auf ein kryptographisches System
bezeichnet ein Verfahren, mit dem Schwachstellen in diesem
System ausgenutzt werden mit dem Ziel, eine verschlüsselte
Botschaft zu entschlüsseln, d.h. lesbar zu machen
(¨knacken¨). Angriffe sind das Ergebnis
einer erfolgreichen Kryptoanalyse.
vereinigt Kryptographie und Kryptoanalyse. Ein Kryptologe ist
also auf beiden Gebieten tätig. Er entwickelt selbst
kryptographie Algorithmen und führt Tests an anderen
Verfahren durch.
ist ein Synonym für ein Verschlüsselungsverfahren.
ist ein Synonym für Verschlüsselung; damit kann aber auch ein
Verschlüsselungs-Verfahren gemeint sein, kann also auch synonym
zu Chiffre verwendet werden.
ist ein Synonym für Entschlüsselung.
ist das Resultat der Verschlüsselung.
(auch Chiffrat, Geheimtext)
der unverschlüsselte Text.
32
Kapitel 7
Sourcecode
Datei: fkt_coder.php
<?
########################################################
##
## Bibliothek für Kodier und Dekodieralgorithmen
## Version 1.3, Marcel Brätz, 30.04.2004
##
########################################################
## Autokey-Chiffre v1.0, baut auf Vigenère-Chiffre auf
########################################################
function kodAutokey($orgtxt, $key, $alfa){
$key2 = $key.$orgtxt;
$codtxt= kodieren($orgtxt, $key2, $alfa);
return $codtxt;
}
function dekAutokey($codtxt, $key, $alfa){
$offset=strlen($key);
$orgtxt=dekodieren(substr($codtxt,0,$offset), $key, $alfa);
for ($t=$offset;$t<(strlen($codtxt));$t++){
$orgtxt.=dekodieren(substr($codtxt,$t,1), substr($orgtxt,$t-$offset,1), $alfa);
}
return $orgtxt;
}
########################################################
## Vigenère-Chiffre v1.0
########################################################
function kodieren($orgtxt,$key,$alfa){
// Buchstabenweise Verchiebekodierung
// monoalphabetisch bei Schlüssellänge 1
// sonst polyalphabetisch
$laengetxt=strlen($orgtxt);
$laengekey=strlen($key);
for($t=0;$t<$laengetxt;$t=$t+1){
$keytxt .= substr($key,($t%$laengekey),1);
}
$wertbuch = indexVonBuchstabe($alfa,substr($orgtxt,$t,1));
$wertkey = indexVonBuchstabe($alfa,substr($keytxt,$t,1));
$codtxt
= $codtxt.buchstabeVonIndex($alfa,($wertbuch+$wertkey)%26);
}
33
return $codtxt;
}
function dekodieren($codtxt,$key,$alfa){
// siehe kodieren
$laengetxt=strlen($codtxt);
$laengekey=strlen($key);
$keytxt .= substr($key,($t%$laengekey),1);
}
$wertbuch = indexVonBuchstabe($alfa,substr($codtxt,$t,1));
$wertkey = indexVonBuchstabe($alfa,substr($keytxt,$t,1));
if ($wertbuch<$wertkey){
$wertbuch=$wertbuch+26;
}
$orgtxt
= $orgtxt.buchstabeVonIndex($alfa,($wertbuch-$wertkey)%26);
}
return $orgtxt;
}
########################################################
## Funktionen zur Erzeugung neuer Alphabete
########################################################
function createMulAlfa($alfa, $key){
// erzeugt ein Alphabet auf für eine Multiplikative Chiffre
for($t=0;$t<26;$t++){
$alfa2[$t]=buchstabeVonIndex($alfa,(indexVonBuchstabe($alfa,$alfa[$t])*$key)%26);
}
return $alfa2;
}
function rotieren($alfa, $key){
// Rotiert ein Alphabet
for($t=0;$t<26;$t++){
$alfa2[$t]=buchstabeVonIndex($alfa,(indexVonBuchstabe($alfa,$alfa[$t])+$key)%26);
}
return $alfa2;
}
function substituiere($text, $alfa1, $alfa2){
// Algorithmus zur Umsetzung eines Textes aus einem Alphabet in ein anderes
// dies ist eine Ersetzung des Zeichen aus alfa1 durch das Zeichen an der selben
// Stelle in alfa2
$laengetxt=strlen($text);
$buchstabe = buchstabeVonIndex($alfa2, indexVonBuchstabe($alfa1,substr($text,$t,1)));
$codtext
= $codtext.$buchstabe;
}
return $codtext;
}
########################################################
## Hilfsfunktionen
########################################################
function indexVonBuchstabe($alfa,$letter){
// liefert den Index des Buchstaben aus dem verwendeten Alphabet
// A..Z --> 0..25
for ($t=0;$t<sizeof($alfa);$t=$t+1){
if($letter==$alfa[$t]) {
34
return $t;
break;
}
}
}
function buchstabeVonIndex($alfa,$index){
// liefert den Buchstaben aus dem verwendeten Alphabet
// 0..25 --> A..Z
return $alfa[$index];
}
function getmstime(){
return (substr(microtime(),11,10)+substr(microtime(),0,10));
}
function spacing($text, $zeichen){
if($zeichen<=1) {$zeichen=1;}
for ($t=0;$t<strlen($text);$t++){
$text2.=substr($text,$t,1);
if(($t+1)%$zeichen==0 && $t>0) {$text2.=" ";}
}
return $text2;
}
?>
Datei: fkt_decipher.php
<?
function prob($x,$y){ // rel Häufgkeit
if($y==0) $y=-1;
return ($x/$y);
}
function hauf($text){
// absolute Häufigkeiten der Buchstaben aus dem Alphabet
global $alfa;
$hauf=array(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0);
for ($t=0;$t<strlen($text);$t++){
$zeichen
= substr($text,$t,1);
$index
= indexVonBuchstabe($alfa,$zeichen);
$hauf[$index]
= ($hauf[$index]+1);
}
return $hauf;
}
function entropie($text){
// binärer Informationsgehalt
$hauf = hauf($text);
for ($t=0;$t<26;$t++){
$p=prob($hauf[$t],strlen($text));
if($p>0) {
$z=$p*log($p)/log(2);
}else{
$z=0;
}
$ent=($ent+$z);
}
$ent=(-$ent);
return $ent;
}
function koinzidenzIndex($text){
35
//wahrscheinlichste Keylänge aus Häufigkeiten der Buchstaben im Text
$kappa=0;
$n=strlen($text);
$hauf = hauf($text);
for ($t=0;$t<26;$t++){
$kappa = ( $kappa + ( $hauf[$t] * ( $hauf[$t] - 1 ) ) );
}
if($n!=0) $kappa = ( $kappa / ( $n * ( $n - 1 ) ) );
$ki = ( .0377 * $n / ( ($n-1) * $kappa - .0385 * $n + .0762 ) );
return $ki;
}
function str_splitt($text){
for($t=0;$t<strlen($text);$t++){
$arr[$t]=substr($text, $t, 1);
}
return $arr;
}
function akt($text){
// Autokorellation liefert Mustertreffer
global $ungefiltert;
$arr1=str_splitt($text);
$arr2=@array_fill(0,sizeof($arr1),0);
for($t=0;$t<sizeof($arr1);$t++){
$summe=0;
for($u=0;$u<sizeof($arr1);$u++){
if( $arr1[$u]==$arr1[($u+$t)%(sizeof($arr1))] ){
$summe++;
}
}
$arr2[$t]=$summe;
}
$am=@array_sum($arr2)/sizeof($arr2);
if($arr2[$t]>3*$am && !$ungefiltert) $arr2[$t]=4*$am;
}
return $arr2;
}
function ak_akt($text, $siz){
$n=strlen($text)/$siz;
for ($t=0;$t<$n;$t++){
$z=($t*$siz);
$txt=substr($text, $z, $siz);
$arr_tmp=akt($txt);
if(is_array($arr2)){
for ($x=0;$x<sizeof($arr_tmp);$x++){
$arr2[$x]=$arr2[$x]+$arr_tmp[$x];
}
}else{
$arr2=$arr_tmp;
}
}
return $arr2;
}
function filterakt($arr2){
// gute Werte filtern
36
global $schw1;
global $schw2;
switch((($arr2[$t]-$am*$schw1))>=$schw2){
case 1:
$wert=100;break;
default:
$wert=0;break;
}
$arr[]=$wert;
}
return $arr;
}
function showakt($arr2,$height,$part,$width,$space,$ab){
// Trefferspektrum anzeigen
global $schw1;
global $schw2;
echo "<center><table border=0 cellspacing=0 cellpadding=0>";
echo "<tr><td valign=bottom>";
for($t=0;$t<sizeof($arr2)/$part;$t++){
// nur die Hälfte des spektrums nötig...
// weil Spiegelsymmetrisch $part=2;
if($t>=$ab){
if(($arr2[$t]-$schw2)>($am*$schw1)){
echo "<img src=image/bar2.gif width=$width height=";
echo round($arr2[$t]/max(array_slice($arr2,1,sizeof($arr2)-2))*$height,0).">";
}else{
echo "<img src=image/bar.gif width=$width height=";
echo round($arr2[$t]/max(array_slice($arr2,1,sizeof($arr2)-2))*$height,0).">";
}
if($space>0) echo "<img src=image/bar.gif width=$space height=0>";
}
}
echo "</td></tr>";
echo "<tr><td valign=bottom>";
echo "</td></tr>";
echo "</table></center>";
}
function gzt($n){
// Alle ganzzahligen Teiler
$t=1;
$i=0;
while($t<=$n){
if(($n%$t)==0){
$liste[] = $t;
$i++;
}
$t++;
}
return $liste;
}
function keylen($arr){
// Keylänge ermitteln (häufigster Abstand des Spektrums, Modus)
$pos=0;
for($t=0;$t<sizeof($arr)/2;$t++){
if($arr[$t]>0) {
37
$tmp[$t-$pos]++;
$pos=$t;
}
}
$arr2=@array_fill(0,sizeof($tmp),0);
return (@array_search(@max($tmp),$tmp));
}
function trennen($text, $num){
// Codetext in monoalphabetische Buchstabenmengen aufteilen
$txt=str_splitt($text);
for($t=0;$t<sizeof($txt);$t++){
$strngs[$t%$num]=$strngs[$t%$num].$txt[$t];
}
return $strngs;
}
function findrot($text){
// Alphabetverschiebung finden
global $AP;
global $alfa;
$VX=varianz($AP[de]);
$SX=sqrt(varianz($AP[de]));
$sp=hauf($text);
$sps=array_sum($sp);
for ($t=0;$t<sizeof($sp);$t++){
$sp[$t]=round($sp[$t]/$sps*100,2);
}
for ($t=0;$t<sizeof($sp);$t++){
for ($u=0;$u<sizeof($sp);$u++){
$sp2[$u]=$sp[($t+$u)%sizeof($sp)];
}
$VY=varianz($sp2);
$SY=sqrt(varianz($sp2));
$cov=covarianz($AP[de], $sp2);
$r[$t]=abs($cov/sqrt($VX*$VY));
}
$b=array_search(max($r),$r);
return $b;
}
function findpw($text, $pwl){
// Schlüsselwort ermitteln
global $alfa;
$texte = trennen($text, $pwl);
for($t=0;$t<sizeof($texte);$t++){
$rot[$t]=findrot($texte[$t]);
$pass=$pass.buchstabeVonIndex($alfa, $rot[$t]);
}
return $pass;
}
function findpw_ak($text, $pwl){
// Schlüsselwort ermitteln für Autokey
global $alfa;
global $AP;
$texte = trennen($text, $pwl);
for($t=0;$t<sizeof($texte);$t++){
unset($arr);
38
for ($u=0;$u<sizeof($alfa);$u++){
$arr[]=koinzidenzIndex(dekAutokey($texte[$t],$alfa[$u],$alfa));
}
echo "<br>";
$y[$t][0]=array_search(min($arr),$arr);
echo $alfa[$y[$t][0]].$y[$t][0]." ";
$arr2=array_merge(array_slice($arr, 0, $y[$t][0]-1),
array_slice($arr, $y[$t][0]+1, sizeof($arr)));
$y[$t][1]=array_search(min($arr2),$arr2);
if($y[$t][1]>=$y[$t][0]) $y[$t][1]++;$y[$t][1]++;
echo $alfa[$y[$t][1]].$y[$t][1];
$rot1=abs(13-findrot(dekAutokey($texte[$t],$alfa[$y[$t][0]],$alfa)));
$rot2=abs(13-findrot(dekAutokey($texte[$t],$alfa[$y[$t][1]],$alfa)));
echo " ".$rot1." ".$rot2;
if($rot1==13){
$letter=$alfa[$y[$t][0]];
}
if($rot2==13) {
$letter=$alfa[$y[$t][1]];
}
$pass=$pass.$letter;
}
return $pass;
}
function varianz($arr){
$x=mittelwert($arr);
for ($t=0;$t<sizeof($arr);$t++){
$n=$arr[$t];
$m=(($n-$x))*(($n-$x));
$summe=$summe + $m;
}
return ($summe/sizeof($arr));
}
function covarianz($arr, $arr2){
if (sizeof($arr)!=sizeof($arr)){
return "error";
}else{
$x=mittelwert($arr);
$y=mittelwert($arr2);
$summe=$summe+($arr[$t]-$x)*($arr2[$t]-$y);
}
return $summe/sizeof($arr);
}
}
function mittelwert($arr){
$summe=$summe+$arr[$t];
}
return $summe/sizeof($arr);
}
?>
39
Literaturverzeichnis
[1] Skript zu CrypTool 1.3.04 (Stand Aug. 2003)
Technische Universität Darmstadt, Universität Siegen, Deutsche Bank
http://www.cryptool.de/
[2] Facharbeit zum Thema Kryptographie von Daniel Faber (Stand Dez. 2002)
http://daniel-faber.org/schule/facharbeit/
[3] Angewandte Kryptographie von W. Ertel (2001 Fachbuchverlag Leipzig)
http://www.fh-weingarten.de/˜ertel/kryptobuch.html
[4] Famous Unsolved Codes and Ciphers
http://www.elonka.com/UnsolvedCodes.html
[5] Kryptographiespielplatz
http://www.mbraetz.de/ (Stand Mai 2004)
[6] Geheime Botschaften von Simon Singh
http://www.simonsingh.net/
[7] CryptoLounge - Offlineversion (Stand Feb. 2002)
http://cryptolounge.cjb.net/
[8] http://www.und.nodak.edu/org/crypto/crypto/
[9] http://www.wikipedia.de/
[10] http://encyclopedia.thefreedictionary.com/Autokey%20cipher
[11] http://codebreaker.dids.com/index.htm
[12] http://www.deutsches-museum.de/ausstell/meister/enigma.htm
40
Abbildungsverzeichnis
2.1
2.2
2.3
Schema der Vigenère-Chiffre [5] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Schema der Autokey-Chiffre [5] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Collossus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.1
3.2
3.3
Häufigkeitsanalyse und Diagramme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Autokorrelation vigenère-verschlüsselter Text . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Autokorrelation autokey-verschlüsselter Text . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
41
Tabellenverzeichnis
2.1
Vigeneré-Quadrat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.1
4.2
4.3
Häufigkeitstabelle für Buchstaben in deutschen Texten[2] . . . . . . . . . . . . . . . . . . . . . . 22
Häufigkeitstabelle für Bigramme in deutschen Texten[2] . . . . . . . . . . . . . . . . . . . . . . . 22
Buchstaben-Rangfolge verschiedenener Sprachen[8] . . . . . . . . . . . . . . . . . . . . . . . . . . 22
42
Index
Additive Chiffren, 4
ADFGVX-Cipher, 6
Alberti, Leon Battista, 10
Angriff, 32
Autokey-Chiffre, 10, 12, 14
ROT13, 5
Beale-Chiffre, 7
Bigramme, 13
Tauschchiffren, 6
Schwarze Kammern, 10
Skytale, 6
Substitutive Chiffre, 7
Vigenère, Blaise de, 10
Vigenère-Chiffre, 10, 11, 14, 20
Vigenère-Quadrat, 11
Caesar-Chiffre, 4
Chiffre, 32
Chiffretext, 32
Chiffrierung, 32
Wheatstone, Charles, 13
Zimmermann-Chiffre, 14
Dechiffrierung, 32
Enigma, 15
Firedman-Test, 24
Friedman-Test, 19
Große Chiffre, 7
Häufigkeitsanalyse, 23
homophone Chiffren, 9
Kasiski-Test, 19, 23
Klartext, 32
Kryptoanalyse, 18, 32
Kryptoanalytiker, 32
Kryptographie, 32
Kryptographiespielplatz, 13
Kryptologie, 32
Le Chiffre indechiffrable, 10
Mann mit der eisernen Maske, 8
Modulo, 5, 32
monoalphabetische Chiffren, 4
Morse-Code, 7
Multiplikative Chiffre, 5
Mustersuche, 19
One-Time-Pad, 13
Play-Fair-Chiffre, 13
polyalphabetische Chiffren, 9
Rossignol, Antoine und Boneventure, 8
43

Hochschule Wismar

Transcrição

Documentos relacionados

Mitschrift 21.04.2015

Bastelanleitung

Elternbriefe GS Deutsch - schul

Ausarbeitung

IT-Sicherheit in der Medizin - Webseiten der Mitarbeiter der Universität

Sicherheitsanalyse des WEP Protokolls im IEEE 802.11

Alfa Club Spirito Sportivo 2001 2001 wurde der Alfa Club

Geheime Botschaften - Die Caesar

TEAM NAME

(Es waren zwei K\366nigskinder) - Drehleier