я читаю Введение в современную криптографию, 3-е издание (Предварительный просмотр соответствующего раздела Google Книги, страницы 10-11) и изо всех сил пытаюсь понять описание метода атаки на одноалфавитный шифр замены.
Похоже, что это улучшенная версия подхода анализа частоты букв, устраняющая необходимость «проверки того, что имеет смысл» вручную. Некоторая предоставленная информация:
- Всем буквам английского языка присвоено значение 0-25
- Неизвестный ключ, используемый для кодирования открытого текста в зашифрованный текст, состоит из случайного отображения 1:1 букв из (1). например (а -> х, б -> г, с -> о, ...)
Авторы описывают этот подход следующим образом:
Теперь мы опишем атаку, которая не страдает этими недостатками [подхода ручного частотного анализа]. Как и прежде, свяжите буквы английского алфавита с $0, ..., 25$. Позволять $p_i$, с $0 <= р <= 1$, обозначают частоту $ с $ буква в обычном английском тексте (например, 0,082). ... [используя эти цифры] дает:
$(1)$ $\displaystyle \sum_{i=0}^{25} p_i^2 \приблизительно 0,065$
Примечание: Где $0.065$ является контекстуальным для корпуса данного английского текста (т.е. может варьироваться в зависимости от источника; например, слова словаря Вебстера).
Теперь предположим, что нам дан некоторый зашифрованный текст, и пусть $q_i$ обозначают частоту ябуква алфавита в зашифрованном тексте, деленная на длину зашифрованного текста. Если ключ к, тогда $p_i$ должно быть примерно равно $q_{я+к}$ для всех я поскольку ябуква сопоставляется с $\влево(я+к\вправо)-й$ письмо. (мы используем $я+к$ вместо более громоздкого $\влево[I+k \mod 26\вправо]$.) Таким образом, если мы вычислим
$(2)$ $I_j := \displaystyle \sum_{i=0}^{25} p_i \cdot q_{i+j}$
для каждого значения $j \in \left \{0, ..., 25\right\}$, то мы ожидаем найти это $I_k \приблизительно 0,065$ (куда к является фактическим ключом), тогда как $I_j$ за $j \neq k$ будет отличаться от 0,065. Это приводит к атаке с восстановлением ключа, которую легко автоматизировать: $I_j$ для всех $j$, и выведите значение $к$ для которого $I_k$ ближе всего к 0,065.
Мой вопрос относится к общему подходу второго суммирования $(2)$ -- Я не понимаю, в чем ценность $j$ для каждого члена суммирования. Является $j$ предназначено быть ятермин ключа $к$? Такой, что каждый член в $2$ будет рассчитан для каждого возможное значение $j$?
Я понимаю генерацию частоты, понимаю, что происходит в концепции $(1)$ и что найти ближайший $q_i$ к $p_i$ подойдет $p_i^2$ при этом фактический $k_i$ сведет к минимуму это, таким образом найдя наиболее подходящее отображение.
Однако похоже, что это всего лишь метод грубой силы, учитывая, как окончательный расчет сравнивается с первоначальным. $0.065$ значение, как если бы было принято во внимание правильное сопоставление для каждой буквы.
Я что-то пропустил? В противном случае я чувствую, что просто сортирую каждое частотное распределение по значению, предполагая наличие в зашифрованном тексте равного количеству букв в пространстве исходного сообщения (т. Е. Отсутствие возможных пробелов в распределении).
