Почему работает автокорреляционный метод в криптоанализе
Метод, предложенный Уильямом Фридманом, известен и пременяется для криптоанализа шифра Виженера уже более ста лет.
Но по какой-то причине сложно найти простое обьяснение работы этого метода с парой примеров "на пальцах".
Кстати, надо сказать, что описанный выше автокорреляционный метод применим в целом к полиалфовитным шифрам, а не только к шифру Виженера.
Более того, особый интерес с этой точки зрения представляет шифрование операцией XOR с ключом ограниченного размера (циклически повторяющемся для соответствия длине открытого текста).
Итак, почему же работает метод Фридмана?
Алгоритм нахождения длины ключа шифрования этим способом заключается в поочередном сравнении зашифрованной строки со строками, полученными из нее же сдвигом на 1, 2, 3...n символов вправо. Длина ключа будет равна сдвигу, на котором индекс совпадений (обратнопропорциональный расстоянию Хэмминга) будет близок к известному среднему его значению для используемого языка.
Это объясняется парой моментов:
1. Если шифротекст разделить на блоки, длина которых будет кратна длине ключа шифрования, и сравнить их попарно между собой, то количество совпадающих между ними символов будет таким же, как если бы сравнивались те же самые блоки, но из открытого текста.
Потому что символы, находящиеся на одной и той же позиции в этих блоках шифруются одним и тем же символом ключа шифрования.
Сравнение блоков шифротекста любой другой длины ближе к сравнению двух случайных наборов символов.
2. При сравнении двух осмысленных строк (а в нашем случае строки и ее копии, сдвинутой на несколько символов) количество совпадающих символов будет больше, чем при сравнении двух строк, состоящих из просто случайных символов.
Так происходит из-за того, что некоторые буквы встречаются в словах чаще, чем другие. Этот перевес в сторону части алфавита и приводит к аномалиям при сравнении реальных тестов.
Как раз это мне не кажется интуитивно понятным, но это очень легко объяснить.
Для простоты представим, что существует язык, алфавит которого состоит всего из двух букв: А и Б.
Случайно сгенерированная строка в этом языке будет содержать примерно одинаковое количество обеих букв алфавита.
Тогда вероятность того, что при сравнении ее с другой случайной строкой, два символа на какой-то определенной позиции будут совпадать, составляет интуитивно понятные 50%.
Теперь представим, что в "реальных" текстах этого выдуманного языка буква А встречается в 9 раз чаще, чем буква Б.
Так же интуитивно понятно, что две строки, соответствующие такой пропорции (почти полностью состоящие из одной буквы) будут иметь в среднем больше совпадающих символов, чем две случайные строки.
Если же взять больший по размеру алфавит, но представить, что он используется в языке, слова которого все так же на 90% состоят из одной буквы, то разница в индексе совпадений между реальными текстами и случайными строками будет еще больше.
В существующих языках из-за меньшего разброса частот появления разных букв в словах, конечно, такие корреляции будут намного реже. Но количество совпадений между осмысленными текстами и случайными строками все равно будет отличаться.
XOR вместо таблицы Виженера
Автокорреляционный метод, очевидно, одинаково применим не только к шифру Виженера, но и к другим полиалфавитным шифрам.
Но если зашифрованное сообщение получено операцией XOR между символами ключа и исходного текста, то в некоторых случаях для поиска длины ключа эффективнее будет использовать бинарное представление шифротекста вместо явного посимвольного сравнения.
Этому способствует совокупность 3 фактов:
1. Поиск несовпадающих битов можно свести так же к операции исключающего ИЛИ между двумя сравниваемыми подстроками и последующим подсчетом разрядов результата, равных единице.
2. Если над зашифрованной строкой и ее копией, циклически сдвинутой на N символов, выполнить операцию побитового исключающего "ИЛИ", то количество переменных, влияющих на результат будет зависеть от того, кратно ли N длине ключа шифрования.
И вот почему:
Так как каждый бит шифротекста в процессе шифрования и сам был получен XOR-ом над определенными разрядами открытого текста и ключа, в операции фактически участвуют четыре значения: два бита открытого текста (из оригинальной и сдвинутой строки: P1, P2) и два соответствующих им бита ключа (K1, K2):
(i-ый бит символа шифротекста) XOR ((i+N)-ый бит символа шифротекста) = (P1 XOR K1) XOR (P2 XOR K2)
Это в общем случае. Но если N кратен длине ключа шифрования, то символы из двух рассматриваемых строк были получены шифрованием одним и тем же символом ключа (K).
А это значит, что в силу самообратимости и идемпотентности исключающего "ИЛИ", ключ в этом случае вообще перестает влиять на конечный результат:
(P1 XOR K) XOR (P2 XOR K) = (P1 XOR P2) XOR (K XOR K) = (P1 XOR P2)
Поэтому для сдвигов шифротекста, кратных длине ключа, каждый разряд результата будет зависеть от двух битов, а для не кратных - от четырех.
3. В некоторых случаях вероятность получить 1 в результате XOR-a с 4-мя операндами больше, чем с 2-мя. Это проще объяснить на монетке.
Допустим, есть монета, которая чаще падает орлом вверх. Если подбросить такую монету четное количество раз, то, вероятнее всего, "орел" выпадет тоже в четном количестве случаев.
Все потому, что вообще наиболее ожидаемый результат нескольких бросков такой монетки - "все орлы".
И именно из-за этой комбинации происходит "перекос" вероятности в сторону четного количества выпавших орлов при четном количестве бросков. Но с увеличением количества бросков падает вероятность того, что не выпадет ни одной решки.
То есть выкинуть 4-ех орлов подряд сложнее, чем 2-ух. И, следовательно, вероятность выпадения нечетного количества орлов в случае 4-ех бросков хоть и меньше 50%, но больше, чем в случае 2-ух.
| Комбинация 2 битов | Частота (при вероятности единицы 90%) | Частота (при вероятности единицы 60%) | |--------------------------------------------------------|---------------------------------------|---------------------------------------| | 00 | 0.01 | 0.16 | | 11 | 0.81 | 0.36 | | Любая комбинация с четным количеством нулей и единиц | 0.82 | 0.52 | | 01 | 0.09 | 0.24 | | 10 | 0.09 | 0.24 | | Любая комбинация с нечетным количеством нулей и единиц | 0.18 | 0.48 |
| Комбинация 4 битов | Частота (при вероятности единицы 90%) | Частота (при вероятности единицы 60%) | |--------------------------------------------------------|---------------------------------------|---------------------------------------| | 0000 | 0.0001 | 0.0256 | | 0011 | 0.0081 | 0.0576 | | 0101 | 0.0081 | 0.0576 | | 0110 | 0.0081 | 0.0576 | | 1001 | 0.0081 | 0.0576 | | 1010 | 0.0081 | 0.0576 | | 1100 | 0.0081 | 0.0576 | | 1111 | 0.6561 | 0.1296 | | Любая комбинация с четным количеством нулей и единиц | 0.7048 | 0.5008 | | 0001 | 0.0009 | 0.0384 | | 0010 | 0.0009 | 0.0384 | | 0100 | 0.0009 | 0.0384 | | 1000 | 0.0009 | 0.0384 | | 0111 | 0.0729 | 0.0864 | | 1011 | 0.0729 | 0.0864 | | 1101 | 0.0729 | 0.0864 | | 1110 | 0.0729 | 0.0864 | | Любая комбинация с нечетным количеством нулей и единиц | 0.2952 | 0.4992 |
Таким образом эффективность этого способа зависит от бинарного представления символов алфавита, используемого в исходном открытом тексте. А точнее от наличия "перекоса" в распределении вероятностей появления 0 или 1 на определенной позиции в двоичном представлении символов алфавита.
Для примера рассмотрим представление букв латинского алфавита в ASCII-кодировке:
| Символ | Двоичное представление | Символ | Двоичное представление | |--------|------------------------|--------|------------------------| | A | 01000001 | a | 01100001 | | B | 01000010 | b | 01100010 | | C | 01000011 | c | 01100011 | | D | 01000100 | d | 01100100 | | E | 01000101 | e | 01100101 | | F | 01000110 | f | 01100110 | | G | 01000111 | g | 01100111 | | H | 01001000 | h | 01101000 | | I | 01001001 | i | 01101001 | | J | 01001010 | j | 01101010 | | K | 01001011 | k | 01101011 | | L | 01001100 | l | 01101100 | | M | 01001101 | m | 01101101 | | N | 01001110 | n | 01101110 | | O | 01001111 | o | 01101111 | | P | 01010000 | p | 01110000 | | Q | 01010001 | q | 01110001 | | R | 01010010 | r | 01110010 | | S | 01010011 | s | 01110011 | | T | 01010100 | t | 01110100 | | U | 01010101 | u | 01110101 | | V | 01010110 | v | 01110110 | | W | 01010111 | w | 01110111 | | X | 01011000 | x | 01111000 | | Y | 01011001 | y | 01111001 | | Z | 01011010 | z | 01111010 |
Видно, что два старших бита одинаковы для всех букв в обоих регистрах и результат XOR-a по ним всегда будет равен 0, поэтому их можно сразу выбросить из рассмотрения.
Для всех остальных разрядов вероятности появления единицы/нуля будут примерно такими:
| Разряд | 5 | 4 | 3 | 2 | 1 | 0 | |---------------|-----|------|------|------|-----|-----| | Вероятность 1 | 0.5 | 0.42 | 0.42 | 0.46 | 0.5 | 0.5 | | Вероятность 0 | 0.5 | 0.58 | 0.58 | 0.54 | 0.5 | 0.5 |
Вероятность появления единицы в 2, 3 и 4 разрядах каждого символа ниже, чем вероятность появления нуля. А это как раз тот случай, который попадает по условие 3-го пункта выше.
Так что даже если исходный текст до шифрования представлял собой строку из случайных букв в ASCII-кодировке, все равно есть вероятность найти длину ключа через работу с битовым представлением шифротекста.