Sicherheit durch Kryptologie und Steganographie - diese Maßnahmen zur Verschlüsselung und Geheimhaltung von Nachrichten sind einerseits uralt und andererseits gewinnen sie heute zunehmend an Bedeutung.
Ziel des theoretischen Teils dieser Arbeit ist eine verständliche Heranführung an das Thema der Kryptologie und Steganographie. Es werden speziell ausgewählte Verschlüsselungsmethoden (u.a. Vigenere-Chiffre, RSA) vorgestellt und als Schwerpunkt deren interessanter mathematischer Hintergrund erläutert. Den praktischen Teil meiner Arbeit bildete die Entwicklung eines leistungsfähigen Steganographieprogrammes für Bitmap-Dateien, genannt Binary Chameleon.
Meine Arbeit ist in 3 Bereiche gegliedert. Im ersten Bereich wird das Thema der Kryptologie in seinen Grundlagen und mit ausgewählten Chiffren vorgestellt. Der zweite Teil behandelt das Thema der Steganographie. Ebenso wird unter diesem Punkt das Programm Binary Chameleon beschrieben. Den dritten Bereich bildet ein mathematischer Anhang, in welchem verwendete mathematische Zusammenhänge hergeleitet und erläutert werden.
Inhaltsverzeichnis
1 Kryptologie
1.1 Grundlagen
1.1.1 Grundbegriffe
1.1.2 Kryptographische Algorithmen
1.1.2.1 Symmetrische Algorithmen
1.1.2.2 Asymmetrische Algorithmen
1.1.3 Kryptanalyse
1.2 Klassische Chiffren
1.2.1 Verschiebechiffren
1.2.2 Multiplikative Chiffren
1.2.3 Tauschchiffren
1.2.4 Kryptanalyse monoalphabetischer Chiffren
1.2.5 Die Vigenère-Chiffre
1.2.5.1 Kryptanalyse nach dem Kasiski-Test
1.2.5.2 Kryptanalyse nach dem Friedmann-Test
1.3 Public-Key-Kryptographie
1.3.1 Allgemeines
1.3.2 Der RSA-Algorithmus
1.3.2.1 Verwendung
1.3.2.2 Mathematischer Hintergrund
1.3.2.3 Die wirkliche Sicherheit von RSA
2 Steganographie
2.1 Grundlagen
2.1.1 Allgemeines
2.1.2 Steganographie in BMP-Dateien
2.1.3 Praktische Umsetzung
2.2 Binary Chameleon
2.2.1 Einleitung
2.2.2 Aufbau und Funktionsbeschreibung
2.2.3 Geplante Verbesserungen
3 Mathematischer Anhang
3.1 Modulare Arithmetik
3.2 Euklidischer Algorithmus
3.3 Die Eulersche j-Funktion
4 Literatur- und Quellenverzeichnis
5 Erklärung
1 Kryptologie
1.1 Grundlagen
1.1.1 Grundbegriffe
In diesem Kapitel werden zunächst die Grundbegriffe dieses wissenschaftlichen Bereichs erklärt. Es folgt eine Übersicht über die grundlegenden Themengebiete:
Abbildung in dieser Leseprobe nicht enthalten
In diesen Bereichen werden im Verlauf dieser Arbeit weitere Vokabeln verwendet, die sich dabei an die Quelle „Angewandte Kryptographie“ anlehnen sollen. Diese werden in der nachfolgenden Tabelle erläutert.
Abbildung in dieser Leseprobe nicht enthalten
Nach den Definitionen gilt folgendes:
E(M) = C Einem Element des Klartextes wird durch die Verschlüsselung/Chiffre ein Element des Geheimtextes/Chiffretextes zugeordnet.
D(C) = M Durch die Entschlüsslung wird jedem Element des Chiffretextes ein Element des Klartextes zugewiesen. Um den originalen Klartext zu erhalten, muss die Chiffre E injektiv sein, damit jedem Element aus C auch das gleiche Element aus M wieder zugeordnet werden kann.
D(E(M)) = M Das ist eine Ableitung aus den beiden vorhergehenden Funktionen, die den Zusammenhang zwischen Verschlüsselung und Entschlüsselung deutlicher macht.
Zur Veranschaulichung der Begriffe dient die Abbildung 1.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 1: Austausch einer Nachricht
In Abbildung 1 möchte Alice eine Nachricht (Klartext M) an Bob senden. Weil Alice die Nachricht für geheim hält entscheidet sie sich, die Nachricht verschlüsselt als Geheimtext (Chiffretext C) an Bob zu versenden. Bei der Verschlüsselung der Nachricht generiert Alice mithilfe eines Schlüssels K durch die Verschlüsselungsfunktion E den Chiffretext C. Die Geheimbotschaft wird nun an Bob übermittelt, der mittels der Entschlüsslung D und demselben Schlüssel K aus dem Chiffretext den Klartext wieder generieren kann.
Fängt ein Dieb den übertragenen Chiffretext ab, dann besitzt er weder Kenntnisse über die Verschlüsselung E, noch hat er den Schlüssel K, mit dem der Chiffretext entschlüsselt werden kann.
Der Sender (Alice) muss also die Nachricht chiffrieren (verschlüsseln) und der Empfänger (Bob) die Nachricht dechiffrieren (entschlüsseln). In diesem Beispiel haben Sender und Empfänger den gleichen Schlüssel. Das ist nicht bei jeder Chiffre so, wie in folgendem Kapitel gezeigt wird.
1.1.2 Kryptographische Algorithmen
Kryptographische Algorithmen sind mathematische Funktionen, die als Vorschrift dienen, um einen Klartext zu verschlüsseln und einen Chiffretext zu entschlüsseln.
Dabei gibt es folgende Unterteilungen:
- Symmetrische Algorithmen
- Stromchiffren
- Blockchiffren
- Asymmetrische Algorithmen
Man kann kryptographische Algorithmen ebenfalls in eingeschränkte und uneingeschränkte Algorithmen unterteilen. Bei eingeschränkten Algorithmen ist die Sicherheit des Verfahrens davon abhängig, ob der Algorithmus in seiner Arbeitsweise geheim bleibt. Ebenso wird bei eingeschränkten Algorithmen meist kein Schlüssel zur Ver- und Entschlüsslung verwendet. Daher haben eingeschränkte Algorithmen sehr große Nachteile, weil ein solcher Algorithmus kaum geheim gehalten werden kann. Folglich war man gezwungen neuere (uneingeschränkte) Algorithmen mit Schlüssel zu benutzen, wie es heute der Fall ist.
Bei Algorithmen sollte somit die Sicherheit von der Geheimhaltung des Schlüssels abhängig sein und nicht von der Sicherheit des Algorithmus, was eine sehr wichtige Grundvoraussetzung für alle kryptographischen Algorithmen schafft.
Heutzutage werden neue kryptographische Algorithmen absichtlich veröffentlicht, um sie den kryptoanalytischen Attacken von Experten auszusetzen. Sollten diese Attacken scheitern, so gewinnt der neu entwickelte Algorithmus an Sicherheit und Vertrauen.
1.1.2.1 Symmetrische Algorithmen
Symmetrische Algorithmen sind Verfahren, bei denen zum Ver- und Entschlüsseln derselbe Schlüssel verwendet werden muss. Das bedeutet, dass Sender und Empfänger über den gleichen Schlüssel verfügen müssen. Folglich muss für die Sicherheit der Geheimnachricht vorausgesetzt werden, dass der Schlüssel nicht in andere Hände gegeben werden darf.
Man unterscheidet symmetrische Algorithmen zwischen Stromchiffren und Blockchiffren. Bei Stromchiffren nimmt man ein Zeichen nach dem anderem aus dem Klartext und verschlüsselt es. Bei Blockchiffren (z.B. Data-Encryption-Standart DES) hingegen wird zuerst der Klartext in so genannte Blöcke zerlegt und jeder Block einzeln nacheinander chiffriert.
In dieser Arbeit werden hauptsächlich Stromchiffren eine Rolle spielen.
Für symmetrische Algorithmen gelten folgende Funktionen in Bezug auf den Schlüssel:
E(M) = C Es wird zum Chiffrieren und Dechiffrieren der gleiche Schlüssel benutzt.
D(C) = M Die Entschlüsslung geschieht mithilfe des Schlüssels K und ist abhängig
D(E(M)) = M von der verschlüsselten Nachricht, die mit demselben Schlüssel verschlüsselt wurde.
Zur Veranschaulichung verweise ich auf Abbildung 1 aus Kapitel 1.1.1, die einen symmetrischen Algorithmus mit gleichem Schlüssel wiedergibt.
1.1.2.2 Asymmetrische Algorithmen
Asymmetrische Algorithmen sind Verfahren, bei denen zum Ver- und Entschlüsseln verschiedene Schlüssel verwendet werden müssen. Ein sehr passendes Beispiel dafür ist die Public-Key-Kryptographie, die in einem späteren Kapitel näher erläutert wird. Allgemein kann man sagen, dass der Empfänger einen eigenen Schlüssel K generiert und aus diesem einen zweiten Schlüssel K. Der Schlüssel K dient zur Entschlüsslung der Nachricht und der Schlüssel K zur Verschlüsselung. Der Empfänger behält also den ersten Schlüssel K und gibt den Schlüssel K an den Sender weiter, so dass dieser ihm Nachrichten senden kann, die mit dem Schlüssel K verschlüsselt sind. Man kann die Nachricht jedoch nur wieder mit dem Schlüssel K, den allein der Empfänger besitzt, entschlüsseln. Aus dem Schlüssel K lässt sich der Schlüssel K nicht auf praktischem Wege herleiten. Es ist also noch viel mehr Sicherheit bei asymmetrischen Algorithmen garantiert als bei symmetrischen Algorithmen.
Für symmetrische Algorithmen gelten nun andere Funktionen als bei asymmetrischen Algorithmen in Bezug auf den Schlüssel:
E(M) = C Es werden unterschiedliche Schlüssel zum Chiffrieren und Dechiffrieren
D(C) = M verwendet, wobei die Entschlüsslung mithilfe eines Schlüssels K geschieht
D(E (M)) = M und der entstehende Klartext ebenso abhängig von dem Schlüssel K ist, mit dem die Nachricht verschlüsselt wurde.
Die Abbildung 2 dient als Veranschaulichung eines asymmetrischen Algorithmus am Beispiel von Public-Key-Algorithmen.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2: Funktionsweise von Public-Key-Algorithmen
In Abbildung 2 erkennt man den entscheidenden Vorteil von asymmetrischen Algorithmen. Der wichtigste Schlüssel K (zum Entschlüsseln einer Nachricht) wird in Händen des Empfängers generiert und muss niemals weitergegeben werden. Selbst wenn der Dieb den Schlüssel K abfangen könnte, während er an den Sender weitergegeben wird, könnte er die Nachricht nicht entschlüsseln.
1.1.3 Kryptanalyse
In diesem Abschnitt werden allgemeine Angriffe auf Kryptosysteme (Zusammenfassung aus Verschlüsselungsalgorithmus, Schlüssel und Chiffretext) genannt und erläutert. Bei jedem dieser Angriffe geht der Angreifer (auch Kryptanalytiker genannt) von einer bestimmten Angriffssituation aus und versucht dann, mittels bestimmter Methoden den Schlüssel des Kryptosystems herauszufinden.
Abbildung in dieser Leseprobe nicht enthalten
Die Sicherheit eines Kryptosystems bei einem Brute-Force-Angriff
Ich möchte in diesem Kapitel noch einmal die Mächtigkeit des Brute-Force-Angriffs und Schutzmaßnahmen gegen diesen Angriff verdeutlichen. Bei moderneren Verschlüsselungsmethoden, die in der Gegenwart verwendet werden, ist es meist zwecklos das Kryptosystem auf Schwachstellen zu analysieren, da fast jeder heutzutage genutzter Verschlüsselungsalgorithmus veröffentlicht wird und somit automatisch von Mathematikern und Kryptanalytikern geprüft wird. Ist der Algorithmus nicht zu knacken und hat sich als tauglich erwiesen, kommt meistens nur ein Brute-Force-Angriff in Frage.
Derzeit werden immer schnellere Prozessoren entwickelt, wodurch das "Probieren von Schlüsseln" mittels eines solchen Angriffs schneller geschehen kann. Doch das ist vollkommen nutzlos, wenn z.B. ein Programm über eine Zeitsperre verfügt. Das heißt, nach der Eingabe eines falschen Passworts ist eine Eingabe erst nach einer bestimmten Zeit wieder möglich. Es folgt nun ein Beispiel, was deutlich machen soll, wie man sich gegen Brute-Force-Angriffe schützen kann.
Das Programm besitzt eine Zeitsperre von 2 Sekunden. Das Alphabet, aus dem ein digitales Passwort erzeugt werden kann, besteht aus 256 Zeichen (das entspricht dem ASCII Zeichensatz, der im Tafelwerk zu finden ist). Doch man verwendet zunächst nur 8 Ziffern (jeweils von 0 bis 9) für das Passwort.
Dann gibt es 10 Möglichkeiten.
Die Brute-Force-Attacke bräuchte dann 10*2 Sekunden » 2315 Tage (ca. 6 Jahre).
Ziel ist es, diese Zeit t, welche ebenfalls neben finanziellen Mitteln Aufwand im Rahmen eines Brute-Force-Angriffs darstellt, zu erhöhen. Dazu kann man folgende Verallgemeinerung betrachten, die sich aus dem Beispiel herleiten lässt:
t = tz * n
tz = Dauer der Zeitsperre + benötigter Rechenzeit für ein Passwort
n = Mächtigkeit des Alphabets (Anzahl der verwendbaren Zeichen).
l = Länge des Schlüssels k
Die Erhöhung dieser 3 Größen führt zu einem größeren Aufwand für einen Brute-Force-Angriff. Es wird klar, dass die Schlüssellänge am wichtigsten ist, denn um t konstant zu halten, müsste man für n sein Quadrat einsetzen, wenn man die Schlüssellänge nur um 1 vermindert (wenn tz konstant ist). Als Benutzer eines Verschlüsselungsprogramms kann man zwar tz nicht verändern, aber dafür n und l. Natürlich kann man die Mächtigkeit des digitalen ASCII Codes von 256 Zeichen nicht überschreiten, aber mit dem alleinigen Verwenden von Ziffern wie in dem obigen Beispiel reduziert man n automatisch auf 10 mögliche Zeichen. Das ist durch das Vorgehen eines Brute-Force-Programms zu erklären, welches systematisch nur Zifferkombinationen, danach nur Buchstabenkombinationen und nachträglich alle Kombinationen ausprobiert. Folglich kann man mit dem Verwenden von Buchstaben, Zahlen und Sonderzeichen in einem Passwort und einer hohen Schlüssellänge die Sicherheit eines Kryptosystems in Bezug auf einen Brute-Force-Angriff deutlich erhöhen, was noch einmal gezeigt werden soll.
Jetzt wird ein Passwort benutzt, dass die Zeichen aus dem gesamten ASCII-Zeichensatz verwendet und aus 10 Stellen besteht. Die Zeitsperre des Programms bleibt gleich.
t = 2 Sekunden * 256 » 76669572527564001 Jahre ( >> 6 Jahre)
Aus diesem Beispiel folgt nun:
Die Sicherheit eines Schlüssels (eines Passwortes) und damit eines Kryptosystems ist stark von der Schlüssellänge und den Kombinationen aus verwendeten Zeichen abhängig.
1.2 Klassische Chiffren
In diesem Abschnitt werden einige der klassischen Chiffren vorgestellt. Man bezeichnet alle kryptographischen Algorithmen, die bis 1950 entwickelt und eingesetzt wurden, als klassische Chiffren. Solche Algorithmen, die sogar bis zur Zeit Cäsars reichten, benötigen Grundlagen der modularen Arithmetik (siehe mathematischer Anhang, Abschn. 1). Man verwendet für die Repräsentation der Buchstaben im Alphabet daher auch die Positionen 0 bis n-1, wobei n wie gehabt die Anzahl der Buchstaben (Mächtigkeit) des Alphabets darstellt.
Man teilt klassische Chiffren grundsätzlich in 2 Gruppen ein:
Transpositionschiffren: Bei diesen Chiffren werden nur die Positionen der Klartextzeichen verändert. Man bezeichnet diesen Vorgang auch als Permutation.
Substitutionschiffren: Hier werden die Klartextzeichen durch andere Zeichen ersetzt. Man unterscheidet hier zwischen monoalphabetischen Chiffren, wo jedes Klartextzeichen jeweils immer durch dasselbe Geheimtextzeichen ersetzt wird (z.B. Verschiebechiffren, multiplikative Chiffren, Tauschchiffren) und polyalphabetischen Chiffren, wo jedes Klartextzeichen nicht immer mit demselben Geheimtextzeichen dargestellt wird (z.B. Vigenère-Chiffre).
Das "Knacken" klassischer Chiffren ist durchaus einfach, weshalb diese heute kaum noch verwendbar sind.
1.2.1 Verschiebechiffren
Verschiebechiffren gehören zu den ältesten monoalphabetischen Chiffren. Schon Julius Cäsar entwickelte eine Verschiebechiffre, um seine Nachrichten geheim zu übermitteln. Diese Chiffre wurde als Cäsar-Chiffre bekannt und ist dadurch gekennzeichnet, dass jeder Buchstabe im Alphabet um 3 Stellen nach rechts verschoben wird, wodurch folgendes Alphabet entstand:
Abbildung in dieser Leseprobe nicht enthalten
Natürlich müssen die Klartextbuchstaben nicht allgemein um 3 Stellen verschoben werden, sondern können beliebig um einen Summanden e verschoben werden. Da unser Alphabet 26 Buchstaben ohne Umlaute besitzt ist klar, dass es maximal 26 Verschiebechiffren gibt, wobei e die ganzzahligen Werte 0 bis 25 annehmen kann. Dabei gilt folgende allgemeine Vorschrift für die Verschlüsselung:
Abbildung in dieser Leseprobe nicht enthalten
Beispiel zur Verschlüsselung und Entschlüsslung:
Die Nachricht, die übermittelt werden soll, lautet: "um drei in neustadt"
Der Summand e soll hier 8 betragen.
Ausgehend von der Nummerierung der Alphabetbuchstaben von 0 bis 25 hat "u" die Nummer 20. Die Nummer des ersten Geheimtextbuchstabens im Alphabet lautet also:
c = (20 + 8) mod 26 = 2 (entspricht dem Buchstaben "C")
Es folgt: C # u (Der Chiffrebuchstabe "C" wird dem Klartextbuchstaben "u" zugeordnet)
Insgesamt entsteht folgendes Alphabet:
Abbildung in dieser Leseprobe nicht enthalten
Der Geheimtext lautet also: CU LZMQ QV VMCABILB
Umgekehrt erhält man für den Geheimtextbuchstaben "C":
(Da c = 2 < e = 8) m = 26 + (2 - 8) mod 26 = 26 - 6 = 20 (entspricht dem Buchstaben "u")
1.2.2 Multiplikative Chiffren
Statt Klartextzeichen mit einem Summanden e zu addieren, ist es auch möglich, diese mit einem Faktor k zu multiplizieren. Dabei gibt es jedoch eine kleine Einschränkung was k betrifft.
Die allgemeine Vorschrift lautet: c = (m * k) mod n
Zunächst folgt ein Beispiel für ein Geheimtextalphabet, was entsteht, wenn jede Buchstabennummer mit 4 multipliziert wird.
Abbildung in dieser Leseprobe nicht enthalten
Bei dem entstandenen Alphabet ist zu erkennen, dass einige Geheimtextbuchstaben durch 2 Klartextbuchstaben repräsentiert werden. Damit wäre die Injektivität dieser multiplikativen Chiffre mit dem Faktor 4 nicht gegeben, wodurch die Vorraussetzung für einen funktionierenden kryptographischen Algorithmus nicht geschaffen ist.
Es gilt bei den multiplikativen Chiffren folgende Regel:
Der größte gemeinsame Teiler von k und n muss 1 sein: ggT(k, n) = 1
Tatsächlich ist in dem Beispiel mit dem Faktor 4 der größte gemeinsame Teiler von 4 und 26 nicht 1, sondern 2. Warum diese Regel gelten muss, kann ich mit folgenden Überlegungen zeigen:
Abbildung in dieser Leseprobe nicht enthalten
Eine mögliche Zahl für k wäre demnach 3, denn es gilt:
ggT(3, 26) = 1
Für den Faktor 3 erhält man folgende Zuweisungen für die Geheimtextbuchstaben:
Abbildung in dieser Leseprobe nicht enthalten
Wie man sieht, wird hierbei kein Geheimtextbuchstabe einem Klartextbuchstaben mehrfach zugewiesen. Das heißt, dass die Vorraussetzungen für eine funktionierende Ver- und Entschlüsslung gegeben sind. Für die Berechnung des größten gemeinsamen Teilers, verweise ich auf den mathematischen Anhang, Absch. 2. Aber wie sieht die Vorschrift für die Entschlüsslung aus?
Um das herauszufinden, hatte ich folgende Grundidee:
Für eine normale Rechnung gilt:
m * a = c
c * a = m
Dabei ist a zu a multiplikativ invers. Da die Verschlüsselungsfunktion c = (m * k) mod n gilt, wird nun wie oben ein Inverses x zu k mod n gesucht, mit dem die Verschlüsselung ebenso rückgängig gemacht werden kann:
Abbildung in dieser Leseprobe nicht enthalten
An dieser Stelle kann ich meine Überlegungen nicht weiter verallgemeinert ausführen, da es aufgrund der 2 unersetzbaren Variablen p und q nicht möglich ist, eine allgemeine Lösung für x in Abhängigkeit von k und n zu ermitteln. Daher soll der erste Schritt sein, n so lange mit sich selbst zu addieren, bis eine Zahl entsteht, die addiert mit 1 ein Vielfaches von k ist. Danach kann das Ergebnis durch k dividiert werden, wodurch man x erhält.
Alternativ zu dieser Methode, ein multiplikatives Inverses zu k mod n zu berechnen, gibt es den so genannten erweiterten Euklidischen Algorithmus, der im mathematischen Anhang, Abschn. 2 zu finden ist.
Zunächst folgt eine Zusammenfassung:
Abbildung in dieser Leseprobe nicht enthalten
* Der ggT zweier Zahlen kann mithilfe des Euklidischen Algorithmus berechnet werden.
Beispiel zur Verschlüsselung und Entschlüsslung:
Die übermittelte Nachricht lautet wieder: "um drei in neustadt"
Als Faktor k wird nun 3 benutzt, für den bereits gilt: Der größte gemeinsame Teiler von k (3) und n (26) ist 1. Also kann die Verschlüsselung und Entschlüsslung durchgeführt werden:
Der 2. Klartextbuchstabe "m" hat die Nummer 12. Die Nummer des Geheimtextbuchstabens wird nun mit der Verschlüsselungsfunktion berechnet:
c = (12 * 3) mod 26 = 10 (entspricht dem Buchstaben "K")
Es folgt: K # m (Der Chiffrebuchstabe K wird dem Klartextbuchstaben m zugeordnet)
Insgesamt entsteht wieder folgendes Alphabet:
Abbildung in dieser Leseprobe nicht enthalten
Der Geheimtext lautet also: IK JZMY YN NMICFAJF
Um für den Geheimtextbuchstaben "K" den Klartextbuchstaben wieder zu erhalten, wird noch ein multiplikatives Inverses x zu k mod n gesucht, was in diesem Falle 9 beträgt (die Berechnung mittels des erweiterten Euklidischen Algorithmus bleibt in dem Beispiel aus):
m = (12 * 9) mod 26 = 10 (entspricht wieder dem Buchstaben "m")
1.2.3 Tauschchiffren
Diese Art von Chiffren ist eine Kombination aus Verschiebechiffre und multiplikativer Chiffre. Alternativ kann man diese Chiffre auch affine Chiffre nennen.
Man kann sich die Kombination aus Verschiebechiffre und multiplikativer Chiffre wie das Abarbeiten beider Verschlüsselungs- und Entschlüsslungsvorgänge hintereinander vorstellen. Zunächst gilt folgende Vorschrift für die Verschlüsselung: c = (m*k + e) mod n
Hierbei entspricht m*k dem Chiffretextbuchstaben der multiplikativen Chiffre, wobei dieser erneut mit einer Zahl e addiert wird. Es ist jetzt zu erkennen, dass die Einschränkungen für k wie bei multiplikativen Chiffren gelten müssen. Das bedeutet: Der größte gemeinsame Teiler von k und n muss 1 sein, damit die Verschlüsselungsfunktion injektiv ist. Ebenso muss erneut ein modulares Inverses für k mod n gefunden werden.
Hier kann man anhand der Beispieltabelle sehen, wie zunächst m*k (bei k = 3) berechnet wird und anschließend mit e (bei e = 4) addiert wird:
Abbildung in dieser Leseprobe nicht enthalten
Wie man sieht, funktioniert aufgrund ihrer Injektivität die Verschlüsselungsfunktion:
c = (m*3 + 4) mod n, da auch gilt: Der größte gemeinsame Teiler von k und n ist 1.
Es folgt eine Zusammenfassung:
Abbildung in dieser Leseprobe nicht enthalten
Beispiel zur Verschlüsselung und Entschlüsslung:
Als Klartextnachricht wird wieder "um drei in neustadt" verwendet.
Als Faktor k und Summand e werden die obigen Werte (k = 3, e = 4) benutzt, wofür bereits eine geeignete Tabelle für das entstehende Geheimtextalphabet existiert.
Am Beispiel des 3. Klartextbuchstabens "d", der durch die Nummer 3 im Klartextalphabet dargestellt wird, wird nun die Verschlüsselungsfunktion angewandt:
c = (3 * 3 + 4) mod 26 = 13 (entspricht dem Buchstaben "N")
Es folgt: N # d (Der Chiffrebuchstabe "N" wird dem Klartextbuchstaben "d" zugeordnet)
Um die gesamte Nachricht zu verschlüsseln, kann auch wieder das durch die Verschlüsselung entstandene Geheimtextalphabet genutzt werden:
Abbildung in dieser Leseprobe nicht enthalten
Ersetzt man die Klartextbuchstaben nun durch die Chiffretextbuchstaben, erhält man für den Chiffretext: MO NDQC CR RQMGJENJ
Jetzt wird der 3. Chiffretextbuchstabe "N" wieder mithilfe der Verschlüsselungsfunktion in den Klartextbuchstaben umgeformt. In diesem Beispiel beträgt x = 9, wie auch in dem Beispiel für Tauschschiffren, da das gleiche k = 3 mit der gleichen Alphabetmächtigkeit n = 26 benutzt wird.
m = ((13 - 4) * 9) mod 26 = 3 (entspricht wieder dem Buchstaben "d")
1.2.4 Kryptanalyse monoalphabetischer Chiffren
Die 3 letzten vorgestellten Chiffren (Verschiebechiffre, multiplikative Chiffre und Tauschchiffre) können in ihrer Kryptanalyse zusammengefasst werden. In diesem Abschnitt soll klar werden, dass diese monoalphabetischen Chiffren alle sehr leicht knackbar sind und eine nur sehr geringe Sicherheit für die Übertragung von Nachrichten bieten. Dazu wird zunächst gezeigt, wie viele Möglichkeiten für die entsprechende monoalphabetische Chiffre auf unserem Alphabet mit der Mächtigkeit n = 26 in Frage kommen.
Begonnen wird mit der Verschiebechiffre. Entscheidend ist hier der Summand e, denn laut Einschränkung darf er die Werte 0 bis n-1 annehmen, da sonst keine neuen Verschiebechiffren entstehen. Ist jedoch e = 0, dann entspräche das Chiffretextalphabet dem Klartextalphabet, womit die Verschlüsselung sinnlos wäre. Also gibt es 25 mögliche Werte für e und damit 25 verschiedene Verschiebechiffren.
Bei der multiplikativen Chiffre, wird k für die Anzahl der Möglichkeiten betrachtet. Entsprechend der Einschränkungen für k, kommen dafür nur die Werte 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 und 25 in Frage. Hierbei wäre eine Verschlüsselung mit k=1 wieder zwecklos, da erneut das Geheimtextalphabet dem Klartextalphabet entspricht. Folglich gibt es nur 11 Möglichkeiten für k und damit nur 11 mögliche Verschiebechiffren.
Für die Tauschschiffre können die Möglichkeiten für Verschiebechiffre und multiplikativer Chiffre multipliziert werden. Dabei gilt zunächst, dass e gleich 0 sein darf und k den Wert 1 annehmen kann, womit sich die Anzahl der Möglichkeiten für beide Chiffren um jeweils 1 erhöht.
Somit erhält man bei der Multiplikation 26 * 12 = 312 mögliche Chiffren. Doch auch hierbei entsteht ein Sonderfall, wenn e=0 und gleichzeitig k=1 ist. Das heißt, es muss noch 1 (Fall für e und k) subtrahiert werden und man erhält 311 mögliche (sinnvolle) Chiffren.
Es scheint zwar mehr Möglichkeiten für die Tauschchiffre als für die anderen beiden Chiffren zu geben, jedoch ist diese Zahl immer noch zu klein, um heute als sicher zu gelten. Der Angreifer müsste also bei der Tauschchiffre nur 311 Möglichkeiten ausprobieren, wenn er von einem Chosen-Plaintext-Angriff ausgeht. Doch der Angreifer hat noch eine andere Methode, um an den Schlüssel und an den Klartext zu kommen, wenn ihm eine monoalphabetisch verschlüsselter Chiffretext vorliegt und er über die Art der Verschlüsselung Bescheid weiß. Da bei monoalphabetischen Chiffren immer jeder Geheimtextbuchstabe durch den gleichen Klartextbuchstaben repräsentiert wird, kann man die Häufigkeiten für die Geheimtextbuchstaben in einem Geheimtext auszählen und anschließend mit den durchschnittlichen Häufigkeiten der Buchstaben in einem deutschen Text (siehe nachfolgende Tabelle) vergleichen.
Abbildung in dieser Leseprobe nicht enthalten
Tabelle 1: durchschnittliche Häufigkeiten von Buchstaben in deutschen Texten
Auffallend ist, dass die Buchstaben "e" und "n" am häufigsten vorkommen. Das heißt, es wird angenommen, dass die am häufigsten ausgezählten Chiffretextbuchstaben dem Klartextbuchstaben "e" entsprechen und die am zweithäufigsten Buchstaben n entsprechen. Dabei kann es vorkommen, dass es z.B. 2 verschiedene Geheimtextbuchstaben gibt, die beide eine ähnliche Häufigkeit wie "n" aufweisen. In diesem Falle müsste man nachschauen, welcher der beiden häufiger in Verbindung mit dem Chiffretextbuchstaben für den Klartextbuchstaben "e" auftritt. Das Buchstabenpaar (Bigramm) "en" beispielsweise kommt in deutschen Texten häufiger vor als eine andere Buchstabenkombination mit dem Buchstaben "n". Für die durchschnittlichen Häufigkeiten der 10 häufigsten Buchstabenpaare in deutschen Texten folgt nun eine weitere Tabelle.
Abbildung in dieser Leseprobe nicht enthalten
Tabelle 2: durchschnittliche Häufigkeiten von Buchstabenpaaren in deutschen Texten
Abgesehen von dem Fall, dass 2 Häufigkeiten für 2 Chiffretextbuchstaben einer durchschnittlichen Häufigkeit für einen Buchstaben in einem deutschen Text entsprechen, kann man auch Buchstabenpaare aus dem Chiffretext auszählen und die Häufigkeiten mit den Häufigkeiten in Tabelle 2 vergleichen.
Während man bei Tauschchiffren und multiplikativen Chiffren nur auf das Vergleichen der Häufigkeiten der Buchstabenpaare und zusätzliches Erraten der übrig gebliebenen Chiffretextbuchstaben vertrauen kann, findet man sehr leicht heraus, dass es bei Verschiebechiffren möglich ist, den Summanden e genau zu bestimmen. Dazu muss man zunächst wissen oder sicher sein, dass es sich um die entsprechende Chiffre handelt, mit der der Klartext ursprünglich verschlüsselt wurde.
- Arbeit zitieren
- Sebastian Mußlick (Autor:in), 2006, Kryptologie und Steganographie, München, GRIN Verlag, https://www.hausarbeiten.de/document/123633