# AIM: To Decrypt a text using MCMC approach. i.e. find decryption key which we will call cipher from now on.
import string
import math
import random
# This function takes as input a decryption key and creates a dict for key where each letter in the decryption key
# maps to a alphabet For example if the decryption key is "DGHJKL...." this function will create a dict like {D:A,G:B,H:C....}
def create_cipher_dict(cipher):
cipher_dict = {}
alphabet_list = list(string.ascii_uppercase)
for i in range(len(cipher)):
cipher_dict[alphabet_list[i]] = cipher[i]
return cipher_dict
# This function takes a text and applies the cipher/key on the text and returns text.
def apply_cipher_on_text(text,cipher):
cipher_dict = create_cipher_dict(cipher)
text = list(text)
newtext = ""
for elem in text:
if elem.upper() in cipher_dict:
newtext+=cipher_dict[elem.upper()]
else:
newtext+=" "
return newtext
# This function takes as input a path to a long text and creates scoring_params dict which contains the
# number of time each pair of alphabet appears together
# Ex. {'AB':234,'TH':2343,'CD':23 ..}
def create_scoring_params_dict(longtext_path):
scoring_params = {}
alphabet_list = list(string.ascii_uppercase)
with open(longtext_path) as fp:
for line in fp:
data = list(line.strip())
for i in range(len(data)-1):
alpha_i = data[i].upper()
alpha_j = data[i+1].upper()
if alpha_i not in alphabet_list and alpha_i != " ":
alpha_i = " "
if alpha_j not in alphabet_list and alpha_j != " ":
alpha_j = " "
key = alpha_i+alpha_j
if key in scoring_params:
scoring_params[key]+=1
else:
scoring_params[key]=1
return scoring_params
# This function takes as input a text and creates scoring_params dict which contains the
# number of time each pair of alphabet appears together
# Ex. {'AB':234,'TH':2343,'CD':23 ..}
def score_params_on_cipher(text):
scoring_params = {}
alphabet_list = list(string.ascii_uppercase)
data = list(text.strip())
for i in range(len(data)-1):
alpha_i =data[i].upper()
alpha_j = data[i+1].upper()
if alpha_i not in alphabet_list and alpha_i != " ":
alpha_i = " "
if alpha_j not in alphabet_list and alpha_j != " ":
alpha_j = " "
key = alpha_i+alpha_j
if key in scoring_params:
scoring_params[key]+=1
else:
scoring_params[key]=1
return scoring_params
# This function takes the text to be decrypted and a cipher to score the cipher.
# This function returns the log(score) metric
def get_cipher_score(text,cipher,scoring_params):
cipher_dict = create_cipher_dict(cipher)
decrypted_text = apply_cipher_on_text(text,cipher)
scored_f = score_params_on_cipher(decrypted_text)
cipher_score = 0
for k,v in scored_f.iteritems():
if k in scoring_params:
cipher_score += v*math.log(scoring_params[k])
return cipher_score
# Generate a proposal cipher by swapping letters at two random location
def generate_cipher(cipher):
pos1 = random.randint(0, len(list(cipher))-1)
pos2 = random.randint(0, len(list(cipher))-1)
if pos1 == pos2:
return generate_cipher(cipher)
else:
cipher = list(cipher)
pos1_alpha = cipher[pos1]
pos2_alpha = cipher[pos2]
cipher[pos1] = pos2_alpha
cipher[pos2] = pos1_alpha
return "".join(cipher)
# Toss a random coin with robability of head p. If coin comes head return true else false.
def random_coin(p):
unif = random.uniform(0,1)
if unif>=p:
return False
else:
return True
# Takes as input a text to decrypt and runs a MCMC algorithm for n_iter. Returns the state having maximum score and also
# the last few states
def MCMC_decrypt(n_iter,cipher_text,scoring_params):
current_cipher = string.ascii_uppercase # Generate a random cipher to start
state_keeper = set()
best_state = ''
score = 0
for i in range(n_iter):
state_keeper.add(current_cipher)
proposed_cipher = generate_cipher(current_cipher)
score_current_cipher = get_cipher_score(cipher_text,current_cipher,scoring_params)
score_proposed_cipher = get_cipher_score(cipher_text,proposed_cipher,scoring_params)
acceptance_probability = min(1,math.exp(score_proposed_cipher-score_current_cipher))
if score_current_cipher>score:
best_state = current_cipher
if random_coin(acceptance_probability):
current_cipher = proposed_cipher
if i%500==0:
print "iter",i,":",apply_cipher_on_text(cipher_text,current_cipher)[0:99]
return state_keeper,best_state
## Run the Main Program:
scoring_params = create_scoring_params_dict('war_and_peace.txt')
plain_text = "As Oliver gave this first proof of the free and proper action of his lungs, \
the patchwork coverlet which was carelessly flung over the iron bedstead, rustled; \
the pale face of a young woman was raised feebly from the pillow; and a faint voice imperfectly \
articulated the words, Let me see the child, and die. \
The surgeon had been sitting with his face turned towards the fire: giving the palms of his hands a warm \
and a rub alternately. As the young woman spoke, he rose, and advancing to the bed's head, said, with more kindness \
than might have been expected of him: "
encryption_key = "XEBPROHYAUFTIDSJLKZMWVNGQC"
cipher_text = apply_cipher_on_text(plain_text,encryption_key)
decryption_key = "ICZNBKXGMPRQTWFDYEOLJVUAHS"
print"Text To Decode:", cipher_text
print "\n"
states,best_state = MCMC_decrypt(10000,cipher_text,scoring_params)
print "\n"
print "Decoded Text:",apply_cipher_on_text(cipher_text,best_state)
print "\n"
print "MCMC KEY FOUND:",best_state
print "ACTUAL DECRYPTION KEY:",decryption_key
MCMC 破译密码 http://mlwhiz.com/blog/2015/08/21/MCMC_Algorithms_Cryptography/的相关教程结束。
