Введение

Длина шифротекста, необходимая для однозначного взлома шифра

В криптографии, расстояние однозначности – это длина исходного шифротекста, необходимая для взлома шифра путем сокращения числа возможных ложных ключей до нуля при переборе. То есть, после проверки всех возможных ключей, должна остаться только одна расшифровка, имеющая смысл, то есть ожидаемый объем шифротекста, необходимый для полного определения ключа, при условии, что исходное сообщение обладает избыточностью. Клод Шеннон определил расстояние однозначности в своей статье 1949 года «Теория связи систем секретности». Рассмотрим атаку на шифротекстовую строку "WNAIW", зашифрованную шифром Виженера с использованием пятибуквенного ключа. Вполне возможно, что эта строка может быть расшифрована в любую другую строку – RIVER и WATER являются возможными вариантами для определенных ключей. Это общее правило криптоанализа: без дополнительной информации невозможно однозначно расшифровать это сообщение. Разумеется, даже в этом случае лишь определенное количество пятибуквенных ключей приведет к получению осмысленных слов на английском языке. Перебрав все возможные ключи, мы получим не только RIVER и WATER, но и SXOOS и KHDOP. Число «рабочих» ключей, вероятно, будет значительно меньше общего числа возможных ключей. Проблема заключается в том, чтобы определить, какой из этих «рабочих» ключей является верным, а остальные – ложными.

Отношение к размеру ключа и возможным простым текстам

В целом, при определенных предположениях о размере ключа и количестве возможных сообщений, существует средняя длина шифротекста, для которой (в среднем) существует только один ключ, способный генерировать читаемое сообщение. В приведенном выше примере мы видим только заглавные английские буквы, поэтому, если предположить, что открытый текст имеет такую форму, то для каждой позиции в строке существует 26 возможных букв. Аналогично, если предположить, что ключи состоят из пяти заглавных букв, то существует K = 26⁵ возможных ключей, большинство из которых не будут "работать". Даже с использованием этого ограниченного набора символов можно сгенерировать огромное количество возможных сообщений, N = 26ᴸ, где L – длина сообщения. Однако, лишь меньшая часть из них будет являться читаемым открытым текстом из-за правил языка, возможно, M из них, где M, вероятно, значительно меньше N. Более того, M находится в отношении один к одному с количеством рабочих ключей, поэтому, при K возможных ключах, только K × (M/N) из них будут "работать". Один из них – верный ключ, остальные – ложные. Поскольку M/N становится сколь угодно малым с увеличением длины L сообщения, в конечном итоге найдется такое L, которое будет достаточно большим, чтобы количество ложных ключей стало равным нулю. Приблизительно, это то L, при котором KM/N = 1. Это L и есть расстояние однозначности.

Единообразное расстояние замены шифра

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

Практическое применение

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