Индекс совпадений

Индекс совпадений — это статистическая мера, используемая в криптографии и лингвистике для оценки вероятности того, что две случайно выбранные буквы из заданного текста окажутся одинаковыми. Индекс совпадений (обозначается IC, от англ. Index of Coincidence) позволяет характеризовать распределение символов в тексте и, в частности, отличать тексты, зашифрованные простыми шифрами подстановки, от случайных последовательностей или текстов на естественных языках. Величина индекса зависит от частоты встречаемости символов в алфавите и длины текста.

История и происхождение

Понятие индекса совпадений было впервые предложено американским криптографом и математиком Уильямом Фридманом в 1920-х годах. Фридман разработал этот показатель для анализа шифротекстов, полученных с помощью шифра Виженера, который в то время считался одним из самых стойких. Идея заключалась в том, чтобы статистически отличить зашифрованный текст, полученный с использованием моноалфавитной подстановки (где частоты букв сохраняются), от текста, зашифрованного многоалфавитным шифром (где распределение символов становится более равномерным). Индекс совпадений стал одним из ключевых инструментов для криптоанализа, позволяя не только распознавать тип шифра, но и определять длину ключа в шифрах типа Виженера.

Определение и математическая формула

Индекс совпадений для текста длины \( N \), состоящего из символов алфавита размером \( n \), вычисляется по формуле:

\[ IC = \frac{\sum_{i=1}^{n} f_i (f_i - 1)}{N (N - 1)} \]

где:

• \( N \) — общее количество символов в тексте,
• \( n \) — размер алфавита (например, 33 для русского, 26 для английского),
• \( f_i \) — частота (количество вхождений) i-го символа алфавита в тексте.

Значение IC лежит в интервале от 0 до 1. Чем выше индекс, тем более неравномерно распределены символы в тексте.

Значения для различных типов текстов

Индекс совпадений принимает характерные значения для разных видов данных:

• Случайный текст (равномерное распределение): Если все символы алфавита встречаются с одинаковой вероятностью, то \( f_i \approx N/n \), и IC стремится к \( 1/n \). Для латинского алфавита (26 букв) это примерно 0,0385, для русского (33 буквы) — около 0,0303.
• Естественный язык: Для текстов на естественном языке, где частоты букв сильно различаются (например, в русском языке буква «о» встречается значительно чаще, чем «ф»), IC значительно выше. Для русского языка типичное значение IC составляет около 0,055–0,060. Для английского языка — около 0,065–0,067.
• Зашифрованный текст (моноалфавитная подстановка): При шифровании методом простой замены (каждая буква заменяется на другую по фиксированному правилу) частотное распределение символов не меняется, поэтому IC зашифрованного текста будет таким же, как у исходного открытого текста на естественном языке.
• Зашифрованный текст (многоалфавитная подстановка): При использовании шифра Виженера или других многоалфавитных систем распределение символов в шифротексте становится более равномерным, и его IC приближается к значению \( 1/n \), то есть к случайному.

Применение в криптоанализе

Индекс совпадений является фундаментальным инструментом для взлома классических шифров. Его основные применения:

Определение типа шифра

Сравнивая IC шифротекста с теоретическими значениями для случайного текста и естественного языка, криптоаналитик может сделать вывод о том, является ли шифр моноалфавитным (IC близок к языковому) или многоалфавитным (IC близок к случайному).

Определение длины ключа в шифре Виженера

Это одно из самых известных применений. Для шифра Виженера, если известна длина ключа \( k \), то шифротекст можно разбить на \( k \) столбцов, каждый из которых зашифрован одной и той же буквой ключа (то есть моноалфавитной подстановкой). Для каждого столбца IC будет высоким (близким к языковому). Если же длина ключа выбрана неверно, то столбцы будут содержать символы, зашифрованные разными буквами, и их IC будет низким. Таким образом, перебирая возможные длины ключа и вычисляя средний IC по столбцам, можно найти истинную длину: она будет соответствовать максимальному значению IC.

Тест на случайность последовательности

В криптографии IC используется для проверки качества генераторов псевдослучайных чисел. Если выходная последовательность генератора имеет IC, близкий к \( 1/n \), это свидетельствует о хорошей равномерности распределения.

Применение в лингвистике

Помимо криптографии, индекс совпадений применяется в лингвистике для:

• Анализа авторства текста: Разные авторы могут иметь характерные особенности частотного распределения букв, что отражается в IC.
• Изучения языковых особенностей: Сравнение IC для разных языков позволяет оценить степень равномерности их алфавитов.
• Определения языка текста: Зная типичные IC для различных языков, можно с определённой вероятностью идентифицировать язык, на котором написан неизвестный текст.

Пример расчёта

Рассмотрим короткий текст на русском языке: «МАМА МЫЛА РАМУ». Удалим пробелы: «МАМАМЫЛАРАМУ». Длина текста \( N = 11 \). Алфавит: А, М, Р, Ы, Л, У. Частоты: А — 4, М — 3, Р — 1, Ы — 1, Л — 1, У — 1. Подставляем в формулу: \[ IC = \frac{4\cdot3 + 3\cdot2 + 1\cdot0 + 1\cdot0 + 1\cdot0 + 1\cdot0}{11 \cdot 10} = \frac{12 + 6}{110} = \frac{18}{110} \approx 0,1636 \] Это значение очень высокое, что характерно для короткого текста с повторяющимися буквами. Для длинных текстов на русском языке IC будет значительно ниже, но всё равно выше случайного значения.

Ограничения

Индекс совпадений не является универсальным инструментом. Его эффективность снижается при:

• Коротких текстах: Для текстов длиной менее 50–100 символов статистическая погрешность велика, и IC может сильно отклоняться от теоретического значения.
• Сжатых данных: Тексты, сжатые алгоритмами (например, ZIP), имеют практически равномерное распределение символов, и их IC близок к случайному, что делает невозможным определение языка.
• Современных шифрах: Для современных блочных и поточных шифров (AES, ChaCha20) IC шифротекста всегда равен \( 1/n \), так как их выход неотличим от случайного. Индекс совпадений не применим для их криптоанализа.

Источники

• Фридман, У. Ф. «Элементы криптоанализа». — 1920.
• Шнайер, Б. «Прикладная криптография». — 1996.
• Столлингс, В. «Криптография и сетевая безопасность». — 2017.
• Лингвистические исследования частотных распределений букв в русском и английском языках.