В криптографии расстояние уникальности — это длина исходного зашифрованного текста , необходимая для взлома шифра путем уменьшения количества возможных поддельных ключей до нуля при атаке методом перебора . То есть после перебора всех возможных ключей должна быть только одна расшифровка, которая имеет смысл, т. е. ожидаемый объем зашифрованного текста, необходимый для полного определения ключа, при условии, что базовое сообщение имеет избыточность. [1]
Клод Шеннон определил расстояние единственности в своей статье 1949 года « Теория связи секретных систем ». [2]
Рассмотрим атаку на строку зашифрованного текста «WNAIW», зашифрованную с использованием шифра Виженера с пятибуквенным ключом. Возможно, эту строку можно расшифровать в любую другую строку: РЕКА и ВОДА являются возможными для определенных ключей. Это общее правило криптоанализа : без дополнительной информации невозможно расшифровать данное сообщение.
Конечно, даже в этом случае только определенное количество пятибуквенных клавиш даст английские слова. Перепробовав все возможные ключи, мы получим не только RIVER и WATER, но также SXOOS и KHDOP. Число «рабочих» ключей, вероятно, будет намного меньше, чем набор всех возможных ключей. Проблема в том, какой из этих «рабочих» ключей правильный; остальные ложные.
В общем, учитывая конкретные предположения о размере ключа и количестве возможных сообщений, существует средняя длина зашифрованного текста, при которой существует только один ключ (в среднем), который будет генерировать читаемое сообщение. В приведенном выше примере мы видим только английские символы в верхнем регистре , поэтому, если предположить, что открытый текст имеет такую форму, то для каждой позиции в строке будет 26 возможных букв. Аналогично, если мы предположим, что ключи состоят из пяти символов в верхнем регистре, существует K = 26 5 возможных ключей, большинство из которых не «работают».
Огромное количество возможных сообщений N может быть сгенерировано даже с использованием этого ограниченного набора символов: N = 26 L , где L — длина сообщения. Однако из-за правил языка только меньший набор из них является читаемым открытым текстом , возможно, из них M, где M, вероятно, будет намного меньше, чем N. Более того, M имеет однозначное отношение с числом из ключей, которые работают, поэтому, учитывая K возможных ключей, только K × (M/N) из них будут «работать». Один из них правильный, остальные поддельные.
Поскольку M/N становится сколь угодно малым по мере увеличения длины L сообщения, в конечном итоге существует некоторое L, достаточно большое, чтобы количество поддельных ключей стало равным нулю. Грубо говоря, это L, которая делает KM/N=1. Это L — расстояние единства.
Расстояние уникальности эквивалентно можно определить как минимальный объем зашифрованного текста, необходимый для того, чтобы позволить злоумышленнику с неограниченными вычислительными возможностями восстановить уникальный ключ шифрования. [1]
Тогда можно показать, что ожидаемое расстояние единственности будет: [1]
где U — расстояние единственности, H ( k ) — энтропия пространства ключей (например, 128 для 2128 равновероятных ключей, а точнее меньше, если ключ представляет собой заученную фразу-пароль). D определяется как избыточность открытого текста в битах на символ.
Теперь алфавит из 32 символов может нести 5 бит информации на символ (так как 32 = 2 5 ). Обычно количество бит информации на символ равно log 2 (N) , где N — количество символов в алфавите, а log 2 — двоичный логарифм . Таким образом, в английском языке каждый символ может передать log 2 (26) = 4,7 бит информации.
Однако среднее количество фактической информации, передаваемой на символ значимого английского текста, составляет всего около 1,5 бита на символ. Таким образом, избыточность простого текста равна D = 4,7 − 1,5 = 3,2. [1]
По сути, чем больше расстояние единства, тем лучше. Для одноразового блокнота неограниченного размера, учитывая неограниченную энтропию пространства ключей, мы имеем , что согласуется с невозможностью взлома одноразового блокнота .
Для простого шифра замены количество возможных ключей равно 26! = 4,0329 × 10 26 = 2 88,4 — количество способов перестановки алфавита. Предполагая, что все ключи одинаково вероятны, H ( k ) = log 2 (26!) = 88,4 бита. Для английского текста D = 3,2 , таким образом, U = 88,4/3,2 = 28 .
Таким образом, учитывая 28 символов зашифрованного текста, теоретически возможно определить открытый текст на английском языке и, следовательно, ключ.
Расстояние уникальности — полезная теоретическая мера, но она мало что говорит о безопасности блочного шифра при атаке злоумышленника с реальными (ограниченными) ресурсами. Рассмотрим блочный шифр с расстоянием единственности в три блока зашифрованного текста. Хотя очевидно, что информации достаточно, чтобы противник, не обладающий вычислительными возможностями, мог найти правильный ключ (простой исчерпывающий поиск), на практике это может быть вычислительно неосуществимо.
Расстояние уникальности можно увеличить за счет уменьшения избыточности открытого текста. Один из способов сделать это — использовать методы сжатия данных перед шифрованием, например, удаляя лишние гласные, сохраняя при этом читабельность. В любом случае это хорошая идея, поскольку она уменьшает объем шифруемых данных.
Можно предположить, что зашифрованные тексты, превышающие расстояние уникальности, имеют только одно значимое дешифрование. Зашифрованные тексты короче расстояния единственности могут иметь несколько правдоподобных расшифровок. Расстояние уникальности не является мерой того, сколько зашифрованного текста требуется для криптоанализа. [ Почему? ] , но какой объем зашифрованного текста требуется, чтобы существовало только одно разумное решение для криптоанализа.
