Substitutionschiffren knacken

Python :: Aufgabe #100

1 Lösung

Fortgeschrittener - Python von eulerscheZhl - 09.03.2016 um 21:41 Uhr

Bei einer Substitutionschiffre werden Buchstaben durch andere Buchstaben ersetzt.
Dadurch bleiben die Häufigkeitsverteilungen der Buchstaben allerdings erhalten, weshalb etwa ein 'e' leicht erkannt werden kann.

Für diese Aufgabe soll aber ein Wörterbuch (z.B. von der Uni Kiel, benötigt aber etwas Nachbearbeitung) verwendet werden, um die ursprüngliche Nachricht zu erhalten.
So ist es zwar schwer, eine komplett richtige Dekodierung zu erhalten (da nicht alle Wörter im Wörterbuch enthalten sind), aber man kann lesbare Ergebnisse erzielen.

Im Anhang befinden sich Texte aus zufälligen Artikeln der deutschsprachigen Wikipedia. Es ist jeweils mindestens die Hälfte der vorkommenden Wörter im verlinkten Wörterbuch enthalten.

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

Lösungen:

von devnull (8870 Punkte) - 29.03.2016 um 16:48 Uhr

Die nachfolgende Lösung verfolgt einen interaktiven Ansatz zur Dechiffrierung. Zunächst werden die Häufigkeitsverteilungen der Zeichen aus einem Wörterbuch und dem Chiffretext ermittelt. In "nullter" Näherung werden die Zeichen entsprechend ihrer Position in der Verteilung zugeordnet. Das ergibt i.d.R. noch keinen lesbaren Text, nur der Vokal "e" lässt sich mit einiger Sicherheit identifizieren. Danach wird der Chiffretext und der Text im jeweiligen Stadium der Dechiffrierung untereinander in Zeilenpaaren angezeigt. Der Anwender kann nun fortlaufend Buchstaben austauschen und sich den neuen Text anzeigen lassen. Auf diese Weise muss er versuchen, der Lösung auf die Spur zu kommen.
Chiffretext 11: zum Artikel
Chiffretext 25: zum Artikel

Konsolenausgabe:

Nummer des Chiffre-Textes: 11
total characters:  367640 (dict), 464 (cipher)
 1) (13.26%)  48740 : e - l :   83 (17.89%) 
 2) ( 8.01%)  29443 : n - b :   43 ( 9.27%) 
 3) ( 7.85%)  28856 : r - p :   37 ( 7.97%) 
 4) ( 7.46%)  27419 : t - t :   36 ( 7.76%) 
 5) ( 6.96%)  25584 : i - s :   35 ( 7.54%) 
 6) ( 6.29%)  23133 : s - w :   28 ( 6.03%) 
 7) ( 6.14%)  22562 : a - d :   27 ( 5.82%) 
 8) ( 4.98%)  18313 : u - k :   25 ( 5.39%) 
 9) ( 4.79%)  17611 : g - ü :   22 ( 4.74%) 
10) ( 4.65%)  17102 : l - h :   18 ( 3.88%) 
11) ( 4.02%)  14791 : h - r :   13 ( 2.80%) 
12) ( 2.96%)  10890 : o - a :   11 ( 2.37%) 
13) ( 2.71%)   9948 : c - ä :   10 ( 2.16%) 
14) ( 2.62%)   9643 : k - v :   10 ( 2.16%) 
15) ( 2.56%)   9399 : m - ß :    9 ( 1.94%) 
16) ( 2.49%)   9139 : b - j :    9 ( 1.94%) 
17) ( 2.26%)   8300 : f - o :    9 ( 1.94%) 
18) ( 2.15%)   7897 : d - q :    9 ( 1.94%) 
19) ( 1.70%)   6259 : p - c :    8 ( 1.72%) 
20) ( 1.34%)   4918 : z - x :    6 ( 1.29%) 
21) ( 1.11%)   4076 : w - e :    4 ( 0.86%) 
22) ( 0.98%)   3617 : ä - y :    4 ( 0.86%) 
23) ( 0.97%)   3558 : v - g :    2 ( 0.43%) 
24) ( 0.72%)   2632 : ü - u :    2 ( 0.43%) 
25) ( 0.31%)   1132 : ß - ö :    1 ( 0.22%) 
26) ( 0.31%)   1125 : ö - f :    1 ( 0.22%) 
27) ( 0.14%)    511 : y - i :    1 ( 0.22%) 
28) ( 0.11%)    404 : j - m :    1 ( 0.22%) 
...

bjßlbk asüülbäldd (* 2. wlxklüßlb 1884 tp qtlp; † 17. wlxklüßlb 1950 tp xdspa 
robert kammerzell (* 2. september 1884 in wien; † 17. september 1950 in plank 

sü asüx) qsb ltp ptlrlbfwklbbltvhtwvhlb agpwkdlb opr hltüskyjbwvhlb. asüülbäldd 
am kamp) war ein niederösterreichischer künstler fnd heimatäorscher. kammerzell 

qsprlbkl 1912 tp rtl elbltptcklp wkssklp sow. lb sbßltklkl sp rlb ülkbjxjdtksp 
wanderte 1912 in die wereinipten staaten afs. er arbeitete an der metropolitan 

jxlbs tp plq öjba sdw aodtwwlpüsdlb. plßlp rtlwlü lhlb hsprqlbadtvhlü äocspc 
opera in new ßork als kflissenmaler. neben diesem eher handwerklichem zfpanp 

äob üsdlblt qsb lb sovh agpwkdlbtwvh kuktc, qtl äshdbltvhl iosdtkukejddl 
zfr malerei war er afch künstlerisch tütip, wie zahlreiche yfalitütwolle 

dsprwvhsykwßtdrptwwl rlb mshbl 1914 ßtw 1917 (oü 1975 pjvh tü ßlwtkäl rlw 
landschaätsbildnisse der jahre 1914 bis 1917 (fm 1975 noch im besitze des 

hlbbp ybspä ytwvhlb tp dspclpdjtw, ltplü elbqsprklp asüülbälddw) ältclp. 
herrn äranz äischer in lanpenlois, einem werwandten kammerzells) zeipen. 

sdw üsdlb twk asüülbäldd hlokl sßlb qltkclhlpr elbclwwlp. 
als maler ist kammerzell hefte aber weitpehend werpessen. 

Buchstabe zu ersetzen: o
Buchstabe als Ersatz : u

Python-Code

#!/usr/bin/python3
#
charTabDict = {}
charTabCipher = {}
charMap = {}

def makeCharDistrib(path, chtab):
	words = open(path, "r")
	for word in words:
		for ch in word.lower():
			oc = ord(ch)
			if (ch >= 'a' and ch <= 'z') or ch in ('ä','ö','ü','ß'):
				if ch in chtab:
					chtab[ch] += 1;
				else:
					chtab[ch] = 1;
	words.close()


def printDechipheredText(words, chMap):
	for word in words:
		for ch in word:
			if ch in chMap:
				print(chMap[ch], end="")
			else:
				print(ch, end="")
		print(" ", end="")
	

def printText(lines, chMap):
	line_length = 0
	line_words = []
	for line in lines:
		for word in line.split():
			print(word, end=" ")
			line_words.append(word)
			line_length += len(word)+1
			if line_length > 72:
				print("")
				printDechipheredText(line_words, chMap)
				print("\n")
				line_words[:] = []
				line_length = 0
	if len(line_words) > 0:
		print("")
		printDechipheredText(line_words, chMap)
	print("\n")


#main
cipherNumber = input("Nummer des Chiffre-Textes: ")
if cipherNumber > "0":
	cipherPath = "../chiffre/chiffre{:02d}.txt".format(int(cipherNumber))

	makeCharDistrib("../words/hkwords.txt", charTabDict)
	makeCharDistrib(cipherPath, charTabCipher)
	
	nCharsDict = 0
	nCharsCipher = 0
	for key in charTabDict:
		nCharsDict += charTabDict[key]
	for key in charTabCipher:
		nCharsCipher += charTabCipher[key]
	print("total characters:  {:d} (dict), {:d} (cipher)".format( 
			nCharsDict, nCharsCipher))		

	freqDict = sorted(charTabDict.items(), key=lambda x: x[1], reverse=True)
	freqCipher = sorted(charTabCipher.items(), key=lambda x: x[1], reverse=True)

	for n in range(0, len(freqCipher)):
		di = freqDict[n]
		ci = freqCipher[n]
		dp = 100.0 * di[1] / nCharsDict
		cp = 100.0 * ci[1] / nCharsCipher
		charMap[ci[0]] = di[0]
		print("{:2d}) ({:5.2f}%) {:6d} : {:1s} - {:1s} : {:4d} ({:5.2f}%) ".format(
				n+1, dp, di[1], di[0], ci[0], ci[1], cp))

	print("\n")
	textfile = open(cipherPath, "r")
	lines = textfile.readlines()
	textfile.close()
	
	while True:
		printText(lines, charMap)
		inchar = input("Buchstabe zu ersetzen: ")
		if inchar == "":
			break
		else:	
			mapchar = input("Buchstabe als Ersatz : ")
			charMap[inchar] = mapchar

	print("")
	print(charMap)

Bitte melden Sie sich an um eine Kommentar zu schreiben.

Kommentar schreiben