Клод Шеннон. Теория связи в секретных системах. Характеристика ненадежности для "случайного" шифра.

14. Характеристика ненадежности для "случайного" шифра.

В предыдущем разделе была вычислена характеристика ненадежности для простой подстановки, примененной к языку с двухбуквенным алфавитом. Но даже для этого почти самого простого шифра и языка полученные формулы уже настолько сложны, что почти бесполезны. Что же делать в практически интересных случаях, скажем в тех случаях, когда дробная транспозиция применена к английскому тексту с его крайне сложной статистической структурой. Эта сложность сама выдвигает метод подхода. Достаточно сложные проблемы часто могут быть разрешены статистически. Чтобы облегчить дело, введем понятие "случайного" шифра.

Сделаем следующие допущения.

1. Число возможных сообщений длины N равно таким образом R₀ = log₂G, где G – число букв алфавита. Предполагается, что число возможных криптограмм длины N также равно T.
2. Все возможные сообщения длины N можно разделить на две группы: группу с высокими и достаточно равномерными априорными вероятностями и группу с пренебрежимо малой полной вероятностью. Высоко вероятная группа будет содержать S = 2^RN сообщений, где R = H(M)/N, т.е. R – энтропия источника сообщений на одну букву.
3. Операцию расшифрования можно представлять графически в виде ряда линий (как на рис. 2 и рис. 4), идущих от каждого Е к различным M. Предположим, что имеется k равновероятных ключей, и что от каждого E будет отходить k линий. Предположим, что для случайного шифра линии от каждого E отходят к случайному набору возможных сообщений. Тогда случайный шифр будет представлять собой фактически целый ансамбль шифров и его ненадежность будет равна средней ненадежности этого ансамбля.

Ненадежность ключа определяется с помощью равенства

.

Вероятность того, что от частного E к высоковероятной группе сообщений отходит ровно m линий, равна

.

Если перехвачена криптограмма, которой соответствует m таких линий, то ненадежность равна log m. Вероятность такой криптограммы равна mT/Sk, так как она может быть создана из высоковероятных сообщений, каждое из которых имеет вероятность T/S с помощью одного из m ключей. Отсюда ненадежность равна

.

Требуется найти простое приближенное выражение для H_E(K), когда k велико. Если для величины m ее среднее значение  = SK/T много больше 1, то изменение log m в области тех m, для которых биномиальные слагаемые велики, будет малым и мы можем заменить log m на log. Этот множитель можно вынести за знак суммы, которая даст значение . Таким образом, при этом условии

,

H_E(K)H(K) – DN,

где D – избыточность на букву первоначального языка (D = D_N/N).

Если мало по сравнению с k, то биномиальное распределение может быть приближенно пуассоновским:

,

где = Sk/T. Отсюда

.

Заменив m на m+1, получим

.

Это выражение можно использовать, когда близко к 1. Если же 1, то существенным является лишь первый член ряда. Отбрасывая другие, получим

.

Итак, подводя итог вышесказанному, получаем, что H_E(K), рассматриваемая как функция от N – числа перехваченных букв – при N = 0 равна H(K). Далее она убывает линейно с наклоном –D до окрестности точки N = H(K)/D. После небольшой переходной области H_E(K) начинает убывать экспоненциально со временем "полураспада" 1/D, если D измеряется в битах на букву. Поведение H_E(K) показано на рис. 7 вместе с аппроксимирующими кривыми.

С помощью аналогичных рассуждений можно подсчитать ненадежность сообщения. Она равна

HE(M) = R0N	для	R0NHE(K),
HE(M) = HE(K)	для	R0NHE(K),
HE(M) =  HE(K) - (N)	для	R0N ~ HE(K).

где (N) – функция, показанная на рис. 7, причем шкала N сжата в D/R₀ раз. Таким образом, H_E(M) возрастает линейно с наклоном R₀ до тех пор, пока она не пересечет линию H_E(K). После закругленного перехода она идет ниже кривой H_E(K).

Рис. 7. Ненадежность для случайного шифра.

На рис. 7 видно, что кривые ненадежности стремятся к нулю довольно резко. Поэтому можно с достаточной определенностью говорить о точке, в которой решение становится единственным. Найденное при этом число букв мы будем называть расстоянием единственности. Для случайного шифра оно приблизительно равно H(K)/D.

[Титульный лист] [Предыдущий раздел] [Следующий раздел]
[Начало осмотра] [Что нового] [Статьи] [Выпуски в "Байтах"] [Что скачать] [Криптоалгоритмы] [Глоссарий] [Ссылки] [Гостевая книга] [Форум] [Напиши мне]

Версия от 01.01.02. (c) 2002 Андрей Винокуров.