Einfuehrung in die Kryptologie
[Back]
[Caesarcode]
[Multiplikative Chiffren]
[Vigenere Chiffre]
[Kasiski Test]
Zusammenfassendes Material
Um einen Einstieg in die Kryptographie zu erhalten, ist es notwendig, verschiedene Begrifflichkeiten zu unterscheiden.
Die Kryptographie als solches bezeichnet eine Wissenschaftsdisziplin, deren Inhalt es ist, Verschlüsselungsverfahren
zu entwickeln, die primär dem Schutz geheimer Daten dienen. Der zu verschlüsselnde Text wird dabei als Klartext bezeichnet,
der verschlüsselte Text im Weiteren als Geheimtext. Im Laufe der Jahrhunderte war es notwendig Botschaften über offene
bzw. unsichere Kanäle auszutauschen. Während früher der Transport von beschriebenem Papier den Kanal darstellte, ist heute der
Austausch über elektronische Mail möglich. Das grundlegende Problem ist dabei jedoch das gleiche geblieben. Es gilt, die Daten
zu sichern.
Monoalphabetische Verschlüsselungsverfahren
Die Entwicklung moderner Verschlüsselungsverfahren basiert auf einer langen Geschichte. Entwickelte Kryptosysteme
wurden jedoch immer wieder durch eine geeignete Kryptoanalyse in Frage gestellt. Programmiertechnisch nachvollziehen
läßt sich die Kryptoanalyse am ehesten bei den sogenannten klassischen Verfahren. Gemeint sind hierbei Verfahren,
die bis in die 50ger Jahre entwickelt wurden. Eine vergleichsweise große Gruppe dieser Chiffren stellen die sogenannten
Substitutionschiffren dar. Diese sind dadurch gekennzeichnet, dass die Klartextzeichen über einer Alphabetmenge
durch andere Zeichen ersetzt werden, ohne die Position zu ändern.
Wird das Klartextzeichen dabei immer auf ein und dasselbe Geheimtextzeichen abgebildet, spricht man von sogenannten
monoalphabetischen Chiffren, ist diese Abbildung nicht injektiv, verwendet man den Begriff
polyalphabetisch.
Der Code, benannt nach seinem Erfinder Julius Caesar (100 bis 44 v. Chr), ist ein Verschiebechiffre und zählt damit
zur Gruppe der monoalphabetischen Substitutionschiffren. Das Prinzip dieses Kryptosystems ist relativ einfach.
Jedes Klartextzeichen wird durch ein um den Index i verschobenes Zeichen ersetzt. Da die zugrundeliegende Alphabetmenge eine
entsprechende Mächtigkeit von z.B. M = |26| besitzt. wird bei einem Überlauf der Restklassenoperator verwendet.
01 class caesar :
02 windows/C/Dungeon/Site/Informatik/krypt
03 def __init__(self) :
04 self.schub = 0
05
06 def eingabe (self) :
06 return raw_input("String >")
07
08 def verschiebung (self, verschiebung) :
09 self.schub = verschiebung
10
11 def caesar_code (self) :
12 s = ""
13 for i in range (0, len(orginal)): :
14 if orginal [i] == "\n" or orginal [i] ==" " : s = s + orginal [i]
15 else : s = s + chr (ord(orginal [i]) + self. schub)
16 return s
17
18
19 [SOURCE]
20 ............
|
Die Einfachheit des Caesarcodes legt die Verwendung etwas komplexerer Algorithmen nahe. In diese Gruppe gehören
multiplikative Chiffren, die vergleichbar dem Caesarcode über ein Histogramm dechiffrierbar sind, aber zumindest
in Bezug auf die Herleitung der Dechiffrierfunktion einen komplexeren Ansatz haben. Ist keine einfache Addition
die Grundlage der Chiffre, sondern eine Multiplikation, besteht das Problem in der Bestimmung des sogenannten
Umkehrwertes des Verschlüsselungsfaktors, dem sogenannten multiplikativen Inversen.
Dieses multiplikativ Inverse läßt sich über den sogenannten Erweiterten Euklidischen Algorithmus bestimmen, der in Kurzform wie folgt
lautet. Beachten Sie bitte, dass der Algorithmus trotz der Kürze des Umfangs sehr komplex ist.
01 def eeuklid (a,b,d=0, y=0) :
02
03 if b == 0 : return (a, 1, 0)
04 (d,x,y) = eeuklid (b, a % b)
05 return (d, y, x - (a//b)*y)
|
Die Nutzung des Codes ist nun relativ einfach. Da der Erweiterte Euklidische Algorithmus
ein Tupel liefert, welches auf dem ersten Wert das ggt zweier Zahlen enthält und auf dem zweiten Wert, das gesuchte multiplikativ Inverse reicht ein einfaches Auslesen des Tupels an dieser Stelle aus um eine Decodiermethode zu generieren.
11 def decode (self) :
12 s = ""
13 for i in range (0, len(orginal)): :
14 if orginal [i] == "\n" or orginal [i] ==" " : s = s + orginal [i]
15 else : s = s + chr (((ord(orginal [i]-ord('A')) * eeuklid (26, self.faktor) [1]) % 26) + ord ('A'))
16 return s
17
18 ............
|
Polyalphabetische Verschlüsselungsverfahren
Nachdem gezeigt wurde, dass mittels eines einfachen Histogramms die monoalphabetischen Chiffren geknackt werden können,
liegt es nahe sich, anderen klassischen Verfahren zuzuwenden. Eines der bekanntesten in diesem Zusammenhang stellt dabei
Chiffrierung nach Vigenere dar. Dieses polyalphabetische Verfahren ist ebenso relativ übersichtlich und basiert auf dem
Auslesen der sogenannten Vigeneretafel.
Konkret bedeutet dies, dass durch ein Geheimwort und dem Klartext die Tafel, wie eine Matrix ausgelesen wird.
Verschiedene kleine Tools demonstrieren diese Verfahren sehr gut. Einige seien hier als Verweis ausgewiesen.
Material - Links
Cryptool
Simulationsshareware
Bei beide Programmen handelt es sich um Anwendungssoftware, wobei Cryptool ein sehr leistungsfähiges Programm,
auch zur Demostration moderner Verfahren darstellt, während die Shareware der Veranschaulichung der klassischen Verfahren
dient.
Der Vigenere Algorithmus lässt sich nachvollziehbar in Python implementieren. Als
Möglichkeit sei hier die Verwendung eines Dictionarys angedeutet.
Zur Verständlichkeit des Prinzips sei ein Source gegeben.
[Ansatz 1 : SOURCE Vigenere]
Bezieht man mathematische Grundlagen in die Implementierung ein, so erkennt man das es sich bei der Vigenere Tafel um
verschobene Alphabete handelt. Es ist also eigentlich nur notwendig, die Ordnungsnummer des Klartextbuchstaben und
die Ordnungsnummer des Schlüsselbuchstaben zu addieren, um den verschlüsselten Buchstaben zu generieren. Implementierungstechnisch
ist allerdings die Verschiebung im AscII Alphabet zu beachten. Auch dieser Weg sei durch einen rudimentären Source
vorgegeben.
[Ansatz 2 : SOURCE Vigenere]
Dechiffrierung
Im Jahre 1854 gelang es Charles Babbage den Vigenere Algorithmus zu entschlüsseln, der dann
1863 von Friedrich Kasiski, einem preußischen Infanteriemajor veröffentlicht wurde.
Die Vorgehensweise ist algorithmisch :
1.)
Der Geheimtext wird nach Wiederholungen von Zeichenfolgen mit mindestens 3 Zeichen
durchsucht
Die Abstände werden erfasst.
Bsp : AFR......AFR -> 6 (Anzahl der Buchstaben)
Die Abstände werden in Primfaktoren zerlegt.
2.)
Mögliche Schlüssellängen sind die häufigsten Primfaktoren.
Ist die Länge des Schlüssels bekannt, (unterstützend verwendet den
Test von Friedmann) wird der Geheimtext in Teiltexte zerlegt. Dies
geschieht abzählend. Ist die Schlüssellänge 3, denkt man sich den
Text in Dreierblöcke zerlegt. Der erste Teiltext beinhaltet jeden ersten,
der zeite jeden zweiten, der dritte jeden dritten Buchstaben.
Die Teiltexte können nun monoalphabetisch dechiffriert werden. Ist im
ersten Teiltext der Buchstabe F am häufigsten, würde damit vermutlich im
Orginal dem Buchstaben E entsprechen, ergibt sich der vermutliche
Schlüsselbuchstabe B, da es sich (vgl. Caesar) um eine Verschiebung um 1
handelt.
Lustige Histogrammdarstellungen in kommerziellen oder freien Programmen
beziehen sich auf eben diese monoalphabetische Verschlüsselung der Teiltexte.