Statistische Analyse mit Substitutionschiffren

Neue Frage »

Auf diesen Beitrag antworten »
yuro123 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?
 
Auf diesen Beitrag antworten »
eulerscheZahl

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.
Auf diesen Beitrag antworten »
yuro123

@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?
Auf diesen Beitrag antworten »
eulerscheZahl

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.
 
Auf diesen Beitrag antworten »
yuro123

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?
Auf diesen Beitrag antworten »
eulerscheZahl

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.
Auf diesen Beitrag antworten »
yuro123

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.
Auf diesen Beitrag antworten »
eulerscheZahl

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.
Auf diesen Beitrag antworten »
yuro123

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.
Auf diesen Beitrag antworten »
eulerscheZahl

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?
Auf diesen Beitrag antworten »
yuro123

Kann man screenshots hier hochladen??
Auf diesen Beitrag antworten »
eulerscheZahl

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.
Auf diesen Beitrag antworten »
yuro123

So hab es jetzt mal als .PNG hochgeladen smile
Auf diesen Beitrag antworten »
eulerscheZahl

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.
Auf diesen Beitrag antworten »
yuro123

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
Auf diesen Beitrag antworten »
eulerscheZahl

So, habe mich mal an einer Umsetzung versucht (sicher noch an einigen Stellen zu verbessern).
Habe mir von hier eine Wortliste besorgt: http://www.fernuni-hagen.de/mathinf/stud...rtraetsel.shtml

Weil ich keine Lust auf Abtippen hatte, habe ich nur die horizontalen Worte geprüft:
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
QUERLAGE  OPTIMIST  RIA       NAVARRA   OST       ALAAF     OMA       AIR       
NARBE     LEH       FELS      MIDI      OIE       BENGALI   BUS       FELCHEN   
LEI       LETAL     RIO       REVAL     LAUTLOS   AGNES     ANIS      ZART      
ARES      NANA      SEM       DAEMMEN   MAE       NATO      LAI       FLACHS    
TYP       YOGI      ASYL      EID       KAMERA    ETA       OSTE      RUR       
SPRINTS   ASA       VIZE      DEO       EST       EBRO      OWENS     EMAILLE   
PLAID     ZOO       PIQUE     MAE       INTERNA   SUK       JERICHO   BOR       
ROCK      JERICHO   BOR       ROCK      BETA      HOF       AWARE     HAG       
PAN       BEATE     VAN       ITALIEN   EDO       CENTIMES  KRYOLITH  
58 bekannte Worte
22=P, 1=R, 6=I, 11=M, 10=A, 5=E, 4=O, 2=L, 15=S, 3=N, 7=T, 19=B, 25=H, 23=C, 9=U, 26=D, 12=G, 17=K, 20=F, 8=V, 21=Y, 18=Z, 13=W, 14=Q, 24=J


Das ist die Datei puzzle.txt (nur dein Scrrenshot abgetippt, zumindest die waagerechten Worte eben:
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
14 9 5 1 2 10 12 5
4 22 7 6 11 6 15 7
1 6 10
3 10 8 10 1 1 10
4 15 7
10 2 10 10 20
4 11 10
10 6 1
3 10 1 19 5
2 5 25
20 5 2 15
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
1 5 8 10 2
2 10 9 7 2 4 15
10 12 3 5 15
10 3 6 15
18 10 1 7
10 1 5 15
3 10 3 10
15 5 11
26 10 5 11 11 5 3
11 10 5
3 10 7 4
2 10 6
20 2 10 23 25 15
7 21 22
21 4 12 6
10 15 21 2
5 6 26
17 10 11 5 1 10
5 7 10
4 15 7 5
1 9 1
15 22 1 6 3 7 15
10 15 10
8 6 18 5
26 5 4
5 15 7
5 19 1 4
4 13 5 3 15
5 11 10 6 2 2 5
22 2 10 6 26
18 4 4
22 6 14 9 5
11 10 5
6 3 7 5 1 3 10
15 9 17
24 5 1 6 23 25 4
19 4 1
1 4 23 17
24 5 1 6 23 25 4
19 4 1
1 4 23 17
19 5 7 10
25 4 20
10 13 10 1 5
25 10 12
22 10 3
19 5 10 7 5
8 10 3
6 7 10 2 6 5 3
5 26 4
23 5 3 7 6 11 5 15
17 1 21 4 2 6 7 25



Und der Quellcode (C#):
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
using System.Linq;
using System.Text.RegularExpressions;

namespace infoboard
{
	class MainClass
	{
		static string[] dict;
		static int[][] puzzle;
		static int bestFit;
		static void Main(string[] args) {
			string path = "/home/eulerschezahl/Downloads/";
			//einlesen
			dict = File.ReadLines (path + "worte.txt").Select (x => x.Substring (0, x.IndexOf (" "))).ToArray ();
			puzzle = File.ReadLines (path + "puzzle.txt").Select (x => x.Split(' ').Select(y => int.Parse(y)).ToArray()).ToArray ();
			bestFit = puzzle.Length * 3 / 4;

			//buchstabenhäufigkeit
			List<KeyValuePair<int,int>> letterCount = new List<KeyValuePair<int,int>> ();
			for (int i = 0; i <= 26; i++)
				letterCount.Add (new KeyValuePair<int, int>(i, 0));
			foreach (int[] word in puzzle)
				foreach (int i in word)
					letterCount [i] = new KeyValuePair<int, int> (i, letterCount [i].Value + 1);
			letterCount = letterCount.OrderBy (x => -x.Value).Where(x => x.Value > 0).ToList();
			letterCount = letterCount.Where (x => (new List<int> { 1, 6, 11, 22 }).IndexOf (x.Key) < 0).ToList ();
			int[] nextLetter = letterCount.Select (x => x.Key).ToArray();

			//Zuweisung vordefinierter Buchstaben P, R, I, M
			bool[] used = new bool[26];
			Dictionary<int,char> letters = new Dictionary<int, char> ();
			letters.Add (22, 'P'); used ['P' - 'A'] = true;
			letters.Add (1, 'R');used ['R' - 'A'] = true;
			letters.Add (6, 'I');used ['I' - 'A'] = true;
			letters.Add (11, 'M');used ['M' - 'A'] = true;

			FindLetters (letters, used, nextLetter, 0);
		}

		static void FindLetters(Dictionary<int, char> letters, bool[] used, int[] nextLetter, int index) {
			int fit = CountFit (letters);
			if (fit < bestFit)
				return;
			if (index == nextLetter.Length) { //Alle Buchstaben zugeteilt, Bilanz ziehen und gegebenenfalls Ergebnis ausgeben
				bestFit = fit;
				foreach (int[] word in puzzle) {
					StringBuilder sb = new StringBuilder ();
					foreach (int i in word) {
						sb.Append (letters.ContainsKey (i) ? letters [i] : '?');
					}
					Console.Write (sb.ToString().PadRight(10));
				}
				Console.Write ("\n" + fit + " bekannte Worte\n" + String.Join (", ", letters.Select (x => x.Key + "=" + x.Value)) + "\n\n");
				return;
			}

			List<KeyValuePair<char, int>> fitCount = new List<KeyValuePair<char, int>> ();
			for (char c = 'A'; c <= 'Z'; c++) {
				if (used [c - 'A'])
					continue;
				Dictionary<int, char> newDict = new Dictionary<int, char> (letters);
				newDict.Add (nextLetter [index], c);
				fitCount.Add (new KeyValuePair<char, int>(c, CountFit (newDict)));
			}
			fitCount = fitCount.OrderBy (x => -x.Value).ToList();
			foreach(KeyValuePair<char, int> pair in fitCount) {
				if (pair.Value < bestFit)
					return;
				Dictionary<int, char> newDict = new Dictionary<int, char> (letters);
				newDict.Add (nextLetter [index], pair.Key);
				bool[] newUsed = (bool[])used.Clone ();
				newUsed [pair.Key - 'A'] = true;
				FindLetters (newDict, newUsed, nextLetter, index + 1);
			}
		}

		private static int CountFit(Dictionary<int, char> letters) {
			int result = 0;
			foreach (int[] word in puzzle) {
				StringBuilder regex = new StringBuilder ();
				foreach (int i in word) {
					regex.Append (letters.ContainsKey (i) ? letters [i] : '.');
				}
				bool match = false;
				string pattern = regex.ToString ();
				foreach (string s in dict) {
					if (s.Length == word.Length && Regex.IsMatch (s, pattern)) {
						match = true; break;
					}
				}
				if (match)
					result++;
			}
			return result;
		}
	}
}
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »