Vorwort

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. Sie werden in jeder erdenklichen Form auf digitalem Gebiet eingesetzt, wie z.B. im Online-Banking, beim Emailtransfer und bei jeder anderen Form der Datenübertragung. Jährlich erleiden Firmen wegen unzureichender Sicherheitsmaßnahmen Verluste in unvorstellbarer Höhe. Diese Wissenschaft, basierend auf dem Gebiet der Mathematik und der Informatik, bezieht ihre Methoden sogar aus der modernen Quantenphysik. Auch mich als Programmierer hatte dieses Thema längst eingeholt, als es um Fragen der sicheren Übertragung von Informationen ging. Begeistert vom mathematischen Hintergrund dieses Gebietes beschäftigte ich mich immer eingehender damit und beschloss, dieses Thema im Rahmen meiner Jahresarbeit zu bearbeiten. Ziele

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 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. Derzeit gibt es kaum gute und frei verfügbare Software zur sicheren Übertragung von Daten mittels Steganographie in Kombination mit Verschlüsselung. Ich denke, im Rahmen dieser Arbeit, diese Lücke ein wenig geschlossen zu haben. Gliederung der Arbeit

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 mein Programm Binary Chameleon beschrieben, was jedoch leider im Rahmen einer Jahresarbeit nicht vollständig geschehen kann. Den dritten Bereich bildet ein mathematischer Anhang, in welchem verwendete mathematische Zusammenhänge erläutert werden. Persönliche Erfahrungen

Diese Jahresarbeit war für mich ein sehr großer persönlicher Erfolg in vielerlei Hinsicht. Zum einen hätte ich nicht geglaubt, dass ich alle mathematischen Zusammenhänge aus diesem Bereich verstehen würde. Doch selbst eigene Beweise konnte ich durch intensives Arbeiten herleiten. Noch mehr eigene Erfahrungen konnte ich auf dem Gebiet der Steganographie sammeln. Da es zu diesem Thema kaum Lektüre gibt, war ich bei der Programmierung und Entwicklung meines Steganographieprogrammes auf mich allein gestellt. Das gab mir die Möglichkeit, auf diesem Gebiet selbst zu forschen und komplett neue Methoden zu entwerfen.

Besondes im Rahmen der Jahresarbeit konnte ich mich mit dieser Thematik sehr intensiv beschäftigen, was zu meinem Entschluss führte, mich weiterhin mit dem Thema Kryptologie auseinanderzusetzen sowie auf dem Gebiet der Steganographie neue Methoden zu erforschen und zu entwickeln.

Inhaltsverzeichnis Seite 3

Inhaltsverzeichnis   

1  KRYPTOLOGIE  4

1.1  Grundlagen  4

1.1.1  Grundbegriffe  4

1.1.2  Kryptographische Algorithmen  5

1.1.2.1  Symmetrische Algorithmen  6

1.1.2.2  Asymmetrische Algorithmen  6

1.1.3  Kryptanalyse  7

1.2  Klassische Chiffren.  9

1.2.1  Verschiebechiffren  10

1.2.2  Multiplikative Chiffren  11

1.2.3  Tauschchiffren  14

1.2.4  Kryptanalyse monoalphabetischer Chiffren.  15

1.2.5  Die Vigenère-Chiffre.  17

1.2.5.1  Kryptanalyse nach dem Kasiski-Test  20

1.2.5.2  Kryptanalyse nach dem Friedmann-Test  22

1.3  Public-Key-Kryptographie  33

1.3.1  Allgemeines  33

1.3.2  Der RSA-Algorithmus.  33

1.3.2.1  Verwendung.  33

1.3.2.2  Mathematischer Hintergrund.  34

1.3.2.3  Die wirkliche Sicherheit von RSA.  35

2  STEGANOGRAPHIE.  36

2.1  Grundlagen  36

2.1.1  Allgemeines  36

2.1.2  Steganographie in BMP-Dateien.  37

2.1.3  Praktische Umsetzung  39

2.2  Binary Chameleon.  41

2.2.1  Einleitung  41

2.2.2  Aufbau und Funktionsbeschreibung.  41

2.2.3  Geplante Verbesserungen  47

3  MATHEMATISCHER ANHANG  48

3.1  Modulare Arithmetik  48

3.2  Euklidischer Algorithmus.  49

3.3  Die Eulersche ϕ-Funktion  55

4  LITERATUR- UND QUELLENVERZEICHNIS  57

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:

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.

Nach den Definitionen gilt folgendes:

E(M) = C

D(C) = M 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.

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 K (M) = C D K (C) = M D K (E K

(M)) = M 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 1 generiert und aus diesem einen zweiten Schlüssel K 2 . Der Schlüssel K 1 dient zur Entschlüsslung der Nachricht und der Schlüssel K 2 zur Verschlüsselung. Der Empfänger behält also den ersten Schlüssel K 1 und gibt den Schlüssel K 2 an den Sender weiter, so dass dieser ihm Nachrichten senden kann, die mit dem Schlüssel K 2 verschlüsselt sind. Man kann die Nachricht jedoch nur wieder mit dem Schlüssel K 1 , den allein der Empfänger besitzt, entschlüsseln. Aus dem Schlüssel K 2 lässt sich der Schlüssel K 1 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 K2 (M) = C Es werden unterschiedliche Schlüssel zum Chiffrieren und Dechiffrieren D K1 (C) = M D K1 (E K2

(M)) = M Die Abbildung 2 dient als Veranschaulichung eines asymmetrischen Algorithmus am Beispiel von Public-Key-Algorithmen.

In Abbildung 2 erkennt man den entscheidenden Vorteil von asymmetrischen Algorithmen. Der wichtigste Schlüssel K 1 (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 2 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.

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 l k

tz = Dauer der Zeitsperre + benötigter Rechenzeit für ein Passwort n = Mächtigkeit des Alphabets (Anzahl der verwendbaren Zeichen). l k = 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 k . 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:

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:

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:

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.

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:

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:

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 ^-1 = m

Dabei ist a ^-1 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:

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:

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:

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:

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:

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:

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.

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.

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. Spezielles Vorgehen bei einer Verschiebechiffre:

Angenommen der Angreifer weiß, dass der Klartext mit einer Verschiebechiffre verschlüsselt wurde und auf dem deutschen Alphabet von 26 Buchstaben basiert. Er ist sich ebenso sicher, dass der Geheimtextbuchstabe "K" (10) dem Klartextbuchstaben "r" (17) entspricht. Folgende Gleichung lässt sich damit aufstellen: 10 = (17 + e) mod 26

Allgemein gilt, dass bei a mod b = r, a so dargestellt werden kann: a = q*n + r Also setzt der Angreifer für a = (17 + e) ein: 17 + e = q*26 + 10

Da eine Verschiebechiffre mit e > n keine neue Chiffre ergibt, wird angenommen, dass e kleiner als n (26) ist. Wäre der Chiffretextbuchstabe kleiner als der dazugehörige Klartextbuchstabe, dann kann für q der Wert 1 eingesetzt werden. Der Angreifer kann für diese Gleichung schlussfolgern: 17 + e = 1*26 + 10 e = 1*26 + 10 - 17 = 19

Damit hat der Angreifer den Summanden e herausgefunden und kann für alle weiteren Geheimtextbuchstaben durch die entsprechende Dechiffrierfunktion mithilfe des Summanden e die Klartextbuchstaben wieder herstellen. Allgemein kann man folgende Regeln aufstellen, um den Summanden e herauszufinden, wenn ein Geheimtextbuchstabe c und der dazugehörige Klartextbuchstabe m vermutet wird:

Es wird nun in diesem Abschnitt kein direktes Beispiel folgen, wie man eine monoalphabetische Chiffre anwendet. Jedoch ist bei der Kryptanalyse der Vigenère-Chiffre ein Beispiel gegeben, bei der die monoalphabetische Kryptanalyse zur Anwendung kommt.

1.2.5 Die Vigenère-Chiffre

Diese polyalphabetische Chiffre wurde von Blaise de Vigenère erfunden und 1586 veröffentlicht. Ziel dieser Chiffre ist es, im chiffrierten Text die Buchstabenhäufigkeiten so zu verschleiern, dass eine Kryptanalyse für monoalphabetische Chiffrierungen, die letztendlich auf den Buchstabenhäufigkeiten beruht, zum Misserfolg führt. Zunächst soll die Vigenère-Chiffre in ihrer Funktionsweise vorgestellt werden und danach möchte ich 2 interessante Verfahren beschreiben, mit denen es möglich ist, diese Chiffre zu knacken.

Damit die Buchstabenhäufigkeiten im Chiffretext etwa gleich werden, darf z.B. der Buchstabe "e" nicht auf einen Chiffretextbuchstaben abgebildet werden, sondern möglichst auf mehrere verschiedene Chiffretextbuchstaben. Das heißt, der Schlüssel darf nicht nur eine einzige Zahl sein, wie bei den monoalphabetischen Verschlüsselungen, sondern sollte möglichst mehr aussagen, z.B. welche Geheimtextbuchstaben für den Klartextbuchstaben "e" abgebildet werden sollen und wie die Entschlüsslung erfolgt. Dabei wird erstmals ein Schlüsselwort k (z.B. "APFEL") als Schlüssel benutzt, was bildlich wiederholt über den Klartext (z.B. "fragezeichen") gelegt wird. Hier ein Beispiel: Schlüsselwort k:

Klartext: Nun stellt man sich jeden Buchstaben im Schlüsselwort wie einen Summanden in einer Verschiebechiffre vor, wobei der Schlüsselwortbuchstabe wieder durch seine Position e im Alphabet (beginnend ab 0) repräsentiert wird. Der darunter stehende Klartext wird dann wie ein Klartextbuchstabe in einer Verschiebechiffre behandelt und es wird der jeweilige Chiffretextbuchstabe nach der Verschlüsselungsvorschrift einer Verschiebechiffre c = (m + e) mod n berechnet. Für das obige Beispiel wäre der dazugehörige Geheimtext: Schlüsselwort k: Summand e Klartext: m Chiffretext: c = (m + e) mod 26

Für die Entschlüsslung wird das Schlüsselwort k über den Chiffretext gelegt und der Klartext mithilfe der Entschlüsslung für Verschiebechiffren wieder hergestellt: Schlüsselwort k: Summand e Chiffretext: F G F K P Z T N G S E C c Klartext

m = (c - e) mod 26 Für jeden Schlüsselwortbuchstaben entsteht also eine eigene Verschiebechiffre. Da ein Schlüsselwortbuchstabe auch ein Buchstabe innerhalb des Alphabets sein muss, gibt es in diesem Beispiel 26 Verschiebechiffren für die 26 verschiedenen Buchstaben in einem Schlüsselwort. Diese Verschiebechiffren werden im so genannten Vigenère-Quadrat aufgelistet:

Ein Beispiel zur Verschlüsselung und Entschlüsslung mithilfe des Vigenère-Quadrats Das Schlüsselwort ist "GLUCK" und wird nun sich wiederholend über den Klartext "denke viel" gelegt. Schlüsselwort: Klartext:

Für den Klartextbuchstaben "v" ist beispielsweise der zugehörige Schlüsselwortbuchstabe "G". Der Schlüsselwortbuchstabe entspricht der Zahl 6, also wird für e = 6 die sechste Zeile gesucht. Die gesuchte Spalte entspricht dann der Nummer des Klartextbuchstabens, also der Zahl 21. Der gesuchte Chiffretextbuchstabe steht demnach in Zeile 6, Spalte 21. Also lautet der Chiffretextbuchstabe "B". Der gesamte Geheimtext sieht dann wie folgt aus: "JPHMO BTYN"

Umgekehrt wird nun für den Klartextbuchstaben zuerst die Zeile des Schlüsselwortbuchstabens "G" gesucht (Zeile 6). Danach wählt man den Buchstaben "G" in Zeile 6 aus und schaut nach dem darüber liegendem Buchstaben im Klartextalphabet, womit der Klartextbuchstabe wieder "v" ist. Insgesamt entsteht wieder der Klartext: "denke viel".

Ich möchte noch eine mathematische Art der Verschlüsselung vorstellen, die ich zur programmtechnischen Umsetzung gebildet habe.

Gerade weil die Vigenère-Chiffre auf der Verschleierung der Buchstabenhäufigkeiten beruht, wird kryptanalytisch versucht durch eine Kombination aus 2 geschickten Verfahren diese Buchstabenhäufigkeiten im Chiffretext zu rekonstruieren. Diese Verfahren werden Kasiski-Test und Friedmann-Test genannt, die in den nachfolgenden 2 Abschnitten beschrieben werden. Ziel beider Tests ist es, die Schlüssellänge l k zu bestimmen.

Für die Analyse wird der folgende Chiffretext verwendet:

Dazu wird er zuerst in eine übersichtliche Form gebracht:

1.2.5.1 Kryptanalyse nach dem Kasiski-Test

Dieses Verfahren wird zunächst zur Bestimmung der Schlüsselwortlänge l k genutzt. Es wurde 1854 von einem englischen Mathematiker namens Charles Babbage erfunden und später 1863 von dem preußischen Major namens Friedrich Kasiski, nach dem dieser Test auch benannt wurde, veröffentlicht. Bei der Bestimmung der Schlüsselwortlänge wird von folgendem Grundgedanken ausgegangen: Wenn eine Zeichenfolge im Klartext (z.B. "gen") mehrmals im Klartext auftaucht, so kann der Sonderfall auftreten, dass diese Zeichenfolge mit dem gleichen Teil des Schlüsselwortes mehrmals verschlüsselt wird. Das würde bedeuten, dass genau der Teil des Schlüsselwortes wieder über dem gleichem Teil des Klartextes steht:

Schlüsselwort: Klartext: Position

Tatsächlich kann man zeigen, dass solche "Sonderfälle" gar nicht so selten sind, da gewisse Buchstabenpaare in deutschen Texten relativ oft auftauchen. Man kann mit dem Addieren der Häufigkeiten der Buchstabenpaare aus Tabelle 2 zeigen, dass 23,49 % der zufällig ausgewählten Buchstabenpaare in einem deutschen Text unter den 10 häufigsten Buchstabenpaaren der Tabelle zu finden sind, was schon fast einem Viertel entspricht. Sollte dann noch der Klartext entsprechend lang sein, erhöht das die Wahrscheinlichkeit, dass eine solche Buchstabenfolge in gleicher Position zum entsprechenden Schlüsselwortteil steht. Diese Wiederholungen treten dann natürlich auch im Chiffretext auf, das heißt dass "en" zweimal mit dem Schlüsselwortteil "LU" chiffriert wird und somit im entstehenden Geheimtext die verschlüsselte Buchstabenfolge auch zweimal an der gleichen Position auftreten würde. Da sich an dieser Stelle ein bestimmter Teil des Schlüsselworts wiederholt, muss der Abstand der Wiederholung auch ein Vielfaches des Schlüsselwortes sein. Die Anzahl der Buchstaben zwischen dem sich wiederholenden Buchstaben aus dem Buchstabenpaar addiert mit 1 ergeben den Abstand. In diesem Beispiel wäre der Abstand gleich 10, was wirklich ein Vielfaches der Schlüsselwortlänge des Schlüssels "GLUCK" ist. Natürlich können auch zufällige Wiederholungen von Buchstabenfolgen auftreten, ohne dass ein solcher Sonderfall auftritt. Aber diese sind viel seltener, da alle Buchstabenfolgen mit relativ gleicher Häufigkeit außerhalb des Sonderfalls auftreten. Zunächst wird versucht, im Beispielchiffretext derartige Wiederholungen von mindestens 4 Buchstaben zu finden. Diese wurden in der folgenden Tabelle markiert.

Es gilt allgemein beim Kasiski-Test:

Je länger der Abstand zwischen den Buchstabenfolgen, desto besser. Denn umso wahrscheinlicher ist es, dass der Abstand tatsächlich ein Vielfaches des Schlüsselworts ist und umso unwahrscheinlicher ist es, dass die Buchstabenfolge innerhalb einer Schlüsselwortlänge existiert, sodass sie zufällig entstünde. Ebenso ist ein weiteres Kriterium, dass die Buchstabenfolge mindestens aus 3 bis 4 Buchstaben bestehen sollte, da sonst die Zahl der sich wiederholenden Buchstabenfolgen zu groß wäre, was auch zu mehr zufälligen Erscheinungen führen kann.

Mit dem Vielfachen der Schlüsselwortlänge ist noch nicht die tatsächliche Schlüsselwortlänge bestimmt, also werden die möglichen Vielfachen der Schlüsselwortlänge in ihre Primfaktoren zerlegt, was für den Beispielchiffretext in der nächsten Tabelle geschieht:

Besonders auffallend ist hier die Zahl 7, welche immer wieder als Primfaktor auftaucht. Am zweithäufigsten wäre die Zahl 2, 3, 5, bzw. 2*7 = 14. Da also die mögliche Schlüssellänge sich aus den Primfaktoren der Abstände zusammensetzt, ist die Schlüssellänge am wahrscheinlichsten, welche durch die Primfaktoren der meisten Abstände repräsentiert werden kann. Folglich könnte die Schlüssellänge dem größten gemeinsamen Teiler der Abstände entsprechen. Aber wie das Beispiel zeigt, haben nicht alle Abstände den gleichen größten gemeinsamen Teiler, was die Ausnahme des Abstands für WUNS zeigt. Programmtechnisch ist also der Kasiski-Test nicht perfekt umzusetzen, da viele Faktoren berücksichtigt werden müssen und Ausnahmen unberücksichtigt bleiben müssen. Jedoch genügt es zunächst einmal, einige verdächtige Schlüssellängen zu notieren. Im Beispiel sind das:

l k1 = 7 (als verdächtigste Schlüssellänge, da sie am häufigsten als Primfaktor vorkommt) l k2 = 2 l k3 = 3 l k4 = 5 l k5 = 2*7 = 14

Im nächsten Test soll nun genauer bestimmt werden, welche dieser "Verdachtsfälle" vielleicht der richtigen Schlüssellänge entspricht.

1.2.5.2 Kryptanalyse nach dem Friedmann-Test

Der Erfinder dieser Methode heißt William Friedmann, der als bester amerikanischer Kryptologe gilt. Dieser Test wurde 1925 von ihm entwickelt. Bevor der Algorithmus beschrieben wird, sind noch einige Gedanken notwendig, um ihn zu verstehen. Dabei soll die Frage geklärt werden, was das Herausfinden der Länge des Schlüsselworts eigentlich bedeutet. Ausgegangen wird wieder von einem Klartext mit bekanntem Schlüsselwort:

Schlüsselwort Klartext Position

Die Klartextbuchstaben "d" an Position 0, "n" an Position 5, "n" an Position 10 und "o" an Position 15 werden alle mit demselben Schlüsselwortbuchstaben "G" verschlüsselt. Allgemein werden alle gleich gefärbten Klartextbuchstaben mit demselben Schlüsselwortbuchstaben verschlüsselt. Nun kann man folgende Tabelle erstellen:

Wie man erkennen kann, haben die Klartextbuchstaben, die mit demselben Schlüsselwortbuchstaben verschlüsselt wurden, den gleichen Abstand. Im vorherigen Kapitel wurde auch ein Abstand erläutert, der ein Vielfaches der Schlüsselwortlänge war. Der Abstand zwischen einem Klartextbuchstaben, der mit demselben Schlüsselwortbuchstaben verschlüsselt wurde, und seinem Nachfolger, der ebenfalls mit demselben Schlüsselwortbuchstaben verschlüsselt wurde, ist immer gleich, nämlich immer gleich der Länge des Schlüsselworts l k (hier ist l k = 5). Schlussfolgern lässt sich, dass alle zu einem Schlüsselwortbuchstaben zugehörigen Klartextbuchstaben sich immer aus dem Vielfachen der Schlüsselwortlänge addiert mit der Position des Schlüsselwortbuchstabens ergeben: p m = q*l k + p s

p m = Die Position eines beliebigen Klartextbuchstabes, der einem Schlüsselwortbuchstaben s zugeordnet ist

q*l k = Ein Vielfaches der Schlüsselwortlänge l k wobei q∈ Í 0 p s = Position des Schlüsselwortbuchstabens s, wobei gilt, p s ∈ Í 0 , p s < l k

Der Klartextbuchstabe m an p m wird also immer mit dem gleichen Schlüsselwortbuchstaben s verschlüsselt, der an Position p s steht. Für die entsprechende Position des Chiffretextbuchstabens c, der aus m p und s p erzeugt wird, gelten die gleichen Regeln. Das heißt: p c = p ^m Das heißt, alle Chiffretextbuchstaben, deren Position sich ebenfalls aus einem gleichen p ergibt, wurden alle mit demselben Schlüsselwortbuchstaben verschlüsselt. Es sei nun M c diese Menge, in der alle Chiffretextbuchstaben mit demselben Schlüsselwortbuchstaben erzeugt wurden. Dann sind automatisch alle Chiffretextbuchstaben aus M c mit derselben Verschiebechiffre erzeugt worden, denn der Schlüsselwortbuchstabe ist immer gleich. Also kann man mit dieser Menge von Chiffretextbuchstaben M c wie bei einer Kryptanalyse von einer Verschiebechiffre vorgehen, wobei die Buchstabenhäufigkeiten aus M c wieder den entsprechenden Buchstabenhäufigkeiten der jeweiligen Sprache entsprechen. Natürlich kann man in M c nur die Buchstabenhäufigkeiten einzelner Buchstaben berechnen, da Buchstabenpaare aus M c nicht als Paare im gesamten Chiffretext zu finden sind. Jetzt wurde also geklärt, warum die Länge des Schlüsselwortes l k und die daraus resultierenden Positionen der Schlüsselwortbuchstaben so wichtig für die Kryptanalyse sind. Im Friedmann-Test wird zuerst eine Schlüsselwortlänge vermutet, wobei in dem Chiffretextbeispiel schon 5 Verdachtsfälle durch

den Kasiski-Test entstanden sind. Hat man sich auf eine Schlüsselwortlänge festgelegt, so ergeben sich automatisch wieder Mengen wie M c in denen alle Chiffretextbuchstaben durch den gleichen Schlüsselwortbuchstaben erzeugt wurden. Damit tauchen auch die Buchstabenhäufigkeiten aus der Ausgangssprache wieder auf.

Jetzt gibt es für jede Sprache eine bestimmte Wahrscheinlichkeit, dass 2 zufällig gewählte Buchstaben, deren Positionen keine Rolle spielen, in einem Text dieser Sprache gleich sind. Diese Wahrscheinlichkeit, welche sich Koinzidenzindex I nennt, resultiert aus den einzelnen Buchstabenhäufigkeiten des Alphabets. Folglich hat jede Sprache basierend auf einem Alphabet seinen eigenen Koinzidenzindex I. Bei einem Text oder einer Menge von Buchstaben (z.B. M c ) kann geprüft werden, ob der Koinzidenzindex des Textes oder der Menge mit einem Koinzidenzindex I einer Sprache (z.B. der deutschen Sprache) übereinstimmt. Sollte der Koinzidenzindex der Menge M c also mit dem der deutschen Sprache übereinstimmen, dann kann man davon ausgehen, dass die vermutete Schlüssellänge und damit die Schlüsselbuchstabenposition für M c richtig vermutet wurde und man kann mit der Kryptanalyse für M c beginnen.

Doch zunächst wird gezeigt, wie der Koinzidenzindex berechnet werden kann.

Zuerst wird die Anzahl der Möglichkeiten x ermittelt, mit der 2 zufällig gewählte Buchstaben aus einer Textmenge M mit der Länge n gleich sind. Es sei x a die Anzahl der Möglichkeiten für die 2 zufällig gewählte Buchstaben aus der Menge M dem Buchstaben "a" entsprechen und es sei n 1 die Anzahl aller "a" in der Menge M. Dann gibt es n 1 Möglichkeiten, das erste Mal ein "a" aus der Menge M zu wählen. Da nun dasselbe "a" nicht noch einmal ausgewählt werden soll, gibt es nur noch (n 1 -1) Möglichkeiten ein weiteres "a" aus der Menge M zu wählen. Die Möglichkeiten nun zweimal ein "a" zu erwischen n 1 *(n 1 -1), jedoch unter Beachtung der Reihenfolge. Da es aber völlig egal ist, ergeben sich aus

welche "a" hintereinander herausgegriffen werden, wird noch zusätzlich mit k Fakultät dividiert, wobei k die Zahl der entnommenen "a" darstellt. Da in diesem Fall ein Buchstabenpaar ausgewählt wird, ist k = 2 und k! = 1 * 2 = 2. Somit ergibt sich für x a : n 1 *(n 1 - 1) x a =

2

Allgemein lässt sich die Anzahl der Möglichkeiten x B für die 2 zufällig gewählte Buchstaben aus der Menge M einem Buchstaben B (für B sind Buchstaben a bis z einsetzbar) entsprechend wie folgt darstellen: n i *(n i - 1)

x B =

2

n i = Position des Buchstabens B in der Menge M, es gilt 0 < i < 27 Die Anzahl der Möglichkeiten für einen Buchstaben B kann nun als x B berechnet werden. Dabei entspricht die Zahl x B auch der Zahl der günstigsten Fälle, in denen ein solches zufällig gewähltes Buchstabenpaar zweimal aus dem Buchstaben B besteht. Die Anzahl aller möglichen Buchstabenpaare (ohne dass es gleiche Buchstaben sein müssen) sei y B = n*(n - 1) / 2. Dabei ist n die Anzahl aller Buchstaben in der Textmenge M. Es gilt auch wieder, dass die Reihenfolge nicht beachtet wird, daher wird wieder durch k! dividiert. Die endgültige Wahrscheinlichkeit p B für einen Buchstaben B, die angibt wie groß die Chance ist, dass 2 zufällig gewählte Buchstaben aus einem Text gleich dem Buchstaben B sind, ist gleich der Anzahl der günstigsten Fälle (x B ) dividiert durch die Anzahl der möglichen Fälle (y B ). Also gilt: n i *(n i - 1)

p B =

Die Wahrscheinlichkeit, dass zwei zufällig gewählte Buchstaben aus einem Text m mit der Länge n gleich einem einzelnen Buchstaben B sind ist also gleich p B . Der Koinzidenzindex gibt jedoch nicht nur die Wahrscheinlichkeit an, wo die 2 ausgewählten Buchstaben gleich einem bestimmten Buchstaben B sind, sondern er gibt die Wahrscheinlichkeit an, wo 2 zufällig ausgewählte Buchstaben gleich sind. Das heißt, es ist völlig egal, welche Buchstaben gleich sind. Folglich ist die Wahrscheinlichkeit p, die im Koinzidenzindex I angegeben wird, gleich der Summe aus den Wahrscheinlichkeiten von p a bis p z . Man schreibt:

p =

Laut den obigen Angaben entspricht der Koinzidenzindex I genau dieser Wahrscheinlichkeit p:

Koinzidenzindex I =

Der Koinzidenzindex lässt sich also auf diese Weise für einen Text bestimmen, in dem nur die Anzahlen der jeweiligen Buchstaben (n i ) und die Länge des Textes bekannt sind. Man braucht natürlich noch den zweiten Koinzidenzindex, der zum Vergleich dient. Dieser Koinzidenzindex gibt dann die Häufigkeit p für die gesamte Sprache an. Um diesen Koinzidenzindex zu ermitteln, hat man jedoch schon die Buchstabenhäufigkeiten aus Tabelle 1 zur Verfügung. Das bedeutet, dass q als Wahrscheinlichkeit für einen zufällig gewählten Buchstaben schon gegeben ist. Zum Beispiel ist die Wahrscheinlichkeit, dass ein zufällig gewählter Buchstabe ein "a" ist gleich 6,51 % Das bedeutet q a würde 0,0651 entsprechen. Nun ist aber nicht die Wahrscheinlichkeit gesucht, womit ein zufällig gewählter Buchstabe gleich a ist, sondern es ist genau die Wahrscheinlichkeit p gesucht, womit zwei zufällig gewählte Buchstaben gleich sind. Am Beispiel vom Buchstaben "a" ist p a = q a * (q a - 1)

In allen Quellen, die das Thema des Koinzidenzindex behandeln, wird jedoch gesagt, dass der eine Sonderfall, wenn der Buchstabe "a" nochmals von der gleichen Stelle ausgewählt wird, nicht beachtet werden kann, wenn der Klartext lang genug ist. Also würde gelten:

² p a = q a * q a = q a

Der Koinzidenzindex besteht wieder als Summe aller Wahrscheinlichkeiten p a bis p z , also kann man ihn durch gegebene Buchstabenhäufigkeiten q i mit der folgenden Formel berechnen:

Koinzidenzindex I = p a + p b + ... + p z = q a

Jetzt soll der Friedmann-Test am Beispiel des gegebenen Chiffretextes beginnen. Zuerst wird der Koinzidenzindex der deutschen Sprache ermittelt, indem die aus Tabelle 1 gegebenen Häufigkeiten für q in die Gleichung dezimal eingesetzt werden:

I De = 0,065 ² + 0,0189 ² + 0,0306 ² + 0,0508 ² + 0,1740 ² + 0,0166 ² + 0,0301 ² + 0,0476 ² + 0,0755 ² + 0,0027 ² + 0,0121 ² + 0,0344 ² + 0,0253 ² + 0,0978 ² + 0,0251 ² + 0,0079 ² + 0,0002 ² + 0,07 ² + 0,0727 ² + 0,0615 ² + 0,0435 ² + 0,0067 ² + 0,0189 ² + 0,0003 ² + 0,0004 ² + 0,0113 ² ≈ 0,0762 (Die Wahrscheinlichkeit, dass ein zufällig herausgegriffenes Buchstabenpaar aus einem deutschen Text aus gleichen Buchstaben besteht, entspricht also I De * 100 = 7,62 %)

Da die Buchstabenhäufigkeiten in einer Vigenère-Chiffre geringere Unterschiede aufweisen, kann man annehmen, dass jeder Buchstabe mit gleicher Häufigkeit auftritt und deshalb mit gleicher

Wahrscheinlichkeit (

Koinzidenzindex aus, so erhält man: ²⁶ I V = ∑ 1 1 ⁺ ... + 1 26 1

26 ) ² = 26 ≈ 0,0385 ( 26 2 = 26 2 =

26 2

i=1

Die Wahrscheinlichkeit, dass ein zufällig ausgewähltes Buchstabenpaar aus denselben Buchstaben besteht, ist mit 3,85 % bei einer Vigenère-Chiffre deutlich geringer als bei einem Text, wo die deutschen Buchstabenhäufigkeiten noch vorhanden sind. Zu einem solchen Text zählt sowohl ein Klartext, als auch ein monoalphabetisch verschlüsselter Klartext. Folglich kann man mit dem Bestimmen des Koinzidenzindex herausfinden, ob ein Chiffretext durch eine Vigenère-ähnliche Chiffre erzeugt wurde oder ob er durch eine monoalphabetische Chiffre erzeugt wurde. Zunächst soll am Beispielchiffretext geprüft werden, ob er durch eine Vigenère-Chiffre kodiert wurde. Dazu werden zuerst die einzelnen Buchstaben im Chiffretext gezählt:

Koinzidenzindex I C des Chiffretextes wird nun durch das Einsetzen der entsprechenden Werte mithilfe der Formel

I C =

Man kann sehen, dass der Koinzidenzindex in diesem Beispiel vom Ideal-Koinzidenzindex I V der Vigenère-Chiffre etwas abweicht. Wie in der Stochastik gilt auch hier, dass sich die tatsächlichen Häufigkeiten, die in einem Versuch beobachtet werden mit der Anzahl der Versuche immer mehr den rechnerischen Häufigkeiten annähern. Das gilt hier genauso, nur dass die Anzahl der Versuche gleich der Anzahl der Buchstaben des Chiffretextes sind.

Da der Koinzidenzindex des Chiffretextes viel weniger dem Koinzidenzindex der deutschen Sprache entspricht, ist anzunehmen, dass es sich um eine Vigenère-Chiffre handelt. Jetzt werden die vermuteten Schlüssellängen auf ihre Richtigkeit geprüft. Bei einer vermuteten Schlüssellänge ergeben sich wieder Mengen wie M c , die alle Chiffretextbuchstaben enthalten, welche mit demselben Schlüsselwortbuchstaben verschlüsselt wurden und somit ein Ergebnis der gleichen Verschiebechiffre sind. Demnach gelten für diese Chiffretextbuchstaben aus M c wieder die Buchstabenhäufigkeiten der deutschen Sprache und damit entspricht auch der Koinzidenzindex von M ^c dem der deutschen Sprache, sofern die Schlüssellänge richtig vermutet ist. Da nun 5 vermutete Schlüssellängen zu Auswahl stehen, wird jede Länge geprüft, indem für die entstehenden Mengen der Koinzidenzindex berechnet wird. Die Schlüssellänge, bei der der Koinzidenzindex der Mengen M c am meisten dem Koinzidenzindex der deutschen Sprache ähnelt, trifft vermutlich zu. Die erste Schlüssellänge ist 7. Dadurch entstehen folgende Mengen, die die Chiffretextbuchstaben enthalten, welche mit demselben Schlüsselwortbuchstaben verschlüsselt wurden. Die Positionen der Chiffretextbuchstaben ergeben sich aus der hergeleiteten Formel: p c = q*l k + p ^s Schlüssellänge l k = 7

Im Durchschnitt beträgt der Koinzidenzindex hier ≈ 0,0748, was schon in etwa dem Koinzidenzindex I De ≈ 0,0762 der deutschen Sprache entspricht. Also lässt sich bereits vermuten, dass die Schlüssellänge 7 hier ganz gut zutreffen könnte. Um Platz zu sparen sind in der nachfolgenden Tabelle nur noch die Durchschnittskoinzidenzindexe für die entsprechenden Schlüssellängen aufgelistet.

Wie man sieht, können die Verdachtsfälle in denen die Schlüssellänge gleich 2, 3 oder 5 ist ausgeschlossen werden. Jetzt gibt es nur noch 2 Verdachtsfälle, bei denen der Durchschnittskoinzidenzindex dem der deutschen Sprache sehr ähnelt. Allerdings kann man die Schlüssellänge 14 aus folgenden Gründen anzweifeln.

Zum einen treten bei der Schlüssellänge 14 sehr große Schwankungen bezüglich der Koinzidenzindexe der einzelnen Textmengen von M 0 bis M 13 auf, wobei diese bei der Schlüssellänge 7 alle relativ gleich sind. Das bedeutet, es sind in den Teiltexten entweder die Häufigkeiten viel größer (Maximum = 0,0941) als 0,0762 oder viel kleiner (Minimum = 0,0546). Man kann daraus schlussfolgern, dass man bei der Bewertung der vermuteten Schlüssellängen nicht nur auf den Durchschnittskoinzidenzindex achten sollte, denn auch die Koinzidenzindexe der einzelnen Textmengen sollten sich bereits dem Wert 0,0762 annähern.

Zum anderen ist klar, dass die Textmenge M 0 der Schlüssellänge 7 eine Zusammenfassung aus den Textmengen M 0 und M 7 der Schlüssellänge 14 ist, da 14 ein Vielfaches von 7 ist. Genauso müsste man bei der Schlüssellänge 7 jeden 7. und jeden 14. Buchstaben, sowie weitere Vielfache in eine Textmenge stecken. Bei der Schlüsselmenge 14 hingegen werden die 7. Buchstaben und die 14. Buchstaben separat in zwei Mengen aufgeteilt. Es folgt, dass die Koinzidenzindexe für die Teiltexte der Schlüssellänge 7 ebenfalls wie die Textmengen der Schlüssellänge 7 unter den Teiltexten für die Schlüssellänge 14 "aufgeteilt" werden.

Ein letzter Punkt, an dem man fest machen kann, dass die Schlüssellänge 7 viel mehr in Frage kommt, ist die folgende Annahme. Wenn die Schlüssellänge 14 betragen würde, dann würden in den Teiltexten der Schlüssellänge 7 die Buchstabenhäufigkeiten sich mehr dem Ideal-Koinzidenzindex für einen Vigenère-Chiffretext annähern, da nur jeder Buchstabe, dessen Position einem Vielfachen von 14 (addiert mit einem Rest kleiner 14) entspricht, mit dem gleichen Schlüsselwortbuchstaben verschlüsselt worden wäre.

Bevor nun die monoalphabetische Kryptanalyse für die einzelnen Teiltexte beginnt, wird der echte Friedmann-Test noch hergeleitet. Dieser Test liefert die eigentliche Schlüssellänge in einer Formel, die allein vom Koinzidenzindex des gesamten Chiffretextes (ausgehend von der deutschen Sprache) abhängig ist. Es ist wesentlich besser die Schlüssellänge über eine Formel zu bestimmen, als jedes Mal Koinzidenzindexe für mehrere Teiltexte zu errechnen und zu vergleichen. Um eine solche Formel herzuleiten, braucht man einige Vorüberlegungen. Zum einen soll die Formel nur vom Koinzidenzindex I des Chiffretextes abhängen, zum anderen muss in irgendeiner Form die Schlüssellänge l k in eine Gleichung gebracht werden. Um eine solche Gleichung herzuleiten, wird davon ausgegangen, dass l k bereits die richtige Schlüssellänge ist. Dann kann man folgende Aussagen treffen:

Wenn l k die richtige Schlüssellänge ist, entspricht der Koinzidenzindex der einzelnen Textmengen, die sich durch l k ergeben, etwa 0,0762. Es ist also zu 7,62 % wahrscheinlich, dass irgendein Buchstabenpaar aus einem Teiltext aus gleichen Buchstaben besteht. Die Wahrscheinlichkeit ist somit gegeben. Jetzt wird nur noch eine mathematische Aussage aller möglichen Fälle benötigt, bei denen diese Wahrscheinlichkeit eintreten kann. Angenommen man wählt einen Buchstaben (egal aus welcher Spalte). Dann hat man n Möglichkeiten (n entspricht wieder der Länge des Chiffretextes). Wenn man einen Buchstaben ausgewählt hat, muss man den zweiten Buchstaben aus derselben Textmenge wählen, in der sich der erste befunden hat. Es gibt in einer Textmenge n / l k Buchstaben (alle zu einem Schlüsselwortbuchstaben gehörenden Chiffretextbuchstaben sind in einer solchen Textmenge

zusammengefasst), wobei die restlichen Buchstaben, die bei der Division übrig bleiben, nicht beachtet werden (Es wird immer davon ausgegangen, dass der Chiffretext so lang ist, dass dies keine Rolle spielt). Man muss also für den zweiten Buchstaben nur noch die Möglichkeit betrachten, diesen aus der gleichen Textmenge zu wählen. Das bedeutet auch, es stehen n / l k Buchstaben zur Verfügung. Dabei muss bedacht werden, dass bereits schon ein Buchstabe aus dieser Textmenge gewählt wurde. Also gibt es für den zweiten Buchstaben (n / l k ) - 1 Möglichkeiten. Die Gesamtmöglichkeit m 1 , zwei Buchstaben aus derselben Textmenge zu erwischen ergibt sich aus dem Produkt der beiden Möglichkeiten, wieder dividiert durch k! = 2 * 1 = 2: n

m 1 =

Dabei gibt m 1 nur die Anzahl der möglichen Fälle an. Oben wurde aufgeführt, dass es zu 7,62 % wahrscheinlich ist, dass ein Buchstabenpaar aus der gleichen Spalte aus zwei gleichen Buchstaben besteht. Somit erhält man die Zahl der günstigen Fälle f 1 , in denen dieser Fall auch auftritt, indem man die Zahl der möglichen Fälle mit der Wahrscheinlichkeit multipliziert:

f 1 = m 1 * 0,0762 =

Für den zweiten Gedanken betrachtet man die Wahrscheinlichkeit, dass ein Buchstabe aus einer Textmenge und ein Buchstabe aus einer anderen Textmenge gleich sind. Wenn man davon ausgeht, dass das Schlüsselwort aus lauter unterschiedlichen Buchstaben besteht, dann entstehen auch für jeden Teiltext unterschiedliche Verschiebechiffren. Die Chance, dass dann ein Buchstabe aus der einen und ein Buchstabe aus der anderen Textmenge gleich sind, entspricht dann dem Ideal-Koinzidenzindex der Vigenère-Chiffre, also 3,85 %. Das ist so, weil die Buchstabenhäufigkeiten außerhalb einer Textmenge genau den Buchstabenhäufigkeiten des gesamten Chiffretextes entsprechen (Es besteht ja außerhalb einer Textmenge kein Bezug auf die Buchstabenhäufigkeiten der deutschen Sprache.). Sollten im Schlüsselwort mehrere Buchstaben gleich sein, dann können auch einige Textmengen gleiche Buchstabenhäufigkeiten haben. Dann wäre die Wahrscheinlichkeit, dass zwei Buchstaben aus verschiedenen Textmengen gleich sind, höher. Jedoch wird in allen Quellen ausgesagt, dass die Wahrscheinlichkeit damit nur gering steigt. Somit könnte jedoch ein Schlüsselwort mit mehreren gleichen Buchstaben dazu beitragen, dass die Formel, welche jetzt hergeleitet wird, möglicherweise zu einem falschen Ergebnis führt. Nun muss aber wieder geklärt werden, wie viele Möglichkeiten es gibt, 2 Buchstaben aus unterschiedlichen Textmengen bei bekannter Schlüssellänge k aus einem Chiffretext herauszupicken. Es gilt wieder, dass am Anfang n Möglichkeiten zur Verfügung stehen. Bei der nächsten Auswahl des Buchstaben soll nun ein Buchstabe aus einer anderen Textmenge gewählt werden. Dann bleiben automatisch noch n - n/l k Textmengen übrig, wobei n/l ^k genau die Textmenge ist, aus der der erste Buchstabe gewählt wurde. Folglich ergibt sich nun wieder die Anzahl der Möglichkeiten für m 2 nach dem ähnlichen Prinzip wie oben:

m 2 =

Es gilt nun wieder, dass m 2 nur die Zahl der möglichen Fälle angibt. Die Zahl der günstigen Fälle, in denen die gewählten Buchstaben tatsächlich gleich sind wäre dann diese Zahl der möglichen Fälle m ² multipliziert mit der Wahrscheinlichkeit, dass sie gleich sind, also 0,0385 (3,85 %). Folglich ist gilt für f 2 :

f 2 = m 2 * 0,0385 =

Die Zahl f 1 gibt also die Anzahl der günstigen Fälle an, in denen ein Buchstabenpaar aus einer gleichen Textmenge gleich ist und die Zahl f 2 gibt die Anzahl der günstigen Fälle an, in denen ein

Buchstabenpaar aus unterschiedlichen Textmengen gleich ist. Die Zahl der günstigen Fälle f, für die aus dem ganzen Chiffretext 2 Buchstaben gewählt werden und gleich sind, setzt sich somit aus f 1 und f ² zusammen. Das kann man zeigen, wenn man die Möglichkeiten m 1 und m 2 addiert:

m =

m sind also alle Möglichkeiten, die entstehen können, wenn 2 Buchstaben aus dem gesamten Chiffretext gewählt werden (wie immer ohne Beachtung der Reihenfolge). Also kann man auch davon ausgehen, dass die Gesamtanzahl f der günstigen Fälle gleich der Summe aus f 1 und f 2 ist.

f = f 1 + f 2 =

Nun gibt der Koinzidenzindex I C eines Chiffretextes an, wie wahrscheinlich es ist, dass zufällig ein Buchstabenpaar aus dem Chiffretext aus gleichen Buchstaben besteht. Es gilt wieder I C = p = Anzahl der günstigsten Fälle (f) dividiert durch Anzahl der möglichen Fälle (m). Also gilt:

I C =

I C =

I C =

I C * l k *(n - 1) = n * 0,0377 - l k * (0,0762 - n*0,0385)

I C * l k *(n - 1) + l k * (0,0762 - n*0,0385) = n * 0,0377 l k * (I C *(n - 1) + 0,0762 - n*0,0385) = n * 0,0377 n * 0,0377

l k =

I C *(n - 1) + 0,0762 - n*0,0385

Die Schlüssellänge, von der von Anfang an vermutet wurde, dass sie richtig ist, lässt sich nun nach dieser Formel berechnen. Dazu muss man lediglich den Koinzidenzindex eines Chiffretextes ausrechnen und für I C einsetzen. Die Variable n entspricht nach wie vor der Länge des Chiffretextes. Jetzt ist es an der Zeit die vermutete Schlüssellänge 7 nochmals über die hergeleitete Formel zu überprüfen. Da der Koinzidenzindex bereits ausgerechnet wurde (I C = 0,042501386) und der Klartext aus 601 Buchstaben besteht (n = 601), muss nur noch eingesetzt werden: 601 * 0,0377

0,042501386 *(601 - 1) + 0,0762 - 601*0,0385 = 9,291534299 ≈ 9 l k =

Dabei ist 7 die vermutete Schlüssellänge. Diese nähert sich der ausgerechneten Schlüssellänge am meisten. Man kann an diesem Beispiel sehen, dass der Kasiski-Test und der Friedmann-Test durchaus

unterschiedliche Schlüssellängen liefern. Es sollten also immer beide Tests zusammen durchgeführt werden. Dabei kommt es bei der Formel deswegen zur Abweichung, weil gesagt wurde, dass der Koinzidenzindex genau dieser Wahrscheinlichkeit p entsprechen soll. Da aber der Koinzidenzindex einer Vigenère-Chiffre auch nicht unbedingt gleich dem Ideal-Koinzidenzindex der Vigenère-Chiffre sein muss, kann man den Koinzidenzindex nur "ungefähr" gleich setzen. Die Abweichungen ergeben sich unter anderem durch die fehlenden Buchstaben, die bei der Division der Gesamtanzahl der Buchstaben n durch die vermutete Schlüssellänge als Rest übrig geblieben sind.

Da die Schlüssellänge 7 nun durch die Friedmann-Formel für die Schlüssellänge bestätigt wurde, kann man nun wieder jede Textmenge als einen, durch eine Verschiebechiffre erzeugten, Geheimtext betrachten. Also wird der Buchstabe bestimmt, welcher in jeder Textmenge am häufigsten ist. Dieser Buchstabe müsste dann nach den Buchstabenhäufigkeiten der deutschen Sprache dem Buchstaben "e" entsprechen. Ist der Geheimtextbuchstabe für den Klartextbuchstaben "e" sicher bestimmt, kann nach dem speziellen Verfahren für die Kryptanalyse von Verschiebechiffren der Schlüsselwortbuchstabe der zugehörigen Textmenge rekonstruiert werden. Begonnen wird nun damit, den häufigsten Buchstaben jeder Textmenge auszuzählen:

Natürlich kann man nicht einfach davon ausgehen, dass der häufigste Chiffretextbuchstabe, dem Klartextbuchstaben "e" entspricht. Es sind meistens 2 bis 3 Buchstaben vorhanden, deren Häufigkeiten sich deutlich von den anderen unterscheiden. Dann muss systematisch probiert werden, welcher Chiffretextbuchstabe dem Buchstaben "e", welcher dem Buchstaben "n" oder welcher dem Buchstaben "a" entspricht. Für diesen Fall wird einfach angenommen, dass der häufigste Buchstabe dem

Buchstaben "e" entspricht, da die Textmengen groß genug sind und die enthaltenden Buchstaben sich somit den Buchstabenhäufigkeiten der deutschen Sprache anpassen. Für das Beispiel kann folgendes angenommen werden: "e" 1 # "O" "e" 2 # "S" oder "e" 2 # "G" "e" 3 # "Q" "e" 4 # "M" "e" 5 # "W" "e" 6 # "G" "e" 7 # "L"

Für den Geheimtextbuchstaben "O" soll nun der Schlüssel mittels des speziellen Verfahrens bei Verschiebechiffren gefunden werden. Aus den Positionen (wieder beginnend ab 0) der Buchstaben ergibt sich für "O" c = 14 und für "e" m = 4. Es gilt c > m, also ist der Schlüssel e (oder additive Verschiebung) e 0 = c - m = 14 - 4 = 10

e entspräche in einem Klartextalphabet dem Buchstaben "K". Also kann angenommen werden, dass K der erste Buchstabe des Schlüssels ist. Wenn man für die restlichen Zuordnungen diese Prozedur wiederholt, so erhält man folgende Lösungen für die Schlüsselwortbuchstaben: e 0 = 10 ("K")

e 1 = 14 ("O") für "e" 1 # "S" und e 1 = 2 ("C") für "e" 2 # "G" e 2 = 12 ("M") e 3 = 8 ("I") e 4 = 18 ("S") e 5 = 2 ("C") e 6 = 7 ("H")

Je nach angenommenen e 1 ergibt sich hier entweder das Schlüsselwort "KOMISCH" oder "KCMISCH". Geht man davon aus, dass das Schlüsselwort einen wörtlichen Sinn haben sollte, dann wäre "KOMISCH" wahrscheinlich das gesuchte Schlüsselwort. In Fällen, wo das Schlüsselwort keinen Sinn ergeben sollte, ist es meist besser, den Klartext nur für die Buchstaben einer Textmenge des Chiffretextes zu rekonstruieren, bei denen man sich der Zuordnung sicher ist. Um an dieser Stelle den Klartext zu reproduzieren, muss man den Chiffretext lediglich über die normale Entschlüsslung der Vigenère-Chiffre mithilfe des vermuteten Schlüsselworts reproduzieren. Also ergibt sich aus dem Chiffretext

Der sicherlich sinnlich sehr fragwürdige Klartext:

Geschafft! Der Chiffretext ist entschlüsselt und die Kryptanalyse war erfolgreich. Die wichtigsten Formeln aus diesem Abschnitt zeigt diese Zusammenfassung:

1.3 Public-Key-Kryptographie

1.3.1 Allgemeines

Public-Key-Kryptographie zählt zu den asymmetrischen Verschlüsselungstechniken. Durch diese Form der Kryptographie ist es möglich, den sonst so gefährlichen Schlüsselaustausch zu vermeiden. Eine Nachricht wird beispielsweise mit einem Schlüssel d chiffriert. Dabei ist d ein so genannter öffentlicher Schlüssel (public-key), der jedem zur Verfügung stehen darf. Denn nur der Empfänger kennt den privaten Schlüssel e (private key), mit der die Nachricht entschlüsselt werden kann. Dabei kann man vom öffentlichen Schlüssel keine Rückschlüsse auf den privaten Schlüssel ziehen. Die allgemeine Funktionsweise ist im Abschnitt 1.1.2.2 übersichtlich erläutert worden.

Diese Art der Kryptographie ist für mich am faszinierendsten von allen kryptographischen Algorithmen. Die benötigte Mathematik, die dahinter steckt, ist gar nicht mal so kompliziert. Trotzdem wird solch ein fast unglaublicher Effekt erzielt. Der folgende Abschnitt beschreibt ein Public-Key-Verfahren, was sich RSA nennt. In dem Abschnitt wird auch der mathematische Hintergrund erklärt, der ein solches Verfahren möglich macht. Für den gesamten Abschnitt werden alle Kenntnisse aus dem mathematischen Anhang, Abschn. 3 benötigt.

1.3.2 Der RSA-Algorithmus

Im Jahr 1977 schafften es die 3 Mathematiker Ronald Rives, Adi Shamir und Leonard Adleman nach mehreren Monaten den bekannten RSA-Algorithmus zu entwickeln. Dieser gilt als der berühmteste Public-Key-Algorithmus und wird heute noch eingesetzt.

1.3.2.1 Verwendung

Der RSA-Algorithmus soll nun allgemein und anhand eines Beispiels demonstriert werden. Als ersten Schritt gilt es, den öffentlichen und privaten Schlüssel zu erzeugen, damit die Vorraussetzungen für Ver- und Entschlüsslung geschaffen werden.

Zunächst wählt man 2 große Primzahlen p und q. Nach den Quellen sollen diese 512 Bit betragen, was wohl den heutigen Sicherheitsstandard darstellt. Zur Vereinfachung werden hier im Beispiel kleinere Primzahlen gewählt (p = 23; q = 71). Nun berechnet man das Produkt der beiden Primzahlen n. Also gilt

n = 23 * 71 = 1633. Jetzt sucht man nach einer Zahl e, dessen größter gemeinsamer Teiler mit ϕ(n) = (p - 1) * (q - 1) = 22 * 70 = 1540 gleich 1 ist. Das heißt, e soll teilerfremd zu ϕ(n) sein. Im Beispiel ist e = 17. Als nächstes wird d als modulares Inverses zu e mod ϕ(n) gesucht, was mit dem erweiterten Euklidischen Algorithmus berechnet werden kann, denn der größte gemeinsame Teiler von e und ϕ(n) ist 1. Nach diesem Algorithmus ist d = 453. Der öffentliche Schlüssel ist das Zahlenpaar e und n, welches dem Sender ("Verschlüssler") geschickt wird. Der private/geheime Schlüssel ist d und n und bleibt beim Empfänger ("Entschlüssler").

Jetzt hat man die Möglichkeit eine Nachricht zu chiffrieren. Dabei werden z.B. wieder in einem deutschen Alphabet die Positionen der Buchstaben verwendet. Ziel ist es nun den Buchstaben "P" zu verschlüsseln. Er besitzt im Alphabet die Position 15, also ist m = 15. Nun erhält man den dazugehörigen Chiffretextbuchstaben c durch c = m e mod n = 15 ¹⁷ mod 1633 = 240

Es ist aber nicht möglich, einen Buchstaben mit der Position 240 im deutschen Alphabet zu finden. Das soll auch nicht so sein, denn der RSA-Algorithmus wurde lediglich für digitale Zwecke entwickelt, wodurch "Chiffretextbuchstaben" und "Klartextbuchstaben" binär dargestellt werden. Jetzt soll der Empfänger mithilfe des Zahlenpaares d und n wieder m berechnen: m = c d mod n = 240 ⁴⁵³ mod 1633 = 15

Tatsächlich erhält man wieder den Klartextbuchstaben mit der Position 15, "P".

Es besteht nun das Problem, wie man den Chiffretext so darstellt, dass die Chiffretextbuchstaben voneinander zu trennen sind. Wenn die Primzahlen p und q jeweils aus 512 Bit bestehen sollen, dann besteht n aus 2 * 2 ⁹ Bit = 2 ¹⁰ Bit = 1024 Bit. Nun ist jeder Chiffretextbuchstabe wegen der Modulo Operation kleiner n. In diesem Fall kann man also jeden Chiffretextbuchstaben durch 1024 Bit darstellen, womit man auch danach wieder stückweise nacheinander 1024 Bit entschlüsseln kann. Jedoch werden die Klartextbuchstaben nicht einzeln verschlüsselt. Es würde dann wieder jedem Klartextbuchstaben der gleiche Chiffretextbuchstabe zugewiesen werden. Damit wäre der Chiffretext durch eine monoalphabetische Kryptanalyse zu knacken. Es werden daher die Bitfolgen mehrerer Klartextbuchstaben zu einer einzigen Zahl zusammengefasst, welche dann als Klartextmenge zu einer Chiffretextmenge chiffriert wird. Beispielsweise werden 128 Zeichen als eine Bitzahl von 128 * 8 Bit = 1024 Bit zusammengefasst (jedes Zeichen wird durch 8 Bit dargestellt). Dabei werden etwa so viele Zeichen zusammengefasst, dass die Bitgröße der Gesamtbitzahl der Bitgröße von n entspricht (wie es in diesem Rechenbeispiel der Fall ist).

Es folgt nun eine verallgemeinerte Zusammenfassung der Schritte für die Verschlüsselung:

1.3.2.2 Mathematischer Hintergrund

Nun soll gezeigt werden, wieso dieser Algorithmus funktioniert. Mithilfe des Satzes von Euler konnte ich das sehr schnell zeigen. c = m ^e mod n m = c ^d mod n

Nun kann man für c in der zweiten Gleichung einsetzen (siehe. mathematischer Anhang, Abschn. 3): m = (m ^e mod n) ^d mod n = m ^e*d mod n

Jetzt muss nur noch gezeigt werden, dass m = m e*d mod n wirklich gilt.

Dazu wird die Vorraussetzung betrachtet, dass d ein multiplikatives Inverses zu e mod n ist. Man kann also für d schreiben: 1 = (e*d) mod ϕ(n)

Nun kann e*d wieder in die alternative Schreibweise umgeformt werden: e*d = q*ϕ(n) + 1

Dieser Term wird für e*d in der obigen Gleichung eingesetzt: m = m ^{q*ϕ(n) + 1} mod n m = (m * m ^q*ϕ(n) ) mod n

Nach dem Satz von Euler gilt: m ^ϕ(n) mod n = 1. Also kann 1 für m ^ϕ(n) eingesetzt werden: m = (m * 1 ^q ) mod n m = m mod n (da m < n wegen Einschränkung folgt...) m = m

Damit konnte gezeigt werden, dass tatsächlich unter der gegebenen Schlüsselerzeugung die Verschlüsselung und die Entschlüsslung für alle m funktioniert.

1.3.2.3 Die wirkliche Sicherheit von RSA

Nun habe ich oben behauptet, dass der geheime Schlüssel nicht durch den öffentlichen Schlüssel berechnet werden kann. Das ist mathematisch gesehen nicht ganz korrekt. Als ich mich mit dem RSA-Algorithmus erstmals beschäftigt habe, konnte ich nicht verstehen, wieso der geheime Schlüssel (e und n) nicht aus dem öffentlichen Schlüssel (d und n) berechnet werden kann. Wie nun aufgeführt wurde, ist d nämlich ein multiplikatives Inverses zu e mod ϕ(n). Es gilt also: (d*e) mod ϕ(n) = 1

Demnach ist e auch invers zu d mod ϕ(n) und man könnte e mithilfe des erweiterten Euklidischen Algorithmus berechnen. Dazu braucht man lediglich ϕ(n) und genau hier liegt der Knackpunkt. Es ist zwar n gegeben, aber um daraus ϕ(n) zu ermitteln müsste man entweder alle zu n teilerfremden Zahlen zählen (das wäre bei einer 1024 Bit großen Zahl mit extrem viel Rechenzeit verbunden) oder man findet die Primfaktoren für n. Denn n wird laut Verschlüsselung aus p und q berechnet. Demnach kann ϕ(n) ebenfalls aus p und q berechnet werden. Das heißt, das Ziel des Angreifers bestünde nun darin, n in seine Primfaktoren zu zerlegen. Wenn für n relativ hohe Zahlen verwendet werden, dann ist es sehr schwierig daraus die Primfaktoren zu ermitteln. Es gibt zwar einige Verfahren, mit denen man die Primzahlen bestimmen kann, aber diese nützen in diesem Fall kaum etwas, da der Zeitaufwand zu

hoch ist. Man kann z.B. aus n = p*q schlussfolgern, dass entweder p oder q kleiner als n ist, denn es gilt n = n * n, wobei p und q in diesem Fall gleich groß wären. Ansonsten müsste einer der Faktoren kleiner als n sein, wenn der andere Faktor größer als n ist.

Zusammenfassend kann man jedoch sagen, dass die Sicherheit von RSA von der Größe von n abhängt und somit von der Größe der gewählten Primzahlen p und q. Dabei ist es nur wegen des Zeitaufwandes nicht möglich den geheimen Schlüssel e zu ermitteln. Anmerkung: In der Programmiersprache Java reicht der größte Variablentyp "long" von -9223372036854775808 bis 9223372036854775807.Also werden für eine Variable des Zahlentyps "long" 64 Bit (ein Bit für das Vorzeichen) reserviert. Wenn man ein Programm für den RSA-Algorithmus programmieren würde, dann könnte man folglich mit keinen Primzahlen mit einer Größe von 512 Bit arbeiten. Daher ist es programmtechnisch wesentlich komplizierter den RSA-Algorithmus umzusetzen, da man über Umwege gehen muss (z.B. Zahlendarstellung über Speicherfelder (Arrays) und damit verbundene Rechenoperationen mit Feldern).

2 Steganographie

2.1 Grundlagen

2.1.1 Allgemeines

Man betrachte die folgenden zwei Bilder.

Es ist optisch wohl kein Unterschied zu erkennen. Dennoch befindet sich in Bild 2 das gesamte Microsoft Word Dokument des Inhaltsverzeichnisses dieser Jahresarbeit. Die Bilder haben selbstverständlich als Datei dieselbe Dateigröße. In diesem Teil der Jahresarbeit soll die Wissenschaft erläutert werden, die solche Dinge möglich macht - die Steganographie. Darunter wird zusätzlich der praktische Teil meiner Jahresarbeit erläutert, ein Steganographie-Programm, welches die Vereinigung aus Steganographie und Kryptologie praktisch in einem anspruchsvollen Niveau umsetzt. Die Steganographie ist die Wissenschaft, Nachrichten in anderen Informationen zu verstecken. Sie dient als eine neue Alternative der Kryptologie, da das Verschlüsseln von Nachrichten mittels kryptographischer Verfahren in einigen Ländern verboten ist (damit z.B. terroristische Planungen überwacht werden können). Ein klassisches Beispiel für die Steganographie ist der so genannte Microdot. Er wurde im zweiten Weltkrieg von deutschen Wissenschaftlern entwickelt. Dabei klebte man einen Microfilm, der so groß wie ein "I"-Punkt war, auf die Satzzeichenpunkte oder "I" Punkte in Schreibmaschinentexten. Natürlich konnte man dem Text äußerlich nicht ansehen, dass er viele Microfilme enthielt, die wiederum geheime Informationen beinhalteten. In dieser Arbeit wird aber nur auf die computergestützte Steganographie eingegangen, die auf dem Verstecken von geheimen Daten in geeigneten Dateien basiert.

Digital lässt sich jede Datei, jede Nachricht und jeder Buchstabe als eine Folge von Einsen und Nullen darstellen, man spricht vom Binärsystem. Dabei wird z.B. jedem Buchstaben (man spricht allgemein von einem ASCII-Zeichen) eine dezimale Nummer von 0 bis 255 zugewiesen. Also kann man jedes Zeichen als eine Folge von 8 Einsen und Nullen (8 Bit = 1 Byte) darstellen, denn in einem Byte können genau 2 8 = 256 verschiedene Werte dargestellt werden. Im Tafelwerk kann man alle ASCII Zeichen mit

ihren zugewiesenen dezimalen Werten in einer Tabelle betrachten.

Wenn ein Computer nun die Zeichenfolge 0100 0001 = 65 einließt, wird er sie als den Buchstaben "A" ausgeben. Angenommen der Buchstabe "A" soll in einem Text versteckt werden. So kann z.B. folgender "Trägertext" erzeugt werden: "Hey, habe ich dir die Zeitung schon gebracht?"

Natürlich fragt man sich jetzt, wo hier der Buchstabe „A“ versteckt sein soll. Die Antwort ist relativ simpel. Zuerst zerlegt man den Buchstaben „A“ in seine Bitfolge, also 0100 0001. Nun wird aus der Bitfolge ein Satz erzeugt, wobei die 0 für ein Wort mit einer ungeraden Zahl von Buchstaben und die 1

für ein Wort mit einer geraden Zahl von Buchstaben steht. Um den Buchstaben „A“ aus dem Text wieder herauszuholen, zählt man die Buchstaben von jedem Wort und setzt für jedes Wort entsprechend eine 0 oder eine 1 sein. So erhält man wieder die Bitfolge 0100 0001, welche dem dezimalen Wert 65 für den Buchstaben „A“ entspricht.

Man unterscheidet in der computergestützten Steganographie folgende Arten von Dateien:

Da die computergestützte Steganographie definitiv zu den neueren Wissenschaften zählt, gibt es bis jetzt nur relativ wenige Steganographie-Programme, was jedoch teilweise auch am Entwicklungsaufwand liegt. Bei dem JPEG-Format ist es beispielsweise notwendig, sich mit der sehr komplizierten verlustbehafteten JPEG-Kompression auseinanderzusetzen. Ebenso gibt es bis jetzt nicht genügend Literatur, die eine qualitative Steganographie für bestimmte Dateien beschreibt.

2.1.2 Steganographie in BMP-Dateien

Da die so genannten Windows Bitmap-Dateien in ihrer Struktur leicht zu verstehen sind und keine verlustbehafteten Kompressionen besitzen, wird in diesem Abschnitt anhand dieser Dateien die computergestützte Steganographie näher erläutert.

BMP-Dateien sind Bilddateien, die aus einem Header (Dateienkopf) und aus den tatsächlichen Bildinformationen bestehen. Der Header spielt in diesem Abschnitt keine Rolle. Es werden zuerst die Bildinformationen näher betrachtet.

Hat eine Bilddatei 24 Bit Farbtiefe, so wird die Farbe eines Bildpunkt durch einen Rot-Wert (8 Bit), einen Grün-Wert (8 Bit) und einen Blau-Wert (8 Bit) repräsentiert. Das bedeutet, die Farbe setzt sich aus einer additiven Farbmischung der 3 Farbanteile (RGB-Werte) zusammen. Also besteht die Farbe eines Bildpunktes (Pixels) aus 8+8+8 = 24 Bit = 3 Byte. Die folgende Tabelle zeigt einige Farben und die zugehörigen Werte, um die additive Farbmischung zu verdeutlichen:

Die Farbe eines Pixels wird also durch diese 3 Byte bestimmt. Die Position des Pixels ergibt sich aus der Anordnung der Bildpunkte. Das soll bedeuten, dass in einer Bitmapdatei alle Bildpunkte hintereinander geschrieben werden. Es werden so Bildzeile für Bildzeile die Bildpunkte aneinander gereiht, wobei einige Regeln gelten:

Es wird bei der untersten Bildzeile begonnen (Bildpunkte werden von links nach rechts beschrieben)

Die Farbanteilanordnung wird "gespiegelt". Das heißt, dass der Rote Farbwert in der Farbbeschreibung mit dem Blau-Wert tauscht. Die Anordnung wäre dabei BGR Es werden zwischen den beschriebenen Zeilen so genannte Null-Bytes eingefügt. Durch einige Testbilder habe ich herausgefunden, dass die Anzahl der Null-Bytes gleich der Bildbreite in Pixeln Modulo 4 ist.

Für folgendes Bild gibt es also die nebenstehende hexadezimale Darstellung. Die entsprechende Farbe wurde markiert und jedes Pixel mit einer Indexzahl versehen. Man beachte jedoch die Spiegelung der RGB-Werte!

Nach dieser kurzen Einführung in das Bitmap-Format, möchte ich nun eine Möglichkeit vorstellen, wie man Informationen in einem Bild verstecken kann. Dabei werden die folgenden zwei roten Farben betrachtet:

Äußerlich bemerkt man keinen Unterschied, in hexadezimaler Darstellung hingegen erkennt man in der RGB-Reihenfolge jedoch schon einen Unterschied: Linkes Rot: FF0000h = 11111111 00000000 00000000b Rechtes Rot: FE0101h = 11111110 00000001 00000001b

Es wurde also das jeweils letzte Bit eines Farbwertes verändert. Weil sich der Wert des Farbanteils aber nur so minimal ändert, erkennt das menschliche Auge keinen Unterschied. Da eine Farbe durch 3 Byte = 24 Bit dargestellt wird, gäbe es 2 ²⁴ = 16777216 Farben. Dabei ist klar, dass man mit dem Auge einzelne Abstufungen nicht unterscheiden kann. Aufgrund dessen, dass das letzte Bit eines jeden Farbwertes verändert werden kann, ohne, dass sich die Farbe für das menschliche Auge ändert, wird es auch Last-Significant-Bit (LSB) genannt. Dieses Bit stellt also den perfekten Ort dar, um ein Datenbit zu verstecken. Beispielsweise könnten die ersten drei Bit (01000001) des Buchstaben „A“ wie folgt in dem roten Pixel versteckt werden: Rot = FF0000h 11111110 00000001 00000000b

Die nächsten Bits des Buchstaben „A“ werden dann in den Farbwerten des nächsten Pixels versteckt. Jetzt soll noch deutlich gemacht werden, wie viele Bits man in einem Bild von 800 Pixeln Höhe und 600 Pixeln Breite (entspricht einem Desktophintergrundbild bei einer Bildschirmauflösung von 800*600 Pixeln) verstecken kann, wobei immer ein Bit der geheimen Datendatei in genau einem Farbanteil versteckt wird (die Bitrate beträgt 1 Bit/Byte).

Das Bild besteht mit 800*600 Bildpunkten aus insgesamt 480000 Pixeln. Ein Pixel besitzt 3 Farbanteile, die jeweils 1 Byte groß sind. Das bedeutet, die Anzahl an möglichen Trägerbytes lässt sich wie folgt berechnen:

Trägerbytes = 800 * 600 * 3 Byte = 1440000 Byte Trägerbytes = Breite (in Pixeln) * Höhe (in Pixeln) * 3 Byte

Da immer ein Datenbit in einem Trägerbyte (entspricht hier einem Farbanteil) versteckt wird bedeutet das, dass eine Datennachricht von 1440000 Bit = (1440000 / 8) Byte = (1440000 / 8 / 1024) = 175,78125 KByte in einem Bild von 800 Pixeln Breite und 600 Pixeln Höhe versteckt werden kann. Am praktischen Beispiel lässt sich der mathematische Anhang dieser Arbeit als Word Dokument bereits in einem solchen Bild verstecken, ohne dass sich ein optischer Unterschied bildet. Die Dateigröße des Bildes bleibt folglich unverändert.

Natürlich bemerkt man auch fast keinen Unterschied, wenn gleich 2 Bit in einem Byte versteckt werden. Das heißt die letzten beiden Bits des Farbanteils werden gleich den 2 Bit der geheimen Nachricht gesetzt. Die folgende Tabelle zeigt noch einmal, wie sich die Farben bei unterschiedlicher Bitrate (entspricht Anzahl der Bits, die in einem Byte geändert werden) verändern. Dabei wird ein zu dem Ursprungsbit entgegengesetztes Bit eingesetzt, um den Extremfall zu demonstrieren:

Die Letzte Farbe stellt bereits die Komplementärfarbe zur Original-Farbe dar. Bei 7 Bit/Byte gibt es deshalb diese graue Stufe, da sich die Farbanteile sehr ähneln. Von den Graustufen Schwarz zu Weiß

werden alle Farbanteile um den gleichen Summanden vergrößert, das bedeutet, dass in einem exakten Grauton alle Farbanteile gleich sind.

*Anmerkung: Binary Chameleon zeigt die Veränderung eines Bildes bei der Änderung der Bit/Byte Rate im Optionsmenü aktiv an. Dort kann man also den Fall für mehrere Pixel in einem Bild betrachten, wobei nur jedes 3. im Bild verändert wird.

2.1.3 Praktische Umsetzung

Zunächst einmal gibt es eine gewisse Reihe von Anforderungen an ein Steganographie-Programm. Ich kenne jedoch kein einziges Steganographie-Programm, was alle oder gar viele Punkte erfüllt. Es handelt sich dabei also um "ideale" Vorstellungen bezüglich eines Steganographie-Programms. Das Programm muss die Daten so in der Trägerdatei verstecken, dass nicht erkennbar sein soll, ob es sich um eine tatsächliche Trägerdatei handelt.

Schlussfolgerung: Das Programm müsste enorme Veränderungen in der Trägerdatei vermeiden und zusätzlich vielen Steganographie-Angriffen (werden hier nicht aufgeführt) widerstehen. Das Programm sollte die Daten so in Trägerdateien verstecken, dass selbst nach dem Umwandeln in andere Dateiformate oder dem Umwandeln in ein anderes Medium (z.B. durch Ausdrucken eines Bildes) die Datendatei wieder entnommen werden kann. Ebenso soll die Nachricht noch in der Trägerdatei erkennbar sein, wenn die Trägerdatei komprimiert wird oder bestimmte Filter angewandt werden.

Schlussfolgerung: Der Programmierer müsste extrem viele Dateiformate kennen und einen Weg finden eine Stelle in der Trägerdatei zu identifizieren, die selbst durch irgendeine Form von Umwandlung immer gleich strukturiert ist. Es ist klar, dass diese Anforderung nur zu einem bestimmten Maß erfüllbar ist. Das Programm muss die Daten in der Trägerdatei davor schützen, dass sie bei der Veränderung eines bestimmten Teiles der Trägerdatei wieder rekonstruierbar sind.

Schlussfolgerung: Das Programm sollte die Datendatei mit einer Information verstecken, die Auskunft über das Gesamtbild der Datendatei gibt. Eine andere von mir gefundene Lösung für das Problem, ist unter dem Abschnitt "Verbesserungen an Binary Chameleon" zu finden.

Das Programm sollte in der Lage sein, immer die benötigte Menge der Datendatei optimal in der Trägerdatei zu verstecken.

Schlussfolgerung: Diese Vorraussetzung ist nur erfüllbar, wenn die Kapazität der Trägerdatei eine solche Menge überhaupt zulässt.

Das Programm muss die Datendatei zusätzlich asymmetrisch verschlüsseln, um mehr Sicherheit zu gewährleisten

Schlussfolgerung: Es muss ein zusätzlicher Schlüsselaustausch stattfinden, wobei möglichst kein Verdacht auf die Trägerdatei fallen soll.

Zusätzlich möchte ich noch 2 interessante Erweiterungen vorstellen, die ein Steganographie-Programm leisten könnte.

Selbstverleugnung: Die Datendatei wird in einer Trägerdatei versteckt, wobei sich das Programm weitere Bitmap-Dateien "ansieht". Dabei wird nur die eine Trägerdatei verändert. Das Programm kann später die Datendatei nur aus der Trägerdatei und aus den weiteren Bitmapdateien rekonstruieren, aber es kann nicht mehr feststellen, welche der Bitmapdateien die eigentliche Trägerdatei ist. Es werden also auch die ursprünglich unveränderten Bitmapdateien als Trägerdateien behandelt. Derjenige, der die Nachricht versteckt hat, könnte somit eine Art Anonymität annehmen. In Binary Chameleon wird beispielsweise jedes einzelne Bit der Datendatei bereits vor dem Verstecken mit bestimmten Bits der anderen beteiligten Dateien addiert und Modulo 2 gerechnet. So wird diese veränderte Datendatei in der Trägerdatei versteckt. Später werden wieder bestimmte Bits aller beteiligten Bitmapdateien addiert und anschließend Modulo 2 gerechnet und man erhält wieder die ursprüngliche Datendatei.

Hier ein Beispiel für eine Kette von 8 Bits: Bits der Datendatei:

Bits einer Bitmap-Datei 1: Bits einer Bitmap-Datei 2:

Die versteckten Bits der eigentlichen Trägerdatei ergeben sich nun aus der beschriebenen bitweisen Addition mit anschließender Modulo Rechnung.

Dateispaltung: Die Datendatei wird in x Teile aufgespalten. Jedes dieser Teile wird dann in einer Trägerdatei versteckt. Die Nachrichtenteile können einzeln nicht aus den Trägerdateien entnommen werden, aber die gesamte Nachricht kann aus allen Trägerdateien entnommen werden. Der Vorteil ähnelt dem eines modernen Banksystems: Jeder der Angestellten kennt (besitzt) nur einen individuellen Schlüssel zum Tresor. Dieser kann aber nur durch alle gemeinsam geöffnet werden.

2.2 Binary Chameleon

2.2.1 Einleitung

Binary Chameleon ist ein auf Bitmap-Dateien spezialisiertes Steganographieprogramm, das ich im Rahmen dieser Jahresarbeit entwickelt habe. Mit einem reichlichem Jahr Entwicklungszeit und 12968 Zeilen ist es mein bisher größtes Software-Projekt.

Das Programm zeichnet sich durch Benutzerfreundlichkeit und einen großen Funktionsumfang aus und ist somit ein funktionsfähiges Steganographieprogramm für Bitmap Dateien. Es besitzt Algorithmen, die vorher in keinem anderen Programm vorhanden waren, wie z.B. das System der Selbstverleugnung oder der so genannte Bitmapping-Prozess. Es folgt eine Liste der wichtigsten Funktionen:

- Bitraten von 1 Bit/Byte bis zu 8 Bit/Byte werden unterstützt.

- Die Datenbits werden in der Trägerdatei abhängig von einem angegebenen Passwort verteilt (Bitmapping). Die Trägerdatei kann hierbei nur durch dieses Passwort wieder verifiziert und eingelesen werden.

- Die Datendatei kann vor dem Verstecken komprimiert werden.

- Man hat die Möglichkeit, zusätzliche Verschlüsselungsmethoden und außerdem ein spezielles Verschlüsselungspasswort zu verwenden.

- Das System der Selbstverleugnung kann benutzt werden.

Bei der programmtechnischen Umsetzung konnte ich vielerlei Erfahrungen sammeln. Wegen Performance-Problemen musste ich z.B. die Programmentwicklung abbrechen und ein völlig neues Konzept entwickeln, um die umzusetzenden Algorithmen leistungsfähiger zu machen. Dies geschah durch die Entwicklung effektiverer Algorithmen. Als Programmiersprache habe ich mich für Java entschieden. Der Hauptgrund für diese Entscheidung ist die Plattform-Unabhängikeit. Ein Java-Programm ist ohne größeren Aufwand unter jedem beliebigen Betriebssystem lauffähig. Für die bereitgestellte MS Windows XP Version wurde das Java Programm zusammen mit dem Java-Runtime-Environment in einer ausführbaren Datei zusammengefasst. Dafür habe ich eine Demo-Version von „Jet“ der Firma Excelsior verwendet. Dennoch gibt es empfohlene Harware Anforderungen:

- 1 GHz CPU Taktfrequenz

- 1 GByte RAM

Das Programm läuft zwar auch unter niederen Systemvoraussetzungen, allerdings dauern dann die Prozesse bei größeren Trägerdateien deutlich länger. Warum das so ist, wird bei der Funktionsbeschreibung des Bitmapping-Prozesses klar.

2.2.2 Aufbau und Funktionsbeschreibung

In diesem Abschnitt können nicht alle Funktionen und deren Umsetzung aufgrund des viel zu großen Umfangs genau beschrieben werden. Daher werden nur die wichtigsten Prozesse grob beschrieben und nur teilweise programmtechnisch erläutert.

Zunächst ist das Programm in folgende Programm-Klassen unterteilt:

Anhand der Tabelle ist zu erkennen, dass jede Programm-Klasse ihre eigenen Aufgaben hat. Die beiden Dateiklassen CBMP.class und CData.class sind hierbei spezielle Unterklassen von CFile.class. Diese Art der Strukturierung dient der Übersicht, sowie der vereinfachten Weiterentwicklung des Programms.

Nun wird Schritt für Schritt beschrieben, wie das Programm eine Datendatei in einer Trägerdatei versteckt. Vorher wird jedoch erklärt, wie die Datenmenge aufgebaut ist, die wirklich versteckt wird. Bestandteile der versteckten Datenmenge:

Vor dem Verstecken werden so genannte Zusatzinformationen an die Datendatei gehangen, woraus letztendlich die zu versteckende Datenmenge entsteht. Das sind vor allem Informationen, die das Programm benötigt, um die ursprüngliche Datendatei wieder zu rekonstruieren. Die zu versteckende Datenmenge setzt sich dann aus folgenden Bestandteilen zusammen:

Wie man erkennen kann, sind die einzelnen Bestandteile der Datenmenge bestimmten Teilen zugeordnet.

Der Teil A enthält nur die nötigsten Informationen, die das Programm braucht, um die Restdatenmenge (Teil B und Teil C) aus der Trägerdatei herauszuholen. Dabei dienen die ersten 2 Byte als Verifikation, ob es sich tatsächlich um eine Trägerdatei handelt. Die Bit/Byte Rate benötigt das Programm, damit es weiß, wie viele Bits in einem Trägerbyte versteckt sind. Die Datenlänge X gibt an, wie viele Datenbytes aus der Trägerdatei gelesen werden sollen. Die maximale Datengröße, die gespeichert und damit versteckt werden kann, beträgt also 256 4 Bytes = 4 GByte. Teil A muss eine statische Größe (7 Bytes)

besitzen, damit das Programm auch immer diesen Teil vollständig einlesen kann. Aber wie weiß das Programm mit welcher Bitrate der Teil A in den Trägerbytes versteckt wurde? Für dieses Problem habe ich eine einfache Lösung gefunden: Teil A wird grundsätzlich mit einer Bitrate von 1 Bit/Byte versteckt. Die anderen beiden Teile werden in anderen Bytes nach der eingestellten Bitrate versteckt. Aus diesem Grund kommt es auch zu einer speziellen Unterteilung der Zusatzinformationen.

Der Teil B enthält zum einen das so genannte Cryptsign, welches in Wirklichkeit aus 2 Teilen besteht. Die ersten 4 Bytes sind das echte Cryptsign und das 5. Byte gibt die Kompressionsart an. Die Funktion des Cryptsigns wird später genauer erläutert.

Die restlichen Elemente von Teil B und C verstehen sich von selbst. Nun kann genauer beschrieben werden, wie das Programm Datendateien in Trägerdateien versteckt. Verstecken einer Datendatei in einer Trägerdatei:

Die folgende Schematische Darstellung soll die wichtigsten Prozesse beim Verstecken einer Datendatei vereinfacht darstellen.

Wie zu erkennen ist, werden zuerst die 2 großen Informationsfelder Datenmap und Stegamap erstellt, aus denen gemeinsam im letzten Schritt die modifizierte Trägerdatei erzeugt wird. Nun wird der Steganographieprozess anhand eines kleinen Beispiels erläutert:

Zur besseren Veranschaulichung wird der Dateiinhalt als dezimale Zahlenfolge dargestellt. Dabei werden für die Zeichen jeweils die dezimalen Stellen aus der ASCII Tabelle benutzt. Der Dateiinhalt lautet nun: 72 65 76 76 76 76 76 76 79 79 79

Innerhalb des 1. Schrittes würde nun die Komprimierung und Verschlüsselung der Datendatei erfolgen. In diesem Fall bietet sich die Faktorisierung als Komprimierungsmethode an. Dabei gibt immer ein Faktor vor einem entsprechenden Byte an, wie oft es sich in der Datendatei wiederholt. Der neue

komprimierte Dateiinhalt würde dann wie folgt aussehen: 1 72 1 65 6 76 3 79 Nun soll die bereits komprimierte Datendatei verschlüsselt werden. Nach der gewählten Verschlüsselungsmethode und dem Verschlüsselungspasswort lautet nun der Datendateiinhalt nach der Verschlüsselung: 100 176 106 167 108 190 104 191

Jetzt soll die erweiterte Datendatei oder die letztendliche Datenmenge aus den Zusatzinformationen und dem Dateiinhalt erstellt werden.

Als erstes wird das Cryptsign erstellt. Das Cryptsign soll Auskunft über die verwendete Verschlüsselungsmethode geben. Allerdings sollte man nur dann erkennen mit welchem Verschlüsselungsalgorithmus die Datei verschlüsselt wurde, wenn man das richtige Passwort kennt. Bei diesem Problem kam ich auf die Idee des Cryptsigns (Unterschrift der Verschlüsselungsmethode). Dabei geht man wie folgt vor:

Jede Chiffre besitzt eine individuelle Folge von 4 Bytes. Diese 4 Bytes werden durch eine Einweg-Verschlüsselung (Einweg-Hash) mithilfe des gewählten Passworts verschlüsselt. Die dabei entstandenen 4 Bytes können durch keine Umkehroperation mit dem Passwort in die individuelle Ursprungsfolge umgeformt werden (Beispiele für derartige Einweg-Verschlüsselungen siehe Quelle 1, ab Seite 96).

Wenn überprüft werden soll, welche Verschlüsselungsmethode angewandt wurde, dann werden die individuellen Byte-Folgen von allen Verschlüsselungsmethoden mit dem eingegebenen Passwort chiffriert und es wird getestet, ob das Ergebnis mit dem gegebenen Cryptsign übereinstimmt. Ist dies der Fall, dann wird die gewählte Verschlüsselungsmethode für die gesamte Datenmenge verwendet. Am Beispiel lautet die dezimale Folge der 4 Bytes für den Vigenere-Algorithmus: 86, 105, 103, 101. Nun wird jedes dieser Bytes durch eine Einwegfunktion mithilfe des Passworts umgeformt. Es werden nun die folgenden neuen Bytes des Cryptsigns berechnet, wobei für die Schlüsselbuchstaben ihre dezimalen Zahlen aus der ASCII-Tabelle benutzt werden (chiffrepass = 99 104 105 102 102 114 101 112 97 115 115):

1. Byte = (99*86 5 + 104*86 4 + 105*86 3 ) mod 256

= 248

2. Byte = (104*105 5 + 105*105 4 + 102*105 3 ) mod 256

= 103

3. Byte = (105*103 5 + 102*103 4 + 102*103 3 ) mod 256

= 111

4. Byte = (102*101 5 + 102*101 4 + 114*101 3 ) mod 256

= 78

Erstelltes Cryptsign ( + Kompressionsmethode 1): 248 103 111 78 1

Es existieren nun alle Informationen, die zur versteckenden Datenmenge zusammengefasst werden. Die folgende Tabelle zeigt die komplette (dezimale) Datenmenge, welche später versteckt wird.

Um den 1. Schritt zu vollenden wird nun diese Datenmenge in eine Bitmatrix zerlegt. Für den Teil A und das Cryptsign der Datenmenge sieht die Bitmatrix wie folgt aus:

Im 2. Schritt muss die Stegamap erstellt werden. Diese kann man sich ebenfalls wie eine Tabelle oder Matrix darstellen. In der ersten Spalte stehen geordnet von oben nach unten die Trägerdateibytes (einzelne Farbwerte der Bitmap-Datei). In den nebenstehenden Spalten stehen die Positionen der Datenbits. Die zusätzliche Spaltenanzahl richtet sich danach, wie viele Datenbits in einem Trägerbyte versteckt werden. Welche Datenbitpositionen welchen Trägebytes zugeordnet werden, wird nach einem Algorithmus abhängig vom Steganographiepasswort berechnet. Die zugeordneten Bitpositionen ergeben sich jedoch nicht aus den Koordinaten der Datenmap, sondern aus den echten Bitpositionen der Datenbits in ihrer Bitfolge in der Datenmenge. Die folgende Tabelle zeigt einen Ausschnitt einer solchen Stegamap. Da eine Bitrate von 2 Bit/Byte verwendet wurde, werden bestimmten Trägerdateibytes auch 2 Datenbitpositionen zugeordnet.

Ist die Datenmap und die Stegamap erstellt, folgt nun der 3. Schritt: Anhand beider Tabellen wird die modifizierte Trägerdatei erstellt. Dabei wird jedes Trägerdateibyte einzeln in der Stegamap eingelesen und so umgewandelt, dass die entsprechenden Datenbits von den zugeordneten Datenbitpositionen in dem jeweiligen Trägerbyte versteckt sind. Da die Datenmenge jedoch tabellarisch vorliegt und die Datenbitpositionen keine Zeilen und Spalten angeben, werden die Zeilen und Spalten anhand der Datenbitposition errechnet:

Spalte = [Datenbitposition / 8] (ganzzahlige Division) Zeile = Datenposition - 8 * Spalte

Dabei ist anzumerken, dass Zeilen, Spalten und Datenbitpositionen beginnend ab 0 nummeriert sind. Beispielsweise ergibt die Datenposition 51 Spalte = [51 / 8] = 6 Zeile = 51 - 8 * 6 = 3

Es befindet sich also das zu versteckende (fett markierte) Datenbit in Zeile 3 und Spalte 6 der Datenmap. Nun wird noch der einfache Algorithmus vorgestellt, der ein Datenbit in einem Trägerbyte an der 8. Bitstelle versteckt.

Beispielsweise wird aus dem Trägerbyte mit dem Wert 28 (00011100) und dem Datenbit 1 das neue Trägerbyte 28 (00011101). Werden 2 Datenbits wie beispielsweise 1 und 0 in dem Trägerbyte mit dem Wert 127 (01111111) versteckt, so wird zuerst das erste Datenbit an 8. Bitstelle versteckt (01111111) und danach das 2. Datenbit an 7. Bitstelle (01111101).

Es folgt nun eine Beschreibung, wie Binary Chameleon die Daten wieder aus einer Trägerdatei exportiert.

Exportieren einer Datendatei aus einer Trägerdatei

Als erstes werden aus der Trägerdatei die Informationen aus Teil A der Datenmenge herausgelesen, damit das Programm weiß, welche und wie viele Bits es aus der Trägerdatei später exportieren muss. Dabei werden nur die ersten 7 Byte der Datenmenge mit einer Bitrate von 1 Bit/Byte gelesen. Ist das Passwort, was zur Positionsermittlung diente, richtig, merkt das Programm anhand der ersten 2 Bytes, ob die Trägerdatei eine Datendatei enthält. Mit den Informationen über die verwendete Bitrate und die Datenlänge wird im 2. Schritt die komplette Stegamap angefertigt, mit deren Hilfe die Positionen der Datenbits rekonstruiert werden. Mit den ermittelten Positionen werden die richtigen Datenbits der gesamten Datenmenge wieder aus der Trägerdatei gelesen. Im letzten Schritt muss diese Datenmenge dann erneut in ihre einzelnen Bestandteile zerlegt werden. Darunter befindet sich die wirkliche Datendatei, die noch entschlüsselt und dekomprimiert wird.

2.2.3 Geplante Verbesserungen

Binary Chameleon wird keinesfalls nur Bestandteil dieser Jahresarbeit bleiben. Mein persönliches Ziel ist es, dieses Programm (unter anderem innerhalb einer BELL) zu einem „Advanced“ Steganographieprogramm zu entwickeln, wodurch es für private als auch kommerzielle Zwecke genutzt werden kann. Da es alle mir bekannten Steganographieprogramme für Bitmap Dateien bezüglich Funktionsumfang übertrifft, ist damit eine gute Grundvoraussetzung geschaffen. Jedoch sollte das Programm besonders für kommerzielle Zwecke in einigen Dingen stark an Qualität gewinnen. Z.B. versuche ich, sicherere Verschlüsselungsalgorithmen zu verwenden, wobei RSA programmtechnisch gut umgesetzt werden sollte. Der für die Jahresarbeit enthaltene Vigenère-Algorithmus wird entfernt, da bereits nach dieser Jahresarbeit klar ist, dass er zu unsicher ist. Ein weiterer Punkt für eine Verbesserung wäre das Hinzufügen von Kompressionsalgorithmen. Besonders interessant finde ich die diskrete Cosinus Transformation, mit der Daten durch die Beschreibung von Cosinus-Kurven dargestellt werden können. Ich sehe in dieser Kompressionsfunktion auch eine Chance, Nachrichtendaten in Trägerdateien erstmalig widerstandsfähiger gegenüber Veränderungen in der Trägerdatei zu machen. Dabei soll neben der Datendatei auch eine komprimierte Wellenbeschreibung der Datendatei in der Trägerdatei mehrfach versteckt werden. Bei einem Verlust von Datenbits könnte dann versucht werden, anhand der komprimierten Wellenbeschreibung der Datenbits die verlorenen Bits zu rekonstruieren. Da Binary Chameleon bereits programmtechnisch so gestaltet ist, dass es auf weitere Trägerdateitypen erweitert werden kann, sollte dies auch umgesetzt werden. Speziell habe ich mich als nächstes auf das JPEG-Format festgelegt, was durch eine mathematisch komplizierte verlustbehaftete Kompression geprägt ist. Ausgehend von dieser Kompression werde ich versuchen, eventuelle Schwachstellen zu finden, die es möglich machen, dass eine Datendatei in einer Trägerdatei trotz einer verlustbehafteten Kompression überdauert. Dabei sollen die Trägerbytes berechnet werden, welche durch eine spätere Kompression unverändert bleiben.

Das größte Problem sind jedoch derzeit die Hardware-Anforderungen des Programms. Jedoch habe ich auch hierfür bereits eine Lösung: Schritt 2 und 3 werden beim Verstecken so zusammengefasst, dass die Datenbits von den errechneten Datenbitpositionen gleich in den Trägerbytes versteckt werden, sodass die Stegamap als eine sehr große Datenmenge ausgelassen werden kann. Was bleibt ist die gleiche Rechenzeit mit weniger Arbeitsspeicherverbrauch.

3 Mathematischer Anhang

3.1 Modulare Arithmetik

Der Modulo Operator ermittelt den Rest einer Division zweier Zahlen. Zum Beispiel ergibt

23 : 5 = 4 mit Rest 3

Um den Rest 2 zu erhalten schreibt man mithilfe des Modulo Operators

23 mod 5 = 3

Dieser Operator dient in den meisten Bereichen dazu, einen bestimmten Zahlenbereich nicht zu verlassen (z.B. von 0 bis 25). Man schreibt allgemein a mod n = b, wobei n als Modul bezeichnet wird.

Restgleichheit

Wenn für zwei Zahlen a, b ∈ Ù, a mod n = b mod n gilt, dann sind a und b restgleich. Man schreibt dafür auch: a ≡ b mod n (gesprochen: "a ist kongruent zu b Modulo n") Dabei gilt folgendes:

Aus der Restgleichheit können bestimmte Regeln begründet werden, die im Verlauf der Arbeit als selbstverständlich betrachtet werden: Regel 1

Ein Vielfaches q*n von n Modulo n ist immer 0. Daher kann es in einer entsprechenden Gleichung zur Vereinfachung wegen der Restgleichheit ausgelassen werden. Beispielsweise ist (q*n + a) ≡ a mod n, also kann man für (q*n + a) mod n auch a mod n schreiben.

Ebenso gilt: wenn a mod n = r, dann kann man für den Term a mod n auch schreiben r mod n. Denn es gilt a = q*n + r. Wegen der Restgleichheit (a - r = q*n) ist also a ≡ r mod n. Regel 2

Bei der Gleichung a mod n = b mod n kann man alternativ schreiben: a = b (mod n)

Dabei kann die Gleichung a = b wie jeder andere Gleichung umgeformt werden.

Regel 3

Wenn b = a mod n, dann ist b kleiner als n. Somit kann man für b auch schreiben: b = b mod n Regel 4

Wenn b = q*n + r dann kann in dem Term (a*b) mod n für b der Rest r eingesetzt werden: (a*b) mod n = (a*r) mod n

Dies gilt, da man alternativ zu (a*b) mod n den gesamten Term für b einsetzen kann: (a*(q*n + r)) mod n = (a*q*n + q*r) mod n

Da a*q*n ein Vielfaches von n ist, kann es laut Regel 1 "weggelassen" werden. Regel 5

Es gilt: (m ^e mod n) ^d mod n = m ^e*d mod n, denn für m ^e kann man schreiben: m ^e = q*n + r r = m ^e - q*n m ^e mod n = r

(m ^e mod n) ^d mod n = r ^d mod n = (m ^e - q*n) ^d mod n ± b) ^x a ^x = Es gilt allgemein laut binomischer Formel (a + Fehler! a ^x ± Es kann nun b ausgeklammert werden: b*( ... )

Diese Form wird auf die obige Gleichung übertragen: (m ^e mod n) ^d mod n = (m ^e - q*n) ^d mod n (m ^e mod n) ^d mod n = (m ^e*d ± q*n*( ... )) mod n

Da q*n*( ... ) ein Vielfaches von n ist, kann es ausgelassen werden und es bleibt: (m ^e mod n) ^d mod n = m ^e*d mod n

3.2 Euklidischer Algorithmus

Der Euklidische Algorithmus, welcher von einem griechischem Mathematiker namens Euklid 300 v. Chr. entwickelt wurde, dient in dieser Arbeit und allgemein in der Kryptographie zum Errechnen des größten gemeinsamen Teilers zweier Zahlen. Es gibt ebenfalls einen erweiterten Euklidischen Algorithmus, der zum Ermitteln der multiplikativen Inversen b zu a mod n genutzt wird. Für den Euklidischen Algorithmus wird die folgende allgemeine Form angewandt, die im Wesentlichen aus 2 Teilen besteht, welche je nach den zu untersuchenden Zahlen unterschiedlich oft wiederholt werden. Um den Euklidischen Algorithmus zur Ermittlung des größten gemeinsamen Teilers verallgemeinert zu verstehen, beschreibe ich den jeweiligen Schritt anhand des Beispiels der Zahlen a = 42 und b = 24.

Zusammenfassung und Beispiel des Euklidischen Algorithmus:

Dieser Algorithmus ist allgemeingültig für alle Zahlen a, b ∈ Í Das möchte ich wie folgt beweisen: Beweis für die Gültigkeit des Euklidischen Algorithmus:

Der erweiterte Euklidische Algorithmus

Ziel ist es mithilfe des erweiterten Euklidischen Algorithmus ein multiplikatives Inverses y zu einer Zahl k mod n zu finden, wenn der größte gemeinsame Teiler von k und n 1 ist. Das heißt, es soll gelten: y*k mod n = 1. Da dieses Inverse für den Faktor einer multiplikativen Chiffre bzw. einer Tauschchiffre gefunden werden soll, muss der kleinste gemeinsame Teiler von n (der Mächtigkeit des Alphabets) und dem Faktor k gleich 1 sein.

In den folgenden Zeilen wird gezeigt, dass es eine Umformung für den Euklidischen Algorithmus gibt, die ein Inverses für k modulo n liefert.

An dem Beispiel k = 7 und n = 26 wird zunächst der kleinste gemeinsame Teiler berechnet, wobei die allgemeine Gleichung für den Euklidischen Algorithmus für k und n in Klammern steht:

(1) 26 = 3*7 + 5

(2) 7 = 1*5 + 2 (3) 5 = 2*2 + 1 (4) 2 = 2*1

Es gilt nach dem Euklidischen Algorithmus: n n = k ^n-1 k n = r n-1

Der größte gemeinsame Teiler x von 5 und 26 ist demnach 1. Nun folgt der eigentliche Teil des erweiterten Euklidischen Algorithmus, der zunächst anhand des Beispiels gezeigt wird. Da in der vorletzten Gleichung x als Rest (r 2 ) bereits vorhanden ist, wird ausgehend von dieser Gleichung nach x umgestellt: x = 1 = 5 - 2*2 (r 3 = x = n 2 - q 2 *k 2 )

Die zweite Gleichung wird nun auch nach dem Rest 5 umgestellt (2 = 7 - 1*5, k 2 = n 1 - q 1 *k 1 ) und man kann in die Gleichung 1 = 5 - 2*2 einsetzen: 1 = 5 - 2*(7 - 1*5)

1 = 5 - 2*7 + 2*1*5 1 = 7*(-2) + 5*3 Man betrachte nun die letzte allgemeine Darstellung in Klammern, um den weiteren Schritt am Zahlenbeispiel zu verstehen: n 2 = k 1 = r 0

Aus Gleichung (1) geht hervor:

r 0 = n 0 - q 0 *k 0

Demnach wird nun für n 2 der Term für r 1 eingesetzt:

1 = 7*(-2) + (26 - 3*7)*3

1 = 7*(-2) + 26*3 - 3*7*3

1 = (-11)*7 + 3*26

↔←←←←←←←←←←←←←←←↑←←←←←←←←←←←←←←←→

(1 + q 2 *q 1 ) * n 0 )

↔←←←←←←←←←↑←←←←←←←←←→

(x = y *k 0 + z *n 0 )

Jetzt erkennt man in der letzten Beispielgleichung, wie auch in der nebenstehenden Verallgemeinerung, die Ausgangswerte und Variablen n = 26 und k = 7. Es gibt also auch eine Möglichkeit, den größten gemeinsamen Teiler x = 1, über eine lineare Gleichung zu bestimmen. Jedoch müssen dafür y und z berechnet werden, was wiederum zur Folge hat, dass man den Euklidischen Algorithmus durchführen muss.

Dafür kann man jedoch mit der linearen Gleichung eine andere Überlegung beginnen. Dazu genügt ein Grundgedanke: Eine Funktion f(a) = f(b) gilt für jedes f. Das heißt, man kann nun für die Gleichung ein Modul bestimmen: a mod c = b mod c. Dieser Gedanke wird auf die letzte Gleichung übertragen, wobei n als Modul benutzt wird: x mod n = (y*k + z*n) mod n für y*k kann man auch schreiben: y*k = q*n + r, wobei wieder gilt: q, r ∈ Í, r < n

Setzt man jetzt diesen Term ein, so erhält man: x mod n = (q*n + r + z*n) mod n = (n*(q+z) + r) mod n

Da n*(q+z) ein Vielfaches von n ist, ist (n*(q+z) + r) mod n immer r. Es folgt: n*(q+z) ist überflüssig: x mod n = (y*k) mod n

Da als Vorraussetzung für multiplikative Chiffren und Tauschchiffren der größte gemeinsame Teiler von k und n = 1 sein soll, setzt man für x ein: 1 mod n = 1 = (y*k) mod n

Diese Gleichung entspricht also der obigen Zielgleichung für die y ein Inverses zu k mod n ist. Um den erweiterten Euklidischen Algorithmus zum Finden einer Inversen y zu k mod n nutzen zu können, folgt zuerst eine von mir entwickelte Herleitung des erweiterten Euklidischen Algorithmus vom Euklidischen Algorithmus. Danach schließt sich eine Zusammenfassung der Schritte mit einem Beispiel an.

Herleitung des erweiterten Euklidischen Algorithmus:

Zusammenfassung des erweiterten Euklidischen Algorithmus mit Beispiel:

3.3 Die Eulersche ϕ-Funktion

Diese Funktion gibt alle teilerfremden natürlichen Zahlen von einer natürlichen Zahl n an, die kleiner als n sind. Sie nimmt in der Kryptographie eine spezielle Rolle für den Fall ein, dass n eine Primzahl ist. Dabei ist zu erwähnen, dass die Funktionswerte durch keinen feststehenden Term bestimmt werden können, es sei denn, n ist eine Primzahl.

Am Beispiel n = 12 ist ϕ(n) = 4, denn der größte gemeinsame Teiler von den 4 Zahlen (1, 5, 7, 11) und 12 ist jeweils 1.

Wenn n eine Primzahl ist, dann folgt daraus, dass keine Zahl x < n existiert, durch die n teilbar ist. Dazu zählen auch Primzahlen, wie z.B. 1, 2 oder 3. Da die Zahlen kleiner n alle entweder selbst Primzahlen sind, oder Vielfache (bestehend aus Primzahlen) von Primzahlen sind, folgt:

Alle Zahlen, die kleiner als n sind, sind zu n teilerfremd. Da dies genau n-1 Zahlen sind, kann man den einen speziellen Fall der Eulerschen Funktion festlegen: Wenn n eine Primzahl ist, so ist ϕ(n) = n - 1.

Sollte n eine Zahl sein, die Produkt zweier Primzahlen p und q ist, so gilt für ϕ(n): ϕ(n) = ϕ(p * q) = ϕ(p) * ϕ(q) = (p - 1) * (q - 1)

Der Satz von Euler

Der Satz von Euler gilt für alle natürlichen Zahlen a und n, die voneinander teilerfremd sind. a ^ϕ(n) mod n = 1 Dieser Satz soll nun bewiesen werden: Beweis des Satzes von Euler:

4 Literatur- und Quellenverzeichnis

Kryptologie

1) Angewandte Kryptographie, 2. Auflage, von Wolfgang Ertel 2) Kryptologie, 6. überarbeitete Auflage, von Albrecht Beutelspacher * 3) http://www.kuno-kohn.de/crypto/crypto/index.htm (Kryptanalyse)

4) http://www.schulmodell.de/info/unterricht/kl10/vigenere.htm (Vigenère-Quadrat wurde von dort kopiert und bearbeitet)

5) http://www.mathematik.de/spudema/spudema_beitraege/beitraege/hillebrand/mathe2002/vignere.htm (Beispielchiffretext für Vigenère-Chiffre wurde damit erzeugt) Steganographie

6) http://www.fitug.de/bildung/kongress/stegano.html (Allgemeines) Mathematik

7) http://mo.mathematik.uni-stuttgart.de/lexikon/ (Modulare Arithmetik, Injektivität) 8) http://de.wikipedia.org/wiki/Euklidischer_Algorithmus (Euklidischer Algorithmus) 9) http://www.hh.schule.de/julius-leber-schule/melatob/SatzEuler.html (Idee für Beweis Satz von Euler) 10) Angewandte Kryptographie, 2. Auflage, von Wolfgang Ertel Gestaltung der Jahresarbeit

11) http://www.scimacros.de/ (Makro zur Darstellung mathematischer Formeln in MS Word) 12) http://tell.fll.purdue.edu/JapanProj/FLClipart/NounsPeople&animal.html (Abbildungen, die zur Gestaltung der Anschauungsgrafiken verwendet wurden) Programmentwicklung

13) Eclipse 3.1 (verwendeter Java-Code-Editor)

14) Java 2 SDK, SE v1.4.2 (verwendetes Java Development Kit für Compilierung) 15) Excelsior JET v4.1 (Java Native Compiler zur Umwandlung in Java-unabhängige EXE-Datei) 16) Clickteam Install Creator 2.0 (Zum Erstellen der Installationsdatei) 17) Adobe Photoshop CS (zur Grafikerstellung)

*Anmerkung: In dieser Quelle habe ich beim Durcharbeiten auf Seite 39 einen Gleichungsfehler entdeckt. Richtig müsste es lauten: