Совершенные шифры

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

Зная шифр и априорные вероятности открытых текстов и ключей, обладая перехватом шифртекста уÎУ противник может вычислить условные вероятности р(х/у) при всех хÎХ. Если при этом окажется, что один из элементов х(0) их Х имеет значительную вероятность р(х(0)/у)=1-e, а все остальные элементы их Х, вместе взятые, имеют вероятность e, то это означает, что с надежностью 1-e найдено истинное открытое сообщение. В этом смысле говорят, что дешифрование сводится к вычислению апостериорных вероятностей р(х/у) при всех хÎХ. Напротив, если окажется, что при любом хÎХ выполняется равенство р(х/у)=р(х), то перехваченная криптограмма у не несет никакой информации об открытом сообщении. Если это равенство выполняется дополнительно и при любом уÎУ, то это свидетельствует о высокой способности шифра противостоять попыткам дешифрования, то есть о высокой криптостойкости шифра. Последние шифры К. Шеннон назвал «совершенными» шифрами.

ОПРЕДЕЛЕНИЕ. Шифр (Х,К,У,f) с вероятностными распределениямиР(Х)=(р(х), хÎХ), Р(К)=(р(c), cÎК) называется совершенным (при нападении на хÎХ по перехвату уÎУ), если при любых хÎХ и уÎУ

р(х/у)=р(х).

Используя формулу условных вероятностей

р(х,у)=р(у/х)р(х)=р(х/у)р(у),

легко показывается, что совершенство шифра равносильно условию

р(у/х)=р(у)

при любых хÎХ, уÎУ.

Несложно доказывается, что свойство совершенности шифра (Х,К,У,f), у которого |Х|=|К|=|У|, равносильно двум условиям:

1) р(c)= , cÎК;

2) уравнение f(х,c)=у однозначно разрешимо относительно cÎК при любых хÎХ и уÎУ.

Одним из примеров совершенных шифров является шифр гаммирования Х=У=К=I^L с равновероятным выбором ключа – гаммы. В качестве совершенных шифров выступают следующие шифры простой замены с множеством ключей К=S(I) (S(I) – симметрическая группа подстановок на I) с равновероятным выбором ключа: 1) Х=I – алфавит текста; 2) X – множество всех слов алфавита I длины L не содержащих одинаковых букв.