Программирую на питоне атаку Касиски, для взлома шифра Виженера. Есть пару вопросов: 1) Мне нужно записать в список позиции найденных блоков, и подсчитать для них НОД(наибольший общий делитель). Затем записать в словарь полученную пару dict_NOD=подсчитанный_НОД для данного “шаблона”, при условии конечно, что таких в строке хотя бы 2 (т.е. сам шаблон+одно совпадение еще). Быть может кто подскажет, как мне это реализовать? Желательно в виде кода 2) Реализация поиска в строке всех подстрок написана верно с моей стороны? 3) Проблема с реализацией НОД для N чисел. Надо попарно брать со списка элементы? Или как-то делать по-другому? Примеры шифра: 1) AXIJZYBISCQMHSJHWSXLIEKTTRPSLTUHENTNJZNXBLSGGZWWVLWIGGGGZHLHNSIHXYZTPS 2) VHVSSPQUCEMRVBVBBBVHVSURQGIBDUGRNICJQUCERVUAXSSR Довел программу до следующего вида: | Код |
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
Реализация атаки Касиского для взлома шифра Виженера
Возвращает наиболее вероятную длину ключа из всех возможных
"""
alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
englishProb = {
'A': 0.08167,
'B': 0.01492,
'C': 0.02782,
'D': 0.04253,
'E': 0.12702,
'F': 0.02228,
'G': 0.02015,
'H': 0.06094,
'I': 0.06966,
'J': 0.00153,
'K': 0.00772,
'L': 0.04025,
'M': 0.02406,
'N': 0.06749,
'O': 0.07507,
'P': 0.01929,
'Q': 0.00095,
'R': 0.05987,
'S': 0.06327,
'T': 0.09056,
'U': 0.02758,
'V': 0.00978,
'W': 0.02360,
'X': 0.00150,
'Y': 0.01974,
'Z': 0.00074
}
def NOD(a,b):
"""
Нахождение НОДа
"""
while b!=0:
a, b = b, a%b
return a
def findsubs(text, len_block):
"""
Входные параметры:
text - строка с зашифрованным текстом
len_block - длина блока в буквах
Совершает:
- Поиск всех повторяющихся блоков в строке text длиной len_block
- Запись этих блоков в "базу" и подсчета для него НОД
"""
dict_NOD={} # словарь вида "Блок=НОД"
for i in range(len(text)-len_block):
lst_NOD=[] # список, хранящий вхождения блоков
NODS=[]
target=text[i:i+len_block]
found=text[i+len_block:].find(target)
if found!=-1:
f=found+i+len_block
# проверка для блоков, которые нашли, т.к. большие включают в себя меньшие
if i>0 and text[i-1:i+len_block] == text[f-1:f+len_block]:
continue
if i+len_block<len(text) and text[i:i+len_block+1] == text[f:f+len_block+1]:
continue
print ("Блок '%s' на расстоянии %d элементов" % (target, found))
lst_NOD.append(found)
# НОД для блока
nd=0;
while len(lst_NOD)>=1:
nd=NOD(lst_NOD[0],lst_NOD[1]))
lst_NOD[0:1]=[]
lst_NOD.append(nd)
print("Блок '%s' NOD = %d" % (target,nd))
# возвращаем словарь с именем блока и НОД для него
return dict_NOD
def startAnalysis(text):
"""
Входные параметры:
text - строка с зашифрованным текстом
Совершает:
- Удаление символов, не входящих в алфавит шифра
- Вызов функции для поиска в строке подстроки и их добавление в словарь вида D[блок]=НОД_для_блока
- Поиск НОД для всех блоков
"""
crText=""
# корректировка строки
for symbol in text.replace(" ",""):
symbol=symbol.upper() # сделаем символ прописным
# если символ входит в состав алфавита
if symbol in alphabet:
# то добавим его в "шифровку"
crText+=symbol
dict_={}
# поиск блоков в строке
for len_block in range(int(len(text)/2),2,-1):
result=findsubs(crText,len_block)
# если словарь не пустой, то проверим содержимое
if(len(result)!=0):
# просмотр базы, полученной из функции findBlock
keys=dict_.keys();
for key in keys:
# проверка на вхождение блока, т.е. есть ли он в базе?
if key in dict_: pass
# если нет, то добавить
else: dict_[key]=resut[key]
if __name__ == "__main__":
# ввод текста
crText=input("")
# анализ текста
startAnalysis(crText)
|
|
Атака Касиски, Проблема кодирования алгоритма 
Загрузка ...
