Entschlüsselung < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:59 Mi 22.11.2006 | | Autor: | Kristien |
Hallo, der folgende Text wurde mit der Tausch-Chiffre codiert:
Code: MUD2ER4EL
Text: Einmal war
Und dieser Text wurde mit dem Schlüsselwort-Chiffre codiert:
Code:EAHL6EG496A366J
Text:Ins Veilchenbeet
Kann mir jemand sagen, welche Schlüssel bei dem Jewiligen Code verwendet wurde, also wie man vom Code-Text auf den Originaltext kam?
Wie lautet die systematik zur Entschlüsselung?
Und ich habe da noch eine Frage: Wie viele korrespondierende Buchstabenpaare benötigt man bei den einzelnen Verfahren zur Bestimmung des Schlüssels?
Danke.
|
|
| |
|
Hallo,
befassen wir uns mit der ersten Verschlüsselung. Gesucht ist eine Tauschchiffre [s,t], also eine Chiffre, bei der sich die Nummer g des Geheimtextbuchstaben aus der Nummer k des Klartextbuchstaben ergibt gemäß:
[mm]g = (k+s)\cdot{}t[/mm]
Nun schreiben wir uns mal auf, welche Beziehungen wir schon kennen (Klartext oben, Geheimtext unten):
ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789
E M U R2D L 4
Das Grüppchen R2D fällt auf. Während wir uns im Klartext um eine Zahl von L nach M und von M nach N bewegen, bewegen wir uns im Geheimtext um ein Vielfaches von R nach 2 und von 2 nach D. Diese Schrittweite entspricht natürlich unserem t. Also rechnen wir:
"2" - "R" = 29 - 18 = 11 oder
"D" - "2" = 4 - 29 = -25 = 11 (in diesem Ring, wir rechnen hier immer modulo!)
Also: t = 11
Nun kommen wir an unser s, indem wir für eines der uns bekannten Buchstabenpaare folgende Gleichung lösen:
[mm]g = (k+s)\cdot{}11[/mm]
Dafür können wir zum Beispiel das Paar ("A","E") nehmen:
("A" + s)*11 = "E", also
(1 + s)*11 = 5
11 + 11s = 5
11s = 5-11 = -6 = 30
Durch Ausprobieren erhalten wir:
s = 6
Unsere Tauschchiffre ist also [6, 11].
Die enstprechende Zuordnung sieht so aus:
ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789
EP0BMX8JU5GR2DOZALW7IT4FQ1CNY9KV6HS3
Die Antwort zur zweiten Frage folgt in Kürze...
Gruß
Martin
|
|
|
| |
|
Kommen wir zu der zweiten Frage:
Wir suchen einen Schlüsselbuchstaben und ein Schlüsselwort, die eine Chiffre erzeugen, die
INSVEILCHENBEET zu
EAHL6EG496A366J verschlüsselt.
Wir gehen davon aus, dass das Schlüsselwort ein sinnvolles Wort ist, oder? (Wenigstens hätte ich eine solche Lösung)
Eindeutig ist die Lösung bei diesem kurzen Klartext-Geheimtext-Paar nicht!
Schreiben wir nieder, was wir bereits wissen:
ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789
34 6 9E G A HJ L
Wir wissen, dass in der unteren Zeile das Schlüselwort (natürlich jeder Buchstabe nur einmal) steht, gefolgt von den übrigen Buchstaben und Ziffern.
Da E und G bereits benutzt werden, bleiben zwischen A und H nur noch die Buchstaben BCDF übrig, die genau in diese Lücke passen. Außerdem kann zwischen J und L nur noch K stehen.
Vervollständigen wir unsere Paarung:
ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789
34 6 9E G ABCDFHJKL
Außerdem sehen wir, das in der Folge ABCDFHJKL der Buchstabe I fehlt. Er muss also im Schlüsselwort vorkommen.
Wir können die Ziffern zwischen 3 und 9 vervollständigen, weil sie genau hinkommen. Außerdem können wir die 0, die 1 und die 2 ergänzen, wenn wir mutig sind und davon ausgehen, dass unser Schlüsselwort einfach nur ein Wort ist und keine Ziffern enthält:
ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789
23456789E G ABCDFHJKL 01
Zwischen L und 0 klafft nun eine große Lücke, in die die entsprechenden Buchstaben bis auf zwei hineinpassen. Wir erhalten für unser Schlüsselwort also:
E**G* oder E**G*A (oder E**G*AB usw.),
wobei die Sternchen drei Buchstaben aus IMNOPQRSTUVWXYZ darstellen.
Wie gesagt: Eindeutig ist es nicht, aber wie wäre es mit dem Schlüsselwort ENIGMA? Der Schlüsselbuchstabe, also der Klartextbuchstabe, unter dem das Schlüsselwort beginnt, ist I.
In dem Fall wäre die komplette Zuordnung:
ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789
23456789ENIGMABCDFHJKLOPQRSTUVWXYZ01
Ach ja:
Um eine Tauschchiffre zu knacken, brauchst du im besten Fall zwei Buchstabenpaare, die direkt aufeinanderfolgen. Es könnte sogar sein, dass zwei immer reichen.
Bei der Schlüsselwortchiffre ist es etwas komplizierter. Da hängt es natürlich von der Schlüsselwortlänge ab und davon, ob man das Schlüsselwort erraten kann. So viel Heuristik muss nun mal sein beim Entschlüsseln von Geheimbotschaften...
Gruß
Martin
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:46 Do 23.11.2006 | | Autor: | Kristien |
Vielen Dank für die Antw.
Wie würde man bei der tausch-Chiffre und bei der schlüsselwortchiffre auf die Lösung kommen, wenn nur der codierte text da stünde?
<<Um eine Tauschchiffre zu knacken, brauchst du im besten Fall zwei Buchstabenpaare, die direkt aufeinanderfolgen. Es könnte sogar sein, dass zwei immer reichen.
Bei der Schlüsselwortchiffre ist es etwas komplizierter. Da hängt es natürlich von der Schlüsselwortlänge ab und davon, ob man das Schlüsselwort erraten kann. So viel Heuristik muss nun mal sein beim Entschlüsseln von Geheimbotschaften...<<
Wieso ist das denn so? Und wie ist es bei der Caesar-Chiffre???
Dankeschö.
|
|
|
| |
|
Hallo,
ich beantworte die Fragen mal in meiner Reihenfolge:
Zuerst vielleicht zwei Begriffe. Mein letzter Beitrag bezog sich auf die sogenannte Known-Plaintext-Attack (KPA), eine Form des Angriffs, bei der ein Paar aus Geheimtext UND Klartext bekannt ist. Hier reicht bereits ein recht kurzes Stück, wenn man Zusatzinformationen hat wie Art der Kodierung, in Frage kommende Schlüsselwörter etc.
Jetzt fragst du nach einer Known-Ciphertext-Attack (KCA), also einem Angriff, bei dem man bloß den Geheimtext hat. Hier fängt der Spaß erst bei einigen hundert Buchstaben an, weil einem ja die wichtigen Infomationen durch den fehlenden Klartext fehlen.
> Und wie ist es bei der Caesar-Chiffre???
Nun, bei einer KPA reicht natürlich nur ein Buchstabenpaar, weil man daraus direkt sieht, um wieviel der Klartext verschoben wurde, damit der Geheimtext entsteht.
Bei einer KCA lohnt sich der Aufwand einer ernsthaften Analyse gar nicht. Hier würde man einfach alle möglichen Verschiebungen auf einem kurzen Ausschnitt ausprobieren und wäre fertig. Natürlich kann man dafür auch die Methoden benutzen, die man für Tauschchiffren nimmt, aber das wäre mit Kanonen auf Spatzen geschossen.
> Wieso ist das denn so?
Wieso man soundsoviele Buchstabenpaare braucht?
Bei der Tauschchiffre:
Hast du zwei nebeneinanderstehende Buchstabenpaare, dann weißt du, dass sie Klartextalphabet direkt aufeinanderfolgen, während sie im Geheimtextalphabet den Abstand t haben. Damit hast du schon den ersten Parameter. Den zweiten Parameter bekommst du, indem du die Gleichung aus meinem vorletzten Beitrag löst.
Hast du nun zwei Buchstabenpaare, die nicht direkt nebeneinander stehen, ist es auch kein Problem. Wenn sie im Klartextalphabet den Abstand a haben, müssen sie im Geheimtextalphabet den Abstand [mm] $t\cdot{}a$ [/mm] haben. (Natürlich bewegen wir uns hier in einem Ring) Da t bei einer sinnvollen Chiffre zu der Alphabetlänge prim ist (also ggT=1), lässt sich t immer eindeutig finden. Hat man dieses, ist das s kein Problem.
Also reichen bei einer Tauschchiffre immer zwei Buchstabenpaare, oder?
Bei einer Schlüsselwortchiffre ist das nicht so einfach, weil das Schlüsselwort eine beliebige Länge haben kann, aus einer beliebigen Sprache (oder aus keiner!) stammen kann, weil sich die Buchstaben darin beliebig oft wiederholen können usw. Hier ist es hilfreich, wenn man sowohl Buchstabenpaare hat, deren Geheimtextbuchstabe im Schlüsselwort vorkommt, als auch andere Paare, die anzeigen, wieviel von der ursprünglichen Ordnung im Geheimtextalphabet herrscht.
Hat man nur Buchstabenpaare, deren Geheimtextbuchstaben nicht im Schlüsselwort vorkommen, dann kann man vielleicht raten, aus welchen Buchstaben sich das Schlüsselwort zusammensetzt und wo es anfängt, aber man muss sich die Reihenfolge zusammenpuzzeln. Also helfen einem hier Vorwissen und Wortschatz.
Optimal ist es, wenn man möglichst viele Buchstabenpaare mit Geheimtextbuchstaben aus dem Schlüsselwort hat. Das erkennt man daran, dass die Klartextbuchstaben recht eng beisammen stehen, die Reihenfolge der entsprechenden Geheimtextbuchstaben aber durcheinander ist (eben die Reihenfolge, in der sie im Schlüsselwort vorkommen). In diesem Fall sieht man mehr oder weniger, wo das Schlüsselwort anfängt, und meist kann man die wenigen fehlenden Buchstaben raten, wenn man weiß, was für ein Schlüsselwort in Frage kommt.
Auf die Anzahl der benötigten Buchstabenpaare will ich mich nicht festlegen...
Man muss heuristisch vorgehen, weil die Sprache nicht unbedingt mathematischen Regeln folgt. Man wandelt für die Kodierung zwar Buchstaben in Zahlen um, aber ihre Reihenfolge ist "beliebig", so dass man mit seinem eigenen Wortschatz und etwaigem Vorwissen oft weiterkommt als mit rechnerischen Methoden. Natürlich kann man auch einen Rechner mit einer Wortliste versorgen. Aber das eigene Gefühl ist bei solch simplen Chiffren doch sehr hilfreich. Natürlich beziehen sich meine Ausführungen auf eine KPA. Bei einer KCA ist der Rechner unser bester Freund...
> Wie würde man bei der tausch-Chiffre und bei der schlüsselwortchiffre auf die Lösung kommen, wenn nur der codierte text da stünde?
Das ist die KCA.
Hier nutzt man sprachspezifische Statistiken. Man nutzt hierbei den Umstand, dass beispielweise im Deutschen das E und das N sehr häufig vorkommen, das Y und das Q dagegen ziemlich selten. Man vergleicht die Häufigkeiten von Geheimtextbuchstaben mit denen der Buchstaben in der deutschen Sprache und findet so recht schnell Korrespondenzen, wenn genug Geheimtext vorhanden ist, der einigermaßen normale Wörter enthält. Danach kann man die Häufigkeiten von Bigrammen bestimmen, also Folgen von zwei Buchstaben, von denen beispielsweise im Deutschen EI und IE mit die häufigsten sind.
So findet man einige Zuordnungen und kann dann wie bei der KPA vorgehen.
Ich hoffe, das war nicht zu konfus. Ich übernehme auch keine Verantwortung für falsche Schätzungen...
Gruß
Martin
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:09 Do 23.11.2006 | | Autor: | Kristien |
Hallo Martin, das mit den korresponierenden Buchstabenpaaren ist mir jetzt schon viel klarer geworden. Danke für die ausführliche Antwort!!!
Ich weiß aber immernoch nicht genau, wie man bei flogendem Tausch-Chiffre Text zum originaltext kommt und wie man auf die schlüssel kommt. der vollstendige code text lautet: MUD2ER4ELMWUDMURBELI7W0J7MMWEIXBM2JUD7ML7MUR
Könntest du mir außerdem die Systematik der Ents. formulieren?
Dies ist der Vollständige schlüsselwort-Chiffre-Text: EAHL6EG496A366J9EA6EA6HO2F6EAF649J6HH49O6EA
Wie kommt man hier ohne weiteren Angaben zum Text und wie finde ich hierbei die schlüssel? Kannst du mir hierbei auch die Systematik zur Entschlüsselung formulieren?
Vielen lieben Dank
|
|
|
| |
|
Hallo,
deine Geheimtexte sind aber reichlich kurz für eine Know-Ciphertext-Attacke! Es ist zu befürchten, dass die Häufigkeiten nicht wirklich repräsentativ sind. Ich kann es aber trotzdem mal im Ansatz zeigen:
Unser Geheimtext:
MUD2ER4ELMWUDMURBELI7W0J7MMWEIXBM2JUD7ML7MUR
Unser Vorwissen:
Tauschchiffre, deutscher Text
Wir zählen also die Buchstabenhäufigkeiten im Geheimtext und kommen auf:
8: M
5: U
4: E7
3: DLRW
2: BIJ2
1: X04
oder in Prozent:
18.2%: M
11.4%: U
9.09%: E7
6.82%: DLRW
4.55%: BIJ2
2.27%: X04
Jetzt beginnt der heikle Teil. Wir schauen unter ![[]](/images/popup.gif) Buchstabenhäufigkeiten nach und sehen dort, dass der mit Abstand häufigste Buchstabe das E ist. Also sagen wir ganz mutig:
E -> M, weil E der häufigste Klartext- und M der häufigste Geheimtextbuchstabe sind.
Nun der zweithäufigste. Im Geheimtext das U, im Klartext das N. Wir probieren es aus, es klappt nicht (Schnellvorlauf), wir probieren den nächsten Buchstaben. Der dritthäufigste deutsche Buchstabe ist das I.
Wir versuchen es also mit (E,M) und (I,U). Wir rechnen mal:
"I" - "E" = 9 - 5 = 4
"U" - "M" = 21 - 13 = 8
Mit diesen Angaben versuchen wir an unsere Parameter s und t zu kommen (s=Verschiebung, t=Faktor). Dabei kommen für t nur Zahlen in Frage, die zu der Alphabetlänge 36 teilerfremd sind, also eine Zahl aus der Menge [mm]T = \left\{1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35\right\}[/mm]
Wir suchen also [mm] $t\in{}T$ [/mm] mit:
[mm] $4\cdot{}t [/mm] = 8$ (natürlich in diesem Ring, also modulo)
Hierfür finden wir zwei Lösungen:
$t=11$ oder $t=19$
Es wäre also besser gewesen, wenn zwischen der Abstand zwischen den Klartextbuchstaben teilerfremd zu 36 gewesen wäre. Aber man kann ja nicht alles haben. Also müssen wir beide Hypothesen ausprobieren.
Wir fangen mit $t=11$ an:
Wir wissen, dass aus dem E ein M wird, wenn wir es um s verschieben und dann mit $t=11$ multiplizieren. Also suchen wir ein geeignetes s, das diese Gleichung erfüllt:
$("E" + [mm] s)\cdot{}11 [/mm] = "M"$
$(5 + [mm] s)\cdot{}11 [/mm] = 13$
Wir lassen rechnen und kommen auf $s=6$
Wir probieren unsere Lösung und sie passt! Also sind wir fertig!
Gruß
Martin
|
|
|
|
