1

Мне нужно написать программу для взлома шифра Виженера. Собственного говоря, я её написал, но столкнулся с проблемой, которая связана со поиска ключа. Получив возможный размер ключа, я основываясь на частоте символов в тексте предполагаю, из каких букв может состоять это слово. А чтобы вручную не перебирать все возможные варианты слова, я пытаюсь найти данное слово в словаре. Для сокращения времени поиска слова в словаре использую программу grep, так как мой поиск будет куда хуже. Но несмотря ни на что, программа ищет слово крайне долго. Допусти слово "кот" она искала минут 15.

from collections import Counter
import itertools
import subprocess
import sys

ru_alphabet = ('а', 'б', 'в', 'г', 'д', 'е', 'ж', 'з', 'и', 'й', 'к', 'л', 'м', 'н', 'о', 'п', 'р', 'с', 'т', 'у', 'ф',
               'х', 'ц', 'ч', 'ш', 'щ', 'ъ', 'ы', 'ь', 'э', 'ю', 'я', '_')


def test_kasiski(text: str) -> list: # тут получаю длинну слова
    size_select_block = 3
    counter_size = []
    select_str_block = []
    for index_start_letter in range(len(text) - size_select_block):
        select_str = text[index_start_letter: index_start_letter + size_select_block]
        if select_str in select_str_block:
            continue
        select_str_block.append(select_str)
        index_start = index_start_letter
        index_end = index_start_letter
        counter = 0
        for index_letter in range(index_start_letter + size_select_block, len(text) - size_select_block):
            if select_str == text[index_letter: index_letter + size_select_block]:
                index_end = index_letter
                counter += 1

        if index_start == index_end:
            continue
        else:
            counter_size.append((index_end - index_start, counter, select_str_block[-1]))

    counter_size = sorted(counter_size, key=lambda x: x[1], reverse=True)
    counter_size = [item for item in counter_size if item[1] != 0]

    return counter_size


def split_text_parts(text: str, size_key: int) -> list: # использую для записи букв в блоки
    part = [[] for _ in range(size_key)]
    for index_letter in range(0, len(text), size_key):
        for index in range(size_key):
            part[index].append(text[index_letter + index:index_letter + index + 1])
    return part


def gen_code(text, lang) -> list: # получаю список индексов букв из словаря
    num_key = []
    for letter in list(text):
        num_key.append(lang.index(letter))
    return num_key


def devi(text, key, lang=ru_alphabet) -> str:
    code_key = gen_code(key, lang)
    text_key = gen_code(text, lang)

    code_text_key = []
    index_letter = 0
    mod = len(lang)
    while index_letter < len(text_key):
        for iter in range(len(code_key)):
            index_code_letter = (text_key[index_letter] - code_key[iter]) % mod
            code_text_key.append(lang[index_code_letter])
            index_letter += 1
            if index_letter >= len(text_key):
                break
    str_text = "".join(code_text_key)
    return str_text


def get_text(text: str, block: list):
    for select_key in range(len(block[0])):
        key = [elem[select_key][0] for elem in block]
        key = "".join(key)
        text = text.replace("\n", "")
        print(devi(text, key))
        select = input("\n>")
        if select == '1':
            return "OK"


# [[('г', 25), ('д', 11), ('й', 10)], [('н', 26), ('ь', 15), ('ъ', 8)], [('я', 16), ('р', 15), ('щ', 11)], [('й', 22), ('п', 12), ('к', 11)], [('_', 17), ('е', 10), ('в', 8)]]
def all_combinations(list_combinations, size_key):
    all_combinations = ""
    for elem in list_combinations:
        all_combinations = all_combinations + "".join([l[0] for l in elem])

    list_comb = list(itertools.combinations(all_combinations, size_key))
    str_comb = ["".join(elem) for elem in list_comb]
    return str_comb


def h_vi(text: str, list_counter_size: list):
    for counter_size in list_counter_size:
        for size_key in range(1, counter_size[0]):
            if counter_size[0] % size_key != 0:
                continue

            size_key = 3 # можно удалить(использую, чтобы поиск начинался сразу с нужной длинны)

            text_parts = split_text_parts(text, size_key) # делю текст на части
            block = []
            for part in text_parts:
                count_part = Counter(part)
                block.append(count_part.most_common(10)) # беру 10 самых часто встечаемых буквы в блоке

            text = text.replace("\n", "")
            # тут наинается перебор
            all_combinators = all_combinations(block, size_key) # все возможные комбинации букв
            if sys.platform.startswith('linux'):
                for str_ in all_combinators:
                    find_word = subprocess.run(['grep', "-w", f'{str_}', 'russian.txt'],
                                               stdout=subprocess.PIPE, text=True).stdout.split('\n') # перебираю все возможные комбинации и ищу совпадения в словаре
                    if len(find_word) == 1: # если ничег не нашо, то беру следующую комбинацию
                        continue 
                    # тут заканчивается
                    if str_ in find_word: # если есть совпадение, то декодиру, если ответ не == 1 продолжаю
                        print("#\n", str_)
                        print(devi(text, str_))
                        select = input(">")
                        if select == '1':
                            return "OK"
            else:  # тут происходит чистый перебор(но на него безразницы)
                for i in range(len(all_combinators)):
                    if size_key == 1:
                        for elem in all_combinators:
                            if elem == " " or elem == "_":
                                continue
                            print(devi(text, elem))
                            select = input("\n>")
                            if select == '1':
                                return "OK"
                        break
                    with open("russian.txt", "r") as word:
                        while True:
                            select_word = word.readline().replace("\n", "")
                            if not select_word:
                                break
                            if all_combinators[i] == select_word:
                                c = all_combinators[i]
                                g = 0
                                print(devi(text, c))
                                select = input("\n>")
                                if select == '1':
                                    return "OK"

    return None

# 'мой_дядя_самых_честных_правил_когда_не_в_шутку_занемог_он_уважать_себя_заставил_и_лучше_выдумать_не_мог_его_пример_другим_наука_но_боже_мой_какая_скука_с_больным_сидеть_и_день_и_ночь_не_отходя_ни_шагу_прочь_какое_низкое_коварство_полуживого_забавлять_ему_подушки_поправлять_печально_подносить_лекарство_вздыхать_и_думать_про_себя_когда_же_черт_возьмет_тебя_так_думал_молодой_повеса_летя_в_пыли_на_почтовых_всевышней_волею_зевеса_наследник_всех_своих_родных_друзья_людмилы_и_руслана_с_героем_моего_романа_без_предисловий_сей_же_час_позвольте_познакомить_вас_онегин_добрый_мой_приятель_родился_на_брегах_невы_где_может_быть_родились_вы'
# вгогждргумьчгыйзтгкйгетпйгыцтгвгртзчгйэйгходлдц_гцйуйф_гвглсдбгжгждьйнгжтпйгрйсвгуфйлфйс_йргсдодлдц_гстгжягогртйнгсйхыдхцстнгитпйгщтц_годупбгкдптхцмгщфдсвгжягсйгтхцджмцйгрйсвгхсдыдпдгвгртпыдц_гщтцйпдгутжйф_цйгртйзтгхцяидгжягсйгчлсдпмгегсмотзид

if __name__ == "__main__":
    text = "цьыйтромсыоюдвсаувьымянаъофтщсфьхоосчусмнйэ_ьэнщкычцьхйьяйафкфтьйсыууинщкягкръхнъйщдаечйрмоаюк_нйычйъ_ннчньсщюъцубйтбэсъцнякаькняшнушфчйъ_унькштинвфаькнвйп_хйядъсыццп_нйцсоуяенъйы_айсчусш_жштрйыъйетнасщю_айсфоьшусчцщфьчйш_мобы_фшнашщдрцфшс_йхтлофхмгенчцасщьцэеьтнашэбкрэи_нйэчаоэеы_йэ_оы_ыцгенэпштъягмьсмхцдвтьйстнцэътьйсщю_йячлмсфьхоосрусаубьнфшхнцугй_члмсьоьйтдцоэйъ_хьцшчсщьфпятйщчьмсмнадщъйытйэ_а__мижйрвпрмбычунфшщчзнщпрчыосчовхуцчцьйрвпвсыр_твсъьцчижйтбэхнинэзтютщмйцсъавхоякнвйсчъьчцнюшухшнбшътчослущйэбптъыщ_мцыйячуншпникясщьщмьэе_чйэ_сытфьют_нйртын_чухтысоьуъиыйъ_унаъцрьуэенбштъхярйытйпбпстяняпрмйсцпнюшфчьнуд_нйю_оцэтянйрмйцэтнухцвьоэтнюшчсацгк_чхйсьоюйычфьхооснаэищстнрйы_йрбптччнвпрчънцхмсцуяи"
# print(devi(text, 'кот')) # у text ключ - "кот"
    all = test_kasiski(text)  # тут не существенных проблем
    a = h_vi(text, all) # а вот тут проблемы со скоростью
    print(a)

Ума не приложy, как ускорить работу программы. Можете что-то посоветовать ? Проблемная часть отмечена (тут начинается перебор) - (тут заканчивается)

6
  • 3
    ай многа букаф.
    – entithat
    Commented 15 июн. 2021 в 18:15
  • Не знаю, как по другому объяснить.
    – murlock
    Commented 15 июн. 2021 в 18:20
  • А словарь большой? Просто запуск процесса - это довольно время затратная операция. Да ещё и grep какое-то время по файлу каждый раз бегает.
    – GrAnd
    Commented 15 июн. 2021 в 18:44
  • 1
    Если файл словаря большой для полной загрузки в память, но там просто заранее отсортированные слова, то можно применить быстрый бинарный поиск по файлу.
    – GrAnd
    Commented 15 июн. 2021 в 18:49
  • А нельзя ли хотя бы функции как-то понятно называть? h_vi - это вот что, например?
    – CrazyElf
    Commented 15 июн. 2021 в 19:10

1 ответ 1

3

Если предварительно загрузить файл со словами в память, то ищет мгновенно.

def h_vi(text: str, list_counter_size: list):
    with open("russian.txt", "r", encoding="utf-8") as f:
        words_rus = set(s.strip() for s in f.readlines())

    for counter_size in list_counter_size:
        for size_key in range(1, counter_size[0]):
            if counter_size[0] % size_key != 0:
                continue

            size_key = 3 # можно удалить(использую, чтобы поиск начинался сразу с нужной длинны)

            text_parts = split_text_parts(text, size_key) # делю текст на части
            block = []
            for part in text_parts:
                count_part = Counter(part)
                block.append(count_part.most_common(10)) # беру 10 самых часто встечаемых буквы в блоке

            text = text.replace("\n", "")
            # тут наинается перебор
            all_combinators = all_combinations(block, size_key) # все возможные комбинации букв

            for str_ in all_combinators:
                if str_ in words_rus: # если есть совпадение, то декодиру, если ответ не == 1 продолжаю
                    print("#\n", str_)
                    print(devi(text, str_))
                    select = input(">")
                    if select == '1':
                        return "OK"

Проверял под Windows, предварительно найдя какой-то файлик с русскими существительными в 34_000 строк (штук).

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.