Расстояние уникальности

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

Клод Шеннон определил расстояние единственности в своей статье 1949 года « Теория связи секретных систем ». ^[2]

Рассмотрим атаку на строку зашифрованного текста «WNAIW», зашифрованную с использованием шифра Виженера с пятибуквенным ключом. Возможно, эту строку можно расшифровать в любую другую строку: РЕКА и ВОДА являются возможными для определенных ключей. Это общее правило криптоанализа : без дополнительной информации невозможно расшифровать данное сообщение.

Конечно, даже в этом случае только определенное количество пятибуквенных клавиш даст английские слова. Перепробовав все возможные ключи, мы получим не только RIVER и WATER, но также SXOOS и KHDOP. Число «рабочих» ключей, вероятно, будет намного меньше, чем набор всех возможных ключей. Проблема в том, какой из этих «рабочих» ключей правильный; остальные ложные.

Связь с размером ключа и возможными открытыми текстами [ править ]

В общем, учитывая конкретные предположения о размере ключа и количестве возможных сообщений, существует средняя длина зашифрованного текста, при которой существует только один ключ (в среднем), который будет генерировать читаемое сообщение. В приведенном выше примере мы видим только английские символы в верхнем регистре , поэтому, если предположить, что открытый текст имеет такую форму, то для каждой позиции в строке будет 26 возможных букв. Аналогично, если мы предположим, что ключи состоят из пяти символов в верхнем регистре, существует K = 26. ⁵ возможные ключи, большинство из которых не «работают».

Даже с использованием этого ограниченного набора символов можно сгенерировать огромное количество возможных сообщений N: N = 26. ^л, где L — длина сообщения. Однако из-за правил языка только меньший набор из них является читаемым открытым текстом , возможно, из них M, где M, вероятно, будет намного меньше, чем N. Более того, M имеет однозначное отношение к числу из ключей, которые работают, поэтому, учитывая K возможных ключей, только K × (M/N) из них будут «работать». Один из них правильный, остальные поддельные.

Поскольку M/N становится сколь угодно малым по мере увеличения длины L сообщения, в конечном итоге существует некоторое L, достаточно большое, чтобы количество поддельных ключей стало равным нулю. Грубо говоря, это L, которая делает KM/N=1. Это L — расстояние единства.

с энтропией ключей и избыточностью текста Связь открытого

Расстояние уникальности эквивалентно можно определить как минимальный объем зашифрованного текста, необходимый для того, чтобы позволить злоумышленнику с неограниченными вычислительными возможностями восстановить уникальный ключ шифрования. ^[1]

Тогда можно показать, что ожидаемое расстояние единственности будет: ^[1]

U=H(k)/D

где U — расстояние единства, H ( k ) — энтропия ключевого пространства (например, 128 для 2 ¹²⁸ равновероятные ключи, а точнее меньше, если ключ представляет собой заученную фразу-пароль). D определяется как избыточность открытого текста в битах на символ.

Теперь алфавит из 32 символов может нести 5 бит информации на каждый символ (так как 32 = 2 ⁵). Обычно количество бит информации на символ равно $log 2 (N)$ , где N — количество символов в алфавите, а $log 2$ — двоичный логарифм . Таким образом, в английском языке каждый символ может передать $log 2 (26) = 4,7$ бит информации.

Однако среднее количество фактической информации, передаваемой на символ значимого английского текста, составляет всего около 1,5 бита на символ. Таким образом, избыточность простого текста равна D = 4,7 − 1,5 = 3,2. ^[1]

По сути, чем больше расстояние единства, тем лучше. Для одноразового блокнота неограниченного размера, учитывая неограниченную энтропию пространства ключей, имеем $U=\infty$ , что соответствует тому, что одноразовый блокнот невозможно сломать.

Расстояние уникальности шифра замены [ править ]

Для простого шифра замены количество возможных ключей равно $26! = 4,0329 \times 10 26 = 2 88.4$ , количество способов перестановки алфавита. Предполагая, что все ключи одинаково вероятны, $H (k) = log 2 (26!) = 88,4$ бита. Для английского текста $D = 3,2$ , таким образом, $U = 88,4/3,2 = 28$ .

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

Практическое применение [ править ]

Расстояние уникальности — полезная теоретическая мера, но она мало что говорит о безопасности блочного шифра при атаке злоумышленника с реальными (ограниченными) ресурсами. Рассмотрим блочный шифр с расстоянием единственности в три блока зашифрованного текста. Хотя очевидно, что информации достаточно, чтобы противник, не обладающий вычислительными возможностями, мог найти правильный ключ (простой исчерпывающий поиск), на практике это может быть вычислительно неосуществимо.

Расстояние уникальности можно увеличить за счет уменьшения избыточности открытого текста. Один из способов сделать это — использовать методы сжатия данных перед шифрованием, например, удаляя лишние гласные, сохраняя при этом читабельность. В любом случае это хорошая идея, поскольку она уменьшает объем шифруемых данных.

Можно предположить, что зашифрованные тексты, превышающие расстояние уникальности, имеют только одно значимое дешифрование. Зашифрованные тексты короче расстояния единственности могут иметь несколько правдоподобных расшифровок. Расстояние уникальности не является мерой того, сколько зашифрованного текста требуется для криптоанализа. ^{[ почему? ]} но сколько зашифрованного текста требуется, чтобы существовало только одно разумное решение для криптоанализа.

Ссылки [ править ]

^ Jump up to: Перейти обратно: ^а ^б ^с ^д Альфред Дж. Менезес ; Пол К. ван Оршот ; Скотт А. Ванстон . «Глава 7. Блочные шифры» (PDF) . Справочник по прикладной криптографии . п. 246.
^ Диворс, Калифорния (1977). «Точки уникальности в криптоанализе» . Криптология . 1 (1): 46–68. дои : 10.1080/0161-117791832797 . ISSN 0161-1194 .

Внешние ссылки [ править ]

Брюс Шнайер : Как распознать открытый текст (информационный бюллетень Crypto-Gram, 15 декабря 1998 г.)
Расстояние уникальности, рассчитанное для распространенных шифров.

[hac-1] Jump up to: Перейти обратно: ^а ^б ^с ^д Альфред Дж. Менезес ; Пол К. ван Оршот ; Скотт А. Ванстон . «Глава 7. Блочные шифры» (PDF) . Справочник по прикладной криптографии . п. 246.

[2] Диворс, Калифорния (1977). «Точки уникальности в криптоанализе» . Криптология . 1 (1): 46–68. дои : 10.1080/0161-117791832797 . ISSN 0161-1194 .

[1]

[2]