Теоретическая стойкость шифров по Шеннону

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

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

Теорема. Шифр А=(М,К,С,Е), где С=E(M х K) является совершенным тогда и только тогда, когда H(M/C)=H(M).

Доказательство теоремы следует из определения совершенных шифров, у которых p(m/c)=p(m) "(m,c) и по свойствам энтропии.

Такие шифры относятся к так называемому классу теоретически стой­ких шифров. Ряд шифров, в том числе и многие практически испо­льзуемые шифры таковы, что эта неопределенность при перехваченной криптограм­ме полностью исчезает, то есть становится известным, что данная крипто­грамма может быть получена шифрованием только един­ственного текста, неизвестно только какого. Уровень стойкости таких систем оценивается по затратам времени и сил, необходимых для получения этого единственного открытого текста. При больших затратах или малой вероятности успеха в дешифровании говорят о практической стойкости шифра.

Понятия ненадежности открытого текста и ключа введены Шенноном в качестве теоретической меры секретности. Алгебраическая модель шифра А включает в себя два вероятностных выбора: выбор открытого сообщения m ÎM и выбор ключа k Î K. Количество информации в сообщении m определяется ее энтропией:

,

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

.

Неопределенности сообщения и ключа в случае известной криптограммы:

 и

.

Эти условные энтропии Шеннон и назвал ненадежностью открытого текста и ключа. Если ненадежность сообщения (ключа) равна нулю, то по свойствам энтропии лишь одно сообщение (ключ) имеет вероятность =1, остальные =0. Этот случай соответствует полной осведомленности дешифровальщика о сообщении (ключе). То есть открытый текст однозначно восстанавливается по шифртексту.

Рассмотрим энтропию модели шифра H (M,K,C). По правилам сложения энтропий:

H (M,K,C) = H (M,K) + H (C/M,K) = H (C,K) + H (M/C,K).

Но по условию однозначности шифрования/дешифрования:

 H (C/M,K) =0 и H (M/C,K) =0 Þ H (M,K,C) = H (M,K) = H (C,K).

Так как ключ и сообщение в вероятностной модели шифра независимы, то

H (M,K) = H (M) + H (K).

Кроме того,

H (C,K) = H (C) + H (К/C).

Отсюда получаем формулу для ненадежности ключа:

H (К/C) =H (M) +H (K) -H (C).

Из этой формулы следует:

H (M) =H (C), Û H (K/C) =H (K).

Аналогично получается формула для ненадежности сообщения:

H (M/C) =H (M) +H (C/M) -H (C).

Используя свойство энтропии, состоящее в том, что уменьшение объема известных сведений может лишь увеличить неопределенность, получим соотношения:

H (M/C)≤ H (M,K/C) =H (K/C) +H (M/C,K) =H (K/C)≤ H (K). (H (M/C,K) =0)

Для совершенных шифров по данной выше теореме выполняется H (M/C) =H (M), и полученное выше неравенство говорит о том, что неопределенность секретного ключа всегда не меньше неопределенности шифруемого текста.

Учитывая связь Н (К) с возможностью кодировки множества ключей, заключаем, что для совершенных шифров средний «размер» секретного ключа не может быть меньше «размера» открытого текста. Следовательно для таких шифров число ключей растет вместе с ростом длины передаваемых сообщений.