Python-сообщество

Relrin · Сен. 12, 2012 17:30:57

Пишу небольшую програмку, которая проводит атаку Касиски по зашифрованному сообщению методом Виженера. Возникло пару проблем при реализации findBlock:
1) не получается сделать, чтобы выводило найденный “шаблон”(если нашли еще подстроки) по одному разу, т.е. нашло еще одну подстроку такую же - вывело один раз
2) где лучше всего расположить обработку расстояний для данного шаблона, если найдено хотя бы 2 таких подстроки (т.е. шаблон+еще найдено хотя бы раз)? где и каким образом, т.к. шаблон все-таки меняется? после строки вот этой?

if i+len_block<len(text) and text[i:i+len_block+1] == text[f:f+len_block+1]:
                continue

3) Реализация поиска в строке всех подстрок написана верно с моей стороны?

Примеры шифра:
1) AXIJZYBISCQMHSJHWSXLIEKTTRPSLTUHENTNJZNXBLSGGZWWVLWIGGGGZHLHNSIHXYZTPS
2) VHVSSPQUCEMRVBVBBBVHVSURQGIBDUGRNICJQUCERVUAXSSR

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
    Реализация атаки Касиского для взлома шифра Виженера
    Возвращает наиболее вероятную длину ключа из всех возможных
"""
alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
def GetString(text,offset):
    """
        Обрезка строки, необходимой для поиска повторяющихся блоков
    """
    return text[offset:]
def findBlock(text,len_block,offset):
    """
        Входные параметры:
            text      - строка с зашифрованным текстом
            len_block - длина блока в буквах
            offset    - смещение
        Совершает:
        - Поиск всех повторяющихся блоков в строке text, длиной len_block
    """
    dict_NOD={} # словарь вида "Блок=НОД"
    lst_NOD=[]  # список, хранящий вхождения блоков
    # ищем в строке блоки одинакового вида
    for i in range(len(text)-len_block):
        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 ("%-10s %3d" % (target, found+len_block))
    # возвращаем словарь с именем блока и НОД для него
    return dict_NOD
def startAnalyze(text):
    """
        Входные параметры:
            text - строка с зашифрованным текстом
        Совершает:
        - Удаление символов, не входящих в алфавит шифра
        - Вызов функции для поиска в строке подстроки и их добавление
           в словарь вида D[блок]=НОД_для_блока
        - Поиск НОД для всех блоков
    """
    crText=""
    # корректировка строки
    for symbol in text:
        symbol=symbol.upper() # сделаем символ прописным
        # если символ входит в состав алфавита
        if symbol in alphabet:
            # то добавим его в "шифровку"
            crText+=symbol
    dict_={}
    # ищем в строке подстроку, поблочно (минимальная единица из 3 символов)
    for index in range(len(crText)-2):
        maxBlockCnt=int((len(crText)/2)-index) # максимальная длина блока для данной строки
        sliced=GetString(crText,index)         # "обрезка" строки
        # совершаем поиск блока
        for len_block in range(3,maxBlockCnt,1):
            result=findBlock(sliced,len_block,index)
            # если словарь не пустой, то проверим содержимое
            if(len(result)!=0):
                keys=dict_.keys();
                for key in keys:
                    # проверка на вхождение блока, т.е. есть ли он в базе?
                    if key in dict_: pass
                    # если нет, то добавить
                    else: dict_[key]=resut[key]
    # вычисляем НОД для всех блоков и определяем возможную длину ключа
    for key in dict_:
        print(key,"=",dict_[key])
    
if __name__ == '__main__':
    # вводим зашифрованную строку
    crText= input("Text: ")
    # анализ строки
    startAnalyze(crText)

Отредактировано Relrin (Сен. 12, 2012 17:35:33)

Relrin · Сен. 12, 2012 18:32:44

Первый пункт решил, остальные еще открыты.
Второй пункт лучше опишу так: Мне нужно записать в список позиции найденных блоков, и подсчитать для них НОД(наибольший общий делитель). Затем записать в словарь полученную пару dict_NOD=подсчитанный_НОД для данного “шаблона”, при условии конечно, что таких в строке хотя бы 2 (т.е. сам шаблон+одно совпадение еще). Быть может кто подскажет, как мне это реализовать? Желательно в виде кода

Довел программу до следующего вида:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
    Реализация атаки Касиского для взлома шифра Виженера
    Возвращает наиболее вероятную длину ключа из всех возможных
"""
alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
def findsubs(text, len_block):
    """
        Входные параметры:
            text      - строка с зашифрованным текстом
            len_block - длина блока в буквах
        Совершает:
            - Поиск всех повторяющихся блоков в строке text длиной len_block
            - Запись этих блоков в "базу" и подсчета для него НОД
    """
    dict_NOD={} # словарь вида "Блок=НОД"
    lst_NOD=[]  # список, хранящий вхождения блоков
    for i in range(len(text)-len_block):
        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+len_block))
    # возвращаем словарь с именем блока и НОД для него
    return dict_NOD
def startAnalysis(text):
    """
        Входные параметры:
            text - строка с зашифрованным текстом
        Совершает:
            - Удаление символов, не входящих в алфавит шифра
            - Вызов функции для поиска в строке подстроки и их добавление в словарь вида D[блок]=НОД_для_блока
            - Поиск НОД для всех блоков
    """
    crText=""
    # корректировка строки
    for symbol in text:
        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)

Python-сообщество

Уведомления

#1 Сен. 12, 2012 17:30:57

Атака Касиски

#2 Сен. 12, 2012 18:32:44

Атака Касиски

Board footer