Теоретическая стойкость шифров: совершенные шифры.

При рассмотрении вопроса о теоретической стойкости шифров отвлекаются от реальных временных и сложностных затрат по вскрытию шифра (что определяет подход к практи­ческой стойкости). Во главу угла ставится принципиальная возможность получения некоторой информации об открытом тексте или использованном ключе. Впервые такой подход ис­следовал К. Шеннон ([Шен63]). Он рассматривал уже знако­мую нам модель шифра и единственную криптоатаку на осно­ве шифртекста. Проследим за его рассуждениями.

Как мы указывали, конечной целью работы криптоаналитика является текст сообщения или ключ шифрования. Одна­ко весьма полезной может быть даже некоторая вероятност­ная информация об открытом тексте. Например, уже предпо­ложение о том, что открытый текст написан по-английски, предоставляет криптоаналитику определенную априорную информацию об этом сообщении даже до того, как он увидит шифртекст. Так, например, он заранее знает, что слово «hello» является более вероятным началом сообщения, чем, скажем, набор букв «abode». Поэтому первая цель криптоанализа со­стоит в том, чтобы увеличить количество этой априорной ин­формации, относящейся к каждому возможному открытому тексту таким образом, чтобы истинный открытый текст сде­лать более вероятным после получения шифртекста, хотя, ко­нечно, и не обязательно точным.

Пусть, например, криптоаналитик перехватил текст «abccd» и знает (или предполагает), что он был зашифрован при помощи шифра простой замены. Этот шифртекст говорит ему о том, что открытый текст состоит из пяти букв, третья и четвертая из которых являются одинаковыми, а остальные отличными от этой буквы и разными. Хотя он не может быть уверенным, что этим словом является «hello» (это может быть еще «lessy» или что-то подобное), тем не менее апостериор­ные вероятности таких открытых текстов возрастают относительно их априорных вероятностей. Криптоаналитик, кроме того, полностью уверен (в предположении, что использова­лась именно простая замена) в том, что этот открытый текст не может быть ни словом «after», ни словом «catch», и, таким образом, апостериорная вероятность обоих этих открытых текстов сокращается до нуля, даже вне зависимости от их ап­риорных вероятностей.

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

Вспомним о введенной нами модели шифра , в кото­рой фигурировали распределения вероятностей Р(Х), Р(К). Они как раз и являются наборами априорных вероятностей и . Будем предполагать, что р_X (х) > 0, р_K (k) > 0 для любых х X, k К.

Далее мы будем рассматривать лишь такие шифры, для которых выбор ключа и выбор открытого текста являются независимыми событиями. Это равносильно тому, что распре­деления Р(Х), Р(К) являются независимыми. Эти распределения естественным образом индуцируют распределение вероятностей P(Y) = на множестве возможных шифртекстов по формуле

(14)

Поясним корректность такого определения. Нужно проверить, что

Р ассмотрим отображение f:X*K Y, определенное условием для любого k К . Тогда, поскольку f ^-1(Y)=X*K , получаем: Естественным образом вводятся и условные вероятности Р_y/x (y/x), Р_y/k (у/k), определяемые формулами
Р_y/x (y/x)= (15)

Р_Y/K (y/k)= (16)
Несложно проверить, что формулы (15) и (16) задают ве­роятностные распределения, то есть что при любом х Х

и при любом k К

С целью упрощения записи нижние индексы в обозначе­ниях будем опускать, и записывать их в виде р(у/х), p(y/k) соответственно.

Отметим, что с помощью формулы для условной вероят­ности

(17)

мы можем вычислить и условные вероятности p(x/y),p(k/y):

(18)

Следующее определение лишь формализует предложен­ный выше подход к теоретической стойкости шифра (только по отношению к атаке на основе единственного шифртекста).

Определение. Назовем шифр , совершенным, если для любых x X,y Y выполняется равенство

Р(х/y)=Р_X(х). (19)

Отметим одно очевидное свойство совершенного шифра.

Утверждение 1. Если шифр , — совершенный, то |X|<|Y|<|K|.

Доказательство. Первое неравенство, очевидно, имеет место для любого шифра. Если шифр — совершенный, то для любых x X, у Y найдется ключ k К, такой, что E_k(x)=у . В самом деле, в противном случае, согласно (15), мы бы имели р(у/х)=0, а тогда и (согласно (18)) р(х/у)=0. Согласно (19), вероятность р_X(х) также оказы­вается равной нулю, вопреки нашей договоренности о том, что р_X(х) > 0 для любого х Х .

Отсюда следует также, что для любого х Х выполня­ется равенство {E_k(x),k K}=Y и, следовательно, |Y| <|К|. Утверждение доказано.

В большинстве случаев применяемые на практике шифры обладают свойством Х = Y. Следуя К. Шеннону, назовем такие шифры эндоморфными. К. Шеннону удалось полностью описать эндоморфные совершенные шифры с минимально возможным числом ключей. Согласно (20), это минимально возможное число ключей |К| равно |Y|. В несколько более общей форме теорема формулируется следующим образом.

Теорема (К. Шеннон). Пусть — шифр, для которого |X|=|Y|=|K|. Тогда шифр , — совершенный тогда и только тогда, когда выполняются два условия:

1) для любых х X, у Y существует единственный

ключ k К, для которого Е_k (х) = у ;

2) распределение вероятностей Р(К) — равномерное, то есть для любого ключа

Доказательство. Пусть шифр — совершенный. Согласно доказательству утверждения 1,

Поэтому из неравенства следует неравенств для любого х Х . Это доказывает необходимость условия 1).

Пусть Х = {х₁,...,х_N}. Зафиксируем произвольный элемент y Y и занумеруем ключи так, чтобы . Тогда

(21)

Так как — совершенный шифр, то р(х_i/у) = р_X (х_i). Отсюда и из (21) получаем равенство р_K (k_i) = р_Y (у) дл любого i =1,..,N , которое доказывает необходимость условия 2).

Пусть условия 1) и 2) выполнены. Тогда, пользуясь для фиксированного элемента у Y введенной выше нумерацией ключей, имеем цепочку равенств:

из которой

Достаточность условий теоремы также доказана.

Обратим внимание на то, что таблица зашифрования шифра, удовлетворяющего условиям теоремы Шеннона, со­гласно условию 1) этой теоремы, является латинским квад­ратом. Поэтому в случае, когда X=Y=K=Z_n сути де­ла, шифры табличного гаммирования со случайными равновероятными ключами, и только они, являются единственными совершенными шифрами.

X/K	x1	…	x1
k1		…
…	…	…	…
kN		…

Легко проверить, что также совершенным будет поточ­ный шифр с основными множествами Х = Y = К = правилом зашифрования, которое определяется покоорди­натно как правило зашифрования шифра табличного гамми­рования, и равномерным распределением Р(К).

Подчеркнем также, что не только указанные шифры являются совершенными. В качестве примера можно указать следующий не эндоморфный совершенный шифр.

Пример

Теорема Шеннона может быть обобщена и для некоторых других криптоатак. Например, в статье [God90] такое обобщение проводится для криптоатак на основе нескольких шифртекстов, полученных на одном ключе, а также для криптоатак на основе ряда открытых и соответствующих им шифрованных текстов, образованных с помощью одного ключа.