Python. Взлом шифров. Продолжение.
На прошлом уроке мы начали писать программу взлома шифров. Напомню краткое содержание: мы написали программу предобработки, которая зашифрованный текст превратила в нечто более осмысленное, но все еще зашифрованное. По крайней мере, теперь мы можем извлекать из этого предобработанного текста информацию: в частности, видеть наборы букв похожие на известные нам слова и выдвигать предположения о том, что нам следует изменить в словаре.
Теперь мы напишем программу, которая, используя модифицированный выгруженный словарь, сделает расшифровку текста:
f_text = open('d:\9\out.txt', 'r')
f_result = open("d:\9\some1.txt", "w")
f_matching = open("d:\9\match1.txt", "r") #файл с сопоставлением словарей
dic={} #словарь
#Прочитаем файл сопоставлений и создадим словарь
for line in f_matching:
ls=line.split("^")
if len(ls)>2:
c=ls[0]
dic=ls[2]
#прочитаем все строки зашифрованного файла и применим к ним предполгаемый ключ
for line in f_text:
i=0
str_len=len(line)
new_str=""
while i<str_len:
c=line[i]
j=0
if c!="\n":
c_dist=dic
new_str=new_str+c_dist
i=i+1
f_result.write(new_str)
f_result.close()
С основными командами, которые используются для работы со словарем и с текстовыми файлами, вы ознакомились на прошлом уроке, так что, думаю, никаких дополнительных комментариев данный код не требует. Просто берем словарь, редактируем его в соответствии с нашими гипотезами, запускаем прогу и смотрим, что получается:
Пример, изображенный на данном скриншоте, получен путем расшифровки шрифта с использованием модифицированного словаря. Как видим, текст стал еще более осмысленный, чем на прошлом уроке. При желании мы можем сделать еще ряд предположений, например, набор букв «Тсследование» означает «Исследование» и поменять в словаре местами буквы «Т» и «И»:
Очевидно, что в тексте «?аучноАисследователыский» зашифрованы слова «Научно-исследовательский», таким образом, мы меняем местами «?» и «Н», а также «А» и «-«, ну и «ы» с «ь».
Смотрим, что получилось:
Как видим, с каждой заменой текст становиться все ближе и ближе к оригиналу. Но это долгий и кропотливый процесс. А тут нам еще и повезло — мы сразу же нашли пробе. А могли бы и не найти, тогда бы мы не смогли видеть в прдобработанном тексте слова, а видели бы какую-то белиберду. Возникает вопрос: «Нельзя ли его как-то сей процесс автоматизировать?». По идее, это уже задачи из области искусственного интеллекта, но мы, все же, попытаемся ее решить.
Итак, как искать слова, похожие на заданные слова? В данном случае рулит мера близости. Мы сравниваем кусок текста с определённым словом и считаем, сколько букв различаться. Самый простой способ. Но вопрос: а какие слова искать? На этот вопрос даст ответ частотный анализ текста, но теперь уже не символьный, а словесный. В первую очередь ищем в нашем зашифрованном тексте слова, которые часто встречаются. Для выполнения этой операции пишем вот такой несложный код на Python:
f_templ = open('d:\9\шаблон.txt', 'r')
f_result = open("d:\9\words.txt", "w")
dic={} #словарь
#Прочитаем файл шаблона и создадим частотный словарь
for line in f_templ:
ls=line.split(" ") #получили список слов
for word in ls:
if len(word)<2:
break
c=word[len(word)-1]
if c=="." or c=="," or c=="!" or c=="?" or c==":" or c=="-":
print(word)
word=word[0:len(word)-1]
print(word)
if dic.get(word)==None:
dic[word]=1
else:
dic[word]=dic[word]+1
#превратим словарь шаблона в список и отсортируем его
#тип полученного списка - список кортежей (тьюплов)
list_templ=list(dic.items())
list_templ.sort(key=lambda item: item[1], reverse=True)
#выгрузим словарь в файл
len_dic=len(list_templ)
i=0
while i<len_dic:
f_result.write(str(list_templ[i][0])+";"+str(list_templ[i][1])+"\n")
i=i+1
f_result.close()
Что в итоге получаем? Вот такой вот выходной файл:
Как оказалось, наиболее часто встречающиеся слова состоят всего из двух букв! Но нам это явное не надо, для эффективного поиска слова должны быть подлиннее. Поэтому, в коде вместо
if len(word)<2:
ставим:
if len(word)<3:
И получаем на выходе:
Это уже лучше. Теперь можно попробовать осуществить поиск по словам. Как это сделать? Для начала нам надо написать функцию, которая бы сопоставляла два слова одинаковой длины и выводила метрику их различия. Но что взять в качестве метрики? Можно количество букв, на которое различаются слова. Но еще лучше учесть, насколько сильно отличаются сами буквы. Для этого мы будем рассчитывать, насколько далеко они находятся друг от друга в словаре. Для удобства словарь лучше всего конвертировать в список и осуществлять потом поиск буквы в этом списке, находя его позицию:
f_matching = open("d:\9\match1.txt", "r") #файл с сопоставлением словарей
dic={} #словарь
#Прочитаем файл сопоставлений и создадим словарь
for line in f_matching:
ls=line.split("^")
if len(ls)>2:
c=ls[0]
dic=ls[2]
ls=list(dic.items())
Для осуществления поиска напишем вот такую функцию:
def search_simbol(s):
i=0
while i<len(ls):
if ls[i][0]==s:
return i
i=i+1
return -1
Ну, и, собственно, сравнение слов:
def matching_word(w1,w2):
i=0
res=0
while i<len(w1):
dif=0
if w1[i]!=w2[i]:
ind1=search_simbol(w1[i])
ind2=search_simbol(w2[i])
if ind1==-1 or ind2==-1:
dif=len(ls)+1
else:
dif=abs(ind1-ind2)
res=res+dif
i=i+1
return res
Ну, и, собственно, веся программа с тестовым примером:
f_matching = open("d:\9\match1.txt", "r") #файл с сопоставлением словарей
dic={} #словарь
#Прочитаем файл сопоставлений и создадим словарь
for line in f_matching:
ls=line.split("^")
if len(ls)>2:
c=ls[0]
dic=ls[2]
ls=list(dic.items())
def search_simbol(s):
i=0
while i<len(ls):
if ls[i][0]==s:
return i
i=i+1
return -1
def matching_word(w1,w2):
i=0
res=0
while i<len(w1):
dif=0
if w1[i]!=w2[i]:
ind1=search_simbol(w1[i])
ind2=search_simbol(w2[i])
if ind1==-1 or ind2==-1:
dif=len(ls)+1
else:
dif=abs(ind1-ind2)
res=res+dif
i=i+1
return res
print(matching_word("мроба","проба"))
print(matching_word("дроба","проба"))
print(matching_word("кроба","проба"))
print(matching_word("цукеп","проба"))
Который выдал следующее:
56
73
51
242
На этом пока все, но продолжение следует.
Comments
So empty here ... leave a comment!