Взаимный индекс совпадения

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

Я только что узнал, что индекс совпадения и индекс взаимного совпадения - это разные вещи. Учитывая моноалфавитный шифр, индекс совпадения всегда будет возвращать ~ 0,067 (для английского языка). Однако, судя по тому, что мне дали, это не так.

Мне нужна помощь в понимании того, как создать алгоритм для определения взаимного индекса совпадения с учетом формулы

Формула МПК

Учитывая, что введите здесь описание изображения где fi — это появление i-й буквы в алфавите, а N — длина текста и qi+k

Из того, что я понял (я ужасен в математике), мне нужно перебрать i от 0 до 25 и получить индекс максимального взаимного индекса совпадения среди 25, и это даст мне ключ для шифра. Для этого мне нужно умножить пи на qi+k. Однако, если pi примерно равно qi+k для всех i, не означает ли это, что pi? При этом разве уравнение не является суммой квадратов пи?


encryption algorithm math caesar-cipher
person Jon K    schedule 11.07.2020    source источник
comment
Я предполагаю, что p_i - это ожидаемая частота букв (данная частотным анализом английского текста). Я думаю, вы пропустили некоторые слова. Я предполагаю, что исходный текст говорит, что вы должны найти k (от 0 до 25) так, чтобы каждое p_i было примерно равно q_{i+k} для каждого i. Взаимный индекс совпадения — это одна из мер того, насколько близки два вектора (по сути, эквивалентно косинусному сходству), поэтому k с самым высоким значением MIC является хорошим кандидатом на роль исходного ключа.   -  person Paul Hankin    schedule 11.07.2020
comment
Да, я думаю, вы правы в том, что находите k (0-25) такое, что каждое p_i примерно равно q_{i+k} для каждого i, хотя в вопросе указаны только все i. Я не уверен, что упускаю из вопроса больше деталей (надеюсь, нет), но я немного застрял в том, как начать получать MIC для каждого k.   -  person Jon K    schedule 11.07.2020
comment
Какова ваша конкретная проблема? Вы вычислили 26 частот q[i]? У вас есть (я думаю, английские) частоты букв p [i]?   -  person Paul Hankin    schedule 11.07.2020
comment
В моем коде мне удалось получить частоты букв для всех символов для каждой клавиши от 0 до 25. Но я не уверен, как мне получить оттуда MIC. Я предположил, что p_i q_{i+k} означает (f_{i+k} / N) * (f_{i+k} /N) в сумме, но я понял, что это одно и то же (и это не дает мне закрыть MIC в любом случае), поэтому я, должно быть, ошибся, пытаясь создать формулу для расчета MIC для каждого k.   -  person Jon K    schedule 11.07.2020
comment
Хм, p[i] должен быть вектором, который выглядит примерно так [0,082, 0,014, 0,028, ...] (частоты букв для английского языка из en.wikipedia.org/wiki/). q[i] должен быть вектором, в котором хранится наблюдаемая частота появления каждой буквы в зашифрованном тексте, деленная на длину зашифрованного текстаt.   -  person Paul Hankin    schedule 11.07.2020
comment
MIC[k] равен sum(p[i] * q[(i+k)%26] for i in range(26)) в питоне.   -  person Paul Hankin    schedule 11.07.2020
comment
Приведенная формула верна, большое спасибо! @ПолХанкин   -  person Jon K    schedule 12.07.2020

Ответы (1)


arrow_upward
0
arrow_downward

Большое спасибо Полу Ханкину за разъяснения. p_i в этом случае на самом деле было не q_{i+k}, а скорее вероятностью появления каждой буквы в английском языке (которая фиксирована), а q_{i+k} относится к появлению каждой буквы, сдвинутой с помощью ключа в зашифрованном тексте.

Решение, предоставленное Полом, где MIC[k] равно sum(p[i] * q[(i+k)%26] для i в диапазоне (26)) верно — результат уравнения нужно разделить на N, чтобы получить взаимный индекс совпадения.

person Jon K    schedule 12.07.2020