Informatiker Board | Druckvorschau: Statistische Analyse mit Substitutionschiffren

Geschrieben von yuro123 am 13.06.2015 um 16:04:

Statistische Analyse mit Substitutionschiffren

Hallo smile

und zwar hab ich folgendes Problem. In einer Aufgabe ist ein Zahlenrätsel gegeben welches entschlüsselt werden soll.

Es handelt sich um einen Text in der deutschen Sprache.

Ich habe eine Analyse über die Häufigkeit der Zahlen durchgeführt dabei ist herausgekommen:

1 = 22
2 = 20
3 = 21
4 = 20
5 = 42
6 = 26
7 = 20
8 = 4
9 = 6
10 = 45
11 = 11
12 = 5
13 = 3
14 = 2
15 = 19
16 = 2
17 = 4
18 = 3
19 = 8
20 = 6
21 = 4
22 = 6
23 = 5
24 = 2
25 = 7
26 = 7

d.h. die Zahl 10 kommt 45-mal vor im Zahlenrätsel folgend von der 5 mit 42-mal. Also ist es wahrscheinlich das die Zahl 10 dem Buchstaben "E" entspricht, da das "E" in der deutschen Sprache am häufigsten vorkommt und die Zahl 5 dem Buchstaben "N".

Muss ich das so verstehen das die Zahlen 1-26 a-z sind beginnend mit 1 statt mit der 0 ?

4 Zahlen wurden mir als Ergebnis gegeben.

1 = R
6 = I
11 = M
22 = P

Ich würde gerne mal wissen wie ich darauf kommen kann?

Geschrieben von eulerscheZahl am 13.06.2015 um 17:45:

Scheint ja eine simple Substitutionschiffre zu sein.
Eine Häufigkeitsanalyse ist natürlich ein guter Ansatz. Das geht nicht nur für einzelne Buchstaben, sondern auch für Gruppen: nach einem 'e' kommt häufig ein 'r', 'i' oder 'u' (nur als Beispiel). Wenn du weißt, welche Häufigkeitswerte bei solchen Kombinationen auftreten, kannst du die auch analysieren. Du kannst das auch gleich mit einem Wörterbuch verknüpfen.

Geschrieben von yuro123 am 13.06.2015 um 17:49:

@eulerscheZahl

Danke erst einmal für deine Antwort. Bist immer ein super Helfer in Not für meine Angelegenheiten hehe smile

Meine Frage ist. Wie erkennt man welche Möglichkeit in nutzen kann.

Ich habe ja zwei zur Auswahl. Die Verschiebechiffre und die Affine Chiffre.

Kannst du mir vll. ein Beispiel geben wie man sehen kann das 1 = R ist?

Geschrieben von eulerscheZahl am 13.06.2015 um 17:58:

Das wirst du so isoliert betrachtet nicht sehen können.
Das E hast du ja schon mit großer Wahrscheinlichkeit zugeordnet. Dann probierst du vielleicht das I oder U als nächstes. Wenn das Ergebnis sinnvoll aussieht, kannst du möglicherweise das Wort "EIN" im Text entdecken. Wenn du während der Substitution merkst, dass Buchstabensalat entsteht, war wohl was falsch und es heißt zurück auf Anfang.

Bei der affinen Chiffre hast du nur 312 Möglichkeiten. Da kannst du einfach alle bilden (per Computer) und die dann von Hand durchschauen, das ist wirklich nicht schwer.

Geschrieben von yuro123 am 13.06.2015 um 18:35:

achsooo und da die angegebene Anzahl oben 320 ist kann man die affine direkt ausschließen und man weiss das es eine Verschiebechiffre bzw. Substitutionschiffre ist?

Geschrieben von eulerscheZahl am 13.06.2015 um 18:52:

Nein, so war das jetzt nicht gemeint.
Prinzipiell hast du bei der Substitution 26! = 403291461126605635584000000 Möglichkeiten (jeder Buchstabe kann jeder Zahl zugeordnet werden). Bei der affinen Verschlüsselung gibt es eben nur 312 Zuordnungen. Das hat aber nichts mit der Anzahl der im Text vorkommenden Buchstaben zu tun.

Aber da die erste Zahl doch selbst für moderne Rechner um ein Vielfaches zu groß ist, einfach alle Kombinationen durchzuprobieren, muss man da mit Wahrscheinlichkeiten arbeiten (der häufigste Buchstabe im Text ist eben mit großer Wahrscheinlichkeit ein E). Je länger der Text ist, desto eher stellen sich die statistisch zu erwartenden Verteilungen ein, was eine Entschlüsselung einfacher macht.

Wenn du mir deinen Text gibst, kann die dir daran erklären, was ich meine.

Geschrieben von yuro123 am 13.06.2015 um 19:17:

Also die Aufgabe besteht rein aus verschlüsselten Zahlen. Du musst dir vorstellen wie eine Sudoku. Ein Quadrat wo Zahlen enthalten sind.

und als Lösungsansicht habe ich eine Tabelle mit den Zahlen 1-26 und da müssen die entschlüsselten Buchstaben eingetragen werden.

Deswegen ist es etwas schwerer für mich zu verstehen.

Geschrieben von eulerscheZahl am 13.06.2015 um 19:23:

Wo hast du das denn gefunden?

Kann sein, dass du es einfach Zeile für Zeile lesen kannst, als würde es in einer stehen. Kann aber auch sein, dass die Breite Teil der Verschlüsselung ist, wie bei ADFGX.

Geschrieben von yuro123 am 13.06.2015 um 19:31:

also ich schreib dir mal die ersten Zeilen auf. Leerzeichen markiere ich als (_)

_ 14 9 5 1 2 10 12 5 _ 4 22 7 6 11 6 15 7 _

20 _ 1 6 10 _ 3 10 8 10 1 1 10 _ 4 15 7 _ 7

10 2 10 10 20 _ 4 11 10 _ 10 6 1 _ 3 10 1 19 5

2 5 25 _ 20 5 2 15 _ 19 _ 11 6 26 6 _ 4 6 5

19 5 3 12 10 2 6 _ 19 9 15 _ 20 5 2 23 25 5 3

_ _ _ 2 5 6 _ 2 5 7 10 2 _ 1 6 4 _ 7 _

Das sind die ersten Zeilen.

Geschrieben von eulerscheZahl am 13.06.2015 um 19:42:

Könnte genauso gut runterwärts zu lesen sein (da taucht "prim" auf), wodurch der Auszug der ersten Zeilen die Sache erheblich verkompliziert. Hast du keinen Link zur Aufgabe?

Geschrieben von yuro123 am 14.06.2015 um 03:22:

Kann man screenshots hier hochladen??

Geschrieben von eulerscheZahl am 14.06.2015 um 06:14:

Ja, bis 200KB.
Klicke unterhalb des Eingabefelds auf "Dateianhänge", wähle dein Bild aus und dann auf "Speichern". Das Bild wird dann unten im Beitrag angehängt.

Bei >200KB entweder mit Kompression versuchen (für png verwende ich meist Trimage), oder extern hochladen.

Geschrieben von yuro123 am 14.06.2015 um 12:35:

So hab es jetzt mal als .PNG hochgeladen smile

Geschrieben von eulerscheZahl am 14.06.2015 um 17:55:

Sieht für mich nach einem Kreuzworträtsel aus.
Damit fällt die Suche nach häufigen Wörtern wie der, die, das, und, ... weg.

Geschrieben von yuro123 am 15.06.2015 um 23:32:

Hmm das hilft mir jetzt leider auch nicht weiter, da ich nicht weiß wie ich weiter vorgehen soll. Ich hab die Häufigkeit der Zahlen ermittelt..ok.. wie geh ich weiter vor? Ich hab hier eine Definition für die Substitutionschiffre:

PT= Plaintext
CT = Ciphertext
K = Schlüssel

Sei PT = CT = Z26 und K die Menge aller Permutationen von Z26:

y = e(x) = Pi(x), Pi € K

x = d(x) = Pi^-1(y)

Pi^-1 ist die zu Pi inverse Permutation.

Die muss ich dann wahrscheinlich entweder für die Verschiebechiffre (Caesar Chiffre) oder die affine Chiffre verwenden, da die ja solche Formeln ebenfalls enthalten.

Verschiebechiffre:

y = ek(x) = x + k mod 26, x € Z26
x = dk(y) = y - k mod 26, y € Z26

Affine Chiffre:

y = ek(x) = ax + b mod 26, x € Z26
x = dk(y) = a^-1(y-b) mod 26, y € Z26