Мера стойкости шифра

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

· шифруемое сообщение содержит большую избыточность;

· процесс шифрования хорошо «перемешивает» структурные единицы сообщения (биты, символы и т. д.).

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

Каким же условиям должен удовлетворять шифр? Ну прежде всего, процедура расшифрования должна всегда восстанавливать открытое сообщение в его исходном виде. Иными словами, для каждого допустимого сообщения T преобразования за- и расшифрования должны удовлетворять следующему свойству:

T = D(E(T)).

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

Для этого сначала вспомним некоторые определения из теории вероятностей. Предположим имеется два события A и B. Тогда величина информации

.

Если A = B, тогда P(A|A) = 1 и I(A) = – log P(A). Пусть производится эксперимент G, который имеет n исходов E₁, E₂, ..., E_n. Построим случайную величину, где i – номер эксперимента.

,

H(G) – энтропия эксперимента G. Энтропия это мера неопределенности эксперимента. Свойства энтропии:

1. 0 £ H(G) £ log n.

2. H(G) = 0 тогда и только тогда, когда существует p_j = 1 для некоторого j.

3. H(G) = log n тогда и только тогда, когда для всех i, 1 £ i £ n. Другими словами, энтропия равновероятного эксперимента всегда больше или равна любого другого эксперимента.

Энтропия случайной величины X может быть также истолкована как среднее количество битов, необходимых для кодирования значений X.

Теперь вернемся к вопросу о мере стойкости шифра. Отправленное сообщение до поступления к получателю является для него и, естественно, для злоумышленника неопределенным – если это было бы не так, тогда не было бы вообще никакого смысла его посылать. Пусть возможна отправка сообщений T₁, T₂, ...,T_nс вероятностью p₁, p₂, ..., p_nсоответственно. Тогда мерой неопределенности сообщения для всех, кто обладает этой априорной информацией, может служить величина математического ожидания логарифма вероятности одного сообщения, взятая со знаком «минус»; по некоторым соображениям в качестве основания логарифма удобно выбрать 2:

.

Эта величина имеет вполне понятный физический смысл: количество битов информации, которое необходимо в среднем передать, чтобы полностью устранить неопределенность. Если никакой априорной информации о сообщении нет кроме его размера в N бит, то все возможные из 2^Nвариантов считаются равновероятными и тогда неопределенность сообщения равна его размеру: H(T) = N = ïTï, где через ïTï обозначен размер блока данных T в битах. А если об исходном тексте неизвестно вообще ничего, даже его размер? В этом случае все равно необходимо принять за основу какую-либо модель распределения. Как правило, в реальности подобных трудностей не возникает, поскольку многие весьма стойкие шифры «не считают нужным» скрывать размер шифруемого сообщения, – в этом действительно почти никогда нет особой необходимости, – и эта характеристика априорно считается известной злоумышленнику. Там же, где этот размер все же реально необходимо скрыть, все сообщения перед зашифрованием преобразуются в массивы данных одной и той же длины, и опять получается рассмотренная выше ситуация.

После перехвата шифротекста характеристика неопределенности открытого текста изменится – она станет апостериорной («после-опытной») условной неопределенностью – условием здесь является перехваченное шифрованное сообщение C. Теперь она определеяется следующей формулой:

,

где через p(T_i|C) обозначена вероятность того, что исходное сообщение есть T_iпри условии, что результат его зашифрования есть C.

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

I = H(T) – H(T|C).

Эта величина всегда неотрицательна. Показателем здесь является, насколько уменьшится – понятно, что увеличиться она не может – неопределенность исходного текста при получении соответствующего шифротекста по сравнению с априорной неопределенностью, и не станет ли она меньше допустимой величины. В наилучшем для разработчиков шифра случае обе эти неопределенности равны H(T) = H(T|C), то есть злоумышленник не может извлечь никакой полезной для себя информации об открытом тексте из перехваченного шифротекста: I = 0. Иными словами, знание шифротекста не позволяет уменьшить неопределенность соответствующего открытого текста, улучшить его оценку и увеличить вероятность его правильного определения. Шифры, удовлетворяющие данному условию, называются абсолютно стойкими или совершенными шифрами, так как зашифрованные с их применением сообщения не только не могут быть дешифрованы в принципе, но злоумышленник даже не сможет приблизиться к успешному определению исходного текста, то есть увеличить вероятность его правильного дешифрования.