summaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
authorRahiel Kasim <rahielkasim@gmail.com>2017-03-31 11:33:29 +0200
committerRahiel Kasim <rahielkasim@gmail.com>2017-03-31 11:35:44 +0200
commitfdcdd8dd8ff15aa0d94cc44df97ae0e1242f4539 (patch)
treecf1e212bd063ae1cda75cbafc572ebe99133c37c
parent41f31232d956f07d85a985ef24f07420e86b940e (diff)
12: Monoalphabetic Cipher
-rw-r--r--12-monoalphabetic-cipher.py68
1 files changed, 68 insertions, 0 deletions
diff --git a/12-monoalphabetic-cipher.py b/12-monoalphabetic-cipher.py
new file mode 100644
index 0000000..ae22bb6
--- /dev/null
+++ b/12-monoalphabetic-cipher.py
@@ -0,0 +1,68 @@
+from math import inf, log10
+from os import system
+from os.path import expanduser
+from random import sample
+from string import ascii_uppercase
+
+from utils import md5
+
+# this implements the attack described at:
+# http://practicalcryptography.com/cryptanalysis/stochastic-searching/cryptanalysis-simple-substitution-cipher/
+# using the quadgram data from:
+# http://practicalcryptography.com/cryptanalysis/text-characterisation/quadgrams/
+
+# This randomized algorithm can find a wrong solution when it's stuck in a
+# local maximum, you may have to run this a couple of times.
+
+ciphertext = "EANOEHHNFJLFXDGFANOYDJINTNOEDJXFOSBFESDOLGDWWSNUEDJNQCSJNUFEFFOUIDTTCOSIFESDOLNJKSINLEDNOXSONNJEZNSJMJDUCIELEDXCFJFOENNGFANOYDJINTNOEFIINLLEDFGGUFEFFYENJGNOXEZHUNWFENFOUKSXDJDCLMJNUSIESDOLDYNOYDJINTNOEIZFOONGLXDSOXUFJREZNLNFEENTMELEDJNXCGFENEZNNTNJXSOXSOENJONEANJNFWFOUDONUSOEZNSOENJKNOSOXHNFJLSOODKFESDODOEZNSOENJONEYGDCJSLZNUFOUGFANOYDJINTNOEFXNOISNLYDCOUONAFOUTDJNNYYNIESKNTNFOLDYFIINLLSOXKFLEGHGFJXNJQCFOESESNLDYUFEFEDUFHANFJNFXFSOZNFJSOXIFGGLYDJJNXCGFESDOEDTFOUFENEZNMJDKSLSDODYNPINMESDOFGFIINLLTNIZFOSLTLSOEZSLJNMDJEFXJDCMDYIDTMCENJLISNOESLELFOULNICJSEHNPMNJELTFOHDYAZDTMFJESISMFENUSOFLECUHDYEZNLNLFTNEDMSILZFLIDOKNONUEDNPMGDJNEZNGSRNGHNYYNIELDYSTMDLSOXNPEJFDJUSOFJHFIINLLTFOUFENLANZFKNYDCOUEZFEEZNUFTFXNEZFEIDCGUWNIFCLNUWHGFANOYDJINTNOENPINMESDOFGFIINLLJNQCSJNTNOELADCGUWNNKNOXJNFENJEDUFHEZFOSEADCGUZFKNWNNOHNFJLFXDSOEZNAFRNDYEZNXJDASOXNIDODTSIFOULDISFGIDLEDYEZNYCOUFTNOEFGSOLNICJSEHDYEDUFHLSOENJONENOKSJDOTNOEFOHMJDMDLFGLEZFEFGENJEZNLNICJSEHUHOFTSILDOGSONLZDCGUWNFMMJDFIZNUASEZIFCESDONPINMESDOFGFIINLLADCGUYDJINSOENJONELHLENTUNKNGDMNJLEDJNKNJLNYDJAFJULNIJNIHUNLSXOMJFIESINLEZFELNNREDTSOSTSBNEZNSTMFIEDOCLNJMJSKFIHAZNOLHLENTLFJNWJNFIZNUEZNIDTMGNPSEHDYEDUFHLSOENJONENOKSJDOTNOEASEZTSGGSDOLDYFMMLFOUXGDWFGGHIDOONIENULNJKSINLTNFOLEZFEONAGFANOYDJINTNOEJNQCSJNTNOELFJNGSRNGHEDSOEJDUCINCOFOESISMFENUZFJUEDUNENIELNICJSEHYGFALWNHDOUEZNLNFOUDEZNJENIZOSIFGKCGONJFWSGSESNLEZNMJDLMNIEDYXGDWFGGHUNMGDHNUNPINMESDOFGFIINLLLHLENTLJFSLNLUSYYSICGEMJDWGNTLFWDCEZDALCIZFONOKSJDOTNOEADCGUWNXDKNJONUFOUZDAEDNOLCJNEZFELCIZLHLENTLADCGUJNLMNIEZCTFOJSXZELFOUEZNJCGNDYGFA"
+
+
+quadgram_scores = {}
+total = 0
+with open(expanduser("~/Documents/english_quadgrams.txt")) as f:
+ for line in f:
+ quadgram, count = line.strip().split(" ")
+ count = int(count)
+ quadgram_scores[quadgram] = count
+ total += count
+for q in quadgram_scores:
+ quadgram_scores[q] = log10(quadgram_scores[q] / total)
+default_qscore = -9.63 # something close to and smaller than log10(1 / total)
+
+def english_score(text, quadgram_scores):
+ quadgrams = [text[i:i+4] for i in range(len(text) - 3)]
+ return sum(quadgram_scores.get(q, default_qscore) for q in quadgrams)
+
+def decrypt(ciphertext, key):
+ return "".join([key[c] for c in ciphertext])
+
+def find_key(ciphertext):
+ key = {c: c for c in ascii_uppercase}
+ score = -inf
+ invariance = 0
+
+ while True:
+ a, b = sample(ascii_uppercase, 2)
+ new_key = key.copy()
+ new_key[a] = key[b]
+ new_key[b] = key[a]
+
+ m = decrypt(ciphertext, new_key)
+ new_score = english_score(m, quadgram_scores)
+ if new_score >= score:
+ key = new_key
+ score = new_score
+ invariance = 0
+ system("clear")
+ print(m)
+ else:
+ invariance += 1
+
+ if invariance > 1000:
+ break
+ return key
+
+
+key = find_key(ciphertext)
+message = decrypt(ciphertext, key)
+print(md5(message))