На прошлом уроке мы начали писать программу взлома шифров. Напомню краткое содержание: мы написали программу предобработки, которая зашифрованный текст превратила в нечто более осмысленное, но все еще зашифрованное. По крайней мере, теперь мы можем извлекать из этого предобработанного текста информацию: в частности, видеть наборы букв похожие на известные нам слова и выдвигать предположения о том, что нам следует изменить в словаре.

Теперь мы напишем программу, которая, используя модифицированный выгруженный словарь, сделает расшифровку текста:

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

На этом пока все, но продолжение следует.

Продолжение.