Основы теории К. Шеннона

Тема: Теоретическая секретность

Лабораторная работа №5

Шеннон рассмотрел модель, в которой источник сообщений порождает открытый текст X. Источник ключей генерирует ключ Z. Шифратор преобразовывает открытый текст X с помощью ключа Я в шифртекст Y: Y=Tz(X)

Дешифратор, получив зашифрованное сообщение Y, выполняет обратную операцию:
X=Tz(-1)(Y)

Модель секретной системы К. Шеннона приведена на рис.1.

pис.1. Модель К.Шеннона.

Задачей криптоаналитика противника является получение открытого текста и ключа на основе анализа шифртекста. Шеннон рассмотрел вопросы теоретической и практической секретности.

Для определения теоретической секретности Шеннон сформулировал следующие вопросы.

1. Насколько устойчива система, если криптоаналитик противника не ограничен временем и обладает всеми необходимыми средствами для анализа криптограмм?

2. Имеет ли криптограмма единственное решение?

3. Какой объем шифртекста необходимо перехватить криптоаналитику, чтобы решение стало единственным?

Для ответа на эти вопросы Шеннон ввел понятие совершенной секретности с помощью следующего условия: для всех Y апостериорные вероятности равны априорным вероятностям, то есть перехват зашифрованного сообщения не дает криптоаналитику противника никакой информации. По теореме Бейеса

Py(X)=P(X)Px(Y)/P(Y)

где P(X) - априорная вероятность сообщения Х;

Рx(Y)- условная вероятность криптограммы Y при условии, что выбрано сообщение X, то есть сумма вероятностей всех тех ключей, которые переводят сообщение X в криптограмму Y;

P(Y) - вероятность получения криптограммы Y;

Рy(Х)- апостериорная вероятность сообщения X при условии, что перехвачена криптограмма Y.

Для совершенной секретности величины Рy(Х) и Р(Х) должны быть равны для любых X и Y.

Теорема 1. Необходимое и достаточное условие для совершенной секретности состоит в том, что Рy(X)=P(X) для всех X и Y, то есть Px(Y) не должно зависеть от X.

Секретная система включает в себя два статистических выбора: выбор сообщения и выбор ключа. Можно измерять количество информации, создаваемое при выборе сообщения X, через энтропию H(X):

Н(Х)= - сум. Р(Х)*logР(Х),

(x)

где суммирование осуществляется по всем возможным сообщениям.

Аналогично при выборе ключа:

Н(Z)= - сум. P(Z)*logP(Z).

(z)

Шеннон ввел в рассмотрение функции ненадежности ключа и сообщения (Ну(Z) и Ну(Х) соответственно):

Нy(Z)= -сум. P(Y,Z)*log Py(Z).

(Y,Z)

Нy(Х)= -сум. Р(Y,X)*log Py(Х),

(W,X)
где P(Y,Z) - вероятность ключа Z и криптограммы Y;

Ру(Z)- апостериорная вероятность ключа Z, если перехвачена криптограмма Y;

P(Y,X)- вероятность сообщения X и криптограммы Y;

Рy(X)- апостериорная вероятность сообщения X, если перехвачена криптограмма Y;

Суммирование для Ну(Z) проводится по всем возможным криптограммам определенной длины (например, длины N) и по всем возможным ключам. Тогда Ну(Z) и Hу(Х) являются функциями от N (количества перехваченных символов), что будет обозначаться Ну(Z,N) и Ну(Х,N) соответственно.

Теорема 2. Ненадежность ключа Hy(Z,N) - не возрастающая функция N.

Это означает, что при S>=N справедливы неравенства:

Hy(Z,S)<=Hy(Z,N);

Нy(Х,S)<=Нy(Х,N):

Hy(Х,N)<=Hy(Z,N).

Последнее неравенство следует из неравенства

Нy(Х)<=Hy(Х,Z)=Нy(Z)+Hy,z(Х)

и из условия Hy,z(X)=0, так как Z и Y полностью определяют X.

Так как сообщения и ключи выбираются независимо, можно записать:

Н(Х,Z)=Н(Х)+Н(Z).

свойства функции ненадежности раскрываются следующими теоремами.

Теорема 3. Ненадежность сообщений для произведения секретных систем не меньше, чем ненадежность для одной системы.

Для случая, когда системы S1,S2,.....Sn имеют функции ненадежности H1,...,Hm соответственно, и система Т определяется как T=p1S1+p2S2+...+pmSm=0, сум. pi=1 (i=1,M) следующая теорема.

Теорема 4. Ненадежность для взвешенной суммы систем ограничена неравенствами:

сум.(Pi*Hi) <= H <= сум.(Pi*Hi)-сум.(Pi*LogPi) (i=1,M)

Эти границы нельзя улучшить. В теореме 4 Hi может означать ненадежность ключа или ненадежность сообщения.

Шеннон определил идеальную систему как такую, в которой Hy(Z) и Hy(Х) не стремятся к нулю при стремлении N к бесконечности. Если в системе Hy(Z)=H(Z), то она называется строго идеальной системой.

Теорема 5. Необходимое и достаточное условие строгой идеальности системы Т заключается в том, что для любых двух ключей отображение Тi**(-1)*Тj должно являться сохраняющим меру отображения пространства сообщений в само себя.

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

Теорема 6. Если все символы алфавита исходных сообщений Равновероятны и выбираются независимо, то любая замкнутая система будет строго идеальной.

Шеннон ввел расстояние единственности - наименьшее N,такое, что Hy(Z) близка к нулю. Расстояние единственности приводит к получению единственного решения криптограммы. Для определения практической секретности Шеннон сфоpмулировал вопрос: надежна ли секретная система, если криптоаналитик противника располагает ограниченным временем и ограниченными возможностями для анализа шифртекста? Шеннон назвал рабочей характеpистикой системы средний объем работы W(N), необходимый для определения ключа, если криптограмма содержит N букв. Из этого определения следует, что для создания хорошего шифра необходимо максимизировать минимальный объем работы, который должен проделать криптоаналитик противника для нахождения решения.

Для противодействия методам статистического анализа криптограмм Шеннон предложил использовать два метода: рассеивание и перемешивание. В настоящее время известно большое число методов криптографического закрытия данных. Классификация основных из них приведена на рис.2.

Таблица 1. Классификация методов криптографического закрытия данных

Методы кpиптогpафического закpытия данных
Шифpование	Шифpование	Шифpование
замена (подстановка)	замена (подстановка)	замена (подстановка)
перестановка	перестановка	перестановка
аналитические преобразования	аналитические преобразования	аналитические преобразования
комбинированные методы	комбинированные методы	комбинированные методы

Дата добавления: 2015-05-10